線形計画法

目的関数は線形であるため、そのレベル集合は互いに平行な超平面である。そのような超平面を凸多面体上でスライドさせるとき、領域を離れる直前に触れる最後の点は常に頂点であり、面の内部の点になることはない。なぜなら、内部の点は常に目的関数を改善する方向にさらに押し進めることができるからである。

$P$は有限個の線形不等式で定義された有界な多面体であるから、有限個の頂点$v_1,\ldots,v_k$を持ち、多面体に関する古典的な事実(ミンコフスキーの定理)により、$P$のすべての点はこれらの頂点の凸結合として表される:$x=\sum_{i=1}^{k}\lambda_i v_i$、ここで$\lambda_i\ge 0$かつ$\sum_i \lambda_i=1$である。

目的関数$c^{\mathsf{T}}x$は線形であるから、そのような凸結合上でこれを評価すると$c^{\mathsf{T}}x=\sum_i \lambda_i\left(c^{\mathsf{T}}v_i\right)\le \left(\max_i c^{\mathsf{T}}v_i\right)\sum_i\lambda_i=\max_i c^{\mathsf{T}}v_i$が得られる。これは各$\lambda_i\ge 0$であり、それらの和が$1$になるからである。

これは、すべての実行可能な$x$の目的関数値が最良の頂点値$\max_i c^{\mathsf{T}}v_i$を超えないことを示す。しかし、その最良の頂点、$v_{i^*}$と呼ぶことにすると、それ自体が$P$の実行可能点であるから、実際にこの上界を達成する:$c^{\mathsf{T}}v_{i^*}=\max_{x\in P} c^{\mathsf{T}}x$。したがって、線形計画問題の最適値は頂点$v_{i^*}$で達成され、主張が証明される。

双対性は、主問題の最大化と双対問題の最小化が同じ数値に対する2つの見方であることを述べている:双対変数$y$は資源の価格として働き、弱双対性は、どんな有効な価格付けのもとでも、実行可能などの生産計画もそれが使う資源の価値以上には決して稼げないことを述べ、強双対性は、最適点において最良の生産計画と最も安い有効な価格付けがちょうど一致することを述べる。

(弱双対性。)$x$を主問題の任意の実行可能点($Ax\le b$、$x\ge 0$)とし、$y$を双対問題の任意の実行可能点($A^{\mathsf{T}}y\ge c$、$y\ge 0$)とする。$x\ge 0$と$A^{\mathsf{T}}y\ge c$より、この不等式に非負ベクトル$x$を掛けても向きは変わらない:$c^{\mathsf{T}}x\le \left(A^{\mathsf{T}}y\right)^{\mathsf{T}}x=y^{\mathsf{T}}Ax$。$y\ge 0$と$Ax\le b$より、同様の議論から$y^{\mathsf{T}}Ax\le y^{\mathsf{T}}b=b^{\mathsf{T}}y$が得られる。この2つの不等式をつなげると、任意の実行可能な組について$c^{\mathsf{T}}x\le b^{\mathsf{T}}y$が成り立ち、これが弱双対性である。

(強双対性。)主問題に対してシンプレックス法を実行し、最適基底行列$B$を持つ最適な基底実行可能解$x^{*}$で終了するとする。このとき$x^{*}_B=B^{-1}b$が成り立ち、非基底変数の被約費用はすべて非負である——この終了条件は$y^{*\mathsf{T}}=c_B^{\mathsf{T}}B^{-1}$を定義することと同値であり、これが$A^{\mathsf{T}}y^{*}\ge c$と$y^{*}\ge 0$を満たすこと、すなわち$y^{*}$が双対実行可能であることを確認できる。

代入すると、主問題の最適値は$c^{\mathsf{T}}x^{*}=c_B^{\mathsf{T}}x^{*}_B=c_B^{\mathsf{T}}B^{-1}b=y^{*\mathsf{T}}b=b^{\mathsf{T}}y^{*}$となる。弱双対性(常に$c^{\mathsf{T}}x^{*}\le b^{\mathsf{T}}y^{*}$が成り立つ)と組み合わせると、ここでの等号は$y^{*}$もまた双対最適解であることを強制し、したがって$c^{\mathsf{T}}x^{*}=b^{\mathsf{T}}y^{*}$となり、強双対性が証明される。