Allocation (assignment) problems

欢迎来到分配问题！

你有没有想过，快递公司如何决定哪位司机应该走哪条路线以节省最多的燃油？或者运动教练如何分配球员位置以获得最佳赛果？这正是分配问题（Allocation Problems / Assignment Problems）的核心！在决策数学 2（Decision Mathematics 2）的这一章中，我们将学习如何使用一种名为匈牙利算法（Hungarian Algorithm）的巧妙方法，每次都能精准地做出这些决定。如果一开始觉得步骤很多，别担心；只要掌握了节奏，它就像跟着食谱做菜一样简单！

1. 什么是分配问题？

分配问题涉及将一组“工作者”分配给一组同样数量的“任务”，目标是最小化总成本（或最大化总利润）。

核心规则：每位工作者必须且只能分配到一个任务，且每个任务必须由一位工作者完成。这称为一对一匹配（one-to-one matching）。

我们使用成本矩阵（cost matrix）来表示这些问题，其中矩阵内的数字代表特定工作者完成特定任务的成本。

小知识：分配问题实际上是你上一章学到的运输问题的一个特殊简化版本。运输问题处理的是“多对多”，而分配问题则严格要求“一对一”！

重点总结：

分配问题旨在找出两组对象之间最高效的一对一配对，通常以方阵形式表示。

2. 匈牙利算法（成本最小化）

匈牙利算法是寻找成本最低分配的“黄金标准”。它的原理是通过简化矩阵，直到最佳选择以零的形式呈现出来。

步骤流程：

步骤 1：列简化（Row Reduction）
查看每一列，找出该列中的最小数字，并从该列的所有数字中减去它。目标是确保每一列至少有一个零。

步骤 2：行简化（Column Reduction）
现在查看新矩阵的每一行（列）。找出该行中的最小数字，并从该行的所有数字中减去它。现在，每一列和每一行都应该至少有一个零。

步骤 3：覆盖零点（Cover the Zeros）
尝试使用最少数量的水平线和垂直线覆盖矩阵中的所有零。
记忆小技巧：想象这就像玩扫雷——你希望用最少的“胶带”来遮住每一个零。

步骤 4：是否为最佳解？
计算你的线条数量。
- 如果线条数量 = 矩阵阶数（例如 3x3 矩阵用了 3 条线），代表你已经找到最佳解！直接跳到步骤 6。
- 如果线条数量少于矩阵阶数，你需要对矩阵进行“增广”（步骤 5）。

步骤 5：增广矩阵（Augmenting the Matrix）
这是学生最常觉得棘手的部分，我们慢慢来：
1. 找出最小的未被覆盖数字（设为 \(e\)）。
2. 从所有未被覆盖的数字中减去 \(e\)。
3. 在所有两条线相交的位置（交点）加上 \(e\)。
4. 只被一条线覆盖的数字保持不变。
5. 回到步骤 3，尝试重新覆盖零点。

步骤 6：分配（Assigning）
寻找在该列或该行中唯一的零，将该工作者分配给该任务。划掉该行和该列，重复此过程直到所有人都完成匹配。

快速回顾：增广矩阵的“3 条法则”

- 未被覆盖？ 减去。
- 交点？ 加上。
- 被一条线覆盖？ 保持不变。

3. 处理“不对称”问题

有时候，现实生活中的问题并非完美的方阵。如果你有 4 个工人但只有 3 个工作，或者某个工人因故无法执行特定任务怎么办？

虚拟位置（Dummy Locations）

匈牙利算法只能在方阵上运作。如果你有一个 3x4 的矩阵，你必须添加一个虚拟（dummy）行或列使其变成 4x4。
- 虚拟行/列中所有单元的成本均设为 0。
- 类比：想象在玩抢椅子游戏时增加了一张隐形的“鬼椅”。如果有人被分配到鬼椅，这就代表他们在最终结果中没有分到真实的椅子！

不完整数据（“大 M”法 / Big M Method）

如果某项任务不能分配给特定的工作者（例如他们缺乏相关证照），我们不希望算法选取该单元。我们给该单元赋予一个无限大的成本（以 \(M\) 或 \(\infty\) 表示）。由于我们的目标是最小化成本，算法会不惜一切代价避开“M”单元！

常见错误：

别忘了步骤 2（行简化）！许多学生做完列简化后，看到每一行似乎都有零，就以为可以跳过步骤 3。务必检查每一行；如果某一行没有零，你必须减去该行中的最小值。

4. 最大化利润

如果矩阵中的数字不是“成本”（坏事），而是“利润”（好事）怎么办？匈牙利算法是为最小化而设计的，所以我们必须用点小技巧，让它帮我们计算最大化。

如何修改算法：

1. 找出原始矩阵中最大的数值。
2. 用这个最大值减去矩阵中的每一个数值。
3. 这会创造一个新的“机会成本”矩阵。
4. 对这个新矩阵执行标准的匈牙利算法以求最小值。这个最小值对应的即是原始问题的最大利润！

例子：如果你的最高利润是 £50，而某个单元的利润是 £10，那么选取该单元的“损失”就是 £40。通过最小化“损失”，你就是在最大化利润！

5. 线性规划公式化（Linear Programming）

你可能会被要求展示如何将分配问题写成线性规划（Linear Program, LP）。这只是将我们“一对一”规则书写下来的一种正式方式。

设 \(x_{ij}\) 为一个变量：
- 若工作者 \(i\) 被分配给任务 \(j\)，\(x_{ij} = 1\)。
- 若工作者 \(i\) 未被分配给任务 \(j\)，\(x_{ij} = 0\)。

目标函数：
最小化 \(C = \sum \sum (c_{ij} \times x_{ij})\)
（意思是：将每个成本乘以其 1 或 0 并加总）。

约束条件：
1. 每位工人只能做一个任务：对于每一列，\(x\) 值的总和必须等于 1。
\(\sum_{j=1}^{n} x_{ij} = 1\) (针对所有 \(i\))
2. 每个任务只能由一位工人完成：对于每一行，\(x\) 值的总和必须等于 1。
\(\sum_{i=1}^{n} x_{ij} = 1\) (针对所有 \(j\))

重点总结：

将问题表述为线性规划使电脑能够“读懂”它。这些约束条件确保了最终分配矩阵中每一列和每一行都恰好有一个“1”，其余皆为“0”。

最终总结检查清单

- 矩阵是方阵吗？ 如果不是，添加一个虚拟行/列（成本设为 0）。
- 这是最大化问题吗？ 如果是，先用最大值减去所有数值。
- 是否有无法完成的任务？ 这些成本设为 \(M\)。
- 步骤 1：列减法。
- 步骤 2：行减法。
- 步骤 3：用最少线条覆盖零点。
- 步骤 4：线条数量 < 矩阵阶数？进行增广（未覆盖处减去，交点加上）。
- 步骤 5：利用零进行最终分配。

继续练习！你“简化”的矩阵越多，匈牙利算法就会变得越自然。你一定没问题的！