Несимметричные двойственные задачи

Запишем задачу линейного программирования на max в каноническом виде.

Max Z = c _j x _j

a _ij x _j = b _i

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

a _ij x _j <= b _I a _ij x _j => b _I,умножим на(-

1)получим задачу в симметричной форме. Max Z =c _j x _j

a _ij x _j <= b _I

(-a _ij) x _j <= -b _I

Введем двойственные переменные Y’_i, Y” _i, тогда двойственная задача примет следующий вид:

Min f = b_i (Y’_i -Y” _i)

a _ij (Y’_i -Y” _i)=> c _j

Y’_I =>0

Y” _i =>0

Введем (Y’_i -Y” _i)= Y _i

Min f = ∑b_i Y _i

a _ij Y _i => c _j

Y’_I и Y” _i, были введены для каждой системы ограничений. Получается, что Y _i может принимать как положительные, так и отрицательные значения. Таким образом эта модель представляет собой пару несимметричных двойственных задач. Так же формируется двойственная задача в случае, когда в ограничении исходной задачи входят как неравенства, так и равенства.

Max Z=c j x j a ij x j <= b I (i=1,…,m) a ij x j =b i (i = M1+1…,m) x j =>0 (j=1,..n1) x j (J=n1+1)

Min f=b i x i a ij Y i => c j a ij Y i = c j (j= n1+1,…,n) Y i=>0 (i=1,….,1m 1)

При этом выполняется ряд правил:

1.Если на переменную x_j прямой задачи накладывается условие неотрицательности, то j – условие системы ограничений двойственной задачи записывается в виде неравенств и наоборот.

2.Если на переменную x_j прямой задачи не наложено условие неотрицательности, то j – ограничение двойственной задачи запишется в виде строгого равенства.

3.Если в прямой задаче имеются ограничения равенства, то на соответствующие переменные двойственной задачи не налагаются условия неотрицательности.

ТЕОРЕМЫ:

1.Для любых допустимых планов x = (x₁,…,x _n) и y = (y₁,…y _m) прямой и двойственной задач линейного программирования справедливо неравенство:

Z (x)<= f (x)

c _j x _j <= b _i y _i

2.Критерий оптимальности Канторовича. Если для некоторых дополнительных планов x* и y* пары двойственных задач выполняется равенство Z (x*)= f (y*), то x* и y* являются оптимальными планами соответствующих задач.

3. Малая теорема двойственности. Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.

4.Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение. Причем экстремальные значения целевых функций должны быть равны. Если одна из двойственных задач не разрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

5. Теорема о допускающей нежесткости. Для того, чтобы планы x* и y* пары двойственной задачи были оптимальны, необходимо и достаточно выполнение условий:

X^*_j (a _ij y _j ^* - c _j) =0 j= 1,…., n

Y _i^* (a _ij x^*_j - b _i) =0 i= 1,…., m

Дата добавления: 2014-01-07