Этап 1. На этом этапе производится исследование плана

на оптимальность. Обозначим через

совокупность

- существующих элементов матрицы С, т.е. таких

, которым соответствуют

, и определим величины

(предварительные потенциалы), удовлетворяющие системе уравнений

для всех

. (1.3)
В силу предположения о невырожденности исследуемой задачи любые два пункта

,

можно соединить маршрутом, состоящим из основных коммуникаций плана

. Далее, из опорности плана

вытекает, что отмеченный маршрут строится однозначно. Поэтому решение системы (1.3) осуществляется предельно просто.
Зададимся значением одной из неизвестных систем (1.3), например положим

. Допустим, что пункт

снабжает в соответствии с планом

пункты

. Тогда из соответствующих уравнений системы (1.3) определяем

.
Далее аналогичным способом определяем значения

для тех

, которые снабжают один из пунктов

. Например, если

снабжает пункт

, то

.
Затем определяются

для

, снабжающихся за счет пунктов

с уже вычисленными значениями

, и т.д. Таким образом, задавшись произвольными значениями

, мы легко определим

,

для всех пунктов

,

, которые можно соединить с

, маршрутами из основных коммуникаций плана

. Но, как было отмечено, подобным маршрутом могут быть соединены любые два пункта рассматриваемой задачи и притом единственным образом. Следовательно, при заданном

величины

,

определяются однозначно для всех пунктов задачи T. Нетрудно усмотреть, что если бы мы задались произвольным значением любой из величин

или

, то получившиеся в результате числа

отличались бы от

,

, вычисленных в предположении

, на некоторую постоянную. Отсюда, в частности, следует, что величина

определяется однозначно для любых i, j.
Если предварительные потенциалы

,

таковы, что для любой пары i, j имеет место неравенство

,
то функция W, определяемая условиями

- потенциал задачи T и, следовательно,

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

,
то план

не оптимален. Необходим переход к этапу 2, на котором этот план будет улучшен.
Этап 2. Вычислим уклонения

(

).
По условию среди чисел

имеются отрицательные. Определим пару индексов

из условия

.
Соединим пункты

,

маршрутом из основных коммуникаций плана

. Пусть построенный маршрут проходит последовательно через пункты

Рассмотрим перевозки по тем коммуникациям маршрута, которые при движении от

к

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

. Таким образом,

.
Введем в план

следующие изменения: величины перевозок из

в

,

, увеличим на

. Кроме того введем новую перевозку между пунктами

,

, равную

. Очевидно, полученная совокупность перевозок является планом исследуемой транспортной задачи. Действительно, все перевозки этой совокупности в силу определения числа

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

,

. В соответствии с новой совокупностью перевозок количества продуктов, перевозимого из

в

, уменьшается на

и одновременно на эту же величину увеличивается грузопоток из

в

.