Очікувана тривалість виконання замовлень на перевезення
різними виконавцями, годин
| Замовлення | Перевізник | |||
| П-1 | П-2 | П-3 | П-4 | |
| З-1 | ||||
| З-2 | ||||
| З-3 | ||||
| З-4 |
Необхідно знайти такий план розподілу замовлень між перевізниками, щоб тривалість часу до моменту закінчення усіх перевезень була б якнайменшою.
Розв’язування задачі на ПК. Для визначеності вважатимемо, що використовується економіко–математична модель задачі, записана у формі (4.9). Створимо файл “Prizn-2.xls” та працюватимемо на аркуші “Лист 1”.
1. У клітинки A1:E3, які об’єднаємо, внесемо назву задачі: “Оптимізація плану розподілу замовлень на перевезення за критерієм мінімізації часу виконання всіх робіт”.
2. Масив клітинок A5:E10 відведемо для інформаційного блоку про можливі тривалості виконання кожного з завдань кожним з перевізників – таблицю 4.2. У тому числі для числових значень відведемо клітинки B8:E11.
3. В клітинках A13: E13 побудуємо інформаційний блок про планову тривалість виконання перевезень згідно плану розподілу замовлень. Для цього об’єднаємо клітинки A13:D13 та впишемо слова: “Час закінчення усіх перевезень”, а клітинку E13 оберемо за цільову, в яку згодом ми введемо формулу для обчислення необхідних витрат часу.
4. Масив клітинок A15: E21 відведемо для блоку інформації про план розподілу замовлень; у тому числі для значень логічних змінних відведемо клітинки B18:E21.
5. У клітинки F18:F21 введемо формули для обчислення кількості перевізників, яким буде доручено виконання відповідного замовлення:
у клітинку F18: =СУММ(B18:E18)
у клітинку F19: =СУММ(B19:E19)
у клітинку F20: =СУММ(B20:E20)
у клітинку F21: =СУММ(B21:E21)
6. У клітинки B22:E22 введемо формули для обчислення кількості замовлень, які доручатимуться кожному перевізнику:
у клітинку B22: =СУММ(B18:B21)
у клітинку C22: =СУММ(C18:C21)
у клітинку D22: =СУММ(D18:D21)
у клітинку E22: =СУММ(E18:E21)
7. Показники, що обчислюватимуться в клітинках F18:E21 та B22:E22, є допоміжними; щоб позначити це, в клітинки F17 та A22 впишемо слово: ”Сума”.
8. У клітинках A24:E30 створимо допоміжний інформаційний блок для значень тривалостей окремих перевезень згідно плану розподілу завдань, у якому в клітинку B27 внесемо формулу: =C9*C19. “Протягнемо” потім цю формулу через клітинки B28:B30, далі – через клітинки C27:E30.
9. В цільову клітинку E13 занесемо формулу для обчислення часу закінчення усіх перевезень:
=МАКС(C27:F30)
Підготовку робочого аркушу закінчено.
10. Оберемо команду “Поиск решения” в меню “Сервис”.
11. В полі “Установить целевую ячейку” діалогового вікна “Поиск решения” вкажемо на адресу E13.
12. Перемикач вибору оптимізаційного спрямування цільової функції увімкнемо у положення “минимальному значению”.
13. У полі “Изменяя ячейки” вкажемо на адреси клітинок з основними незалежними змінними: B18:E21.
14. У поле “Ограничения” введемо обмеження задачі. Для цього натиснемо кнопку “Добавить” та введемо обмеження:
а) щодо кількості замовлень, які доручатимуться кожному перевізнику:
| $B$22:$E$22 | = |
б) щодо кількості перевізників, яким буде доручено виконання кожного замовлення:
| $F$18:$F$21 | = |
в) щодо умов цілочисловості усіх логічних змінних:
| $B$18:$E$21 | цел | =целое |
/Далі ми введемо параметр невід’ємності змінних. Тому, враховуючи обмеження у п.п. 14а та 14б, вимоги цілочисловості достатньо, щоб відповідні змінні набували лише значень 1 або 0. Альтернативним варіантом є використання у цих обмеженнях оператору “двоич”./
15. Введемо параметр пошуку рішення: “Неотрицательные переменные”.
16. Натиснемо на кнопку “Выполнить”.
17. Зафіксуємо результати, натиснувши на клавішу ОК у вікні “Результаты поиска решения”.
Розв’язок задачі пошуку плану розподілу завдань між перевізниками за критерієм мінімізації часу завершення усіх перевезень показано на рисунку 4.2. Мінімально можлива тривалість виконання усіх перевезень становить 11 годин, що засвідчує значення у цільовій клітинці E13. Задачу розв’язано.
| A | B | C | D | E | F | |
| Оптимізація плану розподілу замовлень на перевезення за критерієм мінімізації часу виконання всіх робіт | ||||||
| Тривалість виконання перевезень | ||||||
| Замовлення | Перевізник | |||||
| П-1 | П-2 | П-3 | П-4 | |||
| З-1 | ||||||
| З-2 | ||||||
| З-3 | ||||||
| З-4 | ||||||
| Час закінчення усіх перевезень | ||||||
| План розподілу завдань на перевезення | ||||||
| Замовлення | Перевізник | |||||
| П-1 | П-2 | П-3 | П-4 | Сума | ||
| З-1 | ||||||
| З-2 | ||||||
| З-3 | ||||||
| З-4 | ||||||
| Сума | ||||||
| Тривалості перевезень згідно плану розподілу завдань | ||||||
| Замовлення | Перевізник | |||||
| П-1 | П-2 | П-3 | П-4 | |||
| З-1 | ||||||
| З-2 | ||||||
| З-3 | ||||||
| З-4 | ||||||
Рис. 4.2. Робочий лист книги “Prizn-1” з результатами розв’язування задачі
про оптимізацію плану розподілу замовлень на перевезення
за критерієм мінімізації часу виконання всіх робіт