单纯形法

单纯形法 (Simplex Method)

单纯形法由美国数学家乔治·丹齐格在1947年提出，是运筹学和最优化理论中求解线性规划问题的最基础算法。核心思想是在可行域的顶点之间迭代搜索，每步移动到使目标函数值更优的相邻顶点，直至找到最优解。

标准形式

最大化问题标准形式：目标函数最大化，约束为“$\le$”不等式，所有变量非负。引入松弛变量将不等式转为等式：

最大化：$Z = c_1 x_1 + \cdots + c_n x_n$，服从于：$\sum a_{ij} x_j + s_i = b_i$，$x_j, s_i \ge 0$。

算法核心逻辑

几何：可行域是凸多胞体，最优解在顶点上。从起始顶点开始沿改善方向移动，重复至无法改善。

代数：基本可行解 (BFS)：$m$ 个约束，$n+m$ 个变量，$n$ 个非基变量设为0，解出 $m$ 个基变量。旋转 (Pivoting) 操作实现BFS间转换。

迭代步骤（示例）

最大化 $Z = 3x_1 + 5x_2$，约束：$x_1 \le 4$, $2x_2 \le 12$, $3x_1 + 2x_2 \le 18$。

引入松弛变量 $s_1, s_2, s_3$。初始单纯形表：

1. 最优性检查：Z行有负数就未达最优
2. 选入基变量：选Z行最负系数的变量（$x_2$, -5）
3. 选出基变量：最小比率测试——RHS / 主列正系数，选最小者（$s_2$ 行，12/2=6）
4. 旋转操作：主元2，用高斯消元法变换
5. 重复：Z行仍有 -3，选 $x_1$ 入基，$s_3$ 出基（6/3=2），旋转
6. 终止：Z行系数全部非负 → 最优解 $x_1 = 2$, $x_2 = 6$, $Z = 36$

特殊情况

• 无界解：主列所有元素 ≤ 0，目标函数可无限增大
• 退化：最小比率测试平局，基变量值为0，可能循环（布兰德规则可避免）
• 多重最优解：非基变量Z行系数为0，入基不改变最优值
• 不可行问题：需人工变量和两阶段法/大M法处理≥或=约束

单纯形法在实践中效率极高，其背后的对偶理论和灵敏度分析为经济决策和管理提供深刻洞察。