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]

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

  • az primál
  • és az 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]

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.

  • primál
  • és duál
  • primál
  • és duál
  • primál
  • és

Bonyolultabb alakok[szerkesztés]

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

  • primál
  • duál

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

  • primál
  • duál,

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

közül pontosan egy oldható meg.

  • primál
  • duál

Általános alak[szerkesztés]

A primál feladat pontosan akkor oldható meg, ha nincs duál megoldás:

, ahol b=(b_0, b_1).

Balról szorzós alak[szerkesztés]

Az primál rendszer akkor és csak akkor megoldható, ha nincs x=(x0, x1), amire és .

Alkalmazások[szerkesztés]

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

Források[szerkesztés]