u 3 + v 4=3; 8 + u 3=3; u 3=- 5
v 1=1v 2=6v 3=1v 4=8v 5=0u 1=01 [1500] 41 [2700] 90 [1800] u 2=09228 [2800] 0 [200] u 3=- 561 [2500] 73 [500] 0 Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi> c ij
(1, 2): 0 + 6> 4; ? 12=0 + 6 - 4=2
(2, 2): 0 + 6> 2; ? 22=0 + 6 - 2=4 (2,4)=4
Вибираємо максимальну оцінку вільної клітини (2, 2): 2
Для цього в перспективну клітку (2; 2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
12345Запасы11[1500]41[2700]90[1800]6000292[+]28[2800][-]0[200]3000361[2500][-]73[500][+]03000Потребности15002500270033002000 Цикл наведено в таблиці (2,2; 2,4; 3,4; 3,2;).
З вантажів х ij що стоять в мінусових клітинах, вибираємо найменше, тобто у=min (3, 2)=2500. Додаємо 2500 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 2500 з Х ij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
12345Запасы11[1500]41[2700]90[1800]6000292[2500]28[300]0[200]300036173[3000]03000Потребности15002500270033002000
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких i + vi=c ij,
вважаючи, що u 1=0.
u 1 + v 1=1; 0 + v 1=1; v 1=1 1 + v 3=1; 0 + v 3=1; v 3=1 1 + v 5=0; 0 + v 5=0; v 5=0 2 + v 5=0; 0 + u 2=0; u 2=0 2 + v 2=2; 0 + v 2=2; v 2=2 | 2 + v 4=8; 0 + v 4=8; v 4=8
u 3 + v 4=3; 8 + u 3=3; u 3=- 5
v 1=1v 2=2v 3=1v 4=8v 5=0u 1=01 [1500] 41 [2700] 90 [1800] u 2=092 [2500] 28 [300] 0 [200] u 3=- 56173 [3000] 0
Опорний план є оптимальним, тому всі оцінки вільних клітин задовольняють умові ui + vi <= c ij.
Мінімальні витрати складуть: (x)=1 * 1500 + 1 * 2700 + 0 * 1800 + 2 * 2500 + 8 * 300 + 0 * 200 + 3 * 3000=20600
Перевіримо оптимальність знайденого плану по першій теоремі подвійності (в оптимальному рішенні значення цільових функцій прямої та двоїстих задач збігаються: F=G).=0 6000 + 0 3000 - 5 3000 + 1 1500 + 2 2500 + 1 2700 + 8 3300 + 0 2000=20600
Аналіз оптимального плану.
З 1-го складу необхідно вантаж направити в 1-й магазин (1500), в 3-й магазин (2700)
З 2-го складу необхідно вантаж направити в 2-й магазин (2500), в 4-й магазин (300)
З 3-го складу необхідно весь вантаж направити в 4-й магазин
На 1-му складі залишився незатребуваним вантаж у кількості 1800 од.
Оптимальний план є виродженим, так як базисна змінна x 15=0.
На 2-му складі залишився незатребуваним вантаж в кількості 200 од.
Оптимальний план є виродженим, так як базисна змінна x 25=0.
В ?????
Мені було поставлено завдання скласти програму для розрахунку початкового базису збалансованої транспортної задачі, де сумарні запаси постачальників рівні сумарним запитам споживачів.
...
