概念

单纯形法

丹齐格 1947 年提出的经典算法：在基可行解之间沿边转轴移动直到最优，实际中效率极高，至今仍是求解线性规划的主力。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

已是本主题的起点

单纯形法运筹学

01定义

单纯形法是多面体上的「顶点漫步」：线性规划的最优解必在可行多面体的顶点达到，算法沿目标函数改善的边在基可行解之间转轴，直到最优。丹齐格 1947 年的这一发明让线性规划从理论走向工业实践。

单纯形法：沿多面体的边走向最优顶点

约束 $Ax=b$ 选 $m$ 个基变量得一个顶点；转轴（pivot）换入一个非基变量、换出一个基变量，即沿边移动到相邻顶点。比值检验保证不越界，检验数判断最优。

无现成初始基可行解时：第一阶段引入人工变量求一个可行起点；第二阶段从该起点优化原目标——处理「可行域可能为空」的标准流程。

Klee-Minty 立方体构造出指数步的坏例，但实践中单纯形法常快于多项式算法；平滑分析（Spielman-Teng）解释了「噪声下的多项式期望」这一悖论。

\max\ c^Tx\ \ \text{s.t.}\ Ax=b,\ x\geq 0,\quad \text{检验数}\ c_N-c_BB^{-1}N\leq 0\Rightarrow\text{最优}

丹齐格 1947 年发明单纯形法并用于美国空军规划；坎托罗维奇 1939 年已独立提出相关思想，二人分获 1975 年诺贝尔经济学奖（坎氏）与运筹学界最高荣誉。

航空排班与物流路径、炼油厂混合调度、供应链生产计划、军用物资调配——至今仍是商用求解器的默认主力算法。

单纯形法：沿可行域顶点迭代max 2x₁ + x₂ s.t. x₁ ≤ 3, x₂ ≤ 3, x₁ + x₂ ≤ 4：顶点路径 (0,0) → (3,0) → (3,1)

迭代步0