运筹调度 / 02
LP / ILP / 匹配 / 网络流
运筹优化面试里，LP、ILP、匹配、网络流是最常见的基础工具。你不一定要现场手写求解器，但要知道什么问题适合用什么形式建模。
LP：线性规划
线性规划的形式是：目标函数和约束都是线性的，变量可以连续取值。
典型形式：
minimize c^T x
subject to Ax <= b
x >= 0
LP 适合做资源连续分配，比如预算、流量、库存比例、产能规划。它通常比整数规划更容易求解。
例子：广告预算在多个流量池之间分配。
- 变量：每个流量池分配多少预算。
- 目标：最大化预期转化或 ROI。
- 约束：总预算、单池上限、消耗速度、风险阈值。
ILP：整数规划
整数规划要求变量是整数，常见的是 0/1 变量。
例如：
x_{i,j} = 1 表示订单 i 分给骑手 j
x_{i,j} = 0 表示不分配
ILP 表达能力强，适合选择、分配、排班、路径等离散决策。但求解复杂度高，大规模在线系统往往不能直接求全局最优。
二分图匹配
匹配问题适合“一边对象分配给另一边对象”的场景。
例子：
- 订单分给骑手。
- 用户分配优惠券。
- 广告请求匹配广告。
- 任务分配给机器。
如果每个订单只能分给一个骑手，每个骑手只能接一个订单，可以建成二分图最大权匹配。边权表示收益或负成本。
边权可以包含：
- 骑手到店时间。
- 预计送达时间。
- 超时风险。
- 空驶距离。
- 接单概率。
- 未来机会成本。
最小费用最大流
网络流适合有容量和路径结构的问题。最小费用最大流可以表达“在满足流量需求的同时最小化成本”。
例子：多区域骑手供给调配。
- 源点连接骑手区域供给。
- 中间节点表示区域和时间片。
- 汇点表示订单需求。
- 边容量表示可调配数量。
- 边费用表示调配成本或延迟成本。
网络流比简单匹配更适合多层资源流动和容量约束。
匹配和网络流的区别
匹配更像“一对一或一对多分配”，网络流更像“资源从源头经过网络流向需求点”。
如果问题只是订单和骑手之间选边，匹配够用。
如果问题涉及区域流转、容量、时间层、库存或多阶段路径，网络流更自然。
什么时候不用精确优化
工业场景常常不用精确解，原因包括：
- 问题规模太大。
- 输入预测本身有误差。
- 在线决策时间很短。
- 约束会频繁变化。
- 可解释和稳定比最优更重要。
此时可以用启发式：先排序、再贪心、局部调整、模拟退火、遗传算法、beam search，或者用机器学习模型打分候选动作。
面试题：订单分配给骑手怎么建模
一个基础回答：
我会先构造订单和骑手的二分图。每条边表示某骑手可以服务某订单，边权是服务成本，包括到店时间、送达时间、超时风险、空驶距离和骑手负载。然后在每个滚动时间窗口内做最小成本匹配。如果考虑多单组合和未来订单，就需要扩展候选动作，或者把问题转成带时间窗的 VRP，再用启发式近似求解。
这个回答的重点是：先给简单模型，再说明真实系统如何扩展。
面试题：排班怎么建模
排班通常是整数规划。
变量：
x_{r,t,k} = 区域 r、时间片 t、班次类型 k 的骑手数量
目标：
minimize 缺口成本 + 冗余成本 + 排班成本
约束：
- 每个区域时间片供给覆盖需求。
- 班次长度合法。
- 总人力预算不超过上限。
- 骑手可用时间满足要求。
如果要排到个人，就会更复杂，需要考虑个人偏好、休息时间和公平性。
面试题：优惠券或补贴预算怎么分配
可以看成 knapsack 或整数规划。
变量：
x_{i,k} = 用户或骑手 i 是否获得策略 k
目标：
maximize 增量收益 - 成本
约束：
- 总预算。
- 每个人最多一个策略。
- 每个区域或人群覆盖下限。
- 风险和公平性限制。
如果收益来自 uplift 模型，就要强调它估计的是增量效果，而不是普通转化概率。
如何在面试中表现成熟
不要只说“这个可以用 ILP”。要补充：
- 变量数量多大。
- 约束是否线性。
- 求解是否能满足实时性。
- 输入预测误差会不会影响结果。
- 如果求解超时怎么降级。
- 线上怎么验证比旧策略好。
总结
LP 适合连续资源分配，ILP 适合离散选择，匹配适合两类对象分配，网络流适合容量和路径结构。真实业务中常常是这些方法和启发式、机器学习、仿真一起使用。
下一篇建议继续看：