单纯形法

单纯形法（simplex method）是求解线性规划的一类算法。它把约束改写成等式，选择一组变量作为基变量，在保持可行的条件下更换这组变量，使目标值逐步改善。几何上，这通常表现为沿可行多面体的边从一个顶点走到另一个顶点；退化时，更换基并不一定改变所在的点。

算法的核心不是背诵一张表的加减规则，而是回答三个问题：增加哪个变量能够改善目标；增加到哪里仍然可行；什么时候能证明再也没有更好的方案。

用剩余资源建立初始状态

沿用线性规划中的两产品教学模型。产量 $x,y$ 可以连续取值，收益和资源都按该模型约定的单位计算： $$maxz=3x+2y,x+y\le 4,2x+y\le 5,x,y\ge 0.$$ 引入非负的松弛变量 $s_1,s_2$，分别表示两种资源剩余量： $$x+y+s_1=4,2x+y+s_2=5.$$ 令 $x=y=0$ 时，$s_1=4,s_2=5$。这是一个可行生产方案，尚未消耗任何资源。

把约束解成当前基变量的表达式，称为一种字典： $$\begin{array}{cc}{s}_1& =4-x-y,\\ s_2& =5-2x-y,\\ z& =3x+2y.\end{array}$$ 当前基变量是 $s_1,s_2$，非基变量是 $x,y$。令非基变量为零，就读出当前解。称它为“基”，是因为在两个独立方程中，所选两列线性无关，能够据此解出对应的两个变量。

第一步：为什么要取最小比值

先让 $x$ 从零增加，保持另一非基变量 $y=0$。每增加一个单位 $x$，目标增加三；两种剩余资源却分别减少一个和两个单位。

若增加量为 $\theta \ge 0$，就有 $$s_1=4-\theta \ge 0,s_2=5-2\theta \ge 0.$$ 所以同时要求 $\theta \le 4$、$\theta \le 5/2$。能走的最大距离是两者的最小值 $5/2$。在这里，第二种资源先用尽。

先到零的剩余资源限制步长。图中二点五之后的延长虚线只用来显示违规方向，不属于本步可行范围。

因此新状态为 $x=5/2,y=0,s_1=3/2,s_2=0$，收益为 $15/2$。$x$ 进入基，$s_2$ 离开基。

这说明了最小比值检验的原因：每一个正在减少的基变量，都给出“目前有多少/每步减少多少”的上限，必须遵守最紧的那个。若某基变量随着进入变量增加而上升，或者保持不变，它就没有给出这种上限，不能把零或负的下降系数放进比值比较。

换基就是保持等价的消元

从 $s_2=5-2x-y$ 解出进入变量： $$x=\frac{5}{2}-\frac{1}{2}y-\frac{1}{2}{s}_2.$$ 代入其余两式。第一种剩余资源变为 $$s_1=4-(\frac{5}{2}-\frac{1}{2}y-\frac{1}{2}{s}_2)-y=\frac{3}{2}-\frac{1}{2}y+\frac{1}{2}{s}_2.$$ 目标式也必须同时更新： $$z=3(\frac{5}{2}-\frac{1}{2}y-\frac{1}{2}{s}_2)+2y=\frac{15}{2}+\frac{1}{2}y-\frac{3}{2}{s}_2.$$ 于是新字典是 $$\begin{array}{cc}x& =\frac{5}{2}-\frac{1}{2}y-\frac{1}{2}{s}_2,\\ s_1& =\frac{3}{2}-\frac{1}{2}y+\frac{1}{2}{s}_2,\\ z& =\frac{15}{2}+\frac{1}{2}y-\frac{3}{2}{s}_2.\end{array}$$ 这次消元也称枢轴变换。没有更换原问题，只是换了求解方程时作为输出的变量。

现在 $y$ 的目标系数为 $1/2$，表示在保持新的非基变量 $s_2=0$ 时，沿这条边每增加一个单位 $y$ 的净收益。它已计入相应减少 $x$ 的损失，不再是原始单位收益二。这种调整后的系数称为检验数或约化成本；本文统一把字典右侧能使最大化目标上升的正系数视为可改进方向。

第二步到达最优点

保持 $s_2=0$，增加 $y=\theta$。两个基变量的非负性给出 $$x=\frac{5}{2}-\frac{1}{2}\theta \ge 0⟹\theta \le 5,$$ $$s_1=\frac{3}{2}-\frac{1}{2}\theta \ge 0⟹\theta \le 3.$$ 所以 $y$ 最多增加三，$s_1$ 离开基。由 $s_1=3/2-y/2+s_2/2$ 解得 $$y=3-2s_1+s_2.$$ 代回 $x$ 和 $z$，逐项整理： $$\begin{array}{cc}x& =\frac{5}{2}-\frac{1}{2}(3-2s_1+s_2)-\frac{1}{2}{s}_2=1+s_1-s_2,\\ z& =\frac{15}{2}+\frac{1}{2}(3-2s_1+s_2)-\frac{3}{2}{s}_2=9-s_1-s_2.\end{array}$$ 最终字典为 $$x=1+s_1-s_2,y=3-2s_1+s_2,z=9-s_1-s_2.$$ 令非基变量 $s_1=s_2=0$，得到 $(x,y)=(1,3)$，收益九。

箭头连接的是可行状态。第二步沿2x+y=5移动，增加y的同时减少x。

