EP02. “Assignment Problem 指派问题”
🔒 登录后可标记已读- 指派问题是"把 N 个人分配去做 N 项任务，每人只能做一项、每项任务只需一人，怎么分配总成本最低"这类最优化问题
- 用 0/1（是否分配）的二进制变量建模，再交给 Solver 求解
- 这篇笔记延续 EP01 的建模思路，示范怎么处理"二进制约束"这种特殊限制
- 前置知识是本分类 EP01（Transportation Problem，含 Solver 加载项启用方法）
- 学完能处理"一对一分配"类型的最优化问题
重点内容
适用版本
桌面版通用（Excel 365 / 2021 / 2019 等）。若未启用 Solver 加载项，先参考 EP01 的启用步骤（File → Options → Add-ins）。
第一步：建立模型
三个核心问题：
- 决策变量：每个人是否分配到每项任务，用 1 表示分配、0 表示不分配
- 约束条件：每人只能分配到一项任务，每项任务只能分配给一人
- 目标函数：让总成本最小化
命名范围：涉及成本（Cost）、任务分配变量（Assignments）、已分配人员合计、需求（Demand）、已分配任务合计、供给（Supply）、总成本（TotalCost）等，跟 EP01 运输问题的命名逻辑一致，只是把"运送量"换成了"是否分配"。
第二步：试错法
先手动试一组分配方案：第 1 人做任务 1、第 2 人做任务 2、第 3 人做任务 3，算出总成本是 147，作为对照基准。
第三步：用 Solver 求解
- Data → Analyze → Solver
- Set Objective 选总成本单元格，选择 Min
- By Changing Variable Cells 选分配变量的范围
- 添加三类约束：
- 二进制约束：分配变量必须是 Bin（binary，只能是 0 或 1）
- 需求约束：每项任务恰好分配给一人
- 供给约束：每人恰好分配到一项任务
- Solving Method 选 Simplex LP
- 点击 Solve
[截图：Solver 约束列表，包含 Bin 二进制约束那一条]
📌 关键差异：指派问题比运输问题多了一个"二进制约束"（Bin），因为这里的决策不是"运送多少单位"这种连续数量，而是"分配或不分配"这种是非题，必须限制变量只能取 0 或 1。
求解结果
最优解：第 1 人 → 任务 2，第 2 人 → 任务 3，第 3 人 → 任务 1，总成本降到 129（比试错法的 147 更低）。
[截图：分配变量矩阵，最优解对应位置显示 1、其余显示 0]
学完你会
- ✅ 用 0/1 二进制变量给「一对一分配」问题建模
- ✅ 给分配变量加上 Bin（二进制）约束，避免算出不合理的部分分配
- ✅ 用 Solver 求出比手动试错更低成本的分配方案
常见错误
- 忘记把分配变量的约束设成 Bin（二进制），Solver 可能算出 0.6、0.3 这种不合理的"部分分配"结果
- 人数和任务数不相等时直接套用"每人一项、每项一人"的约束，模型会无解，需要先确认是不是方阵（人数=任务数）
- 只对照了一组试错方案就认定 Solver 结果一定更优，没有多试几组手动方案交叉验证
Sources
Blog / Website：