形式陈述

线性规划在实向量 $x$ 上优化线性目标，例如

$$min{c}^{T}x\text{s.t. }Ax\le b,$$

也可含等式和符号约束。可行域是闭凸多面体。若可行域非空且目标在其上有有限下确界，则最优值能够取到。若可行多面体是 pointed 的（等价地，在非空情形下含极点），则至少有一个最优极点；若可行域含直线，例如最优面本身是一条仿射直线，则可能没有任何极点，非退化性并不是这里所需的条件。每个有限维线性规划都有对偶：弱对偶总成立；若原问题可行且有有限最优值，则对偶也有同一有限最优值并能取到，反之亦然。

直觉

线性约束切出一个多面体，线性目标的等值超平面沿一个方向平移，最后接触可行域的位置给出最优值。

例子与边界

生产计划可用变量表示产品数量、资源不等式表示容量、利润作为目标。整数变量约束会把问题变成整数规划，复杂性和几何性质显著变化。无界可行域不必导致目标无界；退化极点可能对应多个基，也可能使单纯形枢轴停滞。

推论与应用

线性规划是网络流、匹配、调度和近似算法的核心工具，也通过对偶变量提供价格解释和最优性证书。

参考资料

• Bernhard Korte and Jens Vygen, Combinatorial Optimization, 6th ed., Springer, 2018，Chs. 4–11。
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。