欢迎来到分配问题 (Allocation Problems)！
你有没有想过，快递公司是如何决定哪个司机应该走哪条路线以节省最多的燃油？或者运动教练如何决定哪位球员应该担任哪个位置以取得最佳成绩？这正是分配问题 (Allocation/Assignment Problems) 的核心所在！
在决策数学 2 (Decision Mathematics 2) 的这一章中，你将学会如何以最高效率将“员工”与“工作”进行配对。虽然起初这些数字看起来很复杂，但这其实是一个非常有逻辑、一步步解开的谜题。如果觉得过程看起来有点机械化，请不用担心；一旦你掌握了匈牙利算法 (Hungarian Algorithm) 的节奏，你很快就会成为效率专家！
1. 理解目标
分配问题涉及一系列任务以及执行这些任务的等量人数（或机器）。每个人在执行每项任务时都有不同的“成本”（这可以是时间、金钱或距离）。
目标：我们希望指派刚好一个人负责一项任务，从而使总成本达到最小化。
我们这些成本表示在一个成本矩阵 (cost matrix) 中。例如，如果我们有 3 名员工 (A, B, C) 和 3 项工作 (1, 2, 3)，矩阵会显示员工 A 执行工作 1 的“成本”，以此类推。
你知道吗？这个方法被称为匈牙利算法，是因为它是由两位匈牙利数学家 Dénes Kőnig 和 Jenő Egerváry 所开发的！
重点总结：分配问题的核心在于找到“最佳配对”，以保持总成本尽可能低。
2. 成本矩阵简化 (Cost Matrix Reduction)
在我们解题之前，需要先将矩阵“简化”。这可以在不改变最佳指派结果的前提下简化数字。注意：在 Edexcel 课程大纲中，你必须先进行列简化 (reduce rows)。
步骤 A：列简化 (Row Reduction)
1. 逐行查看。
2. 找出该行中最小的数字。
3. 将该行中的所有数字减去这个最小值。
结果：每一行现在至少会有一个零。
步骤 B：行简化 (Column Reduction)
1. 查看你刚刚产生的新矩阵。
2. 逐列查看。
3. 找出该列中最小的数字。
4. 将该列中的所有数字减去这个最小值。
结果：现在每一行 AND 每一列应该都至少会有一个零。
小撇步：如果在列简化后某一行已经有零，那么行简化不会改变它（因为你减去的是 0）！
重点总结：简化过程创造了“机会成本”。这些零代表了每位员工或每项工作的最佳选项。
3. 匈牙利算法
一旦简化了矩阵，你需要检查是否仅利用这些零就能做出完美的分配。如果不可以，则需要调整矩阵。
“覆盖线”测试 (Line Cover Test)
画出最少数量的水平线和垂直线，以覆盖矩阵中所有的零。
• 如果线的数量等于矩阵的大小 (\( n \))，则可以进行最佳分配。
• 如果线的数量小于 \( n \)，则必须改进矩阵。
改进矩阵（“最小未覆盖”法则）
如果线的数量不足，请遵循以下步骤：
1. 找出没有被任何线覆盖的数值中最小的一个，我们称之为 \( e \)。
2. 将所有没有被任何线覆盖的元素减去 \( e \)。
3. 将所有位于两条线交叉点上的元素加上 \( e \)。
4. 被单一线覆盖的元素保持不变。
5. 在这个新矩阵上重复“覆盖线”测试。
类比：想象这些线是“已满”的路径。通过将未覆盖位置减去 \( e \)，你创造了新的“空闲”路径（即零）。通过在交叉点加上 \( e \)，你等于是在为同时使用了两条路径“付出了代价”。
重点总结：我们不断进行调整，直到覆盖零所需的线数等于矩阵的行数/列数。
4. 做出最终分配
当线的数量等于 \( n \) 时，你就可以选取你的零了！
逐步配对：
1. 寻找只有一个零的行或列。圈选它，并划掉该行或该列中的任何其他零。
2. 重复此步骤，直到每位员工都恰好分配到一项工作。
3. 使用原始成本矩阵，将所选配对的成本相加，以计算最终的最小总成本。
常见错误：学生经常使用简化后的矩阵来计算总成本。务必回到题目开头的原始数字进行计算！
5. 处理特殊情况
现实生活中的情况并不总是完美的正方形。以下是如何处理这些“棘手”数据的方法：
虚拟位置 (Dummy Locations)（行数与列数不等时）
匈牙利算法仅适用于正方形矩阵（例如，4 名员工对 4 项工作）。
• 如果你有 4 名员工但只有 3 项工作，请增加一个“虚拟工作 (Dummy Job)”列。
• 为虚拟工作设置所有员工的成本为 0。
• 这代表了一名员工处于闲置状态。
不完整数据（“不可能”的任务）
有时某位员工在生理上无法执行特定任务。在你的矩阵中，用一个非常大的成本替换这个“不可能”的连接，通常用字母 \( M \) 表示。
• 因为 \( M \) 非常大，算法绝不会将其选为最小成本选项。
重点总结：使用虚拟项使矩阵变为正方形，并使用 \( M \) 来屏蔽特定的指派。
6. 最大化利润
如果矩阵中的数字不是“成本”而是“利润”怎么办？我们需要的是最高总额，而不是最低总额。
技巧：我们必须将一个最大化问题转化为最小化问题。
1. 找出整个原始矩阵中最大的数值。
2. 用这个最大值减去矩阵中的每一个数值。
3. 现在，对这个新矩阵正常执行匈牙利算法。
鼓励一下：这感觉有点反直觉，对吧？但通过从最大值中减去所有数字，最好的利润就变成了“0”成本！相信这个过程。
重点总结：要进行最大化，先将所有值从最大值中减去，从而“反转”矩阵。
快速复习清单
1. 先进行列简化：减去每行中的最小值。
2. 进行行简化：减去每列中的最小值。
3. 覆盖零：使用最少的线。
4. 线 < \( n \)？：将未覆盖值减去最小的未覆盖数值；在交叉点加上该数值。
5. 线 = \( n \)？：将员工指派到零的位置。
6. 最终成本：最终总和务必使用原始矩阵的数值。
如果起初觉得棘手也不用担心——只要练习两到三个完整的题目，这个模式很快就会变得像直觉一样自然！