Решение транспортной задачи методом потенциалов
Для решения транспортной задачи используют метод потенциалов (модифицированный распределительный метод).
Потенциалами называются числа uí и vj, удовлетворяющие следующим условиям оптимальности плана перевозок.
1) Для всех занятых клеток (xij > 0) должно выполняться равенство
vj – ui = cij.
2) Для всех свободных клеток (xij = 0) справедливо соотношение vj – ui
≤ cij.
Здесь ui – потенциал i-й строки,
vj – потенциал j-го столбца.
Для определения потенциалов составляют систему m+n–1 линейно независимых уравнений с количеством неизвестных m + n. Так как уравнений на одно меньше, чем неизвестных, то система неопределенна и имеет бесконечное множество решений. Поэтому одно неизвестное определяют произвольно. Обычно полагают u1 = 0. Тогда можно определить все остальные значения потенциалов.
Характеристикой или оценкой свободной клетки (i, j) называют величину wij, которая определяется по формуле:
wij = cij – (vj – ui).
Критерий оптимальностипри решении задачи на минимум целевой функции заключается в следующем. Если оценки базисных клеток равны нулю, а оценки свободных клеток неотрицательны.
wij = 0, если (i, j) – занятая клетка;
wij ≥ 0, если (i, j) – свободная клетка,
то план перевозок 
является оптимальным.
Если хотя бы одна свободная клетка имеет отрицательную оценку (при условии, что все базисные оценки равны нулю), то рассматриваемый опорный план не является оптимальным. Он может быть улучшен путем введения клетки с наибольшей по абсолютной величине отрицательной оценкой в состав базисных клеток. Такая клетка называется перспективной и обозначается (i, j)*.
При решении задачи на максимум целевой функции признаком оптимальности является отсутствие в таблице положительных характеристик: все
wij ≤ 0.
Последовательное улучшение неоптимального опорного плана состоит в перераспределении грузоперевозок. После каждого шага перераспределения план снова проверяется на оптимальность. Вычисления проводят до тех пор, пока не будет получен оптимальный вариант плана.