Szikszayl, 2014. március 13., 12:49-n

2014-03-13T12:49:40Z

← Régebbi változat		A lap 2014. március 13., 14:49-kori változata
105. sor:		105. sor:
	hibát javítottam:-- [[TothZs\|Zsófi]] - 2007.01.19.		hibát javítottam:-- [[TothZs\|Zsófi]] - 2007.01.19.

	[[~~Category~~:~~InfoMsc~~]]		[[Kategória:Mérnök informatikus MSc]]

Szikszayl, 2014. február 7., 17:33-n

2014-02-07T17:33:36Z

← Régebbi változat		A lap 2014. február 7., 19:33-kori változata
56. sor:		56. sor:
	* Először A<sub>x</sub><sup>=</sup>-ből válasszunk ki r db lineárisan független sort.		* Először A<sub>x</sub><sup>=</sup>-ből válasszunk ki r db lineárisan független sort.
	* x nem 0 komponenseinek megfelelő oszlopok lineárisan függetlenek <big>⇒</big> legfeljebb r db van belőlük. Egészítsük ki úgy, hogy r db lineárisan független oszlopot kapjunk.		* x nem 0 komponenseinek megfelelő oszlopok lineárisan függetlenek <big>⇒</big> 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 [[~~RopirxrReszmatrix~~\|metszetük által meghatározott r~~×~~r-es A' mátrix nemszinguláris]].		* A sorok és az oszlopok rangnyi sokan vannak és lineárisan függetlenek, ezért a [[Rendszeroptimalizálás - r x r-es részmátrix nemszinguláris\|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.		* A'x'=b' egyenletrendszert megoldva, és x'-t 0-kkal kiegészítve egy kívánt alakú erős bázismegoldást kapunk.
	</ol>		</ol>
105. sor:		105. sor:
	hibát javítottam:-- [[TothZs\|Zsófi]] - 2007.01.19.		hibát javítottam:-- [[TothZs\|Zsófi]] - 2007.01.19.

			[[Category:InfoMsc]]
	[[Category:~~Infoszak~~]]

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel5}} %BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE% ==!! Bázismegoldások, Caratheodory tétele.== TOC ===Báz…”

2012-10-22T09:44:33Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel5}} %BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE% ==!! Bázismegoldások, Caratheodory tétele.== __TOC__ ===Báz…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel5}}

%BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE%

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

__TOC__

===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 &bdquo;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.*:
<ol style="margin-top:0px; margin-bottom:0px">
<li> Ha x megoldás ilyen alakú, akkor erős bázismegoldás:
* A' sorait egyenlőséggel teljesíti <big>⇒</big> bázismegoldás.
* Az x nem 0 komponenseinek megfelelő oszlopok halmaza A' oszlopainak részhalmaza. Ezek az oszlopok lineárisan függetlenek <big>⇒</big> x erős bázismegoldás.
<li> 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 <big>⇒</big> 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 [[RopirxrReszmatrix|metszetük által meghatározott r×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.
</ol>
*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.

<div id="Caratheodory"></div>
===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.:'''
<ol style="margin-top:0px">
<li> *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.*:
<ol style="margin-top:0px">
<li> 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)
<li> 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'''
<li> Kell egy új sor, ami egyenlőséggel fog teljesülni. Ha '''vannak aiz>0 sorok''', legyen λ=min{(bi-aix0)/(aiz): aiz>0}
<li> A célfüggvény értéke ne csökkenjen. cx'≥cx0 <big>⇒</big> cx0+λcz≥cx0 <big>⇒</big> '''cz≥0'''
</ol>
<li> *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 <big>⇒</big> r(Ax0=)<r(A) <big>⇒</big> ∃aj sor, ami nem kifejezhető Ax0= soraiból lineáris kombinációval <big>⇒</big> yAx0==aj nem megoldható (y a lin. komb.) <big>⇒</big> ([[RopiTetel2#FarkasLemmaKovetkezmeny|Farkas-lemma következménye]]) ∃z: Ax0=z=0 és ajz≠0.
# eset: cz=0 <big>⇒</big> z vagy -z teljesíti mindhárom feltételt.
# eset: cz≠0 <big>⇒</big> 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 <big>⇒</big> ∃i: hogy aiz>0 és ezzel 2. feltétel is OK.
<li> *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.*:
<ol style="margin-top:0px">
<li> x' is legyen bázismegoldás: 
aix' = aix0+λaiz≤bi <big>⇒</big> '''Az=0''' (miért is?)
<li> x0 0 koordinátái maradjanak meg: '''∀i ha x0(i)=0 volt, z(i) is legyen 0'''.
<li> 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.
<li> Legyen cx'=cx0: 
cx'=cx0+λcz <big>⇒</big> '''cz=0'''
</ol>
<li> *Lemma*: ha x0 bázismegoldás, de nem erős, ∃z: Az=0, z≠0, (x0(i)=0 <big>⇒</big> z(i)=0), cz=0. 
*Biz.*: x0 nem erős bázismegoldás <big>⇒</big> a nem 0 koordinátáinak megfelelő oszlopok lineárisan összefüggők A-ban <big>⇒</big> ∃ 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 <big>⇒</big> 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 <big>⇒</big> cx nem felülről korlátos.

-- [[PallosPeter|Peti]] - 2007.01.01.

hibát javítottam:-- [[TothZs|Zsófi]] - 2007.01.19.

[[Category:Infoszak]]

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

Szikszayl, 2014. március 13., 12:49-n

Szikszayl, 2014. február 7., 17:33-n

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel5}} %BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE% ==!! Bázismegoldások, Caratheodory tétele.== __TOC__ ===Báz…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel5}} %BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE% ==!! Bázismegoldások, Caratheodory tétele.== TOC ===Báz…”