12. Двойственные задачи линейного программирования. Построение двойственных задач

Задача линейного программирования обычно записывается в следующем общем виде

(см. подразд. 4.1):

w(x) = sum{j=1,n}(c_jx_j)->min (1)

a_ix-b_i>=0 i€I₁ (2)

a_ix-b_i>=0 i€I₂ (3)

x_j>=0 j€J₁

При этом ограничения (2)-(3) будем называть существенными, а ограничения (4) -

ограничениями по знаку. Напомним, что I = I1 U I2 = {1..m}; I1 П I2 = (пуст множ.); J1 С J =

{1..n}; а через J2 обозначим множество J\J1. Переменные xj ; j € J2 называются

свободными. С этой задачей, которую назовем прямой задачей ЛП, тесно связана задача,

которая называется двойственной к ней или двойственной задачей ЛП.

Двойственная задача строится следующим образом:

1) каждому существенному ограничению (2)-(3) ставится в соответствие двойственная

переменная y_i(i € I);

2) целевой функцией, которую необходимо максимизировать, является произведение

вектор_строки y = (y1… ym) на вектор_столбец b = (b1… bm)^Т;

3) каждому ограничению_неравенству (2) соответствует ограниченная по знаку пере-

менная, т. е. yi >=0(i € I1); а каждому ограничению_равенству (3) соответствует свободная

переменная yi(i € I2);

4) каждой ограниченной по знаку переменной xj(j € J1) соответствует ограничение_

неравенство двойственной задачи, которое имеет вид

sum{i=1,m}(a_ijy_i)<=c_j (j € J1)

и левая часть которого получается умножением вектор_строки y на j-й столбец Aj матрицы

A, а в правой части находится соответствующий коэффициент целевой функции (1);

5) каждой свободной переменной xj (j € J2) соответствует ограничение_равенство, ко-

торое строится так же, как предыдущее неравенство, и имеет вид

sum{i=1,m}(a_ijy_i)=c_j (j € J₂)

Таким образом, двойственной к задаче (1)_(4) является задача

sum{i=1,m}(b_iy_i)->max (1’)

sum{i=1,m}(a_ijy_i)<=c_j (j € J₁) (2’)

sum{i=1,m}(a_ijy_i)=c_j (j € J₂) (3’)

y_i>=0 i€ I₁) (4’)

В векторном виде пару двойственных задач (1)_(4) и (10)_(40) можно представить так:

Существенной особенностью отношения двойственности является тот факт, что задача,

двойственная к задаче (1’)_(4’), совпадает с прямой задачей (1)_(4). Можно считать, что все задачи ЛП разбиваются на пары взаимно двойственных задач.

13. Теоремы двойственности

Отметим следующие важные свойства взаимно двойственных задач. Для определјнно-

сти будем считать, что задача на минимум является прямой, а на максимум _ двойственной.

Свойство 1. Если x и y _ допустимые решения соответственно прямой и двойственной

задачи, то w(x) >= z(y):

Свойство 2. Если x и y _ допустимые решения соответственно прямой и двойственной

задачи и w(x) = z(y), то x и y _ оптимальные решения.

Теорема 1 (первая теорема двойственности). Прямая и двойственная к ней задачи

либо одновременно разрешимы, либо одновременно неразрешимы. При этом в первом случае

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

крайней мере одна из задач неразрешима в силу несовместности ограничений.

Отметим, что существуют примеры взаимно двойственных задач с несовместными ограничениями.

Теорема 2 (вторая теорема двойственности, или теорема о дополняющей

нежјсткости). Допустимые решения x и y соответственно прямой и двойственной за-

дачи оптимальны тогда и только тогда, когда

y_i(a_ix-bi)=0 (i€I)

(c_j-yA_j)x_j=0(j€J)