Алгоритм решения транспортной задачи методом потенциалов.
1. Отыскиваем исходный опорный план перевозок (к примеру, методом минимального элемента). Переход к пункту 2.
2. Строим систему потенциалов. Для этого для каждой базисной
клетки (p,q) записываем уравнение αp+βq=cpq. Получается
система m+n–1 уравнений с m+n неизвестными потенциалами. Один из
потенциалов полагаем равным 0 и находим из системы остальные
потенциалы. Переход к пункту 3.
3. Для каждой свободной клетки (i, j) вычисляем псевдостоимость 
. Если для всех свободных клеток 
, то план оптимален, и алгоритм останавливается. Если же найдется свободная клетка (i, j), для которой 
, то переход к пункту 4.
4. Строим цикл пересчета, проходящий через клетку (i, j),
делаем по нему максимально допустимый сдвиг, получив, таким образом,
новый опорный план. Переход к пункту 2.
Пример. Исходные данные задачи приведены в таблице 5.9.
Методом минимального элемента находим исходный опорный план перевозок и записываем его в ту же таблицу.
Таблица 5.9
| Пн По | В1 | В2 | В3 | В4 | Запасы | αi |
| А1 |  2
15
| 1 4 | 5 7 | 11 6 | ||
| А2 | 5 7 | 4 18 | 8 | 14 9 | ||
| А3 | 3 4 | 2 11 | 6 7 | 12 13 | ||
| Потребности | 70=70 | |||||
| βj |
Для определения потенциалов решим следующую систему:
Положим α1=0. Тогда β1=2; α2=3; β2=1; β3=5; α3=1; β4=11. Найденные потенциалы вносим в таблицу 5.9.
Вычисляем псевдостоимости для свободных клеток и проставляем их в левые верхние углы клеток. Выбираем свободную клетку, в которой ; например, выберем клетку (1,4). Строим цикл пересчета, проходящий через эту клетку, и произведем по нему максимально допустимый сдвиг h = 10 (в отрицательных клетках наименьшей перевозкой является х23=10). После сдвига клетка (2,3) становится свободной, а клетка (1,4) - базисной. Получаем новый опорный план, записанный в таблице 5.10.
Таблица 5.10
| Пн По | В1 | В2 | В3 | В4 | Запасы | αi | ||||
| А1 |
| 1 4 | 0 7 |
| ||||||
| А2 | 5 17 | 4 18 | 3 8 | 9 9 | ||||||
| А3 |
 8 7
| 7 11 | 6 17 |
3 | ||||||
| Потребности | 70=70 | |||||||||
| βj |
5Вновь строим систему потенциалов, рассчитываем псевдостоимости, строим цикл пересчета, проходящий через клетку (3,1), делаем по нему максимально допустимый сдвиг величины h=3.
Таблица 5.11
| Пн По | В1 | В2 | В3 | В4 | Запасы | αi |
| А1 | 2 2 | 1 4 | -4 7 | 6 | ||
| А2 | 5 17 | 4 18 | -1 8 | 9 9 | ||
| А3 | 4 | 2 11 | 6 17 | 8 12 | ||
| Потребности | 70=70 | |||||
| βj | -4 |
После сдвига получим опорный план, записанный в таблице 5.11. Построив систему потенциалов и рассчитав псевдостоимости, видим, что для всех свободных клеток . Поэтому опорный план оптимален.
Итак, оптимальный план имеет следующий вид: х11=2; х14=13; х21=17; х22=18; х31=3; х33=17.
При этом fmln = 2•2 + 13•6 + 17•5 + 18•4 + 3•4 + 17•6 =353