Пусть X=||xij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим
xi,n+1 = ai – ( xi1 +...+ xin ), i=1...,m
xm+1,j = bj – ( x1j +...+ xmj ), j=1...,n.
Пометим
w = x1,n+1 +...+ xm,n+1 = xm+1,1 +...+ xm+1,n.
Если w=0, то x — выходной ДБР.
Если w>0, то исходная ТЗ расширяется за счет фиктивных пунктов производства Pm+1 и потребления Qn+1 с am+1 = bn+1 = w, где
сі,n+1 = M, ri,n+1 = ¥, i=1...,m
cm+1,j = M, rm+1,j = ¥, j=1...,n
cm+1,n+1 = 0, rm+1,n+1 = ¥,
M — достаточно большое положительное число ¥ — бесконечность.
Нераспределенные на первом этапе остатки продукта (как по объемам производства, так и по объемам потребления) распределяются по фиктивным пунктам Pm+1 и Qn+1. Соответствующие заполненные клеточки считаются базисными (поскольку пропускные способности соответствующих им коммуникаций неограниченны) и присоединяются к совокупности базисных клеточек заполненных на первом этапе. Если после этого общее количество базисных клеточек не равное (m+1)+(n+1)–1, то множество базисных клеточек дополняют к этому числу за счет незаполненных клеточек или заполненных к пропускной способности, но так, чтобы расширенное множество базисных клеточек не содержало циклов.
Расширенная ТЗ Решается методом потенциалов.
Если в оптимальном решении x*m+1,n+1=w, то, отбрасывая фиктивные пункты, получим выходной ДБР, иначе ТЗО не имеет решений.