3.1 线性规划与单纯形法
3.1 线性规划与单纯形法
本节摘要：线性规划是目标与约束全为线性的优化模型，可行域是多面体、最优解落在顶点。本节讲单纯形法沿顶点迭代的核心机理与对偶理论的经济含义（影子价格），并以饲料厂采购为战例完成建模、求解、灵敏度三层推演。
三个车间抢两吨豆粕
饲料厂采购员的周一：三个车间共用豆粕库存，A 车间每吨配料赚 800 元、耗电 40 度，B 车间赚 600 元、耗电 20 度，C 车间赚 500 元、耗电 10 度；豆粕日供 6 吨、电力日供 90 度，三车间产量都不超过 4 吨。怎么分配日利润最大？
线性规划（LP）就是为这类局面而生的：变量连续、目标与约束全是线性式。1947 年丹齐格提出单纯形法时，正是为了替美国空军算这类后勤分配。此后七十余年，LP 是运筹学落地最广的一件兵器——石油炼制的配方、航空的机组排班、广告的预算分配，底层全是 LP 或其变体。
单纯形法：沿顶点行军
第 2 章的顶点定理说，线性目标的最优解出现在可行域顶点。单纯形法的策略由此而来：从一个顶点出发，每步沿着多面体的一条棱，移动到能让目标改善的相邻顶点，直到没有更好的邻居为止。三维以下的直觉可以画出来：多面体像一颗切割过的宝石，算法是宝石表面爬行的蚂蚁，永远朝下坡方向的棱走。
顶点数量组合爆炸怎么办？实践中单纯形法访问的顶点数大致与变量数同阶，极少走冤枉路——这个"最坏情况指数级、平均情况多项式"的反差，正是它在工业界长盛不衰的原因。理论界后来补上了内点法（沿多面体内部走，多项式时间），两者今天在求解器里并存。用 HiGHS 求解刚才的战例：
import numpy as np from scipy.optimize import linprog c = np.array([-800.0, -600.0, -500.0]) # 取负转最小化 A = np.array([[1.0, 1.0, 1.0], # 豆粕 [40.0, 20.0, 10.0]]) # 电力 b = np.array([6.0, 90.0]) bounds = [(0, 4), (0, 4), (0, 4)] res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method="highs") print("最优分配(吨):", res.x, " 日利润:", -res.fun) print("豆粕剩余:", 6 - res.x.sum(), " 电力剩余:", 90 - A[1] @ res.x)
最优分配是 A 车间 1.25 吨、B 车间 2.75 吨、C 车间 2 吨，日利润 4950 元，豆粕与电力恰好用完——两条资源约束同时顶格。这个"顶格"信号直接引出 LP 最有管理价值的副产品。
对偶：每份资源值多少钱
原问题问"怎么分配最赚"，对偶问题问"每种资源的边际价格是多少"。res 里的 res.ineqlin.marginals 就是影子价格：
print("豆粕影子价格:", -res.ineqlin.marginals[0], "元/吨") print("电力影子价格:", -res.ineqlin.marginals[1], "元/度") # 豆粕约 466.7 元/吨，电力约 6.67 元/度
影子价格的用法立竿见影：若市场上豆粕可以 400 元/吨买到，每多买一吨净赚 66.7 元，值得追加；若电力增容每度要花 8 元，就不划算。对偶把"要不要扩资源"从直觉谈判变成算术。背后的互补松弛定理说：顶格的约束才有正的影子价格，有富余的资源影子价格为零——这与直觉完全一致，稀缺才有价。
影子价格与资源顶格状态
什么时候 LP 会失灵
三种典型失效。其一，数据本身是估计值：需求预测偏差 10%，"最优解"可能整个换了一副面孔——这属于第 4 章随机规划的领地。其二，决策不可细分：解出"订购 2.7 辆卡车"没有物理意义，取整后可能违反约束，需要整数规划（3.2 节）。其三，规模与稀疏性：上亿变量的 LP（如全局物流网络）要靠列生成、分解法等专门技术，直接硬塞会被内存劝退。
💡 关键直觉：拿到 LP 解之后先别急着交差，问三个问题——哪些约束顶格？影子价格与市价差多少？关键参数抖动 10% 解会不会翻脸？三个答案合起来才是完整的决策依据。
对偶的深层图景：两只手数同一件事
对偶理论值得再站高一层看。原问题问"在资源约束下怎么安排生产最赚"，对偶问题问"把资源直接卖掉，每种资源定价多少，卖方收益不低于生产方收益且定价最克制"。线性规划对偶定理说，两者的最优值相等——最优生产计划的利润，恰好等于资源在最优定价下的总价值。这不是巧合，而是同一枚硬币的两面：市场价格（影子价格）与最优配置互相决定。经济学里的一般均衡理论、第 6 章机制设计里的 VCG 定价，都是这枚硬币的远亲。工程视角的收获则更直接：拿到 LP 解之后，把影子价格列成一张"资源报价单"交给采购与销售部门——豆粕低于 466.7 元每吨就买进，电力高于 6.67 元每度就考虑错峰生产——模型输出就这样变成了可以谈判的筹码。
顺带一提求解器选择的现实考量。开源侧 HiGHS 已能满足教学与中小规模工业问题；商业求解器在大规模整数规划上仍有数量级优势，价格也按年计费不菲——选型时先问问题规模与求解时间预算，再谈采购。另一个常被忽略的细节是数值条件数：约束矩阵里如果同时出现千分之一与十万量级的系数，求解器的数值精度会先于算法极限崩溃，解出来的最优解可能连可行性都存疑。建模时统一量纲（比如金额全部换算成万元），是比换求解器更便宜的第一道防线。
本节要点回顾
- 顶点定理是单纯形法的根基：沿棱移动、每步改善、无邻居可改进即最优；
- 对偶价格 = 资源的边际价值，是 LP 输出里最值钱的一栏；
- 互补松弛：顶格约束有价、松弛资源无价，可用来交叉验证解；
- LP 三大失效：数据不确定、决策不可分、规模爆炸，分别引出后文三套对策；
- 求解器日志要读状态码，最优、达到迭代上限、不可行，三者的决策含义完全不同。
解是连续的、可细分的，这很省心；下一节我们让变量落到格点上，看看"必须取整"这一个小改动如何把问题难度提升一个量级。