Farkas lemma

lemma

Lemma:

$$\exists x:Ax\le b⟺\nexists 0\le y:yA=0,yb<0,$$

Biz.:
$⟹$
Ha a baloldal megoldható, akkor bármilyen nemnegatív lineáris kombinációja a soroknak is megoldható, tehát nem létezhet ilyen $y$.

$⟸$
t.f.h $\exists x,y$, ekkor:
$yAx=y(Ax)\le yb<0$
$yAx=(yA)x=0$
$⟹0=yAx<0$ ellentmondás.

Dependencies:

• Fourier-Motzkin elimináció