З-1 ® П-3, З-2 ® П-1, З-3 ® П-2 .
Загальна вартість виконання робіт за цим планом складає 39 грошових одиниць і є найменшою у порівнянні з усіма іншими допустимими планами розподілу. /Скажімо, попередній план, знайдений за методом мінімального тарифу, вимагав для реалізації 41 грошову одиницю./
Задачу про оптимізацію плану розподілу замовлень на перевезення між перевізниками розв’язано.
Розв’язування задачі на ПК. Розпочнемо роботу зі створення файлу “Prizn-1.xls”, у якому працюватимемо на першому аркуші “Лист 1”.
1. Об’єднаємо клітинки A1:D3 та внесемо туди назву задачі: “Оптимізація плану розподілу замовлень на перевезення за критерієм мінімізації витрат”.
2. Масив клітинок A5:D10 відведемо для інформаційного блоку про індивідуальні тарифи перевізників на виконання кожного з замовлень – таблицю 4.1. У тому числі для числових значень скористаємося клітинками B8:D10.
3. В клітинках A12: D12 побудуємо інформаційний блок про загальні витрати на виконання перевезень згідно плану розподілу замовлень, який ми визначаємо. Для цього об’єднаємо клітинки A12:C12 для слів: “Загальні витрати”, а клітинку D12 оберемо за цільову. Згодом в цю клітинку слід буде ввести формулу для обчислення загальних витрат.
4. Масив клітинок A14: D19 відведемо для інформаційного блоку про план розподілу замовлень; у тому числі для значень логічних змінних відведемо клітинки B17:D19.
5. Уведемо в цільову клітинку D12 формулу для обчислення загальних витрат:
=СУММПРОИЗВ(B8:D10; B17:D19)
6. У клітинки E17:E19 введемо формули для обчислення кількості перевізників, яким буде доручено виконання відповідного замовлення:
у клітинку E17 – формулу: =СУММ(B17:D17)
у клітинку E18 – формулу: =СУММ(B18:D18)
у клітинку E19 – формулу: =СУММ(B19:D19)
/Формулу з клітинки E17 “протягуємо” через клітинки E18 та E19./
7. У клітинки B20:D20 введемо формули для обчислення кількості замовлень, які доручатимуться кожному перевізнику:
у клітинку B20: =СУММ(B17:B19)
у клітинку C20: =СУММ(C17:C19)
у клітинку D20: =СУММ(D17:D19)
/Можна “протягнути” формулу з клітинки B20 на клітинки C20 та D20./
8. Показники, що обчислюватимуться в клітинках E17:E19 та B20:D20, є допоміжними, щоб підкреслити це, в клітинки E16 та A20 впишемо слово: ”Сума”.
Підготовку робочого аркушу закінчено. Далі діятимемо для знаходження розв’язку задачі.
9. Оберемо команду “Поиск решения” в меню “Сервис”.
10. В полі “Установить целевую ячейку” діалогового вікна “Поиск решения” вкажемо на адресу цільової клітинки: D12.
11. Перемикач вибору оптимізаційного спрямування цільової функції увімкнемо у положення “минимальному значению”.
12. У полі “Изменяя ячейки” вкажемо на адреси клітинок з основними незалежними змінними: B17:D19.
13. У поле “Ограничения” введемо обмеження задачі. Для цього натиснемо кнопку “Добавить” та введемо обмеження щодо кількості замовлень, які доручатимуться кожному перевізнику:]
| $B$20:$D$20 | = |
та щодо кількості перевізників, яким буде доручено виконання кожного замовлення:
| $E$17:$E$19 | = |
14. Спробуємо скористатися властивістю методу потенціалів щодо цілочисловості усіх компонентів довільного опорного плану. Тому не вказуватимемо в обмеженнях, що основні змінні мають набирати лише значень 0 або 1 за допомогою оператору “двоич”, а введемо параметри пошуку рішення: “Линейная модель” та “Неотрицательные переменные”.
15. Натиснемо на кнопку “Выполнить”.
16. У вікні “Результаты поиска решения”, яке з’явиться на екрані, натиснемо ОК.
17. Прочитаємо на робочому аркуші Excel знайдений розв’язок (рис. 4.1). Найекономічнішому плану розподілу замовлень на перевезення між різними перевізниками відповідають загальні витрати у сумі 39 грошових одиниць.
| A | B | C | D | E | ||
| Оптимізація плану розподілу замовлень на перевезення за критерієм мінімізації витрат | ||||||
| Тарифи на виконання замовлень | ||||||
| Замовлення | Перевізник | |||||
| П-1 | П-2 | П-3 | ||||
| З-1 | ||||||
| З-2 | ||||||
| З-3 | ||||||
| Загальні витрати | ||||||
| План розподілу замовлень | ||||||
| Замовлення | Перевізник | |||||
| П-1 | П-2 | П-3 | Сума | |||
| З-1 | ||||||
| З-2 | ||||||
| З-3 | ||||||
| Сума | ||||||
Рис. 4.1. Робочий лист книги “Prizn-1” з результатами розв’язування задачі
про оптимізацію плану розподілу замовлень на перевезення
за критерієм мінімізації загальних витрат
4.3. Оптимізація плану розподілу замовлень на перевезення
за критерієм мінімізації часу виконання всіх робіт
Математична постановка задачі. Якщо усі перевезення розпочинаються одночасно, може виникнути задача формування такого плану розподілу завдань між перевізниками, щоб загальний час на виконання усіх перевезень був якнайменшим. Цей час визначається найтривалішим з перевезень та обчислюються за формулою (4.7).
Економіко–математична модель задачі про оптимізацію плану розподілу 
замовлень на перевезення між перевізниками за критерієм мінімізації часу 
виконання всіх робіт, у свою чергу, записується так:
(4.9)
де 
– можлива тривалість виконання 
-го перевезення 
-м виконавцем (
).
Перша група основних обмежень відтворює вимоги про те, щоб кожне з замовлень було доручено точно одному з виконавців. Друга група – про те, щоб кожному з виконавців було доручено точно одне замовлення. Нарешті, останніми обмеженнями відбито те, що основні змінні задачі є логічними та можуть набувати лише значення з множини 
.
Формально задачу (4.9) вважати задачею лінійного програмування не можна, оскільки її цільова функція містить операцію обчислення максимуму із множини 
. Проте її можна звести до задач лінійного типу (зрозуміло, що логічні змінні залишаться), якщо позбутися функції обчислення максимуму. Це перетворення можна зробити у такий спосіб:
(4.10)
Від вибору математичної моделі – (4.9) або (4.10) – залежатиме, чи потрібно вводити у параметри пошуку рішення при розв’язування задачі на комп’ютері параметр “Линейная модель”, чи ні.
Числовий приклад. Припустимо, що 4 перевезення, які слід розпочати одночасно, потрібно розподілити між 4 перевізниками. Тривалості можливого виконання кожним із перевізників кожного завдання відомі та наведені у таблиці 4.2.