线性规划的对偶性

(弱对偶性。)设$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$。把这两个不等式连起来,对任意可行对都有$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^{*}$成立,强对偶性得证。