Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel3}} ==!! Farkas-lemma (két alakban). A lineáris program célfüggvé…”

2012-10-22T09:44:28Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel3}} <style> ol { margin-top: 0px; margin-bottom: 0px; } </style> ==!! Farkas-lemma (két alakban). A lineáris program célfüggvé…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel3}}

<style> ol { margin-top: 0px; margin-bottom: 0px; } </style>

==!! Farkas-lemma (két alakban). A lineáris program célfüggvénye felülről korlátosságának feltételei.==

__TOC__

===Farkas-lemma===

====1. alak====

*Tétel*: (Ax≤b) és (yA=0, y≥0, yb<0) közül pontosan egy megoldható. 
*Biz.*:
# A kettő egyszerre nem megoldható: indirekt, 0 = (yA)x = y(Ax) ≤ yb < 0
# (Ax≤b) nem megoldható => (yA=0, y≥0, yb<0) igen: változók száma szerinti teljes indukcióval (változók száma = A mátrix oszlopainak száma)
** 1 változós eset: ha Ax≤b nem megoldható <big>⇒</big> van egy 0x≤α, α<0 sora, vagy egy x≤α, -x≤β, α+β<0 sora (tehát van triviális ellentmondásos sora, ahol 0<=negatív, vagy pedig olyan sorpárja, amiből a Fourier-Motzkin elimináció triviális ellentmondást csinál). Ha y eze(ke)n a pozíció(ko)n tartalmaz 1-et, a többin 0-t, akkor egy megoldás az második egyenlőtlegségrendszerre.
** n változós eset: ha y megoldás, akkor λy is <big>⇒</big> feltehetjük, hogy yb=-1. Az egyenlőtlenségrendszer tömören: y(A|b)=(0,...,0,-1), y≥0 <big>⇔</big> (A||b) soraiból kifejezhető (0,...,0,-1) nemnegatív együtthatós lineáris kombinációval. (A||b)-re végrehajtva egy eliminációs lépést (A*b*)-ot kapjuk.
*** Mivel (A|b) nem megoldható (ezt feltettük), ezért (A*b*) sem megoldható <big>⇒</big>
*** (0,...,0,-1) kifejezhető (A*|b*) soraiból ≥0 együttható lineáris kombinációval, mivel ez n-1 változós eset <big>⇒</big>
*** (0|A*b*) soraiból is kifejezhető.
*** Mivel a Fourier-Motzkin elimináció pozitív együtthatós lineáris kombinációkat képzett (mivel az elimináció során csak szorozgattuk a sorokat egy konstanssal, vagy átmásoltunk egy sort, vagy összeadtunk 2 sort), így (A|b) soraiból is kifejezhető.

====2. alak====

*Tétel*: (Ax=b, x≥0) és (yA≥0, yb<0) közül pontosan egy megoldható. 
*Biz.*:
# A kettő egyszerre nem megoldható: indirekt, 0 ≤ (yA)x = y(Ax) = yb < 0
# (Ax=b, x≥0) nem megoldható => (yA≥0, yb<0) igen: (Ax=b, x≥0)-t átírjuk (A;-A;-E)x≤(b;-b;0) alakra és alkalmazzuk a lemma első alakját.

====3. alak====

*Tétel*: (yA=c, y≥0) és (Az≥0, cz<0) közül pontosan egy megoldható. 
*Biz.*: A→AT, x→xT=y, y→yT=z, b→bT=c helyettesítésekkel jön a 2. alakból.

<div id="FarkasLemmaKovetkezmeny"></div>
====Következmény egyenletrendszerekre====

*Tétel*:
* (Ax=b) és (yA=0, yb≠0) közül pontosan egy megoldható.
* transzponálva: (yA=c) és (Ax=0, bx≠0) közül pontosan egy megoldható.

===Felülről korlátosság===

*Tétel*: ha ∃z: Az≤0 és cz>0, akkor cx nem felülről korlátos Ax≤b megoldáshalmazán. 
*Biz.*:
* Legyen x0 egy megoldás.
* x0+λz, λ>0 is megoldás, mert A(x0+λz)=A*x0+λ*(A*z)≤A*x0+0≤b.
* c(x0+λz)=cx0+λ(cz) nem korlátos felülről, mert cz>0 és λ tetszőlegesen nagy lehet.

*Tétel*: ha Ax≤b megoldható, a következő 3 feltétel ekvivalens:
# cx felülről korlátos
# ¬∃z: Az≤0 és cz>0
# ∃y: yA=c, y≥0
*Biz.*:
* 1<big>⇒</big>2-t az előbb bizonyítottuk
* 2<big>⇔</big>3 a [[RopiTetel3#3_alak|Farkas-lemma 3. alakjából]] jön annyi változtatással, hogy az Az≥0, cz<0 egyenletrendszernek az ellentettjét kell venni (z→-z helyettesítés).
* 3<big>⇒</big>1: cx=(yA)x=y(Ax)≤yb egy felső korlát.

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

[[Category:Infoszak]]

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

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel3}} ol { margin-top: 0px; margin-bottom: 0px; } ==!! Farkas-lemma (két alakban). A lineáris program célfüggvé…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel3}} ==!! Farkas-lemma (két alakban). A lineáris program célfüggvé…”