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

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

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

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

4) составляем систему уравнений потенциалов по заполненным клеткам. Находим одно из ее решений при u₁=0;

5) Строим оценочную матрицу C₀=|| C_ij- u_i - v_j ||

6) Проверяем критерий оптимальности. Если в оценочной матрице нет отрицательных значений, то план оптимален (критерий оптимальности). Решение закончено: ответ дается в виде плана перевозок последней таблицы и значения f.

7) Если критерий оптимальности не выполняется, то переходим к выполнению последовательных итераций метода потенциалов, связанных с преобразованием двух матриц C₀ и X₀:

8) Для перехода к следующей таблице(плану):

а) В оценочной матрице выбираем отрицательный элемент. Если таких клеток несколько, то выбираем с наименьшим значением. Свободная клетка rk, соответствующая этому элементу, подлежит замещению. Элемент С_rk называется особо выделенным

б) В решении X₀ составляем цикл пересчета для этой клетки rk и расставляем знаки «+», «-» в вершинах цикла путем их чередования, приписывая пустой клетке «+»;

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

г) составляем новую таблицу, добавляя в плюсовые клетки и отнимая из минусовых клеток цикла. Получаем новое решение X₁

д) Подчеркиваем в оценочной матрице C₀ элементы, соответствующие занятым в решении X₁ клеткам. При этом всегда подчеркиваются нули и один ненулевой элемент С_rk, выделенный в пункте а)

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

ж) Прибавляя к выделенным строкам |С_rk |, а из выделенных столбцов вычитая |С_rk|, получим новую оценочную матрицуС₁, у которой на всех подчеркнутых местах окажутся нули. Эта матрица будет оценочной для X₁

9) Переходим к п. 6

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