分配（指派）问题简介
欢迎来到决策数学 2 (Decision Mathematics 2)！我们将从一个在现实生活中非常实用的课题开始：分配问题 (Allocation Problems)。试想你是一间繁忙餐厅的经理。你有四位厨师和四项特定任务（例如：准备食材、烧烤、摆盘和清洁）。有些厨师烧烤速度较快，而另一些则擅长准备食材。你该如何分配，让每个人正好负责一项任务，并使总耗时降至最低？
这正是分配问题的核心。我们的目标是找出将一群人（或机器）与同等数量的任务进行匹配的“最低成本”方案。如果一开始觉得有点棘手也不用担心，我们有一套非常可靠的“食谱”，称为匈牙利算法 (Hungarian Algorithm)，它能助你每次都顺利解决问题！
快速复习：在开始之前，请记住本章通常处理的是方阵 (square matrices)（例如 3x3 或 4x4），因为我们假设人数等于任务数量。
1. 成本矩阵 (Cost Matrix)
你首先会看到的是成本矩阵。这只是一张表格，行代表人员，列代表工作。矩阵内的每个数字都是该人员进行该项工作的“成本”（可以是时间、金钱或距离）。
例子：如果 A 行第 2 列的数值是 15，这意味着人员 A 进行工作 2 需要 15 分钟。
2. 匈牙利算法：逐步详解
匈牙利算法是一种找出最佳分配方案的系统化方法。你可以把它想象成不断“减少”成本直到我们找到零值——这些零代表了最佳的匹配组合！
第 1 步：行减少 (Row Reduction)
在每一行中，找出最小的数字。从该行的每个元素中减去这个数字。重要提示：请务必先处理行！
第 2 步：列减少 (Column Reduction)
观察你新得到的矩阵。在每一列中，找出最小的数字。从该列的每个元素中减去它。（如果某一列已经含有零，则该列保持不变）。
第 3 步：覆盖零值 (Covering Zeros)
尝试使用最少数量的横线和直线来覆盖矩阵中所有的零。
- 如果线的数量等于矩阵的阶数（例如 3x3 矩阵用 3 条线），代表你已经找到最佳解！请跳到第 5 步。
- 如果你使用的线条数量少于矩阵的阶数，请进行第 4 步。
第 4 步：扩充矩阵 (Augmenting the Matrix)
如果线条数量不足，我们需要“制造”更多的零：
1. 找出最小的未被覆盖数字（我们称之为 \(e\)）。
2. 从所有未被覆盖的数字中减去 \(e\)。
3. 将 \(e\) 加到任何被两条线交叉覆盖的数字上。
4. 只被一条线覆盖的数字保持不变。
5. 现在，回到第 3 步，再次尝试覆盖零值。
第 5 步：最终分配
观察零的位置。将人员分配给对应零的工作，确保每个人只分配到一项工作，且每项工作只被执行一次。
记忆小撇步：使用口诀“Really Cool Llamas Act”来记住顺序：Row (行减少)、Column (列减少)、Lines (线条覆盖)、Augment (扩充)！
3. 特殊情况：虚拟任务与不可能的任务
有时候现实世界并非完美的方阵。以下是处理方法：
虚拟行或虚拟列 (Dummy Rows or Columns)
如果你有 3 名员工但有 4 项工作怎么办？你不能让工作空着！我们会加入一个虚拟员工 (dummy worker)。
- 建立一个新行（D 行）。
- 为该行的每一项工作分配 0 的成本。
- 像平常一样解决问题。被分配到“虚拟”工作的人，实际上就是那项没有被真人负责的工作！
数据不完整（不可能的任务）
如果人员 B 对鱼类过敏，不能做“处理鱼类”的工作怎么办？
- 我们将该特定单元格设为极大成本（通常标记为 \(M\) 或像 999 这样非常大的数字）。
- 由于算法会寻找最低成本，它会竭尽所能避开这个“极大”成本！
关键总结
虚拟任务用于将矩阵变为方阵。极大成本用于防止不可能的分配。
4. 最大化而非最小化
通常我们想最小化成本或时间。但如果矩阵中的数字是利润，而我们想要最大化它们呢？
诀窍：要将最大化问题转化为最小化问题：
1. 找出原始矩阵中最大的数字。
2. 用这个最大数字减去矩阵中的每一个数值。
3. 现在，对这个新矩阵正常使用匈牙利算法即可！
例子：如果最高利润是 50，而某单元格是 40，则新值变为 \(50 - 40 = 10\)。求解后，新矩阵中的“最低成本”对应的就是旧矩阵中的“最高利润”。
避开常见错误
- 忘记列减少：许多学生做完行减少后就直接开始画线。一定要检查那些列！
- 画了太多线：永远寻找覆盖零值的绝对最少线条数。如果可以用 2 条线覆盖，就不要用 3 条。
- 交叉点：进行扩充（第 4 步）时，记得将数值加到交叉点上。很容易不小心在那里也做了减法。
快速复习箱
- 目标：以最低成本将 \(n\) 名员工与 \(n\) 项任务进行匹配。
- 算法：匈牙利算法 (行 -> 列 -> 线条 -> 扩充)。
- 非方阵：添加具有零成本的“虚拟”行/列。
- 最大化：先用最大值减去所有数值，再进行计算。
冷知识：匈牙利算法以两位匈牙利数学家 Dénes Kőnig 和 Jenő Egerváry 的名字命名，他们在 1931 年奠定了该算法的基础！直到今天，它仍然是解决这类问题最有效的方法之一。