Rendszeroptimalizálás, 4. tétel forrásának megtekintése

{{GlobalTemplate|Infoszak|RopiTetel4}}


==!! A lineáris programozás dualitástétele (két alakban). A lineáris programozás alapfeladatának bonyolultsága (biz. nélkül). Egészértékű programozás: a feladat bonyolultsága, korlátozás és szétválasztás (Branch and Bound).==

__TOC__

<div id="dualitas"></div>
===Dualitás===

*Dualitás tétel*: ha Ax&le;b megoldható és cx felülről korlátos a megoldáshalmazon, akkor az yA=c, y&ge;0 egyenlőtlenségrendszer is megoldható, az yb célfüggvény alulról korlátos és max{cx:Ax&le;b} = min{yb:yA=c,y&ge;0} és a primál programnak létezik maximuma és a duális programnak létezik minimuma.

*Biz.*:
<ul>
<li> Az 1. és a 3. feltétel ekvivalenciájából következik, hogy a két egyenlőtlenségrendszer ugyanakkor megoldható, és az ekvivalencia bizonyításából kijött, hogy sup{cx:Ax&le;b} &le; inf{yb:yA=c,y&ge;0}.
<li> Állítás: Tegyük fel, hogy A*x&le;b megoldható és t tetszőleges szám. Ha &not;&exist;x: Ax&le;b és cx&ge;t, akkor y*A=c, y&ge;0-nak van olyan megoldása, amire yb&lt;t.<br>
Biz.:Ezt írjuk fel egyben, mátrixos formában (leválasztjuk az utolsó sort, ezt &lambda;-val jelöljük):
<math> \left( \begin{array}{cc} y & \lambda \end{array} \right) \left( \begin{array}{c} A \\ -c \end{array} \right) \left( \begin{array}{c} b \\ -t \end{array} \right) </math>
A [[RopiTetel3#1_alak|Farkas-lemma 1. alakjából]] következik, hogy &exist;y,&lambda;: yA-&lambda;c=0, y&ge;0, &lambda;&ge;0 és yb-&lambda;t&lt;0.

&lambda;&ne;0, mert akkor yA=0, y&ge;0, yb&lt;0 lenne, tehát a Farkas-lemma 1. alakja szerint Ax&le;b nem lenne megoldható. &lambda; csak pozitív lehet, le lehet vele osztani.
* yA-&lambda;c=0 <big>&hArr;</big> (y/&lambda;)A=c
* y&ge;0 <big>&hArr;</big> (y/&lambda;)&ge;0
* yb-&lambda;t&lt;0 <big>&hArr;</big> (y/&lambda;)b&lt;t
Azaz y'=y/&lambda; választással a duális feladatnak egy t-nél kisebb megoldását kapjuk.
<li> Létezik a maximum. <br>
Legyen t=sup{cx:Ax&le;b}. Tegyük fel, hogy nem létezik maximum, azaz &not;&exist;x: Ax&le;b és cx&ge;t <big>&rArr;</big> ... <big>&rArr;</big> &exist;y': y'A=c, y'&ge;0, y'b&lt;t. Mivel cx=(y'A)x=y'(Ax)=y'b<t, ezért ez ellentmondás, mert t-t úgy határoztuk meg, hogy minden cx-nél nagyobb. A duális feladat is egy LP feladat, ezért van minimuma.
<li> max{cx:Ax&le;b} = min{yb:yA=c,y&ge;0} <br>
max{cx:Ax&le;b} &le; min{yb:yA=c,y&ge;0}-t már beláttuk. Indirekt: Nem egyenlőség áll fent, és legyen t=min{yb:yA=c,y&ge;0}. Ekkor a primál programnak nincs cx&ge;t-t teljesítő megoldása. Az állítás miatt azonban a duál programnak van yb&lt;t megoldása, ami ellentmondás (t az yb minimuma, ezért nem lehet kisebb nála)
</ul>

*Második alak*:
Ha a max{cx:Ax&le;b,x&ge;0} program megoldható és felülről korlátos, akkor a  min{yb:yA=c,y&ge;0} program is megoldható és alulról korlátos, a primál programnak létezik maximuma, a duál programnak létezik minimuma, és max{cx:Ax&le;b,x&ge;0} = min{yb:yA=c,y&ge;0}

===Bonyolultságelméleti besorolás===

* A &exist;?x: Ax&le;b, cx&ge;t feladat
** NP-beli, mert eldöntendő és x egy tanú. Valós mátrixnál nem triviális, hogy x polinom méretű.
** coNP-beli, mert a duális feladat megoldása egy tanú.
* A szimplex módszer átlagos esetben gyors, de nem P-beli.
* Az ellipszoid módszer lassú, de polinomiális.

===Egészértékű programozás===

* IP alapfeladata: max{cx:Ax&le;b, x&isin;<b>Z</b><sup>n</sup>}
* IP alapfeladat duálisa: min{yb:yA=c, y&ge;0, y&isin;<b>Z</b><sup>n</sup>}
* IP és DIP kapcsolata: max(IP)&le;max(LP)=min(DLP)&le;min(DIP)

===Egészértékű programozás bonyolultsága===

Az IP alapfeladatát át kell fogalmazni eldöntendővé: <br> Adott A,b,c,t. &exist;?x: Ax&le;b, cx&gt;t, x&isin;<b>Z</b><sup>n</sup>.
* IP&isin;NP, mert x egy tanú.
* IP&isin;?coNP. Nem tudjuk, mert nem igaz a dualitás tétele.
* IP&isin;NP-teljes

*Biz.*: visszavezetjük rá a MAXFTLEN problémát. A gráf i. csúcsának megfeleltetjük az x<sub>i</sub> változót. x<sub>i</sub>=1, ha a csúcs benne van a maximális független csúcshalmazban, és 0, ha nem. A MAXFTLEN probléma a következő lineáris egyenlőtlenségrendszerrel írható le:
* &forall;i 0&le;x<sub>i</sub>&le;1 és x<sub>i</sub>&isin;<b>Z</b>
* &forall;e=uv élre x<sub>u</sub>+x<sub>v</sub>&le;1
* Maximalizáljuk &sum;x<sub>i</sub>-t, azaz c=(1,1,...,1)

===Branch and bound algoritmus===

Tegyük fel, hogy a megoldáshalmaz beszorítható az f&le;x&le;g téglatestbe. Ekkor az IP feladat a következő formában írható fel: max{cx:Ax&le;b, f&le;x&le;g, x egész}. f és g lehet végtelen is, de akkor nem garantált, hogy leáll az algoritmus.

<ol>
<li> Nyilvántartjuk a lehetséges részfeladatok halmazát. Egy részfeladatot egy f és egy g vektor azonosít. 
<li> LP relaxáció: kiválasztunk egy részfeladatot, eldobjuk az egészségi feltételt, és megoldjuk LP feladatként.
<li> Elágazás: ha az LP megoldása nem egész, kettébontjuk a téglatestet valamelyik koordináta mentén:
* f'=(f<sub>1</sub>, f<sub>2</sub>, ..., f<sub>n</sub>), g'=(g<sub>1</sub>, ..., g<sub>i-1</sub>, t, g<sub>i+1</sub>, ..., g<sub>n</sub>)
* f''=(f<sub>1</sub>, ..., f<sub>i-1</sub>, t+1, f<sub>i+1</sub>, ..., f<sub>n</sub>), g''=(g<sub>1</sub>, g<sub>2</sub>, ..., g<sub>n</sub>)
Az &lt;f,g&gt; részfeladatot helyettesítjük &lt;f',g'&gt;-vel és &lt;f'',g''&gt;-vel.
<li> Vágás: ha találtunk olyan egész megoldást, amire a célfüggvény értéke w, a w-nél kisebb-egyenlő felső becsléssel rendelkező ágak levághatók.
</ol>

A következő részfeladatot érdemes LIFO elven választani (mélységi bejárás). Ennek oka, hogy a megoldás mélyen van a fában, és hogy a duál szimplex módszer hatékonyan kezeli az iteratívan bővülő egyenlőtlenségeket. A vágáshoz érdemes azt az x<sub>i</sub> változót választani, ami a &bdquo;legkevésbé egészértékű&rdquo;. A vágás pozíciója t=[x<sub>i</sub>] lesz.

-- [[PallosPeter|Peti]] - 2006.12.30.


[[Category:Infoszak]]