Причем линии цикла пересекаются в узловых ячейках под прямым углом
и количество ячеек цикла – четное.
Отыскивая выгодные клетки с отрицательной ценой, необходимо
определить «дешевую» свободную клетку, для нее найти цикл, вычислить его
цену и, если она будет отрицательной, перенести по этому циклу столько
единиц груза, сколько будет возможно.
При этом данная свободная клетка становится базисной, а какая-то из
бывших базисных – свободной.
Таким образом, разыскивая в транспортной таблице свободные клетки с
отрицательной ценой цикла и перебрасывая по этому циклу наибольшее
возможное количество груза, будем все уменьшать и уменьшать стоимость
перевозок, пока не придем (за конечное число шагов) к оптимальному плану.
Для такого плана уже не останется ни одной свободной клетки с
отрицательной ценой цикла. Это - признак того, что оптимальное решение
найдено.
В теории линейного программирования существуют способы,
позволяющие автоматически выделять свободные клетки с отрицательной
ценой цикла. Это «Метод потенциалов».
Метод потенциалов. Предварительно строятся опорные планы тремя
методами, предложенными выше, затем для дальнейшей оптимизации
выбирается опорный план, у которого наименьшее значение целевой функции
(таким образом можно сократить число шагов для достижения Z
опт
)
Оптимизация производится с помощью симплекс-коэффициентов U
i
,V
j
.
Симплекс-коэффициенты характеризуются тем, что, если умножить все
горизонтальные ограничивающие уравнения соответственно на U
1
, U
2
,…, U
n
, а
вертикальные на V
1
, V
2
, … , V
m
и затем все эти уравнения сложить и вычесть
их сумму из уравнения минимизируемой функции, то новые значения
коэффициентов C
ij
для всех базисных неизвестных окажутся равными нулю, т.е.
базисные неизвестные будут исключены из уравнения минимизируемой