线性规划基本定理

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