
.
Кроме того, все ее

- существенные элементы – нули. Действительно, после вычитания

из

- й строки

элемент

обращается в нуль, а все элементы

становятся равными -

. После прибавления

к столбцам элементов

эти элементы обращаются в нуль, а элементы

принимают значения

. Заметим, что поскольку линии

отмечаются не более одного раза, элементы

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

величину

, обращаем последовательно в нуль элементы

,

и т.д.
После l – 1 шагов все ненулевые

- существенные элементы

оказываются принадлежащими

. Пусть l – нечетное (четное) число. Поскольку

- пустое множество, все

- существенные элементы матрицы, полученной после вычитания (прибавления) величины

из строк (к столбцам) элементов

, равны нулю. Итак, величины

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

.
Следовательно,

- предварительные потенциалы, соответствующие плану

, а

.
Как нетрудно заметить, описанное правило отыскания предварительных потенциалов

,

или, что то же самое, матрицы

, базируется на определении разностей

.
Предварительные потенциалы, отвечающие плану

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

).
Если все элементы матрицы

неотрицательны,

- искомое решение. Если же среди величин

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

. Основой этапа является процесс составления цепочки из положительных элементов этого плана. Выберем наименьший элемент матрицы

, расположенный, скажем, на пересечении

- й строки и

- го столбца, и обозначим его через

. По условию

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

, замыкающейся на элементе

(очевидно,

=0). Соединим стрелками

со всеми положительными элементами его строки, совокупность которых обозначим через

. Затем каждый из элементов

соединим стрелками со всеми положительными элементами, расположенными в его столбце. Совокупность всех таких элементов обозначим через

. Процесс образования множеств

продолжается до тех пор, пока при некотором p (p – нечетное число) среди столбцов, содержащих элементы

, обнаружится столбец с номером

. Заметим, что в силу опорности плана

множества

, не пересекаются, ибо в противном случае существовала бы замкнутая цепочка из ненулевых перевозок плана

. Это обстоятельство, а также то, что любые два пункта невырожденной задачи T могут быть соединены коммуникациями с ненулевыми перевозками, служит доказательством существования введенного выше числа

. Теперь уже нетрудно образовать искомую цепочку. От элемента

перейдем по столбцу к элементу

. От

по строке перейдем к соединенному с ним стрелкой элементу

и т.д. Двигаясь таким образом вдоль намеченных стрелок по строкам и столбцам матрицы

, получим в конце концов последовательность положительных элементов этой матрицы вида

, (4.1)
образующую цепочку, которая замыкается на элементе

.
Построение цепочки (4.1) можно осуществить также с помощью метода вычеркивания строк. Для этого вводится множество Г, состоящее из положительных элементов матрицы

и ее элемента

.
Из матрицы

вычеркиваются строки, содержащие менее двух элементов множества Г. Затем из оставшейся части

вычеркиваются столбцы, в которых содержится менее двух элементов Г. После этого снова возвращаются к строкам, затем к столбцам и т.д.
Элементы матрицы

, оставшиеся после процесса вычеркивания, составляют искомую цепочку. Построив цепочку (4.1), легко сформировать новый план

.
Обозначим совокупность пар индексов

,

через

, а множество пар индексов вида

,

через

. Положим