Транспортная задача

4. Проверим оптимальность  опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 u₁ + v₁ = 13; 0 + v₁ = 13; v₁ = 13

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₃ + v₄ = 11; 3 + u₃ = 11; u₃ = 8

u₃ + v₂ = 4; 8 + v₂ = 4; v₂ = -4

u₃ + v₃ = 10; 8 + v₃ = 10; v₃ = 2

u₂ + v₃ = 6; 2 + u₂ = 6; u₂ = 4

u₁ + v₅ = 18; 0 + v₅ = 18; v₅ = 18

 Опорный план  не является оптимальным, так  как существуют оценки свободных  клеток, для которых u_i + v_i > c_ij

(2;1): 4 + 13 > 7; ∆₂₁ = 4 + 13 - 7 = 10

(2;5): 4 + 18 > 9; ∆₂₅ = 4 + 18 - 9 = 13

(3;1): 8 + 13 > 16; ∆₃₁ = 8 + 13 - 16 = 5

 max(10,13,5) = 13

 Выбираем максимальную оценку свободной клетки (2;5): 9

 Для этого  в перспективную клетку (2;5) поставим  знак «+», а в остальных вершинах  многоугольника чередующиеся знаки  «-», «+», «-». Цикл приведен в таблице.

 Из грузов  х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

4. Проверим оптимальность  опорного плана. Найдем потенциалы  u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 u₁ + v₁ = 13; 0 + v₁ = 13; v₁ = 13

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₁ + v₅ = 18; 0 + v₅ = 18; v₅ = 18

u₂ + v₅ = 9; 18 + u₂ = 9; u₂ = -9

u₂ + v₃ = 6; -9 + v₃ = 6; v₃ = 15

u₃ + v₃ = 10; 15 + u₃ = 10; u₃ = -5

u₃ + v₂ = 4; -5 + v₂ = 4; v₂ = 9

 Опорный план  является оптимальным, так все  оценки свободных клеток удовлетворяют  условию u_i + v_i <= c_ij.

 Минимальные  затраты составят:

 F(x) = 13*20 + 3*13 + 18*20 + 6*10 + 9*7 + 4*20 + 10*10  = 962