імаємо 2 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
1234Запасы11[4]24[2]36243[6]8[2]583276[2]3[8]104000[2]02Потребности4688
. Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi=cij, вважаючи, що u1=0.
Таблиця
u1=1u2=- 1u3=4u4=1v1=01 [4] 24 [2] 3v2=443 [6] 8 [2] 5v3=2276 [2] 3 [8] v4=-4000 [2] 0
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi> cij
(2; 1): 4 + 1> 4
(3; 1): 2 + 1> 2
Вибираємо максимальну оцінку вільної клітини (2; 1): 4
Для цього в перспективну клітку (2; 1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-» . Цикл наведено в таблиці.
1234Запасы11[4][-]24[2][+]3624[+]3[6]8[2][-]583276[2]3[8]104000[2]02Потребности4688
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у=min (2, 3)=2. Додаємо 2 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 2 з Хij, що стоять в мінусових клітинах.
1234Запасы11[2]24[4]3624[2]3[6]8583276[2]3[8]104000[2]02Потребности4688 4. Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi=cij, вважаючи, що u1=0.
u1=1u2=0u3=4u4=1v1=01 [2] 24 [4] 3v2=34 [2] 3 [6] 85v3=2276 [2] 3 [8] v4=- 4000 [2] 0
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi> cij
(3; 1): 2 + 1> 2
Вибираємо максимальну оцінку вільної клітини (3; 1): 2
Для цього в перспективну клітку (3; 1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-» . Цикл наведено в таблиці.
1234Запасы11[2][-]24[4][+]3624[2]3[6]85832[+]76[2][-]3[8]104000[2]02Потребности4688
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у=min (1, 1)=2. Додаємо 2 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 2 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
1234Запасы1124[6]3624[2]3[6]85832[2]76[0]3[8]104000[2]02Потребности4688
. Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi=cij, вважаючи, що u1=0.
u1=0u2=- 1u3=4u4=1v1=0124 [6] 3v2=44 [2] 3 [6] 85v3=22 [2] 763 [8] v4=- 4000 [2] 0
Опорний план є оптимальним.
Витрати складуть:
F (x)=4 * 6 + 4 * 2 + 3 * 6 + 2 * 2 + 3 * 8 + 0 * 2=78
5. Блок-схема і вирішення завдання за допомогою програми Excel
Рішення поставленої задачі
Складаємо матрицю коефіцієнтів
WXYZА14196000В92283000С617330001500250027003300
Додаємо перетворення - вводимо стовпець фіктивного постачальника
