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

118

В новом опорном плане вычислим потенциалы занятых клеток и оценки незанятых клеток. Положим (т.к. во втором столбце наибольшее число заполненных клеток).

Условия оптимальности () нарушаются в клетках (4, 4). Поэтому найденный опорный план не является оптимальным.

Следовательно, эта клетка должна быть загружена некоторым объемом поставок. Включим переменную в число базисных.

Пометим ее знаком «х» и построим цикл, который начинается и заканчивается в этой клетке (4, 4), а вершины цикла располагаются в занятых клетках.

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

Величина поставок, перемещаемая в клетку (4, 4), равна минимуму из поставок со знаком «-», т.е.

.

Величина вычитается из объемов поставок клеток со знаком «-» и прибавляется к объемам поставок клеток со знаком «+».

В результате получаем новый опорный план, затраты на реализацию которого составляют:

5