停止依据直接写在目标式中：所有可行解都有 $s_1,s_2\ge 0$，故 $z=9-s_1-s_2\le 9$。当前方案达到九，所以全局最优。最终字典不只是给出一个答案，还给出了对全部可行解成立的上界。这与线性规划中将两条资源约束相加的对偶证据完全一致。

一般步骤怎样从这个例子得到

把问题写成 $max{c}^{𝖳}x$，约束为 $Ax=b,x\ge 0$，其中 $A$ 有 $m$ 个独立行。选择 $m$ 个线性无关的列形成方阵 $B$，其余列形成 $N$。把相应变量分为 $x_B,x_N$，有 $$x_B=B^{-1}b-B^{-1}N{x}_N.$$ 若 $\overline{b}=B^{-1}b\ge 0$，则 $x_N=0,x_B=\overline{b}$ 是基可行解。目标式为 $$z=c_B^{𝖳}\overline{b}+(c_N^{𝖳}-c_B^{𝖳}{B}^{-1}N)x_N.$$ 括号内就是非基变量的检验数。这里是介绍原理的逆矩阵写法；实现时通常求解关于 $B$ 的线性方程，并更新分解，以减少计算和舍入误差。

选择一个检验数 ${\overline{c}}_j>0$ 的非基变量进入基，记其列为 $a_j$、$p=B^{-1}{a}_j$。让它增加 $\theta$，则 $$x_B(\theta )=\overline{b}-\theta p,z(\theta )=z(0)+{\overline{c}}_j\theta .$$ 只有 $p_i>0$ 的行限制步长，因而 $${\theta }_{\ast }=\underset{i:p_i>0}{min}\frac{{\overline{b}}_i}{p_i}.$$ 如果没有这样的行，所有基变量都不会下降，$\theta$ 可以任意大，目标也可以任意大；这给出无界方向的证据。若所有检验数都非正，则从当前目标字典立刻得到全局上界，可以停止。此处推导及表格形式可对照MIT的单纯形讲义。

退化：目标有改善系数，却一步也走不了

另取问题 $maxx+2y$，约束为 $$x\le 1,x+y\le 1,x,y\ge 0.$$ 从原点先增加 $x$，两项最小比值同为一。若让第一松弛变量 $s_1=1-x$ 离基，到达 $(1,0)$ 后的字典是 $$x=1-s_1,s_2=s_1-y,z=1-s_1+2y.$$ 基变量 $s_2$ 为零。这称为退化基可行解。

虽然 $y$ 的检验数为正，但保持 $s_1=0$ 时有 $s_2=-y\ge 0$，所以步长只能为零。让 $y$ 入基、$s_2$ 出基，得到 $$x=1-s_1,y=s_1-s_2,z=1+s_1-2s_2.$$ 几何位置仍是 $(1,0)$。随后才可以增加 $s_1$ 至一，走到 $(0,1)$，收益变为二。

基是代数表示，顶点是几何位置。中间两种基表示同一个点，所以一次换基可以产生零步长。

退化使“每次换基严格提高目标”的论证失效，某些选择规则可能循环。Bland规则给变量预先编号，在允许进入的变量中选最小编号；最小比值并列时，选编号最小的基变量离开。这个规则可避免循环，有限终止的证明不是“顶点有限”一句就能代替的，见MIT算法课程的线性规划笔记。有限终止也不等于每种问题都能用很少步骤解决。

起点不存在于眼前时：先求可行解

原点不是所有问题的可行起点。例如 $x+y\ge 2$ 要写成 $x+y-s=2$，其中 $s\ge 0$；若把 $x,y$ 都设为零，就会得到负的 $s$。

两阶段法先引入人工变量 $a\ge 0$，得到 $x+y-s+a=2$。第一阶段最小化人工变量总和，此处就是 $a$。初始取 $a=2$ 可行；目标有下界零，而 $x=2,y=s=a=0$ 达到零，于是找到原问题的可行点。

一般问题先把等式右端整理为非负，再添加所需人工变量建立起始基。如果第一阶段最优和严格大于零，原约束不可能有可行解；否则任何原可行解加上全零人工变量都会使第一阶段目标为零，造成矛盾。若最优和为零，删去人工变量并恢复原目标；零值人工变量若还留在基中，需要合法换出，或确认其所在行冗余后处理该行，不能直接删除一个仍在使用的基列。

从手算到数值求解

实际程序会用容差判断“接近零”、检验原约束残差与非负性，并计算对偶可行性和目标差。一个非常小的枢轴可能放大舍入误差；把本应为零的数当成正数，还会改变比值检验。变量、资源和金额相差许多数量级时，需要合理缩放。数值软件返回最优状态后，仍可像本例一样利用可行方案和匹配上界来核验结果。

单纯形法处理的是连续变量问题。若产量必须为整数，顶点可以是分数，后续需要整数规划方法；也不能把它与用于一般非线性搜索的Nelder–Mead“单纯形”方法混为一谈。

来源与相关知识

George Dantzig于1947年发展单纯形法，将大规模线性资源配置问题转化为可操作的计算过程，背景见斯坦福大学记录。

• MIT 15.053，The Simplex Method 1，2013：等价消元、松弛变量、基和比值规则。
• MIT 6.854J，Linear Programming notes，2008：字典、退化及防循环规则。
• 先修：矩阵、线性规划；相关：优化、拉格朗日乘数法。