Контрольная работа: Математичне програмування
4
[-] 150
3
[+] 50
5
[-] 300
0
50
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u1 + v2 = 2; 0 + v2 = 2; v2 = 2
u2 + v2 = 1; 2 + u2 = 1; u2 = -1
u2 + v3 = 4; -1 + v3 = 4; v3 = 5
u2 + v4 = 4; -1 + v4 = 4; v4 = 5
u3 + v4 = 3; 5 + u3 = 3; u3 = -2
u3 + v5 = 5; -2 + v5 = 5; v5 = 7
u3 + v6 = 0; -2 + v6 = 0; v6 = 2
Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(1;3): 0 + 5 > 3; ∆13 = 0 + 5 - 3 = 2
(1;5): 0 + 7 > 1; ∆15 = 0 + 7 - 1 = 6
(1;6): 0 + 2 > 0; ∆16 = 0 + 2 - 0 = 2
(2;1): -1 + 5 > 1; ∆21 = -1 + 5 - 1 = 3
(2;5): -1 + 7 > 2; ∆25 = -1 + 7 - 2 = 4
(2;6): -1 + 2 > 0; ∆26 = -1 + 2 - 0 = 1
(3;3): -2 + 5 > 2; ∆33 = -2 + 5 - 2 = 1