28. Методи розв'язання транспортної задачі.

Один із способів розв’язування транспортної задачі ґрунтується на розгляді двоїстої задачі.

Розглянемо транспортну задачу.

(5.1)

за обмежень:

;(5.2)

;(5.3)

.(5.4)

Оскільки всі обмеження транспортної задачі є рівняннями, то пара спряжених задач є несиметричною і ніякі обмеження на знаки змінних двоїстої задачі та не накладаються.

Для побудови двоїстої задачі поставимо у відповідність обмеженням початкової задачі змінні двоїстої:

(5.20)

(5.21)

.

Згідно з загальними правилами побудови двоїстих задач маємо:

(5.22)

за умов:

,(5.23)

.

Метод потенціалів розв’язування транспортної задачі. Алгоритм методу потенціалів складається з таких етапів:

1.Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу.

2.Побудова першого опорного плану транспортної задачі одним з відомих методів.

3.Перевірка опорного плану задачі на виродженість. За необхідності вводять нульові постачання.

4.Перевірка плану транспортної задачі на оптимальність.

4.1. Визначення потенціалів для кожного рядка і стовпчика таблиці транспортної задачі. Потенціали опорного плану визначають із системи рівнянь ui + vj = cij, які записують для всіх запов­нених клітинок транспортної таблиці, кількість яких дорівнює , а кількість невідомих — . Кількість рівнянь на одне менша, ніж невідомих, тому система є невизначеною, і одному з потенціалів надають нульове значення. 4.2. Перевірка виконання умови оптимальності для пустих клітин.

4.3. Вибір змінної для введення в базис на наступному кроці.

4.4. Побудова циклу і перехід до наступного опорного плану.

5. Перевірка умови оптимальності наступного опорного плану. Якщо умова оптимальності виконується — маємо оптимальний план транспортної задачі

Угорський метод розв’язування транспортної задачі.

(5.27)

(5.28)

(5.29)

Починаючи з деякого початкового плану задачі, подвійної до транспортної , можна знайти послідовність оптимальних планів ряду допоміжних задач на мінімізацію (5.29) за обмежень (5.27) і (5.28), кожний наступний план якої надає нев’язці (5.29) меншого значення у зіставленні з попереднім, а останній план цієї послідовності надає нев’язці нульового значення, збігаючись у такий спосіб з оптимальним планом транспортної задачі.

Отже, кожна ітерація методу означатиме розв’язування допоміжної задачі (5.27)—(5.28) і зменшення при цьому значення цільової функції (5.29) порівняно з попереднім розв’язком цієї задачі.

Ідея методу полягає у здійсненні послідовного переходу від деякого недопустимого плану (не всі потреби задоволені і не вся продукція вивезена) до допустимого, що є розв’язком задачі. Цей перехід здійснюється за скінченну кількість ітерацій (але невідому до кінця обчислень), що пов’язані з перетвореннями матриці вартостей і поточного плану .

Виходячи з наведених теоретичних засад, розглянемо алгоритм угорського методу:

1. Побудова допоміжної задачі з цільовою функцією (5.32) та умовами (5.27), (5.28).

2. Побудова початкового опорного плану допоміжної задачі, що отримана на попередньому кроці алгоритму, одним з відомих методів.

3. Відшукання оптимального плану допоміжної задачі.

3.1.Збільшення значення. Визначають рядки, де сума перевезень по рядку менша від запасів, а за допомогою них — стовпці, які мають у вибраному рядку не заборонені для перевезень клітини. Вибрані рядки і стовпці позначають так:

, ,(5.33)

та .(5.34)

Потім , .(5.35)

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

У загальному випадку послідовність має вигляд:

4. Перехід до наступної допоміжної задачі, оптимальний план якої буде ближчим до оптимального плану початкової транспорт­ної задачі.

5. Повторення кроків 2—4 до відшукання оптимального плану початкової транспортної задачі.

Двохетапна транспортна задача

Метод розв’язування двохетапної транспортної задачі, розроб­лений Орденом-Маршем, полягає у врахуванні місткостей посередників двічі — як постачальників і як споживачів. Умови задачі подаються у вигляді таблиці, в рядках якої записують дані про постачальників, а також про посередницькі фірми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять нульові величини затрат. Решту клітин таблиці блокують, тобто вартості перевезень прирівнюють до деякого досить великого числа М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам двохетапної транспортної задачі. За деяких умов, наприклад, при перевезенні продукції, що швидко псується; матеріалів для аварійних та рятівних робіт тощо вартість перевезень має другорядне значення, а на перше місце виходить завдання мінімізації того часу, протягом якого здійснюються всі перевезення. Так виникає транспортна задача за критерієм часу.

Розглянемо алгоритм розв’язання сформульованої задачі, що ґрунтується на послідовному розв’язуванні ряду допоміжних задач, розглянутих в угорському методі.

1. Знаходять мінімальний елемент матриці тривалостей перевезень Т.

2. Розв’язують додаткову задачу з визначеною множиною заборонених для перевезень клітин .

3. Аналогічно першому кроку знову знаходять мінімальний елемент серед тих елементів матриці тривалостей перевезень Т, які відповідають клітинам, забороненим для перевезень.

4. Аналогічно другому кроку розв’язують нову допоміжну задачу з іншою множиною клітин, заборонених для перевезень

Серед сучасних методів оптимізації і керування виробничими процесами значна роль належить мережевим методам. Широке коло задач математичного програмування можна подати в мережевому вигляді.

На першому етапі складаємо початковий план перевезень

На другому етапі для кожної вершини визначаємо потенціал. Перший потенціал вибираємо довільно, пов’язуємо його з довільною вершиною, наприклад, першою. Потенціали інших вершин визначаємо, виходячи з першого потенціалу.

Третій етап полягає в перевірці плану на оптимальність, причому використовується звичайна ознака оптимальності плану транспортної задачі, яка формулюється в термінах і позначеннях транспортної задачі на мережі.