Twierdzenie o dualności

Twierdzenie o dualności – rezultat przedstawiający cztery możliwości dotyczące istnienia rozwiązań optymalnych i dopuszczalnych problemu programowania liniowego w postaci standardowej.

Wypowiedź

Spełniony jest jeden z czterech warunków:

• (S) oraz (DS) mają rozwiązania optymalne, odpowiednio $x$ i $y$ spełniające równość: $c^{T}x=y^{T}b.$

• (S) nie ma rozwiązania dopuszczalnego, natomiast (DS) ma taki ciąg rozwiązań dopuszczalnych $\left\{y_{n}\right\}_{n\in \mathbb {N} },$ że:

$\lim _{n\to +\infty }~y^{T}b=+\infty .$

• (DS) nie ma rozwiązania dopuszczalnego, natomiast (S) ma taki ciąg rozwiązań dopuszczalnych $\left\{x_{n}\right\}_{n\in \mathbb {N} },$ że:

$\lim _{n\to +\infty }~c^{T}x=-\infty .$

• (S) oraz (DS) nie mają rozwiązań dopuszczalnych, gdzie (S) jest problemem programowania liniowego zapisanym w postaci standardowej:

${\begin{cases}{\begin{matrix}Ax\geqslant b\\x\geqslant 0\\\min c^{T}x\end{matrix}}\end{cases}},$

natomiast (DS) jest postacią standardową problemu do niego dualnego:

${\begin{cases}{\begin{matrix}y^{T}A\leqslant c\\y\geqslant 0\\\max y^{T}b\end{matrix}}\end{cases}}.$