Rendszeroptimalizálás, 4. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

!! 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).

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.*:

• 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}.
• Á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 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 ⇔ (y/λ)A=c
  • y≥0 ⇔ (y/λ)≥0
  • yb-λt<0 ⇔ (y/λ)b<t
  Azaz y'=y/λ választással a duális feladatnak egy t-nél kisebb megoldását kapjuk.
• 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 ⇒ ... ⇒ ∃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.
• 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)

• 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∈Zⁿ}
• IP alapfeladat duálisa: min{yb:yA=c, y≥0, y∈Zⁿ}
• 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∈Zⁿ.

• 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 x_i változót. x_i=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≤x_i≤1 és x_i∈Z
• ∀e=uv élre x_u+x_v≤1
• Maximalizáljuk ∑x_i-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.

1. Nyilvántartjuk a lehetséges részfeladatok halmazát. Egy részfeladatot egy f és egy g vektor azonosít.
2. LP relaxáció: kiválasztunk egy részfeladatot, eldobjuk az egészségi feltételt, és megoldjuk LP feladatként.
3. Elágazás: ha az LP megoldása nem egész, kettébontjuk a téglatestet valamelyik koordináta mentén:
   • f'=(f₁, f₂, ..., f_n), g'=(g₁, ..., g_i-1, t, g_i+1, ..., g_n)
   • f=(f₁, ..., f_i-1, t+1, f_i+1, ..., f_n), g=(g₁, g₂, ..., g_n)
   Az <f,g> részfeladatot helyettesítjük <f',g'>-vel és <f,g>-vel.
4. 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.

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_i változót választani, ami a „legkevésbé egészértékű”. A vágás pozíciója t=[x_i] lesz.

-- Peti - 2006.12.30.