線形計画の双対性

(弱双対性。)$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^{*}$となり、強双対性が証明される。