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

Mindkét rendszer nyilván nem oldható meg, hiszen akkor az $x,\,y$ megoldásokra az $0\leq (yA)x=y(Ax)=yb<0$ ellentmondást kapnánk. Ha a primál rendszernek nincs megoldása, akkor a $\{Ax:x\geq 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\geq 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\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 b,\,x\geq 0\}$ primál és $\{y\geq 0,\,yB\geq 0,\,yb=-1\}$ duál

Bonyolultabb alakok:

• $\{Px=b_{0},\,Qx\leq b_{1}\}$ primál és $\{y_{0}P+y_{1}Q=0,\,y_{1}\geq 0,\,yb=-1\}$ duál, ahol $b=(b_{0},b_{1})$ és $y=(y_{0},y_{1})$.
• $\{Px_{0}+Ax_{1}=b,\,qx_{1}\geq 0\}$ primál és $\{yP=0,\,yA\geq 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:

• $\{Px_{0}+Ax_{1}=b_{0},\,Qx_{0}+Bx_{1}\leq b_{1},\,x_{1}\geq 0\}$ primál és $\{y_{0}P+y_{1}Q=0,\,y_{0}A+y_{1}B\geq 0,\,y_{1}\geq 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\geq c_{1},\,y_{1}\geq 0\}$ primál rendszer akkor és csak akkor oldható meg, ha a $\{Px_{0}+Ax_{1}=0,\,Qx_{0}+Bx_{1}\leq 0,\,x_{1}\geq 0,\,c_{0}x_{0}+c_{1}x_{1}\geq 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).