線形計画法の基本定理

$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^*}$で達成され、主張が証明される。