📚 The Assignment Problem: Process, Strengths and Weaknesses | 指派问题的过程与优缺点
In Edexcel A-Level Mathematics, particularly within the Decision Mathematics 1 (D1) module, the assignment problem (sometimes informally called the appointment problem) models how to allocate a set of tasks to a set of agents in a one-to-one manner, minimising total cost or maximising profit. This article examines the standard step-by-step solution method – the Hungarian algorithm – and critically assesses its strengths and weaknesses.
在 Edexcel A-Level 数学中，特别是在决策数学 1 (D1) 模块里，指派问题（有时也通俗地叫做 appointment problem，即任命或分派问题）描述的是如何将一组任务一对一地分配给一组执行者，以最小化总成本或最大化利润。本文探讨标准的逐步求解方法——匈牙利算法，并批判性分析其优点与缺点。
1. What is the Assignment Problem? | 什么是指派问题？
The assignment problem is a special type of linear programming problem where there are n tasks and n workers (or machines). Each worker must be assigned exactly one task, and each task must be assigned to exactly one worker. The objective is to find the allocation that minimises the total cost, given a cost matrix showing the cost of assigning each worker to each task.
指派问题是一类特殊的线性规划问题，设有 n 项任务和 n 个工人（或机器）。每名工人必须且只能分配一项任务，每项任务也必须且只能分配给一名工人。给定一个成本矩阵，其元素表示将各工人分配到各任务的成本，目标是找到一个分配方案使总成本最小。
2. Mathematical Model | 数学模型
Let cij be the cost of assigning worker i to task j. We define a decision variable xij equal to 1 if worker i is assigned to task j, and 0 otherwise. The formulation is:
设 cij 为工人 i 完成任务 j 的成本。定义决策变量 xij，若工人 i 被指派给任务 j 则取值为 1，否则为 0。数学模型为：
Minimise Σᵢ Σⱼ cij xij
subject to Σⱼ xij = 1 for each i, Σᵢ xij = 1 for each j, xij ∈ {0,1}.
The constraints ensure that every worker is assigned exactly one task and every task is assigned exactly one worker. This structure is what makes the Hungarian algorithm particularly efficient.
约束条件保证了每个工人都被分配恰好一项任务，每项任务也恰被分配一名工人。正是这一特殊结构使得匈牙利算法特别高效。
3. The Hungarian Algorithm: An Overview | 匈牙利算法概述
The Hungarian algorithm is a combinatorial optimisation technique that solves the assignment problem in O(n3) time. It works directly on the cost matrix through row and column reductions, transforming the matrix so that an optimal assignment can be read off from zero entries once a complete set of independent zeros is found.
匈牙利算法是一种组合优化技术，能在 O(n3) 时间内求解指派问题。它直接在成本矩阵上操作，通过行归约和列归约，将矩阵变换至找到一组完全独立的零元素时，即可从这些零条目直接读出最优分配方案。
4. Step 1 – Row Reduction | 第一步 – 行归约
From each row, subtract the smallest entry in that row from every element in the row. This creates at least one zero in each row, and the relative costs between cells in the same row remain unchanged. This operation does not affect the optimal assignment because any feasible solution will contain exactly one element from each row, so subtracting a constant from a row reduces the total cost by that constant regardless of which column is selected.
对每一行，找出该行的最小元素，然后将该行所有元素减去这个最小值。这样每一行至少出现一个零，且同行内单元格的相对成本保持不变。这一操作不影响最优分配，因为任何可行解都恰从每行选取一个元素，从一行减去常数会使总成本减去相同的常数，无论选中哪一列。
Example – initial matrix:
| 8 | 5 | 7 |
| 4 | 6 | 3 |
| 2 | 5 | 4 |
Row minima: 5, 3, 2. After row reduction:
| 3 | 0 | 2 |
| 1 | 3 | 0 |
| 0 | 3 | 2 |
5. Step 2 – Column Reduction | 第二步 – 列归约
Next, examine each column of the row-reduced matrix. If any column does not contain a zero, subtract the smallest entry in that column from every element in that column. This step ensures that every column also has at least one zero without altering the set of optimal assignments, because exactly one element is chosen from each column in a feasible solution.
接下来，检查行归约后矩阵的每一列。如果某一列没有零，则用该列的最小元素去减该列的所有元素。这一步确保每列也至少有一个零，且不改变最优分配集合，因为可行解中恰好从每列选取一个元素。
In our example every column already contains a zero, so no change is needed.
在我们的例子中，每列都已经有零，因此无需改变。
6. Step 3 – Covering Zeros with Minimum Lines | 第三步 – 用最少线覆盖零
Draw the minimum number of horizontal and vertical lines required to cover all zeros in the matrix. If the number of lines equals n, an optimal assignment is available. If the number of lines is less than n, the matrix must be adjusted. The technique for finding the minimum lines involves marking rows without an assigned zero, marking columns with zeros in marked rows, and so on.
画出覆盖矩阵中所有零所需的最少数量的水平线和垂直线。如果线条的数量等于 n，则已可获得最优分配。如果线条数量小于 n，则必须调整矩阵。寻找最少线条的技巧包括：标记没有已分配零的行，再标记在已标记行中有零的列，等等。
7. Step 4 – Adjusting the Matrix | 第四步 – 调整矩阵
When the minimum lines are fewer than n, identify the smallest uncovered element. Subtract this value from every uncovered element, and add it to every element that lies at the intersection of a covering line. This creates new zeros while preserving the cost relationships. Then return to the covering step and repeat until the number of lines equals n.
当最少线条数小于 n 时，找出未被线覆盖的最小元素。从所有未被覆盖的元素中减去该值，并将其加到被线交叉覆盖的元素上。这将产生新的零，同时保持成本关系。然后回到覆盖步骤，重复直到线条数等于 n。
8. Completing the Assignment | 完成指派
Once the number of covering lines equals n, an optimal assignment can be found by selecting exactly one zero in each row and each column, ensuring no two zeros share a row or column. The positions of these independent zeros give the assignment: assign worker i to task j if the cell (i,j) holds a selected zero. The total minimum cost is then obtained by summing the original costs in these positions.
一旦覆盖线条数等于 n，就可以通过在每个行和列中恰好选择一个零来获得最优分配，并确保没有两个零在同一行或同一列。这些独立零的位置就给出了分配方案：如果单元格 (i,j) 中的零被选中，则将工人 i 分配给任务 j。然后将这些位置对应的原始成本相加，即得总的最小成本。
9. Special Cases: Maximisation and Unbalanced | 特例：最大化与不平衡问题
If the problem is to maximise profit, convert it to a minimisation problem by subtracting all entries from a large number (e.g., the largest entry in the matrix) or by multiplying by -1 and then adding a constant to make all entries non-negative. For unbalanced problems where the number of workers and tasks differ, add dummy rows or columns with zero cost to form a square matrix before applying the algorithm.
如果是最大化利润问题，可将其转化为最小化问题：用一个较大的数（如矩阵中的最大元素）减去所有条目，或乘以 -1 再加常数使所有条目非负。对于工人与任务数量不相等的不平衡问题，在应用算法前，需添加具有零成本值的虚拟行或虚拟列，以构成方阵。
10. Strengths of the Assignment Process | 指派过程的优点
The Hungarian algorithm is straightforward to apply by hand for small matrices (up to about 5x5). Its logical, tabular approach reduces the chance of error, and it always produces the globally optimal solution rather than a local one. The method does not require any linear programming software, making it accessible for examinations and small-scale practical problems.
对于小型矩阵（大约 5x5 以内），匈牙利算法可以方便地手工执行。其逻辑清晰的表格化方法降低了出错的可能性，并且总是产生全局最优解，而非局部最优。该方法不需要任何线性规划软件，因此非常适用于考试和小规模的实际问题。
The algorithm guarantees optimality because it works with the concept of 'regret' values and systematically reduces the cost matrix until a zero-cost assignment is revealed. It can also handle maximisation and rectangular matrices with simple transformations, which makes it versatile within the scope of A-Level D1.
该算法保证最优性，因为它基于“后悔值”的概念，并系统地约简成本矩阵，直到出现零成本分配。它还可通过简单变换处理最大化和矩形矩阵，这使得它在 A-Level D1 范围内具有很强的通用性。
11. Weaknesses of the Assignment Process | 指派过程的缺点
The assignment model assumes a strict one-to-one mapping; it does not accommodate scenarios where a worker can perform multiple tasks or where capacity constraints exist. It also requires all cost coefficients to be deterministic and constant, so it cannot capture uncertain or time-dependent costs.
指派模型假设严格的一对一映射；它无法处理一个工人可以执行多项任务或存在容量限制的情形。它同时要求所有成本系数是确定性的、固定的，因此不能反映不确定性或随时间变化的成本。
Although the algorithm is polynomial in complexity, manual execution becomes tedious and error-prone for matrices larger than about 7x7. The iterative covering and adjusting loop requires careful record-keeping. Additionally, the method is purely static: it cannot be used directly for sequential or dynamic assignment problems that arise in real-time scheduling.
尽管算法在复杂度上为多项式级，但对于大于约 7x7 的矩阵，手工执行会变得繁琐且易错。反复的覆盖和调整循环需要细致记录。此外，该方法纯粹是静态的：它不能直接用于实时调度中出现的序贯或动态指派问题。
12. Conclusion | 结论
The Hungarian algorithm is a powerful, elegant tool for solving the classic assignment problem, offering simplicity and a guarantee of optimality that make it ideal for the Edexcel D1 syllabus. However, its limitations remind us that real-world allocation often requires more flexible models, such as transportation problems or general linear programming. Understanding both the strengths and the weaknesses of the appointment process enables students to choose the right tool for the right problem.
匈牙利算法是求解经典指派问题的强大而精巧的工具，其简单性和最优性保证使其完美契合 Edexcel D1 大纲。然而，它的局限性也提醒我们，现实世界中的分配往往需要更灵活的模型，如运输问题或通用线性规划。理解指派过程的优点与缺点，可以帮助学生在面对不同问题时选择合适的工具。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图