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

Заказ №38709

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

Решение:

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 5∙16 + 5∙14 + 10∙4 + 7∙16 + 5∙25 + 5∙5 + 7∙20 = 592