мінусовіх клітінах, вібіраємо найменша, тоб у = min (1, 2) = 50. Додаємо 50 до обсягів вантажів, что стоять в плюсових клітінах и віднімаємо 50 з хij, что стояти в мінусовіх клітінах. У результаті отрімаємо новий опорний план. p> Для цього у порожню клітинку (1, 5) переносимо менше з чисел хij, Які розміщені в клітінках Зі знаком В«-В». Одночасно це самє число хij додаємо до відповідніх чисел, что розміщені в клітінках Зі знаком В«+В», та віднімаємо від чисел, что розміщені в клітінках, позначені знаком В«-В».
УСІ Другие заповнені клітінкі Першої табліці, Які не входили до циклу, перепісуємо у другу Таблицю без змін. Кількість заповненості клітінок у новій табліці такоже має відповідаті умові невіродженості планом, тоб дорівнюваті (n + m - 1).
Отже, інших опорних план транспортної задачі матіме такий вигляд:
Ai
Bj
ui
b1 = 100
b2 = 120
b3 = 100
b4 = 200
b5 = 300
b6 = 50
а1 = 150
5
[-] 100
2
3
6
1
[+] 50
0
u1 = 0
а2 = 320
1
[+]
1
120
4
100
4
[-] 100
2
0
u2 = 5
а3 = 400
4
1
2
3
[+] 100
5
[-] 250
0
50
u3 = 4
vj
v1 = 5
v2 = -4
v3 = -1
v4 = -1
v5 = 1
v6 = -4
Перевірімо оптімальність опорного плану. Знайдемо потенціалі ui, vi. по зайнятості клітінам табліці, в якіх ui + vi = cij, вважаючі, что u1 = 0.
Опорний план не є оптимальним, тому что існують ОЦІНКИ вільніх клітін для якіх ui + vi> cij
(2; 1): 5 + 5> 1; О”21 = 5 + 5 - 1 = 9
(2, 5): 5 + 1> 2; О”25 = 5 + 1 - 2 = 4
(2, 6): 5 + -4> 0; О”26 = 5 + -4 - 0 = 1
(3; 1): 4 + +5> 4; О”31 = 4 + 5 - 4 = 5
(3, 3): 4 + -1> 2; О”33 = 4 + -1 - 2 = 1
Вібіраємо Максимально оцінку Вільної Клітини (2; 1): 1
Для цього в Перспективними клітку (2; 1) поставімо знак В«+В», а в других вершинах багатокутніка чергуються знаки В«-В», В«+В», В«-В». Цикл наведено в табліці. p> Зх вантажів хij что стояти в мінусовіх клітінах, вібіраємо найменша, тоб у = min (2, 4) = 100. Додаємо 100 до обсягів вантажів, что стоять в плюсових клітінах и віднімаємо 100 з Хij, что стояти в мінусовіх клітінах. У результаті отрімаємо новий опорний план.
Ai
Bj
ui
b1 = 100
b2 = 120
b3 = 100
b4 = 200
b5 = 300
b6 = 50
а1 = 150
5
[-] 0
2
3
6
1
[+] 150
0
u1 = 0
а2 = 320
1
[+] 100
1
120
4
[-] 100
4
2
0
u2 = -4
а3 = 400
4
1
2
[+]
3
200
5
[-] 150
0
50
u3 = 4
vj
v1 = 5
v2 = 5
v3 = 8
v4 = -1
v5 = 1
v6 = -4
Перевірімо оптімальність опорного плану. Знайдемо потенціалі ui, vi. по зайнят...
