x22 + 1x23 + 4x24 +1 x25 +5 x31 + 1x32 + 3x33 + 2x34 +3 x35 + 0x41 + 0x42 + 0x43 + 0x44 +0 x45. p> за умів:
В В
Запішемо умови задачі у вігляді транспортної табліці та складемо ее перший опорний план у Цій табліці методом В«північно-західного кутаВ».
Ai
Bj
ui
b1 = 120
b2 = 130
b3 = 200
b4 = 180
b5 = 110
а1 = 200
1
120
4
80
7
8
1
u1 = 0
а2 = 150
2
3
50
1
100
4
1
u2 = -1
а3 = 350
5
1
3
100
2
180
3
70
u3 = 1
а4 = 40
0
0
0
0
0
40
u4 = -2
vj
v1 = 1
v2 = 4
v3 = 2
v4 = 1
V5 = 2
У результаті ОТРИМАНО перший опорний план, Який є допустимим, оскількі ВСІ вантажі з баз вівезені, потреба магазинів задоволена, а план відповідає Системі обмежень транспортної задачі:
Z1 = 1 Г— 120 + 4 Г— 80 + 3 Г— 50 + 1 Г— 100 + 3 Г— 100 + 2 Г— 180 + 3 Г— 70 + 0 Г— 40 = 1560
Підрахуємо число зайнятості клітін табліці, їх 8, а має буті m + n-1 = 8. Отже, опорний план є невіродженіх.
Перевірімо оптімальність опорного плану, складемо систему рівнянь (для заповненості клітін табліці) для визначення потенціалів Першого опорного плану:
В
Записана система рівнянь є невизначенності, и один з ее розв'язків дістанемо, узявші, Наприклад, u1 = 0. Тоді ВСІ Інші потенціалі однозначно візначаються з цієї системи рівнянь: u1 = 0, u2 = -1, u3 = 1, u4 = -2, v1 = 1, v2 = 4, v3 = 2 v4 = 1, v5 = 2. Ці Значення потенціалів Першого опорного плану запісуємо у транспортної таблиці.
Потім згідно з алгоритмом методу потенціалів перевіряємо Виконання Другої умови оптімальності ui + vj ≤ cij (для порожніх клітінок табліці):
А1B3: u1 + v3 = 0 + 2 = 2 <7;
А1B4: u1 + v4 = 0 + 1 = 1 <8;
А1B5: u1 + v5 = 0 + 2 = 2> 1;
А2B1: u2 + v1 = -1 + 1 = 0 <2;
А2B4: u2 + v4 = -1 + 1 = 0 <4;
А2B5: u2 + v5 = -1 + 2 = 1 = 1;
А3B1: u3 + v1 = 1 + 1 = 2 <5;
А3B2: u3 + v2 = 1 + 4 = 5> 1;
А4B1: u4 + v1 = -2 + 1 = -1 <0;
А4B2: u4 + v2 = -2 + 4 = 2> 0;
А4B3: u4 + v3 = -2 + 2 = 0 = 0;
А4B4: u4 + v4 = -2 + 1 = -1 <0. br/>
Опорний план не є оптимальним, тому что існують ОЦІНКИ вільніх клітін для якіх ui + vi> cij
А1B5: u1 + v5 = 0 + 2 = 2> 1
А3B2: u3 + v2 = 1 + 4 = 5> 1;
А4B2: u4 + v2 = -2 + 4 = 2> 0. br/>
Тому від нього звітність, перейти до іншого плану, змінівші співвідношення заповненості и порожніх клітінок табліці.Вібіраємо Максимально оцінку Вільної Клітини (А3B2): 1
ставімие в ній знак В«+В». Для визначення клітінкі, что звільняється, будуємо цикл, починаючі з клітінкі А3B2, та позначаємо вершини циклу почергово знаками В«-В» и В«+В». Тепер звітність, перемістіті продукцію в межах побудованого циклу. Для цього у порожню клітинку А3B2 переносимо менше з чисел хij, Які розміщені в клітінках Зі знаком В«-В». Одночасно це самє число хij додаємо до відповідніх чисел, что розміщені в клітінках Зі знаком В«+В», та віднімаємо від чисел, что розміщені в клітінках, позначені знаком В«-В».
У даним разі, тоб. Виконано перерозподіл перевезень ПРОДУКЦІЇ згідно Із записання правилами, дістанемо Такі Нові значення: для клітінкі А3B3 - 50 од. ПРОДУКЦІЇ, а для А2B2 - звільняється и в новій табліці буде порожнє, а для А3B2 - (0 + 50) = 50 од. Клітінка А2B3 - 100 + 50 = 150. УСІ Другие заповнені клітінкі Першої табліці, Які не входили до циклу, перепісуємо у другу таблицю без змін. Кількість заповненості клітінок у новій табліці такоже має відповідаті умові невіродженості планом, тоб дорівнюваті (n + m - 1).
Отже, інших опорних план транспортної задачі матіме такий вигляд
Ai
Bj
ui
b1 = 120
b2 = 130
b3 = 200
b4...
