Новый ДБР.

Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки Dij. Пометим такую клеточку через (i₀,j₀).

Пусть клеточка (i₀,j₀), для которой

Находится цикл, что образуется этими клеточками. Цикл разбивается на положительный (C+) и отрицательный (C–) полуциклы, клеточки которых чергуються одна из одною, причем клеточка (i₀,j₀) относится к положительному полцикла. Вычисляются величины

q1 = min{x_ij} по C–,

q2= min{r_ij – x_ij} по C+

q = min{q1q2}.

Увеличивают на значение q перевозка x_ij в клеточках полцикла C+ и уменьшают их на то же значение в клеточках C–.

Для клеточки (i₀,j₀) такой, что отмена заключается в том, что она относится к отрицательному полцикла.

В результате выполнения указанных процедур клеточка (i0,j0) вводится к множеству базисных, а клеточка, связанная с q, становится небазисной. Если q достигается на клеточке (i₀,j₀), то множество базисных клеточек не изменяется после перераспределения перевозок вдоль цикла на постоянную q и новый ДБР будет иметь ту же самую систему потенциалов и те же самые оценки, что и предыдущий. Поэтому в этом случае после вычисления нового ДБР непосредственно переходят к проверке его на оптимум.