1.3. Методичні вказівки до виконання лабораторної робіти
Процес пошуку опорного та оптимального планів перевезень у транспортної ( T ) задачі розглянемо на конкретному прикладі. Відмітимо також, що всі без винятку спрощені методи розв’язання Т-задачі базуються на транспортній таблиці (див. табл. 3.3).
В центрі кожної клітинки перехрестя і проставляються обсяги відповідних перевезень ( ), у її верхньому правому куті – відповідні відстані від до , тобто .
Таблиця 3.3
Складання опорного плану перевезень
методом північно-західного кута
|
|
|
|
|
Запаси |
|
4
80
|
7
20
|
2
|
5
|
100 |
|
3
|
6
80 -
|
1
+ 40
|
8
|
120 |
|
9
|
3
+
|
6
70 -
|
2
70
|
140 |
Заявки |
80 |
100 |
110 |
70 |
360 |
Із застосуванням транспортних таблиць Т-задача формулюється наступним чином: визначити такі позитивні значення обсягів перевезень , сума яких по кожному і –му ряду ( ) дорівнює , і сума яких по кожній j-й колонці ( ) дорівнює , при цьому сума добутків ( ) по всіх клітинках буде мінімальною.
Як вже визначалось, починаємо завжди зі складання опорного плану перевезень. Розглянемо найбільш поширений метод складання опорного плану, що зветься методом північно – західного кута.
Згідно таблиці 3.3 маємо: m = 3; n = 4.
b1 = 80 т.; b2 = 100 т.; b3 = 110 т.; b4 = 70 т.; а1 = 100 т.; а2 = 120 т.; а3 = 140 т.;
Заповнення обсягів перевезень починаємо з клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення ; якщо обсягу не вистачає, беремо частину від , якщо в щось залишається, віддаємо решту до і т.д.
Для розглянутого випадку робимо наступне:
Задовольнимо , решту відправимо до B2;
Оскільки ще не задовільнено, додамо необхідний обсяг за рахунок (ще 80); решту відправимо до ;
Щоб повністю задовольнити , додамо необхідний обсяг за рахунок (ще 70). Решту відправимо до , задовольнив таким чином його повністю.
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (n + m – 1) = (4 + 3 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають ( ) і ( ), отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень. Якщо приймемо для спрощення С = 1 грн (вартість 1 ткм), то
Після складання опорного плану стає питання, чи є цей план перевезень оптимальним ? Скоріше за все ні, тому що ми не звертали уваги на існуючі відстані від до , що значно відрізняються одна від одної.
Нехай опорний план, отриманий за допомогою методу північно-західного кута, є такий, що наведено в таблиці 3.4. Простежимо, як буде змінюватися план перевезень (якщо він не є оптимальним) з оцінкою кожного разу поточного значення загальної вартості перевезень. Найвірогідніше, що ця вартість має поступово зменшуватися за рахунок поліпшення плану перевезень.
Перевіряємо, чи зміниться в бік зменшення вартості план перевезень, якщо почергово робити спробу перемістити одиницю вантажу в кожну незайняту клітинку. В цьому випадку кожну незайняту клітинку помістимо у вершину контуру, в інших вершинах якого розташовані зайняті клітинки. Наприклад, для незайнятої клітинки таким контуром буде: .
Для кожного такого контуру знаходимо вартісну характеристику переміщення одиниці вантажу в незайняту клітинку ( ), не змінюючи баланс сум перевезень в рядках та стовпчиках. Для переміщення, наприклад, 1 т вантажу в отримуємо збільшення вартості на ( ), але для збереження балансу вантажів в рядках і стовпчиках зменшуємо на 1 т вантаж в клітинці , що викличе зменшення вартості перевезень на ( ). Оскільки зменшується на 1 т, додамо в клітинку також 1 т, що викличе збільшення вартості перевезення на ( ). Однак збільшення на 1 т повинно призвести до зменшення на 1 т, тобто до зменшення вартості перевезень на ( ). Це зменшення буде скомпенсоване раніше проведеним додаванням 1 т в незайняту клітинку . Таким чином, додавання 1 т в незайняту клітинку призведе до зміни вартості на величину вартісної характеристики (при С = 1 грн/ткм):
Іншими словами, переміщення одиниці вантажу (або будь-якого об’єму) по контуру не викличе зміни вартості перевезень, тобто така модернізація початкового плану недоцільна. Відзначимо, що вартість С = 1 грн/ткм входить в як додатній коефіцієнт при алгебраїчній сумі відстаней по даному контуру, тому будемо визначати в незайнятій (ij)-ї клітинці як алгебраїчну суму відстаней по даному контуру, причому для даної незайнятої клітинки ця відстань приймається завжди зі знаком “+”, потім за мірою просування по контуру (або в одну, або в іншу сторону – напрям проходження контуру не має значення) відстані приймають послідовно знаки “-” або “+”.
Очевидно, що якщо отримане значення для ij-ї незайнятої клітинки буде від’ємним, то це свідчить про те, що переміщення вантажу в цю точку знижують загальну вартість перевезень, якщо ж , то переміщення в цю точку збільшується вартість перевезень; якщо , то вартість перевезень не змінюється.
Визначаємо для всіх незайнятих клітинок:
;
;
α31 = 9 – 4 + 7 – 6 + 1 – 6 = 1;
Таким чином, доцільно перерозподілити обсяги перевезень базового плану по контуру з метою завантаження клітинки , яка має . Будуємо цей контур з виказанням знаків, що послідовно міняються і позначають додавання або зменшення об’ємів перевезень по даному контуру (див. табл. 3.4).
Об’єм вантажу, що переміщається, визначається як мінімальний з від’ємних об’ємів по даному контуру ( ). Таким чином, переміщення вантажу по даному контуру дозволить максимально завантажити клітинку і повністю розвантажити клітинку . Очевидно, що при цьому стане рівним (80 – 70) = 10, а стане рівним (40 + 70) = 110. Інші значення для даного контуру ; .
Очевидно, що загальна вартість перевезень повинна при цьому змінитися на:
і має бути рівною
Щоб перевірити скоректований план на оптимальність, будуємо таблицю 3.4, що аналогічна таблиці 3 для отримання нового плану, і знову перевіряємо його на оптимальність з допомогою вартісних характеристик незайнятих клітинок.
Для отриманого плану перевезень маємо:
;
;
;
Перевіряємо загальну вартість перевезень:
.
Таблиця 3.4
|
|
|
|
|
Запаси |
|
4
80
|
7 - 20
|
2
|
5 +
|
100 |
|
3
|
6
10
|
1
110
|
8
|
120 |
|
9
|
3
70 +
|
6
|
2
70 -
|
140 |
Заявки |
80 |
100 |
110 |
70 |
360 |
що співпадає з очікуваною вартістю перевезень. Але цей план не є також оптимальним, так як , тому будуємо замкнутий контур для клітинки , що має , і переносимо (згідно контуру в таблиці 1.4) в клітинку . Знову заповнюємо транспортну таблицю для скоректованого плану( див. табл. 3.5). При цьому зменшення вартості повинно складати , а загальна вартість
, і т.д.
Нагадаємо, що план буде оптимальним в тому випадку, якщо всі вартісні характеристики незаповнених клітинок будуть невід’ємними ( ). Після цього процес пошуку оптимального плану перевезень завершено. Зокрема для даного плану оптимальним буде наступний план перевезень, який має Lопт=950 грн. Цей метод оптимізації має назву розподільчий.
Більш простим методом оптимізації плану перевезень є метод потенціалів, суть якого полягає у наступному.
1. Приймаємо будь-який початковий потенціал ui для i-го ряду таблиці; шукаємо заповнену клітинку (ij), для якої і визначаємо відповідний потенціал та рахуємо: vj = lij - ui . Робимо аналогічні розрахунки для решти рядів і колонок таблиці, спираючись на вже розраховані транспортні потенціали.
Таблиця 3.5
|
|
|
|
|
Запаси |
|
4
80
|
7
|
2
|
5
20
|
100 |
|
3
|
6
10
|
1
110
|
8
|
120 |
|
9
|
3
90
|
6
|
2
50
|
140 |
Заявки |
80 |
100 |
110 |
70 |
360 |
2. Після визначення i ( ; ) перевіряємо нерівність для всіх (ij) незайнятих клітинок таблиці (тобто для ). Якщо ця нерівність має місце для усіх без виключення незайнятих клітинок, план перевезень є оптимальним.
3. Якщо у будь якій незайнятій клітинці , то складений план перевезень не є оптимальним і підлягає корегуванню. Корегування полягає в заповненні незайнятих клітинок, що мають , згідно правил перерозподілу вантажу по клітинках, що вже застосовувалась раніше, при розгляданні розподільчого методу оптимізації плану перевезень.
При умові для незайнятої клітинки ( ) означає, що перерозподіл вантажу в цю клітинку можливий, але це не поліпшує, ні погіршує план перевезень. Це означає, що є ще один план, еквівалентний по вартості перевезень. Тому в подальшому домовимось вважати, що клітинка залишається незайнятою при .
Наприклад, є певний опорний план перевезень (табл. 3.6). Розрахуємо потенціали і , використовуючи саме зайняті клітинки, і занесемо їх в додаткові стовпчик і рядок.
Приймаємо , тоді ; . Використовуючи вже отримані потенціали, визначаємо решту потенціалів:
; ;
;
Відмітимо, що для отриманого плану (при C = 1 грн/ткм) маємо L = 980 грн, що набагато краще опорного плану, отриманого за методом північно-західного кута (L1=1540 грн.).
Перевіряємо опорний план на оптимальність, використовуючи отримані потенціали. Для цього перевіряємо умову оптимальності для всіх незайнятих клітинок плану, тобто :
; ; ;
; ; .
Опорний план не є оптимальним, тому що для клітинки . Це означає, що ця клітинка, як кажуть, є потенційною і має бути завантажена.
Таблиця 3.6
|
|
|
|
|
|
|
4
|
7
|
2
|
6
|
|||
|
0
|
4
|
7
30 -
|
2
70
|
5
+
|
100 |
|
-1
|
3
80
|
6
|
1
40
|
8
|
120 |
|
-4
|
9
|
3 + 70
|
6
|
2 - 70
|
140 |
|
80 |
100 |
110 |
70 |
360 |
Для цього шукаємо контур, що містить у решті кутів зайняті клітинки. Це контур: . Оскільки ми завантажуємо , присвоюємо їй знак “+”, потім, пересуваючись по контуру, послідовно міняємо знаки. Мінімальне абсолютне значення від’ємного обсягу знаходиться в клітинці і дорівнює x = 30 т. Пересуваємо цей обсяг по контуру з урахуванням знаків і отримуємо новий план перевезень. Далі процес повторюється до отримання оптимального плану.