形式陈述

单纯形法把标准形线性规划的基可行解视为多面体顶点，通过选入变量和离开变量的枢轴操作沿边移动，使目标不劣。若发现所有约化成本满足最优性符号条件则停止；若存在改善方向而比值检验无离开变量，则目标无界。退化时目标可能不变，需 Bland 规则等防止循环。

直觉

最优线性目标可以在某个顶点取得，因此算法不扫描整个连续区域，而在相邻顶点间选择改进方向。

例子与边界

松弛变量把 $Ax\le b$ 化为等式并给出初始基；没有显然基可行解时需两阶段法。单纯形法实践中常很快，但存在指数步坏例；它不是已知的多项式时间保证算法。浮点实现还需处理容差、缩放和数值退化。

推论与应用

单纯形法用于大规模工业规划、敏感性分析和暖启动，其基与约化成本也揭示原始—对偶结构。

参考资料

• 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。