02 — 数学建模 / SCHEDULING
展销会排班 Optimization
ILP 整数规划 · 三步法数学证明 · 东北三省数模省一
400 人展销会 10 天 11 时段排班，ILP 整数规划求解，三步法证明 400 人是理论下界。
01 — WHY
为什么做
某大型展销会持续 10 天，设 10 个展区，每日营业时间 8:00 - 19:00，共 11 个时段。每个时段、每个组的人力需求不同，临时工管理面临三个核心问题：
- 招多少人？招多了浪费，招少了崩盘。
- 怎么排？每人每天 2 个 4 小时班次，中间至少间隔 6 小时；10 天内工作 8 天、休息 2 天。
- 能不能证明这是最优？不只是"找到一个方案"，而是"证明这就是最好的方案"。
题目分三问：Q1 固定组别 → Q2 允许换组 → Q3 弹性排班，层层递进。
02 — WHAT
三个问题 · 三个最优解
| 问题 | 约束 | 最优工人数 |
|---|---|---|
| Q1 固定组别 | 工人不换组，按 8 个 4 小时班次配对 | 417 人 |
| Q2 允许换组 | 每天可换组，班次可不连续 | 406 人 |
| Q2 班次间隔 | 增加"班次间休息 1 小时"约束 | 506 人 |
| Q3 弹性排班 | 块间隔 6 小时 + 严格证明 | 400 人（下界） |
🏆 核心结论：在最宽松的 Q3 条件下，我们严格证明 400 人是该问题的理论下界，并验证 400 人方案可行。
3,198
总工日需求
110
时段-组组合
400
最少工人数
省一
东北三省奖项
03 — HOW
三步法数学证明
这是论文最有价值的部分——不仅"找到" 400 人这个解，而是从三个维度证明"400 不能再少了"。
| 步骤 | 模型 | 规模 | 作用 |
|---|---|---|---|
| Step 1 下界证明 | 聚合 ILP 模型 | 6,000 变量 + 1,100 约束 | 证明总工日 ≥ 3,198 |
| Step 2 人数上限 | 理论推导 | — | 199 人不可能（199×8=1,592 < 需求） |
| Step 3 可行性 | Per-Worker 紧凑模型 | 16.2 万变量（45 种 8 天工作模式） | 证明 400 人方案能满足所有时段 |
为什么是 400？10 天 11 时段共 110 个时段-组组合，累计需求 3,198 工日。每人最多工作 8 天，所以工人数 ≥ ⌈3,198/8⌉ = 400。
04 — HARD
我解决的难点
- 模型规模爆炸：Step 3 的 Per-Worker 模型有 16.2 万变量，需要用 CBC 求解器配合聚合策略才能在合理时间内出解。
- 下界 vs 实际可行：数学下界 400 不一定"凑得出"实际排班表——必须再用紧凑模型验证可行性。
- 约束层层累加：Q1 → Q2 → Q3 约束复杂度指数上升，每个都要重新求解 + 验证。
- 三人协作：组长负责建模 + 代码 + 论文核心推导，另外两位负责资料整理和写作辅助。