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

Учитывая задачу линейного программирования как

Основная проблема

min CtxSubject toAxbx0AMmxn, rank(A)=mbRm, CRn,xRn


Это связано с другой проблемой. Которую мы называем Двойственной формой

Двойная проблема

\( max\ b^tw \\ Subject\ to \\

max btwSubject toAtwCw0AMmxn, rank(A)=mbRm, CRn,wRm


То есть то. Что было вектором затрат. Теперь является вектором ограничений и наоборот. Матрица ограничений транспонируется в двойственную. В некоторых случаях проще решить одно. Чем другое. Или можно дать условия для одного. Определяющие свойства решений другого.

В более общем случае. Если у нас есть задача линейного программирования как

\( max\

max CtxSubject toj=1naijxjbi, iM1j=1naijxj=bi, iMM1xj0, jN1

, то есть у нас есть только ограниченные в знак кому-то из переменных. И только в некоторых ограничений. У нас есть неравенство. То двойственная задача будет:

max btwSubject toi=1majiwiCi, jN1i=1majiwi=Ci, jNN1wi0, iM1

т. е. у нас есть
1. Ограничение неравенства в первичной переменной означает ограничение в знаковой переменной в двойственной.

2. Ограничение равенства в первичном. Приводящее к неограниченной по знаку переменной в двойственном.

Теорема существования
а) Если одна из двух задач имеет конечное оптимальное решение. То и другая имеет.
б) Если первичная задача имеет неограниченное решение. То двойственная задача не имеет выполнимо оптимального решения (обратное неверно).

Следствие 1

Для пары двойственных задач истинно только одно из этих условий:

1) Ни одно из них не имеет выполнимого оптимального решения.

2) У одного есть решение. Осуществимое. Но неограниченное. А у другого нет решения.

3) Они оба имеют конечные оптимальные решения.

Следствие 2 (теорема дуальности)

Учитывая пару двойственных задач. Необходимым и достаточным условием для начального оптимального решения имеет конечный x. Является то. Что существует двойственное допустимое решение w такое, что

\( Cx = bw \)

Cx=bw