6.2 6.2 线性规划与整数规划
6.2 线性规划与整数规划
本节摘要：线性规划是"目标与约束全线性"的优化模型，有多项式时间算法与成熟求解器，是运筹学的头号生产力工具。本节走完一个配送中心选址工单的建模—求解—对偶解读全程；再引入整数约束，看可行域如何从凸多面体碎成离散点集，分支定界如何用"松弛加切割"的方式搜索。
读完这节你能做什么
阅读完本节，你应当能够：
- 独立完成一个线性规划的建模与求解，并用对偶解读资源价格；
- 解释整数约束如何破坏凸性与多项式时间保证；
- 说出分支定界的搜索机制与剪枝逻辑。
配送工单：线性规划全程
三家门店的需求、两座仓库的库存与单位运费给定，求总运费最小的配送方案。变量是"从仓库 i 到门店 j 的运量"，九个（或六个）连续变量；约束是每座仓库的发货不超库存、每家门店的需求恰好满足。
import numpy as np from scipy.optimize import linprog # 成本矩阵：仓库 i 发往 门店 j 的单位运费 cost = np.array([[4, 6, 9], [5, 3, 8]]).ravel() # 按变量顺序展开 supply = [80, 70] # 两仓库存 demand = [50, 60, 40] # 三店需求 # 约束：仓库发货 <= 库存；门店收货 = 需求 A_ub = np.kron(np.eye(2), np.ones((1, 3))) # 每仓求和行 b_ub = supply A_eq = np.kron(np.ones((1, 2)), np.eye(3)) # 每店求和行 b_eq = demand res = linprog(cost, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=[(0, None)]*6, method='highs') plan = res.x.reshape(2, 3) print("配送方案（行=仓库 列=门店）:") print(plan.round(1)) print(f"最小总运费: {res.fun:.0f}")
解的结构很典型：运费便宜的通路打满，贵的通路只兜底。线性规划的最优解永远落在可行域的顶点上——这是"线性"带来的几何礼物，单纯形法就是沿顶点爬行。配送工单的三个交付物：方案本身、总成本、以及下一节要用的对偶价格（哪个门店的需求边际最贵）。
对偶问题的经济读法在上一节已经建立，这里补一句工程话术：把原问题的"最小化运费"翻个面，对偶问题变成"给库存与需求定价，让定价体系解释当前方案"。求解器返回的对偶变量直接告诉你：某门店需求再增加一件，总运费涨多少——涨价最陡的需求点就是扩容或调价的优先对象。
加一个"整数"要求，世界碎裂
现实工单常要求变量取整数：不能发 0.7 辆车、不能开半个人。整数规划看起来只是加了一点点限制，性质却发生质变：可行域从凸多面体碎成离散点集，凸性的全部红利（局部即全局、多项式时间）作废。理论上整数规划是 NP 难的——没有已知的多项式时间算法，且学界普遍相信不存在。
分支定界是标准解法，思路漂亮：先解"整数约束扔掉"的松弛问题，得到一个下界（最小化场合）；若松弛解恰好全整数，收工；否则挑一个小数变量分支成两个子问题（变量向下取整一支、向上取整一支），各自再解松弛。剪枝有三把刀：下界剪枝（子问题下界已超过当前最好整数解，整支砍掉）、整数剪枝（松弛解全整数，更新最好解）、不可行剪枝（子问题无解）。
import numpy as np from scipy.optimize import milp, LinearConstraint, Bounds # 演示用最小模型：两仓两店，仓 i 开设费 f_i, 运费 c_ij c = np.array([100, 80, # 开设费 x1 x2 4, 6, 5, 3]) # 运费 y11 y12 y21 y22 integrality = np.array([1, 1, 0, 0, 0, 0]) # x 取整 # 需求约束: y11+y21 = 40; y12+y22 = 30 cons = [ LinearConstraint([60, 0, -1, -1, 0, 0], -np.inf, 0), LinearConstraint([0, 50, 0, 0, -1, -1], -np.inf, 0), LinearConstraint([0, 0, 1, 0, 1, 0], 40, 40), LinearConstraint([0, 0, 0, 1, 0, 1], 30, 30), ] res = milp(c, constraints=cons, integrality=integrality, bounds=Bounds(0, [1, 1, np.inf, np.inf, np.inf, np.inf])) x = np.round(res.x).astype(int) print(f"开设决策: 仓1={'开' if x[0] else '关'}, 仓2={'开' if x[1] else '关'}") print(f"总成本: {res.fun:.0f}")
混合整数求解器内部就是分支定界加割平面，规模上去后求解时间指数爆炸是常态。工程对策三板斧：给好的上界（先跑一个启发式得可行解，剪枝更狠）、收紧松弛（约束写紧一点，下界更贴近真值）、限制分支变量顺序（先分支持配对结果影响大的变量）。还有一条经常被忽视的：允许百分之几的间隙提前收工——差最优解百分之一的可行方案，往往比三小时后才出来的精确最优值钱。
补充一个通用直觉：分支定界是"乐观估计指导搜索"的范式——松弛问题的值是乐观下界，凡是乐观不过现有最好解的分支直接放弃。这个范式从下棋的剪树到路线规划无处不在，值得当成通用思维工具吸收。
连续与整数：两个世界
本节要点回顾
- 线性规划全程：变量—目标—约束三件套建模，求解器分钟级给出全局最优；
- 最优在顶点是线性结构的几何礼物，对偶价格随解免费附赠；
- 整数约束碎裂凸性，问题变 NP 难，规模大时求解时间指数爆炸；
- 分支定界三把剪枝刀：下界、整数、不可行，乐观下界指导搜索；
- 工程三板斧：好上界、紧松弛、允许间隙——差百分之一的早解常胜过迟到的精确解。