線形計画法

$c\cdot x$ の値の集合 $T:=\{c\cdot x\mid x\in P\}\subset\mathbb{R}$ は、多面体 $P$ の線形写像 $x\mapsto c\cdot x$ による像なので、多面体 の記事の系「多面体の線形写像による像」により $\mathbb{R}$ の多面体である。すなわち有限個の不等式 $\alpha_kt\le\beta_k$ の解の全体であり、閉区間・閉半直線・$\mathbb{R}$・1 点・空集合のいずれかで、とくに閉集合である。仮定より $T$ は空でなく上に有界なので、上限 $v^*:=\sup T$ は有限で、$T$ が閉であることから $v^*\in T$ である。$v^*=c\cdot x^*$ となる $x^*\in P$ が最適解である。$\square$

最適値を $v^*$ とし、最適解の全体 $F:=P\cap\{x\mid c\cdot x=v^*\}$ を考える。$F$ は $P$ を表す不等式に $c\cdot x\le v^*$ と $-c\cdot x\le-v^*$ を加えた空でない多面体で、$P$ に含まれるので直線を含まない。多面体 の記事の定理「頂点をもつための条件」により $F$ は頂点 $w$ をもち、同じ記事の定理「頂点の特徴づけ」により $w$ は $F$ の端点である。
$w$ が $P$ の端点であることを示す。$w=(1-t)y+tz$（$y,z\in P$、$0< t< 1$）とすると、$c\cdot y\le v^*$、$c\cdot z\le v^*$ で、$(1-t)c\cdot y+tc\cdot z=c\cdot w=v^*$ だから $c\cdot y=c\cdot z=v^*$、すなわち $y,z\in F$ である。$w$ は $F$ の端点なので $y=z=w$ である。よって $w$ は $P$ の端点であり、「頂点の特徴づけ」により $P$ の頂点である。頂点が有限個であることは同じ記事の系「頂点は有限個」による。$\square$

両方が成り立つとすると、$y\ge0$ と $Ax\le b$ から $0=(A^{\mathsf T}y)\cdot x=y\cdot(Ax)\le y\cdot b<0$ となって矛盾する。
1 が成り立たないとして 2 を示す。多面体 の記事の定理「Fourier–Motzkin の消去法」で $x_n,x_{n-1},\dots,x_1$ を順に消去する。各段で得られる不等式系の解の全体は、前の段の多面体の射影なので、前の段の系に解があることと次の段の系に解があることは同値である。また、各段の不等式はその前の段の不等式に $0$ 以上の係数を掛けて足したものなので、帰納的に、どの段の不等式もある $y\ge0$ を用いて $(A^{\mathsf T}y)\cdot x\le b\cdot y$ と書け、すでに消去した変数の係数は $0$ である。すべての変数を消去すると、変数を含まない不等式 $0\le b\cdot y^{(k)}$（$y^{(k)}\ge0$、$A^{\mathsf T}y^{(k)}=0$、$k=1,\dots,K$）の系が残る。もとの系に解がないので、この最後の系は成り立たない（最後の段は同じ定理の $n=1$ の場合の読み方による）。すなわちある $k$ で $b\cdot y^{(k)}<0$ であり、$y:=y^{(k)}$ が 2 を満たす。$\square$

要点：1 を不等式 $Ax\le b$、$-Ax\le-b$、$-x\le0$ の系に書き直して thm-lp-farkas を当て、最初の 2 つに掛ける乗数の差を $y$ とする。

$x\ge0$ と $A^{\mathsf T}y\ge c$ から $c\cdot x\le(A^{\mathsf T}y)\cdot x$、$y\ge0$ と $Ax\le b$ から $y\cdot(Ax)\le y\cdot b$ であり、$(A^{\mathsf T}y)\cdot x=y\cdot(Ax)$ なので $c\cdot x\le b\cdot y$ である。$c\cdot x=b\cdot y$ なら、(P) の任意の実行可能解 $x'$ について $c\cdot x'\le b\cdot y=c\cdot x$ なので $x$ は最適であり、$y$ も同様である。$\square$

