Задача про використання потужностей (задача про завантаження устаткування)

1. Підприємству заданий план виробництва продукції за часом і номенклатурою: потрібно за час T випустити n₁, n₂, …, n_k одиниць продукції P₁, P₂, …, P_k... Продукція виробляється на верстатах S₁, S₂, …, S_m... Для кожного верстата відома продуктивність a_ij (тобто число одиниць продукції P_j, яке можна зробити на верстаті S_i) і витрати b_ij на виготовлення продукції P_j на верстаті S_i за одиницю часу.

Необхідно скласти такий план роботи верстатів (тобто так розподілити випуск продукції між верстатами), щоб витрати на виробництво всієї продукції були мінімальними.

2. Є N видів робіт і стільки ж робітників (N = 4). Вартості c_ij виконання i-м робітником j-ої роботи наведені в таблиці. Скласти такий план виконання робіт, за якого всі роботи були б виконані, кожний робітник виконував тільки одну роботу, а сумарна вартість виконання всіх робіт була б мінімальною.

	Робота 1	Робота 2	Робота 3	Робота 4
Робітник 1	1	4	6	3
Робітник 2	9	10	7	9
Робітник 3	4	5	11	7
Робітник 4	8	7	8	5

3. Необхідно розподілити виконання 5 замовлень між 5 цехами. Час виконання кожного замовлення в різних цехах наведений в таблиці.

	Замов-лення 1	Замов-лення 2	Замов-лення 3	Замов-лення 4	Замов-лення 5
Цех 1	6	3	2	5	11
Цех 2	12	5	11	9	1
Цех 3	2	1	7	11	3
Цех 4	4	2	2	10	5
Цех 5	2	9	5	3	2

Скласти план виконання робіт, який би мінімізував сумарний час, витрачений на виконання всіх замовлень.

4. Потрібно розставити 4 робітників для виконання 4 операцій (робіт). Час t_ij виконання i-м робітником j-ої операції наведений в таблиці. Скласти такий план виконання робіт, за якого всі роботи були б виконані, кожний робітник був би зайнятий тільки на одній операції, а сумарний час виконання всіх робіт був би мінімальним.

	Операція 1	Операція 2	Операція 3	Операція 4
Робітник 1	3	8	2	5
Робітник 2	5	12	4	9
Робітник 3	6	5	10	7
Робітник 4	3	7	8	4

5. Потрібно розподілити 8 службовців для виконання 8 функціональних обов’язків. Час виконання кожної роботи різними службовцями подано в таблиці:

	Робота 1	Робота 2	Робота 3	Робота 4	Робота 5	Робота 6	Робота 7	Робота 8
Службовець 1	3	3	6	2	5	8	2	5
Службовець 2	5	1	2	7	11	12	4	9
Службовець 3	6	5	12	11	9	5	10	7
Службовець 4	3	2	4	2	10	7	8	4
Службовець 5	2	5	12	11	9	3	8	6
Службовець 6	4	9	4	2	10	5	12	6
Службовець 7	10	7	2	5	3	6	5	7
Службовець 8	8	4	5	3	7	5	9	4

Скласти такий план розподілу працівників, який би мінімізував сумарні часові витрати на виконання всіх робіт.

6. Є N видів робіт і стільки ж робітників (N = 5). Вартості c_ij виконання i-м робітником j-ої роботи наведені в таблиці. Скласти такий план виконання робіт, за якого всі роботи були б виконані, кожний робітник виконував тільки одну роботу, а сумарна вартість виконання всіх робіт була б мінімальною.

	Робота 1	Робота 2	Робота 3	Робота 4	Робота 5
Робітник 1	3	6	2	5	11
Робітник 2	1	2	7	11	3
Робітник 3	5	12	11	9	1
Робітник 4	2	4	2	10	5
Робітник 5	9	2	5	3	2

7. Необхідно доставити 7 однотипних замовлень клієнтам у 7 різних містах. Вартість доставки кожного замовлення в різні міста наведена в таблиці:

	Замов-лення 1	Замов-лення 2	Замов-лення 3	Замов-лення 4	Замов-лення 5	Замов-лення 6	Замов-лення 7
Місто 1	6	3	2	9	1	5	11
Місто 2	12	5	11	10	5	9	1
Місто 3	2	1	7	3	2	11	3
Місто 4	5	12	11	9	9	4	2
Місто 5	2	4	2	10	7	2	5
Місто 6	4	2	2	6	4	5	3
Місто 7	2	9	5	4		3	2

