A dualitástétel a lineáris programozás fontos tétele. Segítségével ellenőrizhető, hogy tényleg a megfelelő szélsőértéket adták-e meg. De vannak más alkalmazásai is, például a játékelméletben vagy a gráfelméletben.

${\displaystyle \max\{c_{0}x_{0}+c_{1}x_{1}:Px_{0}+Ax_{1}=b_{0))$ ${\displaystyle Qx_{0}+Bx_{1}\leq b_{1}x_{1}\geq 0\))$

${\displaystyle \min\{b_{0}y_{0}+b_{1}y_{1}:y_{0}P+y_{1}Q=c_{0))$ ${\displaystyle y_{0}A+y_{1}B\geq c_{1}y_{1}\geq 0\))$

A duális poliéder függ R megadásától, sőt c-től is.

Tekintve ugyanis a dimenziókat, ${\displaystyle R^{*}\in \mathbb {R} ^{m=m_{1}+m_{2))}$ ${\displaystyle R\in \mathbb {R} ^{n=n_{1}+n_{2))}$

A tétel egy egyszerűbb, szimmetrikus alakja:

Tegyük fel, hogy ${\displaystyle R=\{x:Qx\leq b\))$ nem üres, és ${\displaystyle R=\{cx:x\in R\))$ felülről korlátos. Ekkor a primál program maximuma egyenlő a duál program minimumával. Azaz ${\displaystyle \max\{cx:Qx\leq b\}=\min\{by:y\geq 0,yQ=c\))$.

Az egyik irány könnyű. Hármas szorzattal ${\displaystyle cx=(yQ)x=y(Qx)\leq yb}$. A másik irányhoz kell egy megoldáspár, amire az egyenlőség teljesül. Ezek bázismegoldások lesznek. Ha ${\displaystyle \{cx:x\in R\))$ felülről korlátos, akkor maximumát egy bázismegoldáson is felveszi.

A bizonyítás folytatásához szükség van egy lemmára.

Lemma: legyen ${\displaystyle R=\{x:Qx\leq b\))$ nem üres, és ${\displaystyle \{cx:x\in R\))$ felülről korlátos. Ekkor a következők ekvivalensek:

1. cx^* minden ${\displaystyle x\in R}$, x^* optimális
2. nincs növelő irány, azaz nincs x¹, hogy ${\displaystyle Q_{x^{*))^{=))$x¹ ${\displaystyle cx^{1}>0}$, ahol ${\displaystyle Q_{x^{*))^{=))$ a Q mátrixnak azokat a sorait jelöli, amiket x^* egyenlőséggel teljesít
3. a c vektor benne van x^* aktív sorainak kúpjában, azaz van y^*, ${\displaystyle y^{*}\geq 0}$ ${\displaystyle y^{*}Q=c}$ és ha ${\displaystyle y^{*}(i)>0,}$ akkor ${\displaystyle q_{i}x^{*}=b(i)}$. Ekvivalensen ${\displaystyle cx^{*}=by^{*))$.

A lemma bizonyítása a Farkas-lemma segítségével:

Ha lenne x¹ növelő irány, akkor egy kicsit elmozdulva az x¹ irányban az ${\displaystyle x^{*}+\lambda x^{1))$ vektor még mindig benne lenne R-ben. Ez ${\displaystyle cx^{1}>0}$ miatt ellentmond ${\displaystyle cx^{*))$ maximalitásának.

Ha van x¹ növelő irány, akkor a Farkas-lemma balról szorzós alakja szolgáltat egy y¹ vektort, amit 0 koordinátákkal kiegészítve y^* kapható.

Tetszőleges${\displaystyle x\in R}$ esetén ${\displaystyle cx=y^{*}Qx\leq y^{*}b}$, vagyis y^*b felső korlát ${\displaystyle \{cx:x\in R\))$-re. ${\displaystyle x^{*}\in R}$ biztosan optimális, ha ${\displaystyle cx^{*}=by^{*))$, és a 3.-ban jelzett másik állítás ezzel ekvivalens.

A tétel bizonyítására visszatérve: a lemma szerint van ${\displaystyle y^{*}\in R^{*}:y^{*}(b-Qx^{*}=0)}$, amiből ${\displaystyle y^{*}b=cx^{*))$, és ezzel vége a bizonyításnak.

• http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf