从‘下料问题’到‘建厂选址’：手把手拆解整数规划（ILP）的3个经典建模案例
在制造业的钢板切割车间里，老师傅正对着不同尺寸的订单需求发愁；跨国企业的战略部门会议室中，高管们争论着新工厂的最佳选址方案。这些看似毫不相关的场景，背后却隐藏着相同的数学语言——整数规划（Integer Linear Programming）。当决策变量必须取整数值时，传统的线性规划就像一把没有刻度的尺子，而整数规划正是那把精准的游标卡尺。
对于刚接触数学建模的分析师和工程师而言，理解分支定界算法或许不难，但将现实问题转化为标准的整数规划模型却常令人望而却步。本文将通过三个经典案例的深度剖析，揭示从实际问题到数学模型的转化艺术，让你掌握用0和1定义"建或不建"的决策智慧，用整数变量描述"裁几块"的生产计划。
1. 下料问题：如何用数学语言描述"省料"的艺术
走进任何一家金属加工厂，都能看到这样的场景：大型卷材被切割成不同尺寸的零件，边角料堆积如山。下料问题（Cutting Stock Problem）就是要用最少的原材料满足所有订单需求，这个1940年代由经济学家Kantorovich提出的问题，至今仍是ILP最生动的教学案例。
1.1 问题定义与变量设计
假设我们需要从宽度固定的卷材上裁切三种零件：
- 零件A需要50个，每个宽度0.3米
- 零件B需要75个，每个宽度0.4米
- 零件C需要100个，每个宽度0.5米
原材料卷材的标准宽度为2米。首先需要确定决策变量——这里不是简单地定义"生产多少个零件"，而是要考虑所有可能的切割组合。例如：
# 可能的切割方案示例 方案1 = [6, 0, 0] # 6个零件A (0.3*6=1.8≤2) 方案2 = [0, 5, 0] # 5个零件B (0.4*5=2) 方案3 = [2, 1, 2] # 2A+1B+2C (0.3*2+0.4+0.5*2=2)设共有n种可行切割方案，定义决策变量：
- xⱼ：采用第j种方案切割的卷材数量（非负整数）
1.2 构建数学模型
目标是最小化原材料使用量：
目标函数：
min Z = Σxⱼ (j=1到n)约束条件：
Σaᵢⱼxⱼ ≥ bᵢ (对所有零件i) xⱼ ≥ 0且为整数其中aᵢⱼ表示第j种方案中零件i的数量，bᵢ为零件i的总需求。
1.3 实际建模技巧
在真实场景中，还需要考虑：
- 对称性处理：避免本质相同但排列不同的重复方案
- 方案生成：可采用列生成法动态产生有价值的切割方案
- 松弛技巧：先求解线性松弛问题，再通过取整获得可行解
提示：实际应用中，下料问题的变量规模可能非常庞大。现代求解器如CPLEX和Gurobi都内置了专门的列生成算法来高效处理这类问题。
2. 建厂选址问题：用0-1变量定义"存在与否"
全球供应链管理者常面临这样的抉择：应该在哪些地区建设工厂，才能最小化总成本（建设成本+运输成本）？这类问题完美展现了0-1变量的魅力——用最简单的数字表达最复杂的决策。
2.1 问题场景设定
某电子产品企业考虑在亚洲3个候选地点建厂，供应4个主要市场的需求：
建设成本（百万美元）：
| 地点 | 上海 | 曼谷 | 孟买 |
|---|---|---|---|
| 成本 | 50 | 30 | 40 |
产能（千台/月）：
| 地点 | 上海 | 曼谷 | 孟买 |
|---|---|---|---|
| 产能 | 200 | 150 | 180 |
市场需求（千台/月）：
| 市场 | 东京 | 新加坡 | 迪拜 | 悉尼 |
|---|---|---|---|---|
| 需求 | 100 | 80 | 120 | 90 |
单位运输成本（美元/台）：
| From\To | 东京 | 新加坡 | 迪拜 | 悉尼 |
|---|---|---|---|---|
| 上海 | 15 | 10 | 25 | 30 |
| 曼谷 | 25 | 5 | 20 | 35 |
| 孟买 | 30 | 20 | 10 | 40 |
2.2 数学模型构建
定义两类决策变量：
- yᵢ ∈ {0,1}：是否在第i个地点建厂（1=建，0=不建）
- xᵢⱼ ≥ 0：从工厂i到市场j的运输量
目标函数（最小化总成本）：
min Z = Σ(建设成本ᵢ * yᵢ) + ΣΣ(运输成本ᵢⱼ * xᵢⱼ)约束条件：
- 产能限制：Σxᵢⱼ ≤ 产能ᵢ * yᵢ （对每个工厂i）
- 需求满足：Σxᵢⱼ ≥ 需求ⱼ （对每个市场j）
- 逻辑约束：xᵢⱼ ≤ M * yᵢ （M为足够大的数，确保不建厂时无运输）
2.3 模型优化技巧
- Big-M技巧：选择合适的M值（如总市场需求），既保证逻辑正确又不影响求解效率
- 预处理：剔除明显不经济的运输路线（如孟买到悉尼的单位运输成本接近产品价值）
- 松弛加强：添加有效不等式，如"至少需要建⌈总需求/最大单厂产能⌉个工厂"
# Python调用Gurobi求解的示例代码片段 import gurobipy as gp model = gp.Model('FacilityLocation') y = model.addVars(factories, vtype=gp.GRB.BINARY, name="build") x = model.addVars(arcs, name="ship") model.setObjective(gp.quicksum(cost[i]*y[i] for i in factories) + gp.quicksum(trans_cost[i,j]*x[i,j] for i,j in arcs)) model.addConstrs(gp.quicksum(x[i,j] for i in factories) >= demand[j] for j in markets) model.optimize()3. 员工排班问题：当约束条件比变量还多
服务业管理者每周都要面对复杂的排班难题：如何用最少的人力满足各时段需求，同时遵守劳动法规和员工合同？这类问题往往约束条件远多于变量，展现了ILP的另一面。
3.1 问题描述
某24小时营业的便利店需要安排员工班次，要求：
- 每个班次连续工作8小时
- 每小时人力需求不同（如午夜只需1人，早高峰需要4人）
- 全职员工每周工作5天，每天1个班次
- 兼职员工每周最多工作3天
3.2 模型构建技巧
定义决策变量：
- xⱼₖ ∈ {0,1}：员工j是否被安排在班次k（1=是，0=否）
目标函数：
min Z = Σ（全职员工数量）+ 0.8*Σ（兼职员工数量）约束条件：
- 覆盖需求：每个时段所有在岗员工数 ≥ 需求
- 连续工作：每个员工被分配的班次之间必须满足休息要求
- 合同限制：全职/兼职的工作天数限制
3.3 特殊处理技术
- 列生成：当员工数量庞大时，可采用隐式枚举
- 对称性破缺：添加约束消除等效排班方案
- 松弛策略：将部分约束转化为惩罚项加入目标函数
| 时段 | 需求 | 可能班次 |
|---|---|---|
| 0:00-1:00 | 1 | 夜班1 |
| 6:00-7:00 | 4 | 早班1,早班2 |
| ... | ... | ... |
注意：实际排班问题可能需要考虑员工技能、偏好等软约束，这时可以引入惩罚系数或使用多目标优化方法。
4. 从模型到实践：ILP求解的艺术
建立模型只是第一步，让模型高效求解需要更多技巧。现代ILP求解器如Gurobi、CPLEX都融合了数十年的算法创新。
4.1 预处理技巧
- 变量固定：通过上下界分析确定某些变量必然取值
- 约束收紧：将松散约束转化为更紧凑的形式
- 系数约化：消除约束中的冗余系数
4.2 分支策略对比
| 策略类型 | 适用场景 | 优点 | 缺点 |
|---|---|---|---|
| 最大不可行度 | 变量取值分散 | 快速减少不可行性 | 可能忽略重要分支 |
| 伪成本分支 | 有历史求解数据 | 利用历史信息指导 | 初期效果差 |
| 强分支 | 小型到中型问题 | 选择质量高 | 计算开销大 |
4.3 割平面技术实战
割平面法通过添加有效不等式来缩小可行域。常见割平面类型包括：
- Gomory割：从单纯形表导出
- 覆盖割：针对0-1规划
- 流覆盖割：适用于网络问题
# 添加Gomory割的示例 def add_gomory_cut(model, where): if where == gp.GRB.Callback.MIPSOL: sol = model.cbGetSolution(model._vars) for i in range(model._A.shape[0]): if not sol[i].is_integer(): # 从单纯形表生成割平面 cut = generate_gomory_cut(model, i) model.cbLazy(cut) model._vars = x model.Params.lazyConstraints = 1 model.optimize(add_gomory_cut)在解决某物流中心选址问题时，通过组合使用预处理和割平面技术，将求解时间从8小时缩短到23分钟。关键在于识别问题特有的结构，如运输网络中的树状子结构，据此设计定制化的割平面。
