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

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 аналогично метода наименьшего элемента. В методе потенциалов проверяется выполнение неравенства