Rendszeroptimalizálás, 5. 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

%BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE%

!! Bázismegoldások, Caratheodory tétele.

Bázismegoldás definíciója

Tegyük fel, hogy Ax≤b megoldható és x egy megoldás.

• Def.*: A_x⁼ A azon a_i soraiból áll, amire a_ix=b_i, tehát amikre x „egyenlőséggel teljesül”.
  
• Def.*: x bázismegoldás, ha r(A_x⁼)=r(A).
  
• Def.*: x erős bázismegoldás, ha bázismegoldás és az x nem 0 komponenseinek megfelelő A-beli oszlopok lineárisan függetlenek.

Ekvivalens definíció

Tegyük fel, hogy Ax≤b. A mátrix rangja r. A-ból kiválasztható r db lineárisan független sor és r db lineárisan független oszlop. A kettő metszete egy r×r méretű nemszinguláris A' részmátrix. b oszlopvektor A'-nek megfelelő sorait b'-vel jelöljük. x-et úgy kapjuk, hogy az A'x'=b' egyenlet egyértelmű megoldását kiegészítjük 0-kkal az A'-höz nem tartozó oszlopoknak megfelelő helyeket.

[math] \[ \mathop{ \begin{array}{|cccccc|} \hline &&&&& \\ \cline{3-5} &&\multicolumn{3}{|c|}{}& \\ &&\multicolumn{3}{|c|}{A'}& \\ &&\multicolumn{3}{|c|}{}& \\ \cline{3-5} &&&&& \\ \hline \end{array} }\limits^A \:\: \mathop{ \begin{array}{|c|} \hline \multirow{2}{*}{0} \\ \\ \hline \\ x' \\ \\ \hline 0 \\ \hline \end{array} }\limits^x \le \mathop{ \begin{array}{|c|} \hline \\ \hline \\ b' \\ \\ \hline \\ \hline \end{array} }\limits^b \] [/math]

• Tétel*: Ha az előbbi definicióban szereplő x megoldása Ax≤b-nek, akkor x erős bázismegoldás. Minden erős bázismegoldás előáll így.
  
• Biz.*:

1. Ha x megoldás ilyen alakú, akkor erős bázismegoldás:
   • A' sorait egyenlőséggel teljesíti ⇒ bázismegoldás.
   • Az x nem 0 komponenseinek megfelelő oszlopok halmaza A' oszlopainak részhalmaza. Ezek az oszlopok lineárisan függetlenek ⇒ x erős bázismegoldás.
2. Ha x erős bázismegoldás, A'-t válasszuk ki a következő módon:
   • Először A_x⁼-ből válasszunk ki r db lineárisan független sort.
   • x nem 0 komponenseinek megfelelő oszlopok lineárisan függetlenek ⇒ legfeljebb r db van belőlük. Egészítsük ki úgy, hogy r db lineárisan független oszlopot kapjunk.
   • A sorok és az oszlopok rangnyi sokan vannak és lineárisan függetlenek, ezért a metszetük által meghatározott r x r-es A' mátrix nemszinguláris.
   • A'x'=b' egyenletrendszert megoldva, és x'-t 0-kkal kiegészítve egy kívánt alakú erős bázismegoldást kapunk.

• Következmény*: az erős bázisok száma véges, legfeljebb annyi van belőlük, ahányféleképpen A-ból kiválasztható egy r×r-es részmátrix.

Caratheodory-tétel

Tétel: ha Ax≤b megoldható, {cx:Ax≤b} felülről korlátos, és x₀ egy megoldása, ∃x₁ erős bázismegoldás, hogy cx₁≥cx₀.

• Következmények*:
• Ha Ax≤b megoldható, létezik bázismegoldás. Bizonyítás: legyen c=0, ekkor a célfüggvény korlátos.
• Ha {cx:Ax≤b} felülről korlátos, létezik maximuma. Bizonyítás: véges sok erős bázismegoldás van.
• Ha A totálisan unimoduláris és b egész, Ax≤b minden erős bázismegoldása egész. Bizonyítás: a Cramer-szabály szerint az A'x'=b' egyenletrendszer megoldása x_i' = det(A'_i)/det(A'), ahol A'_i-t úgy kapjuk, hogy A' i. oszlopát helyettesítjük b'-vel. A számláló egész, a nevező ±1, ezért x' egész.

Biz.:

1. *Lemma*: Ha x₀ nem bázismegoldás, ∃x' megoldás, ami több sort teljesít egyenlőséggel, mint x₀ és cx'≥cx₀.
   
   • Köv.*: Caratheodory-tétel gyengített változata, a célfüggvény értéke nem csökken, ha a megoldást alkalmasan választott bázismegoldásra cseréljük. Bizonyítás: while (x₀ nem bázismegoldás) x₀=x'; A ciklus leáll legkésőbb akkor, ha minden sor egyenlőséggel teljesül.
     
   • Biz.*:
   1. Válasszunk alkalmas z-t és λ-t úgy, hogy x'=x₀+λz λ≥0-ra továbbra is megoldás maradjon.
      a_ix' = a_ix₀+λa_iz ≤ b_i, azaz ha az i. sor egyenlőséggel teljesül, legyen a_iz ≤ 0. Röviden: teljesüljön, hogy A_x0⁼z≤0 és azokra a sorokra, amire a_iz>0 teljesül, legyen λ≤(b_i-a_ix₀)/(a_iz)
   2. Ha az i. sor eddig egyenlőséggel teljesült x₀-ra nézve, teljesüljön egyenlőséggel x'-re nézve is.
      Megkötés: A_x0⁼z=0
   3. Kell egy új sor, ami egyenlőséggel fog teljesülni.
      Ha vannak a_iz>0 sorok, legyen λ=min{(b_i-a_ix₀)/(a_iz): a_iz>0}
   4. A célfüggvény értéke ne csökkenjen.
      cx'≥cx₀ ⇒ cx₀+λcz≥cx₀ ⇒ cz≥0
2. *Lemma*: ha x₀ megoldás, de nem bázismegoldás, ∃i,z: A_x0⁼z=0 (1), cz≥0 (3) és a_iz>0 (2).
   
   • Biz.*: x₀ nem bázismegoldás ⇒ r(A_x0⁼)<r(A) ⇒ ∃a_j sor, ami nem kifejezhető A_x0⁼ soraiból lineáris kombinációval ⇒ yA_x0⁼=a_j nem megoldható (y a lin. komb.) ⇒ (Farkas-lemma következménye) ∃z: A_x0⁼z=0 és a_jz≠0.
   1. eset: cz=0 ⇒ z vagy -z teljesíti mindhárom feltételt.
   2. eset: cz≠0 ⇒ z vagy -z választásával cz>0 lesz. (Ezáltal 1. és 3. feltétel OK.) Most Az≤0 nem lehet, mert akkor (Az≤0, cz>0) miatt a cx nem lenne felülről korlátos a megoldáshalmazon ⇒ ∃i: hogy a_iz>0 és ezzel 2. feltétel is OK.
3. *Lemma*: ha x₀ bázismegoldás, de nem erős, ∃x' bázismegoldás, aminek több 0 koordinátája van, mint x₀-nak és cx'=cx₀.
   
   • Köv.*: while (x₀ nem erős) x₀=x'; A ciklus mindenképp leáll, mert legkésőbb a nullvektor erős bázismegoldás lesz.
     
   • Biz.*:
   1. x' is legyen bázismegoldás:
      a_ix' = a_ix₀+λa_iz≤b_i ⇒ Az=0 (miért is?)
   2. x₀ 0 koordinátái maradjanak meg:
      ∀i ha x₀(i)=0 volt, z(i) is legyen 0.
   3. Jöjjön létre egy új 0 koordináta:
      Ha z≠0, alkalmas λ választásával 0-vá lehet tenni x'=x₀+λz valamelyik koordinátáját.
   4. Legyen cx'=cx₀:
      cx'=cx₀+λcz ⇒ cz=0
4. *Lemma*: ha x₀ bázismegoldás, de nem erős, ∃z: Az=0, z≠0, (x₀(i)=0 ⇒ z(i)=0), cz=0.
   
   • Biz.*: x₀ nem erős bázismegoldás ⇒ a nem 0 koordinátáinak megfelelő oszlopok lineárisan összefüggők A-ban ⇒ ∃ nemtriviális 0-t adó lineáris kombinációjuk: (λ₁, ..., λ_k). z első k koordinátája legyen λ₁, ..., λ_k, a többi 0. Ezzel biztosítottuk, hogy Az=0, z≠0 és (x₀(i)=0 ⇒ z(i)=0).
     
   Tegyük fel, hogy cz≠0. z vagy -z választással pozitívvá tehető, miközben az első három feltétel továbbra is fennáll. Az=0 és cz>0 ⇒ cx nem felülről korlátos. -- Peti - 2007.01.01. hibát javítottam:-- Zsófi - 2007.01.19.