Алгоритм метода потенциалов.

1. проверяется тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой;

2. находится опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшей стоимости;

3. проверяем план (таблицу) на удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью «0»;

4. для опорного плана определяются потенциалы u_i и v_j, соответствующие базисным клеткам, по условию:

u_i + v_j = c_ij

Таких уравнений будет m + n - 1, а переменных будет m + n. Для их определения одну из переменных полагают равной любому постоянному значению. Обычно принимают u₁ = 0.

После этого для небазисных клеток опорного плана определяются оценки ,

где

При этом если £0, то опорный план оптимален, если же среди окажется хотя бы один положительный элемент, то опорный план можно улучшить.

Улучшение опорного плана осуществляется путем целенаправленного переноса из клетки в клетку транспортной таблицы отдельных перевозок без нарушения баланса по некоторому замкнутому циклу.

Циклом транспортной таблицы называется последовательное соединение замкнутой ломаной линией некоторых клеток, расположенных в одном ряду (строке, столбце), причем число клеток в одном ряду должно быть равно двум.

Каждый цикл имеет четное число вершин, одна из которых в клетке с небазисной переменной, другие вершины в клетках с базисными переменными. Клетки отмечаются знаком «+», если перевозки в данной клетке увеличиваются и знаком «–» в противном случае. Цикл начинается и заканчивается на выбранной небазисной переменной и отмечается знаком «+». Далее знаки чередуются.

Количество единиц продукта, перемещаемого из клетки в клетку по циклу, постоянно, поэтому сумма перевозок в каждой строке и в каждом столбце остаются неизменными. Стоимость всего плана изменяется на цену цикла.

Цена цикла – это стоимость перевозки единицы продукта по циклу с учетом знаков вершин.

Улучшение опорного плана осуществляется путем нахождения цикла с отрицательной ценой.

5. Если критерий оптимальности не выполняется, то переходим к следующему шагу. Для этого:

а) в качестве начальной небазисной переменной принимается та, у которой оценка имеет максимальное значение;

б) составляется цикл пересчета;

в) находится число перерасчета по циклу: число X=min{X_ij}, где X_ij - числа в заполненных клетках со знаком «-»;

г) составляется новая таблица, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла;

6. Возвращаются к пункту 3 и т.д.

7. Через конечное число шагов (циклов) обязательно приходят к ответу, так как транспортная задача всегда имеет решение.