Теорема двойственности

а) Если и исходная и двойственная ей задачи имеют допустимые решения, то:

1. существует оптимальное решение xj* (j=1,2, ... , n) исходной задачи;

2. существует оптимальное решение yi* (i=1,2, ... ,m)двойственной задачи;

n m

3. имеет место следующее соотношение: c j x j=  b i y i

j=1 i=1

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

Следствие теоремы двойственности (Теорема о дополнительной нежесткости)

Пусть xj* (j=1,2, ... , n) - решение исходной задачи, а у* (i=1,2, ... , m) - решение соответствующей двойственной задачи. Оба решения являются оптимальными тогда и только тогда, когда

n

yi* ( aij xj* - b i ) = 0 (i=1,2, ... , m),

j=1

n

xj* ( aij yj* - cj ) = 0 (j=1,2, ... , n).

j=1

Взаимосвязь между исходной и двойственной задачами более четко прослеживается, если воспользоваться следующими развернутыми каноническими формами представления:

а)Исходная задача:

n

максимизировать  cj xj (I)

j=1

при наличии ограничений

n

 a ij x j <= b i (i=1,2, ... , h<=m), (II)

j=1

n

 a ij x j = b i ( i=h+1,h+2, ... , m), (III)

j=1

xj >= 0 (i=1,2, ... , k<=n), (IV)

xj - не имеет ограничения в знаке при j = k+1, k+2, ... , n. ( V )

б) Двойственная задача:

m

минимизировать  b i y i (I’)

j=1

при ограничениях

n

 a ij y i > = cj ( j=1,2, ... , k), (II’)

j=1

n

 a ij y i = cj ( j= k+1,k+2, ... , n), (III’)

j=1

yi >= 0 ( i=1,2, ... , h ). (IV’)

yi не имеет ограничений в знаке при i= h+1,h+2, ... , m. (V’)

Схема соответствий исходной и двойственной задач

Исходная задача	Двойственная задача
максимизация	минимизация
Константы в правых частях ограничений	Целевая функция
Целевая функция	Константы в правых частях ограничений
j-й столбец, составленный из коэффициентов при неизвестных в ограничениях	j-я строка, составленная из коэффициентов при неизвестных в ограничениях
i-я строка, составленная из коэффици-ентов при неизвестных в ограничениях	i-й столбец, составленный из коэффициентов при неизвестных в ограничениях
j-я неотрицательная переменная	j-е неравенство вида<=
j-я переменная, не имеющая ограни-ченния в знаке	j-е соотношение в виде равенства
i-е неравенство вида<=	i-я неотрицательная переменная
i-е соотношение в виде равенства	i-я переменная, не имеющая ограничения в знаке