Теоретичні відомості
Задача про призначення являє собою окремий випадок транспортної задачі, зміст якої полягає в тому, що необхідно -розподілити серед m виконавців n завдань (робіт). Робота j (j=1,n), яку виконує i-й виконавць, вимагає витрат (оплати, часу) Cij. Розв’язування задачі зводиться до оптимального розподілу робіт серед виконавців, при якому сумарні витрати будуть мінімальні. Причому, кожному виконавцю доручається тільки одна робота.
Замість виконавців в задачах про призначення можуть використовуватися “пункти відправлення”, а замість видів робіт - “пункти призначення”. Пропозиція і попит у кожному пункті відправлення і пункті призначення дорівнює одиниці. Якщо яку роботу не можна доручити якомусь виконавцю, то відповідна вартість Cij береться рівної дуже великому числу М.
Математична модель задачі про призначення.
Нехай
xij
– невідомі перемінні. Очевидно, що
=0 - якщо j-а робота не доручена і-му
виконавцю; або 1 - якщо j-я робота доручена
і-му виконавцю;
Тоді необхідно мінімізувати цільову функцію
,
при обмеженнях
,
j=1, n;
,
i=1, m;
xij=0 або 1.
Методичні рекомендації до виконання завдань:
Задача 1.
Питання для самоконтролю:
1. У чому полягає економічний зміст задачі про призначення?
2. Наведіть загальний вигляда математичної моделі задачі про призначення.
3. Які методи використовуються для розв’язування задачі про призначення?
Практичне заняття 13 Тема. Задачі цілочисельного програмування
Мета роботи: Набути навичок складання і розв’язку оптимізаційних задач про призначення.
Завдання:
Задача 1. Знайти цілочисельний розв’язок задачі, заданої системою обмежень-нерівностей:
та цільовою функцією
.
Задача 2. Меблеве підприємство випускає книжкові полиці, тумбу під телевізори і три види наборів меблів. Характеристики кожного виду продукції наведено в табл. 12.1. За умови отримання максимального прибутку обсяг товарної продукції повинен скласти не менше 459.31 тис. грн. Ситуація зі збутом продукції склалася наступна. Книжковими полицями ринок насичений, тому торгові організації зменшили обсяг договорів до 10 тис. шт. Тумби для телевізорів можуть бути реалізовані в обсягах від 4 до 7 тис. шт., Набори меблів 2 - від 7 до 10 тис. шт. Попит на набори меблів 1 і 3 необмежений, і потрібно не менше 10 тис. шт. Підприємство має технологічне обладнання, кількість якого і норми витрат часу на виготовлення одиниці продукції кожного виду наведені в табл. 12.2. Підприємство працює у дві зміни, ефективний час роботи кожної машини - 3945 годину (коефіцієнт змінності 1,9). Оптимізувати виробничу програму підприємства. (Потрібно знайти план випуску продукції, який максимізує прибуток підприємства).
Таблиця 12.1 – Характеристики видів продукції
|
Показники |
Види продукції | ||||
|
Набори меблів |
Книжкові полиці
|
Тумба під телевізор | |||
|
1 |
2 |
3 | |||
|
Оптова ціна одиниці виробу, тис. грн. |
7,2 |
14,3 |
32,5 |
0,182 |
1,5 |
|
Прибуток від реализації, тис. грн |
2,4 |
4,5 |
8,9 |
0,061 |
0,45 |
Таблиця 12.2 – Норми витрат часу на виготовлення одиниці продукції
|
Найменування обладнання |
Число, шт. |
Види продукції | ||||
|
Набори меблів |
Книжкові полиці |
Тумба під телевізор | ||||
|
1 |
2 |
3 | ||||
|
Лінія розкрою деревостружкових плит |
2 |
0,068 |
0,096 |
0,207 |
0,018 |
0,042 |
|
гільйотинні ножиці |
1 |
0,045 |
0,080 |
0,158 |
0,011 |
0,035 |
|
лінія облицювання |
2 |
0,132 |
0,184 |
0,428 |
0,020 |
0,060 |
|
Лінія обрізки кромки |
2 |
0,057 |
0,082 |
0,230 |
0,010 |
0,028 |
|
Полірувальні верстати |
2 |
0,063 |
0,090 |
0,217 |
0,010 |
0,032 |
|
Полірувальні верстати |
4 |
0,170 |
0,280 |
0,620 |
0,020 |
0,096 |
Завдання для самостійної роботи:
Задача 1.
|
1. |
|
2. |
|
|
3. |
|
4. |
|
|
5. |
|
6. |
|
|
7. |
|
8. |
|
|
9. |
|
10. |
|
Література: 2, 3, 6, 8, 9.