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

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

Farkas-lemma

1. alak

• Tétel*: (Ax≤b) és (yA=0, y≥0, yb<0) közül pontosan egy megoldható.
  
• Biz.*:

1. A kettő egyszerre nem megoldható:
   indirekt, 0 = (yA)x = y(Ax) ≤ yb < 0
2. (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ó ⇒ 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 ⇒ feltehetjük, hogy yb=-1. Az egyenlőtlenségrendszer tömören: y(A|b)=(0,...,0,-1), y≥0 ⇔ (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ó ⇒
    • (0,...,0,-1) kifejezhető (A*|b*) soraiból ≥0 együttható lineáris kombinációval, mivel ez n-1 változós eset ⇒
    • (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.*:

1. A kettő egyszerre nem megoldható:
   indirekt, 0 ≤ (yA)x = y(Ax) = yb < 0
2. (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→A^T, x→x^T=y, y→y^T=z, b→b^T=c helyettesítésekkel jön a 2. alakból.

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 x₀ egy megoldás.
• x₀+λz, λ>0 is megoldás, mert A(x₀+λz)=A*x₀+λ*(A*z)≤A*x₀+0≤b.
• c(x₀+λz)=cx₀+λ(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:

1. cx felülről korlátos
2. ¬∃z: Az≤0 és cz>0
3. ∃y: yA=c, y≥0

• Biz.*:
• 1⇒2-t az előbb bizonyítottuk
• 2⇔3 a 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⇒1: cx=(yA)x=y(Ax)≤yb egy felső korlát.

-- Peti - 2006.12.30.