Twierdzenie o dualności

Szablon:Dopracować 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:

$\underset{n\to +\mathrm{\infty }}{\lim }{y}^{T}b=+\mathrm{\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:

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

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

$\{\begin{array}{c}\begin{array}{c}Ax⩾b\\ x⩾0\\ \min c^{T}x\end{array}\end{array},$

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

$\{\begin{array}{c}\begin{array}{c}{y}^{T}A⩽c\\ y⩾0\\ \max y^{T}b\end{array}\end{array}.$