Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых (Решение → 11798)

Заказ №38709

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 5; 0 + v2 = 5; v2 = 5 u3 + v2 = 3; 5 + u3 = 3; u3 = -2 u1 + v3 = 5; 0 + v3 = 5; v3 = 5 u1 + v4 = 10; 0 + v4 = 10; v4 = 10 u2 + v4 = 15; 10 + u2 = 15; u2 = 5 u2 + v1 = 5; 5 + v1 = 5; v1 = 0 u1 + v5 = 7; 0 + v5 = 7; v5 = 7

Решение:

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (2;2): 5 + 5 > 5; ∆22 = 5 + 5 - 5 = 5 > 0 (2;3): 5 + 5 > 7; ∆23 = 5 + 5 - 7 = 3 > 0 (2;5): 5 + 7 > 9; ∆25 = 5 + 7 - 9 = 3 > 0 (3;4): -2 + 10 > 7; ∆34 = -2 + 10 - 7 = 1 > 0 max(5,3,3,1) = 5 Выбираем максимальную оценку свободной клетки (2;2): 5 Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»