p> загаль математична модель сформульованої задачі має вигляд:
minZ = 1x11 + 4x12 + 1x13 + 5x14 +6 x15 + 0x16 +1 x21 + 3x22 + 1x23 + 1x24 +2 x25 +0 x26 +4 x31 + 1x32 + 2x33 + 2x34 +3 x35 + 0x36. br/>
за умів:
В В
Запішемо умови задачі у вігляді транспортної табліці та складемо ее перший опорний план у Цій табліці методом В«північно-західного кутаВ».
Ai
Bj
ui
b1 = 100
b2 = 120
b3 = 90
b4 = 70
b5 = 80
B6 = 290
а1 = 300
1
100
4
[-] 120
1
[+] 80
5
6
0
u1 = 0
а2 = 250
1
3
1
[-] 10
1
70
2
80
0
[+] 90
u2 = 0
а3 = 200
4
1
[+]
2
2
3
0
[-] 200
u3 = 0
vj
v1 = 1
v2 = 4
v3 = 1
v4 = 1
v5 = 2
V6 = 0
У результаті ОТРИМАНО перший опорний план, Який є допустимим, оскількі ВСІ вантажі з баз вівезені, потреба магазинів задоволена, а план відповідає Системі обмежень транспортної задачі.
Підрахуємо число зайнятості клітін табліці, їх 8, а має буті m + n-1 = 8. Отже, опорний план є НЕ вироджених.
Перевірімо оптімальність опорного плану, складемо систему рівнянь (для заповненості клітін табліці) для визначення потенціалів Першого опорного плану:
В
Записана система рівнянь є невизначенності, и один з ее розв'язків дістанемо, узявші, Наприклад, u1 = 0. Тоді ВСІ Інші потенціалі однозначно візначаються з цієї системи рівнянь: u1 = 0, u2 = 0, u3 = 0, v1 = 1, v2 = 4, v3 = 1 v4 = 1, v5 = 2, v6 = 0. Ці Значення потенціалів Першого опорного плану запісуємо у транспортної таблиці.
Потім згідно з алгоритмом методу потенціалів перевіряємо Виконання Другої умови оптімальності ui + vj ≤ cij (для порожніх клітінок табліці):
А1B4: u1 + v4 = 0 + 1 = 1 <5;
А1B5: u1 + v5 = 0 + 2 = 2 <6;
А1B6: u1 + v6 = 0 + 0 = 0 = 0;
А2B1: u2 + v1 = 0 + 1 = 1 = 1;
А2B2: u2 + v2 = 0 + 4 = 4> 3;
А3B1: u3 + v1 = 0 + 1 = +1 <4;
А3B2: u3 + v2 = 0 + 4 = +4> 1;
А3B3: u3 + v3 = 0 + 1 = 1 <2;
А3B4: u4 + v1 = 0 + 1 = 1 <2;
А3B5: u4 + v2 = 0 + 2 = 2 <3;
Опорний план не є оптимальним, тому что існують ОЦІНКИ вільніх клітін для якіх ui + vi> cij
А2B2: u2 + v2 = 0 + 4 = 4> 3;
А3B2: u3 + v2 = 0 + 4 = +4> 1;
Тому від нього звітність, перейти до іншого плану, змінівші співвідношення заповненості и порожніх клітінок табліці. Вібіраємо Максимально оцінку Вільної Клітини (А3B2): 1
ставімие в ній знак В«+В». Для визначення клітінкі, что звільняється, будуємо цикл, починаючі з клітінкі А3B2, та позначаємо вершини циклу почергово знаками В«-В» и В«+В». Тепер звітність, перемістіті продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B4 переносимо менше з чисел хij, Які розміщені в клітінках Зі знаком В«-В». Одночасно це самє число хij додаємо до відповідніх чисел, что розміщені в клітінках Зі знаком В«+В», та віднімаємо від чисел, что розміщені в клітінках, позначені знаком В«-В».
Зх вантажів хij что стояти в мінусовіх клітінах, вібіраємо найменша,, тоб. Додаємо 10 до обсягів вантажів, что стояти в плюсова клітінах и віднімаємо 10 з Хij, что стояти в мінусовіх клітінах. У результаті отрімаємо новий опорний план. УСІ Другие заповнені клітінкі Першої табліці, Які не входили до циклу, перепісуємо у другу таблицю без змін. Кількість заповненості клітінок у новій табліці такоже має відповідаті умові невіродженості планом, тоб дорівнюваті (n + m - 1).
Отже, інших опорних план транспортної задачі матіме такий вигляд:
Ai
Bj
ui
b1 = 100
b2 = 120
b3 = 90
b4 = 70
b5 = 80
B6 = 290
а1 = 300
1
100
...
