做优化的人，几乎都绕不开LP Simplex。LP是线性规划，Simplex是单纯形法，这两个词合在一起，就是在“若干线性约束下求解线性目标函数极值”的经典方法。很多教程一上来就推单纯形表、算检验数，读者学完只会机械操作，换一个题目就发懵。我当年也一样，直到在项目里亲手把生产计划问题建模、写算法、调数值、对比不同求解思路之后，才真正理解单纯形法每一步迭代背后的几何意义。这篇文章不打算抄书，而是从实际需求出发，把线性规划建模、单纯形法的核心原理、手算流程、工程实现里的坑以及常见排查思路一次讲透。适合刚接触优化的学生、刚转行的算法工程师，以及被单纯形法困扰过但想真正弄懂原理的开发者。
1. 先从一道生产排程题说起
1.1 线性规划建模：把问题翻译成数学语言
我经常用一道生产排程题来开场：某车间要生产两种产品A和B。每单位A需要2小时机器工时和1小时人工，利润40元；每单位B需要1小时机器工时和3小时人工，利润30元。车间每天机器工时最多8小时，人工最多9小时，问A和B各生产多少，总利润最大。用x1表示A的产量，x2表示B的产量，目标函数就是求最大值：max z = 40x1 + 30x2。约束条件是两个资源上限：2x1 + x2 <= 8，x1 + 3x2 <= 9，再加变量非负x1, x2 >= 0。这就是一个最典型的线性规划模型。
这里有个很多人忽略的关键点：为什么目标函数和约束都必须写成线性？线性意味着比例性与可加性，生产2个单位A的利润正好是1个单位的两倍，消耗的工时也成比例。现实世界中当然有规模效应、固定成本这类非线性因素，但只要在决策变量变化范围不大时近似成立，LP模型就是性价比很高的选择。反过来，如果你在目标里写入“数量超过某阈值后利润翻倍”这种规则，模型就不再是线性，单纯形法不能直接用，贸然跑出来的结果往往不是全局最优。
建模时我习惯先列三样东西：决策变量是什么、目标函数怎么算、资源或规则限制有哪些。顺序不能乱。很多人上来先写约束，结果变量定义还没统一，检查半天才发现x2的含义在不同式子里漂来漂去。把这三样东西在纸上写清楚再转成数学符号，后面调试的时间能省一半。
1.2 单纯形法在解LP问题时扮演什么角色
有了数学模型，怎么求最优解？最朴素的想法是把所有可能生产方案都试一遍。可x1、x2是连续变量，取值有无穷多个，根本没法枚举。更进一步的观察是：如果某个点在可行域内部而不是边界，它通常还能往某个方向移动来增加利润，所以最优解一定出现在边界上，而且对线性规划来说，一定会出现在顶点上。单纯形法就是抓住这个性质，从可行域的一个顶点出发，沿着棱走到相邻的、目标值更好的顶点，一步步逼近最优解。
这样的求解思路很直观，但实现时要回答三个问题：如何表示一个顶点？如何知道往哪个方向走能改善目标？如何判断已经走到最优？单纯形法用基变量、检验数、主元变换解决这三个问题。理解单纯形法，不只是为了应付课程，更是为了在工程选型、查看求解器日志、判断结果是否可信时，知道背后的运行机制。而且单纯形法牵涉的对偶解、灵敏度分析，在真实项目中比单纯求解一个数值有用得多。
2. 单纯形法的几何直觉与关键原理
2.1 可行域为什么是凸多面体
线性规划每个不等式在二维空间中，是一条直线切出来的半平面；多个半平面相交，得到一个凸多边形。三维空间里，每个线性不等式是一个半空间，交集构成凸多面体。高维的情况也类似，只是没法直接画出来。这个集合有一个关键性质：任取可行域内两个点，连接它们的线段上每个点仍然可行。这种性质叫凸性，简单理解就是集合没有“凹坑”，不会出现“两个可行点连线的中间点反而不可行”的怪事。
凸性为什么让单纯形法有底气？因为线性目标函数在凸多面体上的最大值，一定能在某个顶点取到，而不是藏在某个内部点或棱的内点上。可以这么想：目标函数是一个倾斜的平面，在凸多面体上，平面沿某个方向不断抬升，最后撑住它的必然是某个顶点。如果可行域不是凸的，比如你在约束里加入了一个非线性的“x1、x2必须落在某个圆形区域外”条件，可行集可能中间被挖空，最优解可能落在非顶点的弧线上，单纯形法就彻底失效。
这个点听起来偏理论，实际排查时却有奇效。我有一次在项目里发现求解结果不对劲，明明手工检查能找到更优方案，但求解器给出的“最优解”就是差一截。仔细检查模型才发现，某位同事在约束里写了一个条件判断：如果x1大于3，则x2不得小于2。这本质上是让可行域出现非凸结构，而我一直用线性求解器去解它。把这种条件改成用0-1变量建模后，问题才回到线性可解的范围。所以看到一个线性规划模型求解异常，先检查约束里有没有“如果……则……”这种逻辑，它十有八九破坏了凸性。
2.2 从顶点到顶点：迭代的方向与最优性判断
要实现从顶点到顶点的移动，单纯形法把变量分成两组：基变量和非基变量。如果原问题有n个变量、m个等式约束，通常让n-m个非基变量固定为0，再在等式约束里解出m个基变量，得到一个基解。如果这个基解同时满足不等式约束和所有变量的非负要求，就叫基可行解，它恰好对应可行域的一个顶点。初始时，只要找出一个现成的基可行解，迭代就可以开始。
迭代方向由检验数决定。每个非基变量的检验数，相当于把它增加一个单位时目标函数的净变化量。以最大化问题为例，如果某个非基变量的检验数大于0，说明让它从0变大，目标还能提升；把所有正检验数都比一遍，通常选最大的那个入基。入基变量增大后，为了让等式约束继续成立，原来基变量里必然有一些会下降，其中最先降到0的基变量就要出基，这个叫最小比值原则。比值原则保证了新的解仍然满足非负约束，不会走出可行域。
什么时候停？当所有非基变量的检验数都不大于0时，当前顶点沿着任何可行棱走，目标函数都不会再上升，所以已经是最优。对凸问题来说，不存在“局部最优但不是全局最优”的情况，因此可以放心停下。极小化问题怎么办？把目标函数整体乘-1转成极大化问题，或者把检验数符号反过来，本质是一样的。手工算的时候，只要记住统一规则，别在最大化、最小化之间来回切换，就能少犯低级错误。
3. 手算一遍：完整的两阶段单纯形流程
3.1 标准化与引入松弛变量
继续用刚才的生产题。原始约束是小于等于不等式，单纯形法标准形式要求等式约束，所以需要引入松弛变量。2x1 + x2 <= 8，引入s1表示机器工时剩余量；x1 + 3x2 <= 9，引入s2表示人工剩余量。约束变为2x1 + x2 + s1 = 8，x1 + 3x2 + s2 = 9，同时s1, s2 >= 0。目标函数仍是max z = 40x1 + 30x2。之所以叫松弛变量，是因为它松弛了不等式，把一个“不能超过”转换成“正好等于加上一个非负余量”。
如果约束是大于等于，比如x1 + x2 >= 5，则要先减去一个剩余变量x5，使其变成x1 + x2 - x5 = 5。但这个剩余变量可以为正，形式满足等式，却不能让初始基变量直接有单位阵，因为它的系数是负1。这时需要再加一个人工变量x6，变成x1 + x2 - x5 + x6 = 5，初始基可以用x6，后续通过两阶段法或大M法把人工变量赶出基。这一步操作的目的只有一个：给初始基可行解一个现成的落点。没有它，单纯形表没法起步。
两阶段法的第一阶段，是暂不考虑原目标，先构造一个人工目标：最小化所有人工变量之和。如果这个最小值是0，说明人工变量可以全被踢出，原问题有可行解；否则说明原问题约束矛盾，直接判无解。第一阶段结束后，再恢复原目标继续第二阶段。比大M法好在不用猜惩罚系数，数值上更稳定。初学者第一次手算时，建议用全是小于等于约束的题目练手，先把松弛变量模型跑熟，再碰人工变量。
3.2 构造初始可行解与单纯形表
回到生产题，因为两个约束都是小于等于，松弛变量s1、s2天然构成初始基。此时非基变量x1=0，x2=0，基变量s1=8，s2=9，正好在原点，利润0。接下来把系数写进单纯形表。表头依次是基变量名、各列变量系数、右侧常数RHS。第一行对应s1：2、1、1、0、8；第二行对应s2：1、3、0、1、9。目标行先写成检验数形式：基变量在目标函数里的系数要消成0，这里s1、s2本来就不是目标变量，所以检验数行直接是40、30、0、0、0。
| 基变量 | x1 | x2 | s1 | s2 | RHS |
|---|---|---|---|---|---|
| s1 | 2 | 1 | 1 | 0 | 8 |
| s2 | 1 | 3 | 0 | 1 | 9 |
| 检验数 | 40 | 30 | 0 | 0 | 0 |
这里有一个新手误区：如果目标函数里有基变量，比如基变量恰好是某个原始变量，它的检验数不一定是0。单纯形表在迭代前必须通过行变换，把当前基变量对应的目标系数消成0，否则后面计算入基变量、判定最优都会出错。只要记住“检验数行描述的是当前基解附近的边际变化”，这个规则就不容易忘。
3.3 迭代规则与入基出基计算
第一步：选入基变量。检验数行里40最大，对应x1，所以x1入基。第二步：选主元行。拿RHS列除以每个约束行里x1的正系数，取最小值：第一行8 / 2 = 4，第二行9 / 1 = 9，最小的是第一行，所以主元素是第一行的x1系数2，出基变量是s1。这一步的意图非常清晰：x1每增加1个单位，第一行约束要求s1减少2个单位，所以x1最多能增加到4；第二行则允许增加到9，为了不让任何基变量变成负数，必须按最小的那个来，所以x1最多到4，同时s1降为0。
第三步行变换。先把主元行除以2，让x1变成1；再用第二行减去新第一行，把s2所在行的x1列消成0；最后做目标行消元，让x1的检验数变成0。得到的新表如下：
| 基变量 | x1 | x2 | s1 | s2 | RHS |
|---|---|---|---|---|---|
| x1 | 1 | 0.5 | 0.5 | 0 | 4 |
| s2 | 0 | 2.5 | -0.5 | 1 | 5 |
| 检验数 | 0 | 10 | -20 | 0 | 160 |
当前解是x1=4，x2=0，利润160。但检验数行里x2的检验数是10，大于0，说明继续增加x2还能提升利润。于是第二轮迭代，x2入基。出基选择再算最小比值：第一行4 / 0.5 = 8，第二行5 / 2.5 = 2，最小是第二行，所以主元是2.5，出基变量是s2。行变换之后得到最终表：
| 基变量 | x1 | x2 | s1 | s2 | RHS |
|---|---|---|---|---|---|
| x1 | 1 | 0 | 0.6 | -0.2 | 3 |
| x2 | 0 | 1 | -0.2 | 0.4 | 2 |
| 检验数 | 0 | 0 | -18 | -4 | 180 |
最终检验数行全是0或负数，对于最大化问题已经达到最优。读表结果：x1=3，x2=2，z=180，机器工时用满8小时，人工也用满9小时。对比原约束：产品A生产3单位，需要机器工时6小时、人工3小时；产品B生产2单位，需要机器工时2小时、人工6小时；总机器工时8小时，人工9小时，全部用完。这个方案与直觉也吻合：利润更高但更耗人工的B产品，虽然单位利润低一点，仍然该生产2单位，完全靠A虽然简单，却达不到最优。
3.4 读表：最优解与对偶信息
单纯形表的价值不止于给出最优产量。看最终表的检验数行，两个负数-18和-4，取相反数之后是18和4，它们分别是对应资源约束的影子价格。s1对应机器工时约束，s2对应人工工时约束，意思是：机器工时每增加1小时，利润能增加18元；人工工时每增加1小时，利润能增加4元。
这组数据在生产决策中非常有用。比如车间想买额外工时，机器工时成本每小时15元，影子价格18元，说明买工时划算；人工工时的影子价格只有4元，如果加班费超过每小时4元，就不值得。单纯形表的最终行把这些经济信号一并算了出来，这也是为什么在很多商业场景下，单纯形法不只是求解工具，还是定价和投资分析的辅助手段。
4. 工程实现中的坑与解法
4.1 退化与循环：防止被“卡死”
实际大规模问题中，经常出现退化解：某个基变量取值恰好是0。这种情况下，不同的基解可能对应同一个几何顶点，单纯形法沿着边界走，可能绕了一圈又回到同一点。严重时会出现循环，迭代次数爆炸但目标值毫无变化。教科书上的单纯形法对退化场景可能死循环，工程实现必须加防护。
最经典的防护是Bland规则：入基时选满足正检验数且编号最小的变量，出基时同样按编号最小原则。这个规则能保证算法有限步终止。另一种思路是扰动法，给约束右侧常数加极小的随机扰动，把退化问题变成非退化问题，迭代结束后再恢复原常数。商业求解器还会记录近期访问过的基，一旦发现重复就换规则。我在自研求解器时遇到过最夸张的情况：一个几十个变量的运输问题，跑了上百万次迭代还没停，目标函数一直卡在同一个值，后来加上Bland规则，几百次迭代就结束了。遇到这种症状，先怀疑退化，再怀疑写错主元选择，不要急着调参数。
4.2 数值稳定性与预处理
单纯形法本质是浮点数上的高斯消元，每次迭代都在做行变换，数值误差会累积。最危险的信号是主元绝对值太小。假设主元是1e-8量级，用它做除法会把其他系数放大到1e8量级，后续所有判断都可能在噪声中进行。工程上常用部分选主元策略：在所有候选主元中，选绝对值最大且满足比值条件的那一个，而不是随意选第一个。更进一步，使用修正单纯形法，每次迭代只更新基矩阵的逆，而不是维护整张表，数值稳定性会好很多。
除了算法本身，模型预处理同样关键。冗余约束、固定变量、量纲差异，都会让求解器做一堆无用功。比如一个约束写成“x1 <= 1e9”，相当于没有约束，它却会参与基矩阵运算，增加数值误差。还有人会把成本和资源量纲混在一起，导致目标系数从1e-6到1e6跨越十几个数量级，单纯形表很容易出现病态。写模型时先做量纲归一化，删掉明显冗余的约束，很多所谓“求解器数值失败”的问题根本不会发生。
4.3 单纯形、内点法与何时换方法
单纯形法在最坏情况下的复杂度是指数级的，也就是说理论上存在一类问题，会让单纯形法的迭代次数爆炸。但从事实际优化的工程师都知道，普通规模的LP问题里，单纯形法表现惊人地好，平均迭代次数通常只有约束数量的几倍。真正让单纯形法吃力的问题，往往带有极强的退化或复杂的顶点结构。这时可以考虑内点法。
内点法从可行域内部出发，沿某一方向逐步逼近最优解，单次迭代计算量比单纯形法大，但迭代次数对问题规模增长更平稳，特别适合大规模稀疏问题。两者不是替代关系而是互补关系。内点法很难给出一个“现成的最优基”，因为它通常停在可行域内部；单纯形法迭代到顶点，天然具备基信息。如果需要做灵敏度分析、热启动、或者需要整数规划分支后的快速重解，单纯形法更有价值。很多优化产品内部的默认策略，都是先用某种快速试探，再在单纯形法和内点法之间动态切换，甚至先用内点法求近似解，再用单纯形法收尾拿到精确实用的基解。
这个选择不是非黑即白。我在项目里处理过一个问题，第一次用单纯形法跑了很久没结束，切到内点法秒出结果；但换到另一个有强稀疏结构的问题，单纯形法又快又稳。正确做法是先把问题结构搞清楚：约束数多少、稀疏度如何、需不需要热启动和灵敏度报告。在这些信息明确以前，别迷信任何一种方法。
5. 常见问题速查与排查思路
5.1 为什么初始基可行解找不到
很多初学实现的人，一上来就把所有约束直接丢进单纯形表，结果发现没有现成的单位矩阵，不知道从哪里起步。这正是人工变量的价值。两阶段法第一阶段结束后，如果人工变量之和的最优值不是0，意味着原问题没有可行解。这个结果经常被当成“算法坏了”，其实它是模型矛盾的直接信号。比如有两个约束分别要求总工时至少10小时和最多8小时，显然无解。排查时，先看一阶段目标值是否为0，不为0就顺着约束找不可行区间，多半是边界写反或者上下限冲突。
5.2 为什么变量无界但求解器报错
如果你的模型漏写了某个资源上限，单纯形法会出现一种特有现象：某非基变量检验数为正，但入基时所有比值都是无穷大，找不到可出基的变量。这表示目标函数可以沿着那个方向一直增长，没有约束能拦住它。真实业务里，常见原因包括：漏掉变量上界、资源约束写错方向、目标函数符号和最大化方向设置反了。解决办法不是改求解器参数，而是回头补上物理意义上的上边界。哪怕只是临时给变量加一个很大的上界，也能让求解器跑完，方便你从解里发现到底是哪个资源约束缺失。
5.3 从单纯形表怎么看影子价格
影子价格就在最终单纯形表的检验数行，不过要先弄清方向。对最大化问题，某个松弛变量的检验数取负号后，就是对应约束的边际价值；如果对应的松弛变量仍然在基里且取值大于0，说明这个资源没用完，影子价格是0。我在做项目时，经常用这个表快速判断瓶颈资源。比如上面生产题中，机器工时对应的影子价格18，人工工时是4，机器工时显然更稀缺，增加机器工时比增加人工更值钱。
但要注意，影子价格只在当前最优基不变的范围内有效，不是全局线性关系。当约束右侧增加到一定程度后，最优基可能切换，影子价格会跳变。所以在报告里，写在“当前区间内，每增加一单位资源的边际收益是XX”就足够严谨，不要写成“增加多少都永远按这个价格”。
6. 单纯形法之外：对偶、灵敏度与整数规划
6.1 对偶理论与灵敏度分析
单纯形法每迭代到一步，实际上在同步求解对偶问题。对偶问题给每个原始约束一个“价格”，也就是资源价值。原问题有两个资源约束时，对偶变量分别对应机器工时价格和人工工时价格，对偶目标是最小化资源总成本，同时利润不能低于产品价格。这个视角在经济学里就像给资源定价：如果某资源的影子价格高，说明它稀缺；拥有者可以按这个价格出售使用权，购买者只要成本更低就有利可图。
灵敏度分析回答一个更实际的问题：模型里某个系数变了，最优解会不会变？目标函数系数变化范围、约束右侧变化范围、约束矩阵系数变化范围，都能由单纯形表推出来。工程中，数据本身有噪声，如果某个系数在范围内变化不影响最优解，你就不必花大力气去买更精确的数据；如果最优解对某个系数极其敏感，那就要高度重视数据质量。这种“先敏感性分析，再决定是否精细建模”的思路，能节约大量时间。
6.2 整数规划、网络流与大规模求解
现实决策经常要求整数解，比如产品数量不能是3.5台，项目投资只能选或不选。线性规划的单纯形法不能直接处理整数变量，但它作为LP松弛求解器，是整数规划分支定界法、割平面法等算法的基石。分支定界每探索一个节点，都要在部分变量固定取值的前提下解一个LP子问题，这个子问题规模大、数量多，是否能用单纯形法热启动直接影响整体效率。理解LP Simplex，是掌握整数优化引擎的重要前置条件。
网络流问题也是LP的特例。运输问题、指派问题、最大流问题都可以建模成线性规划，并在特殊网络结构上使用比通用单纯形法快得多的专用单纯形算法。很多看似无关的调度、路由、供应链问题，本质上都会收敛到这类数学模型。从这个角度看，单纯形法不只是孤立的算法，它把线性代数、几何、经济学和算法工程串在了一起，是优化领域最值得先吃透的一块基石。
我个人在实际工作中的体会是，学单纯形法不要急着调库。先把模型写在纸上，把松弛变量、检验数、主元这些概念用手算几遍。尤其第二次迭代时，亲眼看到检验数从正变负，才能建立起“最优解一定停在顶点上”的直觉。之后再去读生产优化、运输调度、投资组合的案例，你会发现自己能很快判断出该用什么模型、该怎么读求解器输出。如果被LP Simplex绕晕过，建议从今天这道生产题开始，拿笔算一遍，很多疑问会自然消失。
