Farkas' Lemma

以下の線形不等式系のいずれか一方のみが解を持つ。
1. $A x = b, x \ge \boldsymbol{0}$
2. $A^{T} y \ge \boldsymbol{0}, b^{T} y < 0$

（1.が成立するなら、2.が成立しない。）

$\begin{aligned} 0 &\le (Ax)^{T} y\\ &= b^{T} y_1 \\ &< 0 \end{aligned}$

より示される。

（1.が成立しないなら、2.が成立する）
$A x = b, x < \boldsymbol{0}$に対して、

$\begin{aligned} 0 &\ge (Ax)^{T} y\\ &= b^{T} y_1 \\ &< 0 \end{aligned}$

となる。$y = -b(\neq \boldsymbol{0})$ととれば、2.は成立する。また、$b = \boldsymbol{0}$のとき$x = 0$とすれば1.を満たすため、考えなくても良い。

定理の参考文献：並木誠, 線形計画法, 朝倉書店, （応用最適化シリーズ, 1）, 朝倉書店(2008).