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 mátrix, és egy vele dimenziók szerint összeillő vektor. Ekkor az , primál és az , 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 megoldásokra az ellentmondást kapnánk. Ha a primál rendszernek nincs megoldása, akkor a generált kúpnak megfelelő metszetkúp nem tartalmazza -t, azaz nincs benne kúpot definiáló homogén félterek metszetében. Ez csak úgy lehetséges, ha legalább az egyik ilyen féltérben nincs benne. A féltér a kúp minden elemét tartalmazza, így oszlopait is. Ezen féltér normálisa megoldja a duál rendszert, ugyanis az előbbiek szerint és .
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.
primál és duál primál és duál primál és duál
Bonyolultabb alakok: primál és duál, ahol és . primál és duál, ahol
Általános alak A Fredholm-alternatíva és a Farkas-lemma közös általánosítása:
primál és duál, ahol , és .
Balról szorzós alak Az primál rendszer akkor és csak akkor oldható meg, ha a duál rendszernek nincs 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).
Kategória:Matematikai tételek Kategória:Lineáris programozás Kategória:Lemmák