Rendszeroptimalizálás, 5. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen Szikszayl (vitalap | szerkesztései) 2014. március 13., 13:49-kor történt szerkesztése után volt.
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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.*: Ax= A azon ai soraiból áll, amire aix=bi, tehát amikre x „egyenlőséggel teljesül”.
  • Def.*: x bázismegoldás, ha r(Ax=)=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 Ax=-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 x0 egy megoldása, ∃x1 erős bázismegoldás, hogy cx1≥cx0.

  • 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 xi' = 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 x0 nem bázismegoldás, ∃x' megoldás, ami több sort teljesít egyenlőséggel, mint x0 és cx'≥cx0.
    • 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 (x0 nem bázismegoldás) x0=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'=x0+λz λ≥0-ra továbbra is megoldás maradjon.
      aix' = aix0+λaiz ≤ bi, azaz ha az i. sor egyenlőséggel teljesül, legyen aiz ≤ 0. Röviden: teljesüljön, hogy Ax0=z≤0 és azokra a sorokra, amire aiz>0 teljesül, legyen λ≤(bi-aix0)/(aiz)
    2. Ha az i. sor eddig egyenlőséggel teljesült x0-ra nézve, teljesüljön egyenlőséggel x'-re nézve is.
      Megkötés: Ax0=z=0
    3. Kell egy új sor, ami egyenlőséggel fog teljesülni.
      Ha vannak aiz>0 sorok, legyen λ=min{(bi-aix0)/(aiz): aiz>0}
    4. A célfüggvény értéke ne csökkenjen.
      cx'≥cx0 cx0+λcz≥cx0 cz≥0
  2. *Lemma*: ha x0 megoldás, de nem bázismegoldás, ∃i,z: Ax0=z=0 (1), cz≥0 (3) és aiz>0 (2).
    • Biz.*: x0 nem bázismegoldás r(Ax0=)<r(A) ∃aj sor, ami nem kifejezhető Ax0= soraiból lineáris kombinációval yAx0==aj nem megoldható (y a lin. komb.) (Farkas-lemma következménye) ∃z: Ax0=z=0 és ajz≠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 aiz>0 és ezzel 2. feltétel is OK.
  3. *Lemma*: ha x0 bázismegoldás, de nem erős, ∃x' bázismegoldás, aminek több 0 koordinátája van, mint x0-nak és cx'=cx0.
    • Köv.*: while (x0 nem erős) x0=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:
      aix' = aix0+λaiz≤bi Az=0 (miért is?)
    2. x0 0 koordinátái maradjanak meg:
      ∀i ha x0(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'=x0+λz valamelyik koordinátáját.
    4. Legyen cx'=cx0:
      cx'=cx0+λcz cz=0
  4. *Lemma*: ha x0 bázismegoldás, de nem erős, ∃z: Az=0, z≠0, (x0(i)=0 z(i)=0), cz=0.
    • Biz.*: x0 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: (λ1, ..., λk). z első k koordinátája legyen λ1, ..., λk, a többi 0. Ezzel biztosítottuk, hogy Az=0, z≠0 és (x0(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.