Farkas-lemma

A lap ellenőrzött változata (ellenőrizve: 2020. november 21.) ezen a változaton alapul.

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$ $yb=-1$ duál

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 0yb=-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$ .