Метод потенциалов

По найденной системе потенциалов вычислим оценки незанятых клеток по формуле:

Условия оптимальности () нарушаются в клетках (1, 3), (1, 5), (3, 2), (3, 3), (3, 5). Поэтому найденный опорный план не является оптимальным. Следовательно, одна из этих клеток должна быть загружена некоторым объемом поставок. В первую очередь заполняется та клетка, для которой достигается максимум среди : . Значит, включим переменную в число базисных. Пометим ее знаком «х» и построим цикл, который начинается и заканчивается в этой клетке (3, 2), а вершины цикла располагаются в занятых клетках.

(3, 2) - (3, 4) - (1, 4) - (1, 2).

Клетка (3, 2) помечается знаком «+», затем клетки, находящиеся в вершинах цикла отмечаются чередующимися знаками «-» и «+». Величина поставок, перемещаемая в клетку (3, 2), равна минимуму из поставок со знаком «-», т.е.

Величина вычитается из объемов поставок клеток со знаком «-» и прибавляется к объемам поставок клеток со знаком «+». В результате получаем новый опорный план, затраты на реализацию которого составляют