Двойственная транспортная задача

Для транспортной задачи, как и для любой ЗЛП, существует двойственная к ней транспортная задача.

Переменные двойственной транспортной задачи обозначим v₁, v₂,…, v_n и (- u₁), (- u₂),…,(- u_m).

Теорема4.2 Двойственная транспортная задача всегда имеет решение и если X_opt = и W_opt = (v,₁_opt, v_2,_opt,…, v_n_,_opt, - u,₁_opt, -u_2,_opt,…, - u_m_,_opt) – оптимальные решения транспортной и двойственной к ней задач соответственно, то выполняется условие:

(4.8)

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

Переменные v_j и (- u_i) называют потенциалами пунктов B_j и A_i для транспортной задачи.

Теорема4.3 Для оптимальности плана Х₀ транспортной задачи необходимо и достаточно существование v₁, v₂,…, v_n и (- u₁), (- u₂),…,(- u_m) таких, что: v_j – u_i (i=1,2,…,m; j=1,2,…,n). При этом, если: v_j – u_i = , то >0.

Эта теорема даёт достаточные условия оптимальности плана Х. Разность между потенциалами пунктов B_j и A_i, т.е. величину v_j – u_i можно рассматривать как приращение ценности единицы продукции при перевозке из пункта A_i в пункт B_j. Поэтому если v_j – u_i < , то перевозка по коммуникации нерентабельна и =0. Если v_j – u_i = то такая перевозка рентабельна и >0.