Для цього елемента запаси рівні 2, потреби 6. Оскільки мінімальним є 2, то віднімаємо його.
x24 = min(2,6) = 2.
| 20 | 16 | 13 | x | x | 0 |
| x | x | 15 | 10 | x | 2 - 2 = 0 |
| x | x | x | 5 | 15 | 10 |
| 0 | 0 | 0 | 6 - 2 = 4 | 6 | 0 |
Шуканий елемент дорівнює 5
Для цього елемента запаси рівні 10, потреби 4. Оскільки мінімальним є 4, то віднімаємо його.
x34 = min(10,4) = 4.
| 20 | 16 | 13 | x | x | 0 |
| x | x | 15 | 10 | x | 0 |
| x | x | x | 5 | 15 | 10 - 4 = 6 |
| 0 | 0 | 0 | 4 - 4 = 0 | 6 | 0 |
Шуканий елемент дорівнює 15
Для цього елемента запаси рівні 6, потреби 6. Оскільки мінімальним є 6, то віднімаємо його.
x35 = min(6,6) = 6.
| 20 | 16 | 13 | x | x | 0 |
| x | x | 15 | 10 | x | 0 |
| x | x | x | 5 | 15 | 6 - 6 = 0 |
| 0 | 0 | 0 | 0 | 6 - 6 = 0 | 0 |
| Завод №1 | Завод №2 | Завод №3 | Завод №4 | Завод №5 | Запаси | |
| Ферма №1 | 20[11] | 16[9] | 13[5] | 15 | 11 | 25 |
| Ферма №2 | 10 | 5 | 15[3] | 10[2] | 23 | 5 |
| Ферма №3 | 25 | 20 | 5 | 5[4] | 15[6] | 10 |
| Потреби | 11 | 9 | 8 | 6 | 6 | 40 |
У результаті отриманий перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
2. Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m + n - 1 = 7. Отже, опорний план є невиродженим.
Значення цільової функції для цього опорного плану одно:
F(x) = 20*11 + 16*9 + 13*5 + 15*3 + 10*2 + 5*4 + 15*6 = 604
Етап II. Поліпшення опорного плану.
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 20; 0 + v1 = 20; v1 = 20
u1 + v2 = 16; 0 + v2 = 16; v2 = 16
u1 + v3 = 13; 0 + v3 = 13; v3 = 13
u2 + v3 = 15; 13 + u2 = 15; u2 = 2
u2 + v4 = 10; 2 + v4 = 10; v4 = 8
u3 + v4 = 5; 8 + u3 = 5; u3 = -3
u3 + v5 = 15; -3 + v5 = 15; v5 = 18
| v1=20 | v2=16 | v3=13 | v4=8 | v5=18 | |
| u1=0 | 20[11] | 16[9] | 13[5] | 15 | 11 |
| u2=2 | 10 | 5 | 15[3] | 10[2] | 23 |
| u3=-3 | 25 | 20 | 5 | 5[4] | 15[6] |
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi > cij
(1;5): 0 + 18 > 11; ∆15 = 0 + 18 - 11 = 7
(2;1): 2 + 20 > 10; ∆21 = 2 + 20 - 10 = 12
(2;2): 2 + 16 > 5; ∆22 = 2 + 16 - 5 = 13
(3;3): -3 + 13 > 5; ∆33 = -3 + 13 - 5 = 5
max(7,12,13,5) = 13
Вибираємо максимальну оцінку вільної клітини (2;2): 5
Для цього в перспективну клітку (2;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
| Завод №1 | Завод №2 | Завод №3 | Завод №4 | Завод №5 | Запаси | |
| Ферма №1 | 20[11] | 16[9][-] | 13[5][+] | 15 | 11 | 25 |
| Ферма №2 | 10 | 5[+] | 15[3][-] | 10[2] | 23 | 5 |
| Ферма №3 | 25 | 20 | 5 | 5[4] | 15[6] | 10 |
| Потреби | 11 | 9 | 8 | 6 | 6 |
Цикл наведено в таблиці (2,2; 2,3; 1,3; 1,2; ).
З вантажів хij стоять у мінусових клітинах, вибираємо найменше, тобто у = min (2, 3) = 3. Додаємо 3 до обсягів вантажів, що стоять у плюсових клітинах і віднімаємо 3 з Хij, стоять у мінусових клітинах. У результаті отримаємо новий опорний план.
| Завод №1 | Завод №2 | Завод №3 | Завод №4 | Завод №5 | Запаси | |
| Ферма №1 | 20[11] | 16[6] | 13[8] | 15 | 11 | 25 |
| Ферма №2 | 10 | 5[3] | 15 | 10[2] | 23 | 5 |
| Ферма №3 | 25 | 20 | 5 | 5[4] | 15[6] | 10 |
| Потреби | 11 | 9 | 8 | 6 | 6 |
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 20; 0 + v1 = 20; v1 = 20
u1 + v2 = 16; 0 + v2 = 16; v2 = 16
u2 + v2 = 5; 16 + u2 = 5; u2 = -11
u2 + v4 = 10; -11 + v4 = 10; v4 = 21
u3 + v4 = 5; 21 + u3 = 5; u3 = -16
u3 + v5 = 15; -16 + v5 = 15; v5 = 31
u1 + v3 = 13; 0 + v3 = 13; v3 = 13
| v1=20 | v2=16 | v3=13 | v4=21 | v5=31 | |
| u1=0 | 20[11] | 16[6] | 13[8] | 15 | 11 |
| u2=-11 | 10 | 5[3] | 15 | 10[2] | 23 |
| u3=-16 | 25 | 20 | 5 | 5[4] | 15[6] |
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi > cij
(1;4): 0 + 21 > 15; ∆14 = 0 + 21 - 15 = 6
(1;5): 0 + 31 > 11; ∆15 = 0 + 31 - 11 = 20
max(6,20) = 20
Вибираємо максимальну оцінку вільної клітини (1;5): 11