Алгоритм решения транспортной задачи

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

1.      Найти исходное опорное решение.

2.      Найти потенциалы из системы уравнений u_i + v_j = c_ij, справедливых для занятых клеток. Так как занятых клеток m+n-1, то система будет состоять из m+n-1 уравнений с m+n неизвестными. Эта система имеет бесконечное множество решений. Для того чтобы найти частное решение системы, придадим одному из неизвестных любое числовое значение, например u₁=0, и найдем значения остальных.

Потенциалы u_i и v_j записываем в столбце и в строке, которые добавляем к таблице.

3.      Для всех свободных клеток найти оценки D_ij= u_i + v_j - c_ij.

4.      Проверка решения на оптимальность.

Если все D_ij£0, то найденное решение оптимально.

Если среди оценок есть хотя бы одно положительное число, то найденное решение не оптимально и его надо улучшить.

5.      Выбирается клетка с наибольшей положительной оценкой, и соответствующую переменную вводят в базис, для этого строят цикл для этой клетки. Даем поставку в эту клетку l. Тогда нарушится баланс и в строке, и в столбце, следовательно, нужно отнимать l от одной из поставок данного столбца и строки до тех пор, пока цикл не замкнется.

Свойства цикла:

1)     в цикле всего одна свободная клетка, в которую пишем +l;

2)     если строка или столбец участвует в цикле, то двумя клетками +l и -l;

3)     число клеток цикла четно.

Можно доказать, что для любой свободной клетки можно построить единственный цикл.

6.      Определяется l так, чтобы одна из занятых клеток освободилась и чтобы оставшиеся поставки x_ij ³0, т.е. l=min íx_ijý для четных клеток цикла.

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

8.      Переход в п. 2.