Farkas-lemma

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

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 a_i elemét tartalmazza, de a b vektort nem.

Néhány további alak

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

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=(b₀, b₁), és y=(y₀, y₁)

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

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

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=(x₀, x₁), 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

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

• a lineáris és a logikai következmények tétele
• két diszjunkt poliéderhez mindig van őket szigorúan elválasztó hipersík
• Carathéodory-elv
• Helly tétele
• Kirchberger tétele
• sztochasztikus mátrix transzponáltjának egyik sajátértéke az 1 szám
• a dualitástétel

Források

• Frank András: Operációkutatás. (Pdf formátumú egyetemi jegyzet; Cs.elte.hu).