线性规划

目标函数是线性的,因此它的水平集是相互平行的超平面;当这样一个超平面在凸多面体上滑动时,它离开该区域前触及的最后一点总是一个顶点,而不会是某个面内部的点,因为内部的点总能沿着改进目标函数的方向再往前推进。

由于$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^*}$处取得,命题得证。

对偶性表明,原始的最大化问题与对偶的最小化问题是同一个数值的两种视角:对偶变量$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$。把这两个不等式连起来,对任意可行对都有$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^{*}$成立,强对偶性得证。