$(x,y)\in\mathbb{R}^{n+m}$ についての不等式系
$$ Ax\le b,\qquad -x\le0,\qquad -A^{\mathsf T}y\le-c,\qquad -y\le0,\qquad -c\cdot x+b\cdot y\le0 $$
に解があれば、$x$ は (P)、$y$ は (D) の実行可能解で $b\cdot y\le c\cdot x$ である。prop-lp-weak と合わせて $c\cdot x=b\cdot y$ となり、$x,y$ は最適解で最適値は等しい。
そこで、この系に解がないと仮定して矛盾を導く。thm-lp-farkas により、5 つの不等式に掛ける乗数 $p\in\mathbb{R}^m$、$q\in\mathbb{R}^n$、$r\in\mathbb{R}^n$、$s\in\mathbb{R}^m$、$\tau\in\mathbb{R}$（すべて $\ge0$）で、$x$ の係数・$y$ の係数が $0$ で右辺が負になるもの
$$ A^{\mathsf T}p-q-\tau c=0,\qquad -Ar-s+\tau b=0,\qquad b\cdot p-c\cdot r<0 $$
がある。$q,s\ge0$ なので $A^{\mathsf T}p\ge\tau c$、$Ar\le\tau b$ である。
$\tau>0$ の場合：$\bar x:=r/\tau$ は $A\bar x\le b$、$\bar x\ge0$ を満たし、$\bar y:=p/\tau$ は $A^{\mathsf T}\bar y\ge c$、$\bar y\ge0$ を満たす。prop-lp-weak により $c\cdot\bar x\le b\cdot\bar y$、すなわち $c\cdot r\le b\cdot p$ であり、$b\cdot p-c\cdot r<0$ に反する。
$\tau=0$ の場合：$A^{\mathsf T}p\ge0$、$Ar\le0$ である。(P)、(D) の実行可能解 $x_0$、$y_0$ をとると、
$$ b\cdot p\ge(Ax_0)\cdot p=x_0\cdot(A^{\mathsf T}p)\ge0,\qquad c\cdot r\le(A^{\mathsf T}y_0)\cdot r=y_0\cdot(Ar)\le0 $$
（$p\ge0$ と $Ax_0\le b$、$x_0\ge0$ と $A^{\mathsf T}p\ge0$、$r\ge0$ と $A^{\mathsf T}y_0\ge c$、$y_0\ge0$ と $Ar\le0$ を使った）なので $b\cdot p-c\cdot r\ge0$ となり、やはり矛盾する。$\square$

要点：(D) が実行不可能なら Farkas の補題から $r\ge0$、$Ar\le0$、$c\cdot r>0$ となる $r$ が得られ、実行可能解を $r$ の向きに動かすと目的関数がいくらでも大きくなる。2 は双対問題に 1 を当てる。

要点：$b\cdot y-c\cdot x=y\cdot(b-Ax)+x\cdot(A^{\mathsf T}y-c)$ で右辺の 2 項は $0$ 以上なので、双対定理と弱双対性から従う。

要点：1 は、$w_N$ を自由に選べることから係数を比べる。2 は、基底解で $0$ になる $n$ 個の変数が $n$ 本の活性な制約に対応し、辞書によりそれらの等式の解がただ 1 つになることによる。3・4 は、実行可能解では $w\ge0$ であることを $z$ の式に入れる。

要点：比 $\beta_i/\alpha_{ik}$ が最小の行を選ぶので、新しい定数項は $0$ 以上のまま残る。

仮定より定数項 $\zeta$ は各ピボットで真に増える。prop-lp-dictionary の 1 により辞書は基底で決まるので、同じ基底は 2 度現れない。基底は高々 $\binom{n+m}{m}$ 通りなので、ピボットは有限回で止まり、止まったときは prop-lp-dictionary の 3 か 4 が当てはまる。$\square$

要点：成分を正にずらし、「最大化 $\mathbf 1\cdot w$、条件 $Mw\le\mathbf 1$、$w\ge0$」とその双対問題に双対定理を当てる。共通の最適値 $V$ で最適解を割ると、両プレイヤーの最適な確率ベクトルが得られ、ゲームの値は $1/V$ である。