Farkas-lemma

A Wikipédiából, a szabad enciklopédiából

A Farkas-lemma a lineáris programozás fontos tétele, amelynek sokféle alakja van. A Fredholm-alternatíva általánosításának is tekinthető. Farkas Gyula magyar matematikus-fizikus dolgozta ki és publikálta 1902-ben. Harold W. Kuhn és Albert W. Tucker amerikai matematikusok fél évszázad elteltével, 1950-ben ismerték fel a lemma jelentőségét, amely a lineáris optimalizáláselmélet egyik alaptétele lett.

Standard alak[szerkesztés | forrásszöveg szerkesztése]

Adva legyen a dimenziók szerint összeillő A mátrix és a b vektor. Ekkor

  • az Ax=b x \geq 0 primál
  • és az yA \geq 0 yb<0 duál

rendszerek közül pontosan az egyik oldható meg.

Bizonyítás: Ha b nincs az A oszlopai által generált kúpban, akkor van egy homogén féltér, ami a kúp minden ai elemét tartalmazza, de a b vektort nem.

Néhány további alak[szerkesztés | forrásszöveg szerkesztése]

A tételt sokféle alakban használják. Ezek mindegyike levezethető a standard alakból. Mindegyikben a primál feladat akkor és csak akkor oldható meg, ha nincs duál megoldás.

  • Ax=b x \geq 0 primál
  • és yA \leq 0 yb=-1 duál
  • Qx \leq b primál
  • és y \geq 0 yQ=0 yb=-1 duál
  • Bx \leq d x \geq 0 primál
  • és y \geq 0 yB \geq 0

Bonyolultabb alakok[szerkesztés | forrásszöveg szerkesztése]

A Fredholm-alternatíva és a Farkas-lemma közös általánosítása:

  • Px_0+Ax_1=b_0 Qx_0+Bx_1 \leq b_1 x_1 \geq 0 primál
  • y_0 P+y_1 Q=0 y_0 A+y_1 B\geq 0 y_1 \geq 0 yb=-1 duál

akkor és csak akkor oldható meg a primál feladat, ha nincs duál megoldás.

  • Px=b_0 Qx \leq b_1 primál
  • y_0 P+y_1 Q=0 y_1 \geq 0 yb=-1 duál,

ahol b=(b0, b1), és y=(y0, y1)

közül pontosan egy oldható meg.

  • Px_0+Ax_1=b x_1 \geq 0 primál
  • yP=0 yA \geq 0 yb=-1 duál

Általános alak[szerkesztés | forrásszöveg szerkesztése]

A Px_0+Ax_1=b_0 Qx_0+Bx_1 \leq b_1 x_1 \geq 0 primál feladat pontosan akkor oldható meg, ha nincs duál megoldás:

y=(y_0,y_1) y_0 P+y_1 Q =0 y_1 \geq 0 yb=-1, ahol b=(b_0, b_1).

Balról szorzós alak[szerkesztés | forrásszöveg szerkesztése]

Az y_0 P+y_1 Q=c_0 y_0 A+y_1 B \geq c_1 y_1 \geq 0 primál rendszer akkor és csak akkor megoldható, ha nincs x=(x0, x1), amire Px_0+Ax_1=0 Qx_0+Bx_1 \leq 0 x_1 \geq 0 és c_0 x_0+c_1 x_1 \geq 0.

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

A tétel segítségével bizonyítható például:

Források[szerkesztés | forrásszöveg szerkesztése]