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

1.Для всех базисных клеток создать систему уравнений вида .

Выбрать переменную U_i или V_j, которой соответствует наибольшее количество занятых клеток, приравнять её к нулю, решить систему уравнений относительно U_i и V_j и найти эти значения.

2.Для всех свободных клеток составить и проверить выполнение неравенств:

Условия оптимальности: если для всех свободных клеток выполняется это неравенство, то тогда найден оптимальный план.

Если хотя бы для одной клетки не выполняется это неравенство, то необходимо улучшить опорный план с помощью коэффициента перераспределения W.

3.Находим клетку, где сильнее всего не выполняется неравенство. Если таких клеток несколько, то выбирается любая. В эту клетку ставим W со знаком «+».

4.Построить контур перераспределения груза, начиная с выбранной клетки, исходя из следующих правил:

-В строке и столбце должно быть четное число W;

-Контур меняет направление только в базисных клетках;

-Коэффициент W меняет свой знак с «+» на «-» поочередно в углах контура.

5.После построения контура отметить, в каких базисных клетках коэффициент W стоит с отрицательным знаком. Из этих клеток найти клетку с наименьшим значением перевозки, коэффициент W будет равен перевозке в выбранной клетке.

6.Найти новый план, перераспределив найденное значение W по контуру с учетом знаков «+» и «-», прибавляя или уменьшая стоящую в клетке перевозку.

7.Проверить новый план в соответствии в п.2, если неравенства для свободных клеток выполняются, значит найденный план оптимален.

Если в математической модели целевая функция прямой задачи на максимум (Z_max), то задача решается методом максимального элемента. т.е. грузоперевозка (X_ij) распределяется при составлении опорного плана с учетом наибольшего значения C_ij аналогично алгоритма метода наименьшего элемента. В методе потенциалов проверяется выполнение неравенства .