Выходной ДБР ТЗО. II этап

Пусть X=||x_ij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим

x_i,n+1 = a_i – (x_i1 +...+ x_in), i=1...,m

x_m+1,j = b_j – (x_1j +...+ x_mj), j=1...,n.

Пометим

w = x_1,n+1 +...+ x_m,n+1 = x_m+1,1 +...+ x_m+1,n.

Если w = 0, то x — выходной ДБР.

Если w > 0, то исходная ТЗ расширяется за счет фиктивных пунктов производства P_m+1 и потребления Q_n+1 с a_m+1 = b_n+1 = w, где

с_і,n+1 = M, r_i,n+1 = ¥, i=1...,m

c_m+1,j = M, r_m+1,j = ¥, j=1...,n

c_m+1,n+1 = 0, r_m+1,n+1 = ¥,

M — достаточно большое положительное число ¥ — бесконечность.

Нераспределенные на первом этапе остатки продукта (как по объемам производства, так и по объемам потребления) распределяются по фиктивным пунктам P_m+1 и Q_n+1. Соответствующие заполненные клеточки считаются базисными (поскольку пропускные способности соответствующих им коммуникаций неограниченны) и присоединяются к совокупности базисных клеточек заполненных на первом этапе. Если после этого общее количество базисных клеточек не равное (m+1)+(n+1) –1, то множество базисных клеточек дополняют к этому числу за счет незаполненных клеточек или заполненных к пропускной способности, но так, чтобы расширенное множество базисных клеточек не содержало циклов.

Расширенная ТЗ Решается методом потенциалов.

Если в оптимальном решении x*_m+1,n+1=w, то, отбрасывая фиктивные пункты, получим выходной ДБР, иначе ТЗО не имеет решений.