Транспортна задача
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів
| | B1 | B2 | B3 | B4 | Запаси |
| A1 | 3 | 7 | 4 | 5 | 180 |
| A2 | 4 | 3 | 4 | 5 | 200 |
| A3 | 3 | 4 | 3 | 4 | 240 |
| A4 | 2 | 3 | 7 | 4 | 160 |
| Потреби | 280 | 200 | 320 | 240 | |
Перевіримо необхідна і достатня умова розв'язання задачі.
Σa = 180 + 200 + 240 + 160 = 780
Σb = 280 + 200 + 320 + 240 = 1040
Як видно, сумарна потреба вантажу в пунктах призначення перевищує запаси вантажу на базах. Отже, модель вихідної транспортної задачі є відкритою. Тобто жоден оптимальний план не може задовольнити умови повністю, враховуючи, що ПОТРЕБИ перевищують ЗАПАСИ.
Щоб отримати закриту модель, введемо додаткову (фіктивну) базу з запасом вантажу, рівним 260 (1040-780).
Тарифи перевезення одиниці вантажу з бази в усі магазини вважаємо дорівнюють нулю.
Занесемо вихідні дані в розподільну таблицю.
| | B1 | B2 | B3 | B4 | Запаси |
| A1 | 3 | 7 | 4 | 5 | 180 |
| A2 | 4 | 3 | 4 | 5 | 200 |
| A3 | 3 | 4 | 3 | 4 | 240 |
| A4 | 2 | 3 | 7 | 4 | 160 |
| A5 Фіктивна база | 0 | 0 | 0 | 0 | 260 |
| Потреби | 280 | 200 | 320 | 240 | |
Модель приведено до закритого типу Σa = Σb (за рахунок введення фікт. бази)
Етап I. Пошук першого опорного плану.
1. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі.
Суть методу полягає в тому, що з усієї таблиці вартостей вибирають найменшу, і в клітку, яка їй відповідає, поміщають менше з чисел ai, або bj.
Потім, виключають або рядок, відповідно постачальнику, запаси якого повністю витрачені, або стовпець, відповідно споживачеві, потреби якого повністю задоволені, або і рядок і стовпець, якщо витрачені запаси постачальника і задоволені потреби споживача.
З решти таблиці вартостей знову вибирають найменшу вартість, і процес розподілу запасів продовжують, поки всі запаси не будуть розподілені, а потреби задоволені.
Далі приводимо ітерації пошуку опорн6ого плану
Шуканий елемент дорівнює c41 = 2. Для цього елемента запаси рівні 160, потреби 280. Оскільки мінімальним є 160, то віднімаємо його.
x41 = min (160,280) = 160.
| 3 | 7 | 4 | 5 | 180 |
| 4 | 3 | 4 | 5 | 200 |
| 3 | 4 | 3 | 4 | 240 |
| 2 | x | x | x | 160 - 160 = 0 |
| 0 | 0 | 0 | 0 | 260 |
| 280 - 160 = 120 | 200 | 320 | 240 | |
Шуканий елемент дорівнює c11 = 3. Для цього елемента запаси рівні 180, потреби 120. Оскільки мінімальним є 120, то віднімаємо його.
x11 = min (180,120) = 120.
| 3 | 7 | 4 | 5 | 180 - 120 = 60 |
| x | 3 | 4 | 5 | 200 |
| x | 4 | 3 | 4 | 240 |
| 2 | x | x | x | 0 |
| x | 0 | 0 | 0 | 260 |
| 120 - 120 = 0 | 200 | 320 | 240 | |
Шуканий елемент дорівнює c22 = 3. Для цього елемента запаси рівні 200, потреби 200. Оскільки мінімальним є 200, то віднімаємо його. В даному випадку неважливо, що саме ми оберемо…
x22 = min (200,200) = 200.
| 3 | 7 | 4 | 5 | 60 |
| x | 3 | x | x | 200 - 200 = 0 |
| x | 4 | 3 | 4 | 240 |
| 2 | x | x | x | 0 |
| x | 0 | 0 | 0 | 260 |
| 0 | 200 - 200 = 0 | 320 | 240 | |
Шуканий елемент дорівнює c33 = 3. Для цього елемента запаси рівні 240, потреби 320. Оскільки мінімальним є 240, то віднімаємо його.
x33 = min (240,320) = 240.
| 3 | 7 | 4 | 5 | 60 |
| x | 3 | x | x | 200 - 200 = 0 |
| x | 4 | 3 | 4 | 240 |
| 2 | x | x | x | 0 |
| x | 0 | 0 | 0 | 260 |
| 0 | 200 - 200 = 0 | 320 | 240 | |
Шуканий елемент дорівнює c13 = 4. Для цього елемента запаси рівні 60, потреби 80. Оскільки мінімальним є 60, то віднімаємо його.
x13 = min (60,80) = 60.
| 3 | 7 | 4 | x | 60 - 60 = 0 |
| x | 3 | x | x | 0 |
| x | 4 | 3 | x | 0 |
| 2 | x | x | x | 0 |
| x | 0 | 0 | 0 | 260 |
| 0 | 0 | 80 - 60 = 20 | 240 | |
Шуканий елемент дорівнює c53 = 0. Для цього елемента запаси рівні 260, потреби 20. Оскільки мінімальним є 20, то віднімаємо його.
x53 = min (260,20) = 20.
| 3 | 7 | 4 | x | 0 |
| x | 3 | x | x | 0 |
| x | 4 | 3 | x | 0 |
| 2 | x | x | x | 0 |
| x | 0 | 0 | 0 | 260 - 20 = 240 |
| 0 | 0 | 20 - 20 = 0 | 240 | |
Шуканий елемент дорівнює c54 = 0. Для цього елемента запаси рівні 240, потреби 240. Оскільки мінімальним є 240, то віднімаємо його.
x54 = min (240,240) = 240.
| 3 | 7 | 4 | x | 0 |
| x | 3 | x | x | 0 |
| x | 4 | 3 | x | 0 |
| 2 | x | x | x | 0 |
| x | 0 | 0 | 0 | 240 - 240 = 0 |
| 0 | 0 | 0 | 240 - 240 = 0 | |
Далі, згідно з алгоритмом, шукаємо елементи серед тих, що залишились ( не викреслених).
| 3 | 7 | 4 | 5 | 180 |
| 4 | 3 | 4 | 5 | 200 |
| 3 | 4 | 3 | 4 | 240 |
| 2 | 3 | 7 | 4 | 160 |
| 0 | 0 | 0 | 0 | 260 |
| 280 | 200 | 320 | 240 | |
Шуканий елемент дорівнює c42 = 3, так як обмеження виконані, то x42 = 0.
| | B1 | B2 | B3 | B4 | Запаси |
| A1 | 3[120] | 7 | 4[60] | 5 | 180 |
| A2 | 4 | 3[200] | 4 | 5 | 200 |
| A3 | 3 | 4 | 3[240] | 4 | 240 |
| A4 | 2[160] | 3[0] | 7 | 4 | 160 |
| A5 | 0 | 0 | 0[20] | 0[240] | 260 |
| Потреби | 280 | 200 | 320 | 240 | |
В результаті отримано опорний план, який є допустимим, оскільки всі вантажі з баз вивезені (сума виділених жирним чисел в матриці рівна по горизонталі запасам, а по вертикалі потребам), потреби магазинів задоволені, а план відповідає системі обмежень транспортної задачі.
2. Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m + n - 1 = 8. Отже, опорний план є невиродженим.
Значення цільової функції для цього опорного плану рівне:
F (x) = 3*120 + 4*60 + 3*200 + 3*240 + 2*160 + 0*20 + 0*240 = 2240
Етап II. Поліпшення опорного плану.
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vj. по зайнятих клітинам таблиці, в яких ui + vj = cij, вважаючи, що u1 = 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u4 + v1 = 2; 3 + u4 = 2; u4 = -1
u4 + v2 = 3; -1 + v2 = 3; v2 = 4
u2 + v2 = 3; 4 + u2 = 3; u2 = -1
u1 + v3 = 4; 0 + v3 = 4; v3 = 4
u3 + v3 = 3; 4 + u3 = 3; u3 = -1
u5 + v3 = 0; 4 + u5 = 0; u5 = -4
u5 + v4 = 0; -4 + v4 = 0; v4 = 4
| | v1=3 | v2=4 | v3=4 | v4=4 |
| u1=0 | 3[120] | 7 | 4[60] | 5 |
| u2=-1 | 4 | 3[200] | 4 | 5 |
| u3=-1 | 3 | 4 | 3[240] | 4 |
| u4=-1 | 2[160] | 3[0] | 7 | 4 |
| u5=-4 | 0 | 0 | 0[20] | 0[240] |
Опорний план є оптимальним, так все оцінки вільних клітин задовольняють умові ui + vj ≤ cij.
Мінімальні витрати складуть:
F (x) = 3*120 + 4*60 + 3*200 + 3*240 + 2*160 + 0*20 + 0*240 = 2240
В результаті всі запаси вивезено, з мінімальними затратами . та максимально можливим варіантом забезпечення потреб.
Запропонований оптимальний план не задовольняє потреби магазину №3 на 20 одиниць продукції, магазин №4 – на 240 одиниць. Дана ситуація спричинена початковим перевищенням потреб над запасами (див. початок, аналіз задачі.)