Farkasの補題と線形計画問題の双対定理

まず$1\wedge 2$は成り立たないことを示す．
$(\mathrm{\neg }1\Rightarrow 2)$
$1$が成り立たないとする．$S:=\{y\in {\mathbb{R}}^m|\mathrm{\exists }x\in {\mathbb{R}}^n,y=Ax,x\ge 0\}$は閉凸集合であることは容易に確かめられる．よって，$b\notin S$であるから 分離超平面定理 より，$\mathrm{\forall }y\in S,⟨a,b⟩>\alpha \ge ⟨a,y⟩$となるような$a\in {\mathbb{R}}^m\setminus \{0\}$と$\alpha \in \mathbb{R}$が存在する．
証明のイメージ図：ベクトル$a_i(i=1,\cdots ,n)$はそれぞれ，基底$e_i(i=1,\cdots ,n)$を行列$A$で写したもの．
ここで$0\in S$と$y\in S$の任意性により$⟨a,b⟩>\alpha \ge 0$なので，$⟨a,b⟩>0$がわかる．

$(1\Rightarrow \mathrm{\neg }2)$
$1\wedge 2$が偽であることを確かめるため，真であると仮定して，背理法を用いる．実際，$0=⟨x,A^{t}y⟩=⟨Ax,y⟩\le ⟨b,y⟩<0$となって矛盾が生じるので命題は確かめられた．
$(2\Rightarrow \mathrm{\neg }1)$
$2$すなわち，$\mathrm{\exists }y\in {\mathbb{R}}^m,A^{t}y=0,⟨b,y⟩<0,I_{m}y=y\ge 0$を仮定する．ただし，$I_m$は$m$次単位行列．
そこで上の仮定から，
$$\begin{array}{rl}& \mathrm{\exists }y\in {\mathbb{R}}^m,\left[\begin{array}{c}{A}^t\\ I_m\end{array}\right]y\ge 0,⟨b,y⟩<0\cdots (\ast )\text{が従うので，}\\ (\ast )⟺& \nexists (x,\lambda )\in {\mathbb{R}}^n\times {\mathbb{R}}^m,{\left[\begin{array}{c}{A}^t\\ I_m\end{array}\right]}^t\left[\begin{array}{c}x\\ \lambda \end{array}\right]=\left[\begin{array}{cc}A& I_m\end{array}\right]\left[\begin{array}{c}x\\ \lambda \end{array}\right]=b,\left[\begin{array}{c}x\\ \lambda \end{array}\right]\ge 0\leftarrow (\because \text{Farkasの補題})\\ ⟺& \nexists (x,\lambda )\in {\mathbb{R}}^n\times {\mathbb{R}}^m,Ax+\lambda =b,x\ge 0,\lambda \ge 0\\ ⟺& \nexists x\in {\mathbb{R}}^n,Ax\le b,x\ge 0\end{array}$$となり，$2$から$\mathrm{\neg }1$が導かれた．$◻$

$$\begin{array}{rl}{x}^M& :(P)\text{の実行可能解}\\ y^m& :(D)\text{の実行可能解}\\ & \text{と仮定する．このとき，}\\ max(P)& =⟨c,x^M⟩\\ & \le ⟨A^t{y}^m,x^M⟩\leftarrow (\because x^M\ge 0,A^t{y}^m\ge c)\\ & =⟨A{x}^M,y^m⟩\\ & \le ⟨b,y^m⟩\leftarrow (\because y^m\ge 0,A{x}^M\le b)\\ & =min(D).\end{array}$$ $◻$

主問題(P)もその双対問題(D)もともに実行可能解をもつと仮定する．このとき弱双対定理から$max(P)\le min(D)$は既知なので，$max(P)<min(D)$とならないことを示す．
背理法を用いて$max(P)<min(D)=:\gamma$を仮定する．このとき，$max(P)<\gamma$より，
$$\begin{array}{rl}& \nexists \overline{x}\in {\mathbb{R}}^n,c^t\overline{x}=⟨c,\overline{x}⟩\ge \gamma ,A\overline{x}\le b,\overline{x}\ge 0\\ ⟺& \nexists \overline{x}\in {\mathbb{R}}^n,(-c{)}^t\overline{x}\le -\gamma ,A\overline{x}\le b,\overline{x}\ge 0\\ ⟹& \mathrm{\exists }(\overline{y},\lambda )\in {\mathbb{R}}^m\times \mathbb{R},{\left[\begin{array}{c}A\\ -c^t\end{array}\right]}^t\left[\begin{array}{c}\overline{y}\\ \lambda \end{array}\right]=\left[\begin{array}{cc}{A}^t& -c\end{array}\right]\left[\begin{array}{c}\overline{y}\\ \lambda \end{array}\right]=0,\\ & {\left[\begin{array}{c}b\\ -\gamma \end{array}\right]}^t\left[\begin{array}{c}\overline{y}\\ \lambda \end{array}\right]\ge 0,\left[\begin{array}{c}\overline{y}\\ \lambda \end{array}\right]\ge 0\\ & (\because \text{Farkasの補題 系})\\ ⟺& \mathrm{\exists }\overline{y}\in {\mathbb{R}}^m,\mathrm{\exists }\lambda \in \mathbb{R},A^t\overline{y}=\lambda c,⟨b,\overline{y}⟩<\lambda \gamma ,\overline{y}\ge 0,\lambda \ge 0\cdots (\ast \ast )\end{array}$$が従う．

1. $\lambda =0$のとき
   $$\begin{array}{rl}(\ast \ast )⟺& \mathrm{\exists }\overline{y}\in {\mathbb{R}}^m,A^t\overline{y}=0,⟨b,\overline{y}⟩<0,\overline{y}\ge 0\\ ⟺& \nexists x^{\prime }\in {\mathbb{R}}^n,A{x}^{\prime }\le b,x^{\prime }\ge 0(\because \text{Farkasの補題 系})\end{array}$$
   となって，主問題(P)が実行可能であるということに反する．
2. $\lambda >0$のとき
   $$\begin{array}{rl}(\ast \ast )⟹\mathrm{\exists }\overline{y}/\lambda \in {\mathbb{R}}^m,A^t(\overline{y}/\lambda )=c,⟨b,\overline{y}/\lambda ⟩& <\gamma \\ & =max(P)\\ & \le min(D)(\because \text{弱双対定理})\end{array}$$
   が導出され，$\overline{y}/\lambda$が双対問題(D)の実行可能領域にあるので，$⟨b,\overline{y}/\lambda ⟩<min(D)$は矛盾．

したがって(1),(2)両方とも矛盾が生じたので，$max(P)<min(D)$は成り立たず，弱双対定理から$max(P)=min(D)$が成立．$◻$