Прежде всего введем справедливость признака оптимальности, т.е. если 
, то план Х k - оптимален.
Действительно, в силу построения Х k, если 
, то 
(эти нули называют существенными). Поэтому план Х k оказывается оптимальным для задачи с матрицей С k, так как
. (3.3.10)
Но матрица С k получена эквивалентными преобразованиями из исходной матрицы С. Докажем, что Х k - оптимален и для задачи с матрицей С. Матрицы С и С k как эквивалентные связаны соотношениями
для всех (i, j) (3.3.11)
Тогда значение целевой функции для плана Х k при матрице С будет равно
(3.3.12)
Но так как 
, то
і. 
(3.3.13)
Подставляя (3.3.13) в (3.3.12), получим с учетом (3.3.10)
. (3.3.14)
Но 
и не зависит от плана Х k, поэтому план Х k оптимален и для исходной задачи с матрицей С.
Перейдем теперь к обоснованию алгоритма.
Предварительный этап. На предварительном этапе строят матрицу Х k элементы которой удовлетворяют условиям
, (3.3.15)
. (3.3.16)
Если все условия (3.3.15), (3.3.16) выполняются как строгие равенства, то план Х 0 - оптимален, согласно только что доказанному.
Первый этап. Цель первого этапа состоит в отыскании такого невыделенного нуля 
, для которого 
. Предположим, что такой нуль найден, и мы перешли ко второму этапу.
Второй этап. Он состоит в построении цепочки из нулей со штрихами и звездочками и переходе к Х k+ 1. Пусть цепочка имеет вид:
. (3.3.17)
Элементы матрицы Х k+ 1 вычисляют по рекуррентным формулами
где 
(3.3.18)
Так как в каждой строке и столбце имеется как 0', так и 0*, либо они оба отсутствуют, за исключением строки 
и столбца 
, где имеется лишь 0', то
(3.3.19)
(3.3.20)
Поэтому, если матрица Х k удовлетворяла ограничениям (3.3.15), (3.3.16), то и матрица Х k+ 1 будет им также удовлетворять.
Наконец, на основании соотношений (3.3.19), (3.3.20) получим
.
Третий этап. В соответствии с правилами перехода от С k к С ' k при выборе элемента h > 0 элементы невыделенных строк С k уменьшаются на величину h, появляются новые нули, и можно снова перейти к первому этапу. При этом по правилу выделения строк и столбцов все существенные нули С k останутся нулями и в матрице C ' k.
Пример 3.5. Найти решение транспортной задачи со следующими условиями:
Проверим условие баланса 
Предварительный этап. Вычитаем из элементов первого столбца 2, из второго - 3, из третьего -1, из четвертого -2. Приходим к матрице С1. Далее, вычитая минимальный элемент из элементов каждой строки, получаем матрицу С0:
Строим начальную матрицу перевозок
Невязки для столбцов d j = 0, 1, 9, 0, для строк d j = 4; 6; 0. Суммарная невязка
Первая итерация. Первый этап. Отмечаем знаком '+' сверху первый и четвертый столбцы, которым соответствуют нулевые невязки, а знаком 'х' слева первую и вторую строки, которым отвечают ненулевые невязки, черточкой сверху - существенные нули.
Просматриваем невыделенный второй столбец матрицы С0, находим в нем невыделенный нуль С32 = 0 и отмечаем его штрихом. Так как d3 = 0, то выделяем третью строку знаком '+'. Просматриваем третью строку относительно выделенных столбцов. Там существенных нулей нет. Поскольку в С0 больше не осталось невыделенных нулей (все нули расположены в выделенных строках или столбцах), то переходим к третьему этапу.
Третий этап. Среди элементов невыделенных строк и столбцов матрицы С0 находим минимальный элемент h = 1, прибавляем его ко всем элементам выделенных столбцов и вычитаем из всех элементов невыделенных строк. Получим матрицу С1.
Переходим к первому этапу.
Первый этап. Среди невыделенных столбцов находим нулевой элемент С22, который расположен в строке с ненулевой невязкой, а потому переходим ко второму этапу.
Второй этап. Цепочка состоит из одного элемента С22 = 0. Находим 
и прибавим q1 = 1 к элементу х1. Получим матрицу Х1.
Вторая итерация. Первый этап. В матрице С1 отмечаем знаком '+' первый, второй и четвертый столбцы, которым отвечают нулевые невязки. Находим в третьем столбце нуль С33 = 0 и отмечаем его штрихом.
Так как невязка в третьей строке равна нулю, то выделяем ее знаком '+'. Просматриваем эту строку, находим в ней существенный нуль С32, расположенный в выделенном столбце. Отмечаем его звездочкой и уничтожаем знак выделения второго столбца.
Далее просматриваем второй столбец и отыскиваем в нем невыделенный нуль С22. Так как невязка по строке d 2 > 0, то отметив этот нуль штрихом, переходим ко второму этапу.
Второй этап. Строим цепочку в матрице С1 вида 
, а затем аналогичную цепочку в матрице Х1.
В результате получаем матрицу Х2: q2 = min {5, 8, 9} = 5
Третья итерация. Первый этап. В матрице С2 отмечаем знаком '+' первый, второй и четвертый столбцы, которым соответствуют нулевые невязки. Находим нулевой элемент С33 в третьем столбце. Так как ему соответствует нулевая невязка в третьей строке, то отмечаем этот нуль штрихом. Далее, просматриваем третью строку, отыскиваем в ней существенный нуль С32 = 0, расположенный в выделенном втором столбце, отмечаем звездочкой этот нуль и уничтожаем знак выделения над вторым столбцом. Просматриваем второй столбец, находим в нем нулевой элемент С22 = 0 и отмечаем его штрихом, а вторую строку, где он лежит, знаком '+' (так как d 2 = 0).
Далее, просмотрев вторую строку, находим в ней существенный нуль С21 = 0 в выделенном первом столбце. Поэтому выделяем этот нуль звездочкой и уничтожаем знак '+' над первым столбцом.
h = min {4, 3, 2} = 2
На этом процесс выделения нулей заканчиваем. Так как больше выделенных нулей не имеется, то переходим к третьему этапу.
Третий этап. Находим минимальный невыделенный элемент в матрице С2 h = 2, вычитаем h из всех элементов невыделенных строк и прибавляем ко всем элементам выделенных столбцов (т.е. прибавляем к четвертому столбцу и вычитаем из первой строки). В результате получим матрицу С3, в которой появился новый невыделенный нуль (С 13). Переходим к первому этапу.
Первый этап. В матрице С3 находим невыделенный нуль С13. Так как d1 > 0, то переходим ко второму этапу.
Второй этап. Вся цепочка состоит из одного элемента 
. Поэтому q3 = min { d 1 = 4, d 2 = 4} = 4. Прибавим q3 к , получим матрицу X 3.
Так как D3 = 0, то Х 3 - оптимальный план. Соответствующее значение целевой функции Lорт = 
(сравните с результатами решения этой задачи методом потенциалов, см. пример 3.3).