Розподілити замовлення по містах (по одному замовленню в одне місто) таким чином, щоб мінімізувати сумарну вартість доставки.

8. Є N видів робіт і стільки ж робітників (N = 4). Час t_ij виконання i-м робітником j-ої роботи наведений в таблиці. Скласти такий план виконання робіт, за якого всі роботи були б виконані, кожний робітник виконував тільки одну роботу, а сумарний час виконання всіх робіт був би мінімальним.

	Робота 1	Робота 2	Робота 3	Робота 4
Робітник 1	3	8	2	5
Робітник 2	5	12	4	9
Робітник 3	6	5	10	7
Робітник 4	3	7	8	4

9. Для підведення комунікацій із 5 джерел до 5 пунктів споживання визначена вартість робіт за кожним варіантом:

	Джерело 1	Джерело 2	Джерело 3	Джерело 4	Джерело 5
Пункт споживання 1	2	6	3	11	5
Пункт споживання 2	11	12	5	1	9
Пункт споживання 3	5	2	9	2	3
Пункт споживання 4	7	2	1	3	11
Пункт споживання 5	2	4	2	5	10

Визначити схему організації комунікацій (від одного джерела – тільки до одного пункту споживання) таким чином, щоб мінімізувати сумарні витрати.

10. Є N видів робіт і стільки ж робітників (N = 5). Вартості c_ij виконання i-м робітником j-ої роботи наведені в таблиці. Скласти такий план виконання робіт, за якого всі роботи були б виконані, кожний робітник виконував тільки одну роботу, а сумарна вартість виконання всіх робіт була б мінімальною.

	Робота 1	Робота 2	Робота 3	Робота 4	Робота 5
Робітник 1	5	6	4	7	10
Робітник 2	4	3	7	10	5
Робітник 3	5	10	10	9	4
Робітник 4	4	4	5	6	5
Робітник 5	8	3	7	3	6

11. На двох автоматичних лініях випускають апарати трьох типів. Інші умови задачі наведені в таблиці:

Тип апарата	Продуктивність роботи ліній, шт. за добу		Затрати на роботу ліній, грош. од. на добу		План, шт.
	1	2	1	2
А	4	3	400	300	50
В	6	5	100	200	40
С	8	2	300	400	50

Скласти такий план завантаження верстатів, щоб витрати були мінімальними, а завдання виконане не більше ніж за 10 діб.

12. Вироби чотирьох типів проходять послідовну обробку на двох верстатах. Час обробки одного виробу кожного типу на кожному з верстатів наведено в таблиці:

Верстат	Час обробки одного виробу, год
	Тип 1	Тип 2	Тип 3	Тип 4
1	2	3	4	2
2	5	2	1	2

Витрати на виробництво одного виробу кожного типу визначаються як величини, прямо пропорційні часу використання верстатів (у машино-годинах). Вартість машино-години складає 10 і 15 у. о. для верстатів 1 і 2 відповідно. Припустимий час використання верстатів для обробки виробів обмежено такими значеннями: 500 машино-годин для верстата 1 і 380 машино-годин для верстата 2. Ціни виробу типів 1, 2, 3 і 4 дорівнюють 65, 70, 55 та 45 у.о. відповідно. Скласти план виробництва, що максимізує чистий прибуток.

13. Процес виготовлення двох видів промислових виробів полягає в послідовній обробці кожного з них на трьох верстатах. Час використання цих верстатів для виробництва даних виробів обмежено 10-ма годинами на добу. Час обробки і прибуток від продажу одного виробу кожного виду наведені в таблиці:

Виріб	Час обробки одного виробу, хв				Питомий прибуток, у. о.
	Верстат 1		Верстат 2	Верстат 3
1	10	6		8	2
2	5	20		15	3

Знайти оптимальний обсяг виробництва виробів кожного виду.

14. Є N видів робіт і стільки ж робітників (N = 5). Вартості c_ij виконання i-м робітником j-ої роботи наведені в таблиці. Скласти такий план виконання робіт, за якого всі роботи були б виконані, кожний робітник виконував тільки одну роботу, а сумарна вартість виконання всіх робіт була б мінімальною.

	Робота 1	Робота 2	Робота 3	Робота 4	Робота 5
Робітник 1	2	3	6	11	5
Робітник 2	2	2	4	5	10
Робітник 3	7	1	2	3	11
Робітник 4	11	5	12	1	9
Робітник 5	5	9	2	2	3