Unknown user: Új oldal, tartalma: „{{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…”

2012-10-22T09:44:30Z

Új oldal, tartalma: „{{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…”

Új lap

{{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≤b megoldható és cx felülről korlátos a megoldáshalmazon, akkor az yA=c, y≥0 egyenlőtlenségrendszer is megoldható, az yb célfüggvény alulról korlátos és max{cx:Ax≤b} = min{yb:yA=c,y≥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≤b} ≤ inf{yb:yA=c,y≥0}.
<li> Állítás: Tegyük fel, hogy A*x≤b megoldható és t tetszőleges szám. Ha ¬∃x: Ax≤b és cx≥t, akkor y*A=c, y≥0-nak van olyan megoldása, amire yb<t. 
Biz.:Ezt írjuk fel egyben, mátrixos formában (leválasztjuk az utolsó sort, ezt λ-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 ∃y,λ: yA-λc=0, y≥0, λ≥0 és yb-λt<0.

λ≠0, mert akkor yA=0, y≥0, yb<0 lenne, tehát a Farkas-lemma 1. alakja szerint Ax≤b nem lenne megoldható. λ csak pozitív lehet, le lehet vele osztani.
* yA-λc=0 <big>⇔</big> (y/λ)A=c
* y≥0 <big>⇔</big> (y/λ)≥0
* yb-λt<0 <big>⇔</big> (y/λ)b<t
Azaz y'=y/λ választással a duális feladatnak egy t-nél kisebb megoldását kapjuk.
<li> Létezik a maximum. 
Legyen t=sup{cx:Ax≤b}. Tegyük fel, hogy nem létezik maximum, azaz ¬∃x: Ax≤b és cx≥t <big>⇒</big> ... <big>⇒</big> ∃y': y'A=c, y'≥0, y'b<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≤b} = min{yb:yA=c,y≥0} 
max{cx:Ax≤b} ≤ min{yb:yA=c,y≥0}-t már beláttuk. Indirekt: Nem egyenlőség áll fent, és legyen t=min{yb:yA=c,y≥0}. Ekkor a primál programnak nincs cx≥t-t teljesítő megoldása. Az állítás miatt azonban a duál programnak van yb<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≤b,x≥0} program megoldható és felülről korlátos, akkor a min{yb:yA=c,y≥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≤b,x≥0} = min{yb:yA=c,y≥0}

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

* A ∃?x: Ax≤b, cx≥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≤b, x∈Zn}
* IP alapfeladat duálisa: min{yb:yA=c, y≥0, y∈Zn}
* IP és DIP kapcsolata: max(IP)≤max(LP)=min(DLP)≤min(DIP)

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

Az IP alapfeladatát át kell fogalmazni eldöntendővé: Adott A,b,c,t. ∃?x: Ax≤b, cx>t, x∈Zn.
* IP∈NP, mert x egy tanú.
* IP∈?coNP. Nem tudjuk, mert nem igaz a dualitás tétele.
* IP∈NP-teljes

*Biz.*: visszavezetjük rá a MAXFTLEN problémát. A gráf i. csúcsának megfeleltetjük az xi változót. xi=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:
* ∀i 0≤xi≤1 és xi∈Z
* ∀e=uv élre xu+xv≤1
* Maximalizáljuk ∑xi-t, azaz c=(1,1,...,1)

===Branch and bound algoritmus===

Tegyük fel, hogy a megoldáshalmaz beszorítható az f≤x≤g téglatestbe. Ekkor az IP feladat a következő formában írható fel: max{cx:Ax≤b, f≤x≤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'=(f1, f2, ..., fn), g'=(g1, ..., gi-1, t, gi+1, ..., gn)
* f''=(f1, ..., fi-1, t+1, fi+1, ..., fn), g''=(g1, g2, ..., gn)
Az <f,g> részfeladatot helyettesítjük <f',g'>-vel és <f'',g''>-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 xi változót választani, ami a &bdquo;legkevésbé egészértékű”. A vágás pozíciója t=[xi] lesz.

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

[[Category:Infoszak]]

Rendszeroptimalizálás, 4. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{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…”