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.

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

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

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

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

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.

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

Bonyolultabb alakok:

• ${\displaystyle \{Px=b_{0},\,Qx\leq b_{1}\}}$ primál és ${\displaystyle \{y_{0}P+y_{1}Q=0,\,y_{1}\geq 0,\,yb=-1\}}$ duál, ahol ${\displaystyle b=(b_{0},b_{1})}$ és ${\displaystyle y=(y_{0},y_{1})}$.
• ${\displaystyle \{Px_{0}+Ax_{1}=b,\,qx_{1}\geq 0\}}$ primál és ${\displaystyle \{yP=0,\,yA\geq 0,\,yb=-1\}}$ duál, ahol ${\displaystyle x=(x_{0},x_{1})}$

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

• ${\displaystyle \{Px_{0}+Ax_{1}=b_{0},\,Qx_{0}+Bx_{1}\leq b_{1},\,x_{1}\geq 0\}}$ primál és ${\displaystyle \{y_{0}P+y_{1}Q=0,\,y_{0}A+y_{1}B\geq 0,\,y_{1}\geq 0,\,yb=-1\}}$ duál, ahol ${\displaystyle x=(x_{0},x_{1})}$, ${\displaystyle b=(b_{0},b_{1})}$ és ${\displaystyle y=(y_{0},y_{1})}$.

Az ${\displaystyle \{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 ${\displaystyle \{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 ${\displaystyle x=(x_{0},x_{1})}$ megoldása.

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

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