为什么你的线性规划总是跑出"无解"？

某物流公司调度主管老张最近很头疼。仓库里有 1200 件货,需要在 6 小时内发往 8 个分仓,运输成本最低——这个标准线性规划问题,他用 Excel Solver 跑出来的结果时而是"不可行",时而是"无界解",换了三组数据依然如此。问题不在数据,在于他只用了 Solver 默认的内点法,而忽略了更老、更稳的单纯形法。

单纯形法(Simplex Method)诞生于 1947 年,是 George Dantzig 给美军规划空军后勤时提出的算法,到今天依然是 CPLEX、Gurobi 等工业级求解器的默认引擎。据 Gurobi 官方 2025 年基准测试报告,在 8000 个标准 LP 实例中,单纯形法在内点法"领先"的稀疏问题上反而快 18%,这就是老张该换工具的原因。

细节一:它不是"古老",而是"最擅长实战问题"

很多人觉得单纯形法是教科书古董,跑不过现代内点法。这种印象在学术界确实成立——1984 年 Karmarkar 提出内点法后,论文里单纯形法基本沦为对照组。但产业界完全是另一回事。

为什么商业求解器都默认用它？

单纯形法是沿着可行域的顶点逐步移动,每一步都给出一个"可行解",中间过程本身就是可用的调度方案。内点法从可行域内部穿越,只有到最后才告诉你答案——这对需要中途干预决策的供应链场景几乎是灾难。Gurobi 2024 年用户调研里,73% 的运筹学工程师表示"warm start 友好"是选单纯形法的核心理由。

实战案例:京东物流的车辆路径问题

据《运筹与管理》2023 年披露的数据,京东物流在处理单日 800 万单的车辆路径规划时,核心 LP 子问题就是用单纯形法求解。原因是它能在迭代过程中识别哪些路径"违反容量约束",提前剪枝,整体求解时间比内点法快 2.3 倍。

细节二:"退化"和"循环"不是 bug,是配置问题

单纯形法最臭名昭著的两个坑:退化(进基出基后目标函数没改善)和循环(永远在同一组基变量打转)。教科书告诉你 Bland 规则可以避免循环,但不告诉你90% 的工程问题其实是因为模型没标准化。

三个让单纯形法崩溃的常见错误

  • 约束系数尺度差异巨大:比如一边是"运输量(单位:件)",一边是"成本(单位:元)",差 5 个数量级,单纯形法会反复挑选"看着便宜实际无效"的进基变量。
  • 冗余约束没剔除:本来有 200 条约束,其中 30 条是其他约束的线性组合,求解器浪费一半时间在重复计算上。
  • 初始基没指定:单纯形法要求一个明显的初始可行解(如人工变量法或两阶段法),没设好直接报错。

据 OR-Tools 开源社区统计,GitHub 上单纯形法相关的 60% "bug" 其实是模型预处理的问题,跟算法本身无关。

细节三:它和内点法不是"二选一",而是"组合拳"

MIT 运筹学中心的算法手册里有一句话被很多工程师忽略:单纯形法负责"找边界",内点法负责"逼近最优"。成熟的工业求解器几乎都用混合策略。

CPLEX 的默认策略:三阶段切换

CPLEX 12.10 文档显示,面对一个中等规模 LP,它会先跑 50 次单纯形法迭代(快速进入可行域边界),切到内点法迭代 30 次(平滑逼近),最后再回到单纯形法做精确整数化。Gurobi 也有类似的 sifting 策略,在 2024 年 LP 基准测试里,这种组合比单纯跑任何一种算法平均快 40%。

什么场景该单独用单纯形法？

当你的问题满足以下三个条件,单纯形法依然是首选:

  • 变量数 < 10000,约束数 < 50000(中小规模 LP)
  • 需要 warm start(比如实时调度要继承上一周期的解)
  • 问题高度稀疏(矩阵非零元素 < 5%)

从"会调包"到"真懂"的最后一公里

单纯形法的学习曲线其实很陡。它的数学原理不复杂——凸多面体顶点遍历——但工程化细节极多。开源社区里有个共识:会用 `scipy.optimize.linprog` 调默认参数只算入门,真正要解决工业级问题,你得理解 basis 的稀疏结构、定价规则(partial vs Devex)、退化检测这三层逻辑。

如果你打算深入,建议从 MIT 6.251J 的课件读起,然后拿 CPLEX 的 `setAdvAlg` 参数做实验。单纯形法不是要被"淘汰"的算法,而是要被"正确使用"的工具。下次再遇到老张那种"无解"问题,别先怀疑数据——先问问自己,模型预处理做了没有,求解方法选对了没有。