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

Legyen adva egy $A$ mátrix, és egy vele dimenziók szerint összeillő $b$ vektor. Ekkor

• az $\{Ax=b$, $x\ge 0\}$ primál
• és az $\{yA\ge 0$, $yb<0\}$ duál

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

Bizonyítás

Mindkét rendszer nyilván nem oldható meg, hiszen akkor az $x,y$ megoldásokra az $0\le (yA)x=y(Ax)=yb<0$ ellentmondást kapnánk. Ha a primál rendszernek nincs megoldása, akkor a $\{Ax:x\ge 0\}$ generált kúpnak megfelelő metszetkúp nem tartalmazza $b$-t, azaz $b$ nincs benne kúpot definiáló homogén félterek metszetében. Ez csak úgy lehetséges, ha $b$ legalább az egyik ilyen féltérben nincs benne. A féltér a kúp minden elemét tartalmazza, így $A$ oszlopait is. Ezen féltér $y$ normálisa megoldja a duál rendszert, ugyanis az előbbiek szerint $yA\ge 0$ és $yb<0$.

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\ge 0\}$ primál és $\{yA\le 0,yb=-1\}$ duál
• $Qx\le b$ primál és $\{y\ge 0,yQ=0,yb=-1\}$ duál
• $\{Bx\le b,x\ge 0\}$ primál és $\{y\ge 0,yB\ge 0,yb=-1\}$ duál

Bonyolultabb alakok:

• $\{Px=b_0,Qx\le b_1\}$ primál és $\{y_{0}P+y_{1}Q=0,y_1\ge 0,yb=-1\}$ duál, ahol $b=(b_0,b_1)$ és $y=(y_0,y_1)$.
• $\{P{x}_0+A{x}_1=b,q{x}_1\ge 0\}$ primál és $\{yP=0,yA\ge 0,yb=-1\}$ duál, ahol $x=(x_0,x_1)$

Általános alak

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

• $\{P{x}_0+A{x}_1=b_0,Q{x}_0+B{x}_1\le b_1,x_1\ge 0\}$ primál és $\{y_{0}P+y_{1}Q=0,y_{0}A+y_{1}B\ge 0,y_1\ge 0,yb=-1\}$ duál, ahol $x=(x_0,x_1)$, $b=(b_0,b_1)$ és $y=(y_0,y_1)$.

Balról szorzós alak

Az $\{y_{0}P+y_{1}Q=c_0,y_{0}A+y_{1}B\ge c_1,y_1\ge 0\}$ primál rendszer akkor és csak akkor oldható meg, ha a $\{P{x}_0+A{x}_1=0,Q{x}_0+B{x}_1\le 0,x_1\ge 0,c_0{x}_0+c_1{x}_1\ge 0\}$ duál rendszernek nincs $x=(x_0,x_1)$ megoldása.

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