Dualitástétel

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.

Általános alak

Dualitás tétel

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

$\min\{b_{0}y_{0}+b_{1}y_{1}:y_{0}P+y_{1}Q=c_{0}$ $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, $R^{*}\in \mathbb {R} ^{m=m_{1}+m_{2}}$ $R\in \mathbb {R} ^{n=n_{1}+n_{2}}$

Bizonyítás

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

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

Az egyik irány könnyű. Hármas szorzattal $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 $\{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 $R=\{x:Qx\leq b\}$ nem üres, és $\{cx:x\in R\}$ felülről korlátos. Ekkor a következők ekvivalensek:

1. cx^* minden $x\in R$, x^* optimális
2. nincs növelő irány, azaz nincs x¹, hogy $Q_{x^{*}}^{=}$x¹ $cx^{1}>0$, ahol $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^*, $y^{*}\geq 0$ $y^{*}Q=c$ és ha $y^{*}(i)>0,$ akkor $q_{i}x^{*}=b(i)$. Ekvivalensen $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 $x^{*}+\lambda x^{1}$ vektor még mindig benne lenne R-ben. Ez $cx^{1}>0$ miatt ellentmond $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$x\in R$ esetén $cx=y^{*}Qx\leq y^{*}b$, vagyis y^*b felső korlát $\{cx:x\in R\}$-re. $x^{*}\in R$ biztosan optimális, ha $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 $y^{*}\in R^{*}:y^{*}(b-Qx^{*}=0)$, amiből $y^{*}b=cx^{*}$, és ezzel vége a bizonyításnak.

Források

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