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:P{x}_0+A{x}_1=b_0$ $Q{x}_0+B{x}_1\le b_1{x}_1\ge 0\}$ $\min \{b_0{y}_0+b_1{y}_1:y_{0}P+y_{1}Q=c_0$ $y_{0}A+y_{1}B\ge c_1{y}_1\ge 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{ℝ}}^{m=m_1+m_2}$ $R\in {\mathbb{ℝ}}^{n=n_1+n_2}$

Bizonyítás

A tétel egy egyszerűbb, szimmetrikus alakja: Tegyük fel, hogy $R=\{x:Qx\le 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\le b\}=\min \{by:y\ge 0,yQ=c\}$. Az egyik irány könnyű. Hármas szorzattal $cx=(yQ)x=y(Qx)\le 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\le 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¹ $c{x}^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^{*}\ge 0$ $y^{*}Q=c$ és ha $y^{*}(i)>0,$ akkor $q_i{x}^{*}=b(i)$. Ekvivalensen $c{x}^{*}=b{y}^{*}$.

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 $c{x}^1>0$ miatt ellentmond $c{x}^{*}$ 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\le y^{*}b$, vagyis y^*b felső korlát $\{cx:x\in R\}$-re. $x^{*}\in R$ biztosan optimális, ha $c{x}^{*}=b{y}^{*}$, é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-Q{x}^{*}=0)$, amiből $y^{*}b=c{x}^{*}$, és ezzel vége a bizonyításnak.

Források

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