З-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.

Таблиця 4.2

Очікувана тривалість виконання замовлень на перевезення

різними виконавцями, годин

Замовлення	Перевізник
П-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” з результатами розв’язування задачі
про оптимізацію плану розподілу замовлень на перевезення
за критерієм мінімізації часу виконання всіх робіт

При розв’язуванні нелінійних задач або задач з цілочисловими чи логічними змінними потрібно уважно проаналізувати отримані результати, оскільки інколи замість точного розв’язку на екран спочатку виводиться лише наближений розв’язок, який може істотно відрізнятися від точного. Наприклад, мій комп’ютер кілька разів зупинявся на плані розподілу замовлень , який вимагає для виконанню 12 годин, що на 9,09% більше, аніж при оптимальному плані. Зараз, щоб переконатися, що оптимальний план розподілу замовлень на перевезення вимагає 11 годин, досить звернути увагу, що третє замовлення (З-3) потребує для свого виконання щонайменше 11 годин (за умови його призначення першому перевізнику П-1), тому виконати всі замовлення за час, менший від 11 годин, неможливо.

В загальному випадку щоб упевнитись у правильності розв’язку, окрім аналітичних досліджень буває корисним запустити інструмент “Поиск решения” декілька разів, починаючи щоразу з іншої “стартової” точки.

4.4. Завдання для самостійного опрацювання

1. Знайти найекономічніший план розподілу п’яти запитів на перевезення між виконавцями за відомими тарифами перевізників на виконання кожного з перевезень (таблиця 4.3). Врахувати вимогу задіяти для перевезень усіх перевізників.

Таблиця 4.3

Тарифи на виконання замовлень різними перевізниками, гривень

Замовлення	Перевізник
П-1	П-2	П-3	П-4	П-5
З-1
З-2
З-3
З-4
З-5

2. Припустимо, що в задачі про призначення кількість запитів на перевезення () не збігається з кількістю виконавців (), причому . Усі перевезення потрібно виконати, залучивши саме перевізників та доручаючи кожному з залучених перевізників точно по одному завданню. Решта виконавців до виконання робіт не залучатимуться. Побудувати економіко–математичну модель задачі, щоб визначити, кого саме із перевізників слід залучити.

3. Припустимо, що в задачі про призначення кількість запитів на перевезення є більшою від кількості виконавців: . Побудувати економіко–математичну модель задачі для випадку, коли окремим виконавцям можна доручати виконання кількох перевезень?

4. Який з планів розподілу завдань на перевезення вимагатиме найменше часу для виконання, якщо перевізники розпочнуть усі перевезення одночасно? /Інформація про очікувану тривалість виконання кожним із перевізників кожного завдання наведена у таблиці 4.4./

Таблиця 4.4

Очікувана тривалість виконання замовлень на перевезення

різними виконавцями, годин

Замовлення	Перевізник
П-1	П-2	П-3	П-4	П-6	П-6
З-1
З-2
З-3
З-4
З-5
З-6

5. Наведіть власні приклади можливого застосування задачі про призначення в економічній та управлінській діяльності діяльності.

РОЗДІЛ 5. ОПТИМІЗАЦІЯ КАЛЕНДАРНОГО ПЛАНУ
ВИРОБНИЦТВА, ЗБЕРІГАННЯ ТА ПОСТАВОК ПРОДУКЦІЇ

5.1. Постановка та економіко–математична модель задачі

5.2. Приклад розв’язування задачі на ПК

5.3. Завдання для самостійного опрацювання