← 返回资讯屏轩教育 · 行业资讯

The Appointment Process and its Strengths and Weaknesses | 指派过程及其优缺点

2026-08-29 22:04 · 本文部分内容由AI辅助创作

📚 The Appointment Process and its Strengths and Weaknesses | 指派过程及其优缺点

In Edexcel A-Level Mathematics, especially in Decision Mathematics, an appointment process is often modelled as an assignment problem: a set of workers must be matched to a set of tasks at minimum total cost or maximum total benefit. The standard solution method is the Hungarian algorithm. This article explains how the appointment process works and evaluates its main strengths and limitations in the context of the A-Level syllabus.

在 Edexcel A-Level 数学中，尤其是在决策数学模块里，指派过程通常被建模为分配问题：一组工作者必须与一组任务一一匹配，使总成本最小或总收益最大。标准的求解方法是匈牙利算法。本文介绍指派过程的运作方式，并结合 A-Level 考纲评价其主要优点与局限性。

1. What is the Appointment Process? | 什么是指派过程？

An appointment process assigns n agents to n tasks. Each agent can perform exactly one task, and each task requires exactly one agent. The objective is to minimise total cost or maximise total profit.

指派过程将 n 个工作者分配给 n 个任务。每个工作者只能完成一个任务，每个任务也只需要一个工作者。目标是使总成本最小或总收益最大。

In a cost matrix, rows usually represent agents and columns represent tasks. The entry cᵢⱼ is the cost of assigning agent i to task j. The same structure can represent profit, time, or distance.

在成本矩阵中，行通常代表工作者，列代表任务。元素 cᵢⱼ 表示将工作者 i 分配给任务 j 的成本。同样的结构也可以表示利润、时间或距离。

2. The Standard Assignment Model | 标准分配模型

A standard assignment model is balanced: the number of agents equals the number of tasks. The decision variable xᵢⱼ equals 1 if agent i is assigned to task j, and 0 otherwise.

标准分配模型是平衡的：工作者数量等于任务数量。决策变量 xᵢⱼ 在工作者 i 分配给任务 j 时等于 1，否则等于 0。

The objective is to minimise Z = Σᵢ Σⱼ cᵢⱼ xᵢⱼ d one per column. These constraints make the problem a special case of linear programming.

目标是最小化 Z = Σᵢ Σⱼ cᵢⱼ xᵢⱼ，并满足每行每列各有一个分配。这些约束使该问题成为线性规划的一个特例。

3. Balanced and Unbalanced Appointment Problems | 平衡与不平衡的指派问题

If the number of agents does not equal the number of tasks, the problem is unbalanced. A dummy row or column with zero costs is added to create a square matrix before the Hungarian algorithm is applied.

如果工作者数量与任务数量不相等，问题就是不平衡的。在应用匈牙利算法前，需要添加一个虚拟行或虚拟列，其成本为零，以构成方阵。

This step is important because the Hungarian algorithm only solves square cost matrices directly. Missing the dummy step is a common exam error.

这一步非常重要，因为匈牙利算法只能直接求解方阵形式的成本矩阵。遗漏虚拟行或列是考试中的常见错误。

4. The Hungarian Algorithm: Overview | 匈牙利算法：概述

The Hungarian algorithm is an efficient procedure for solving assignment problems. It works by reducing the cost matrix so that a set of independent zeros reveals the optimal assignment.

匈牙利算法是求解分配问题的一种高效方法。它通过化简成本矩阵，使一组独立零元素显现出最优分配。

The main steps are row reduction, column reduction, covering zeros, and revising the matrix until the minimum number of covering lines equals n. Each step preserves the optimal assignment in terms of relative costs.

主要步骤包括行化简、列化简、覆盖零元素，以及不断修改矩阵，直到最少覆盖线数等于 n。每一步都在相对成本的意义上保持最优分配不变。

5. Step 1 – Row Reduction | 第 1 步——行化简

For each row, subtract the smallest entry in that row from every entry in the row. This creates at least one zero in each row without changing the relative costs of assignments.

对于每一行，从该行的每个元素中减去该行的最小值。这样每一行至少出现一个零，且不改变各分配方案的相对成本。

with rows (5, 3, 8), (2, 7, 6), (4, 5, 9), row reduction subtracts 3, 2, 4 respectively to give (2, 0, 5), (0, 5, 4), (0, 1, 5).

例如：若某行为 (5, 3, 8)，减去 3 后得到 (2, 0, 5)。对于一个完整的 3 × 3 矩阵，行分别为 (5, 3, 8)、(2, 7, 6)、(4, 5, 9)，行化简分别减去 3、2、4，得到 (2, 0, 5)、(0, 5, 4)、(0, 1, 5)。

6. Step 2 – Column Reduction | 第 2 步——列化简

After row reduction, examine each column. If a column contains no zero, subtract the smallest entry in that column from all entries in that column.

行化简后，检查每一列。如果某列没有零，则从该列所有元素中减去该列的最小值。

In the example above, the matrix after row reduction is (2, 0, 5), (0, 5, 4), (0, 1, 5). Column 1 already has zeros, column 2 has a zero, but column 3 has no zero. Subtract the smallest entry in column 3, which is 4, from all entries in that column to obtain (2, 0, 1), (0, 5, 0), (0, 1, 1).

在上面的例子中，行化简后的矩阵为 (2, 0, 5)、(0, 5, 4)、(0, 1, 5)。第 1 列已有零，第 2 列有零，但第 3 列没有零。将第 3 列的最小值 4 从该列所有元素中减去，得到 (2, 0, 1)、(0, 5, 0)、(0, 1, 1)。

The result is a reduced cost matrix in which every row and every column has at least one zero.

结果是一个化简后的成本矩阵，其中每一行和每一列都至少有一个零元素。

广告 / Sponsored

🛒
TI-Nspire CX II CAS 图形计算器 A-Level数学
¥1298
📱 去京东购买
京东精选

7. Step 3 – Covering Zeros and the Optimality Test | 第 3 步——覆盖零元素与最优性检验

Draw the minimum number of horizontal and vertical lines needed to cover all zeros in the reduced matrix. If the number of lines equals n, an optimal assignment can be made using the uncovered zeros.

用最少的水平线和垂直线覆盖化简矩阵中的所有零元素。如果覆盖线数等于 n，则可以利用未覆盖的零元素作出最优分配。

r column 3, and one horizontal line for row 1. Since 3 = n, the current matrix is optimal.

对于化简后的矩阵 (2, 0, 1)、(0, 5, 0)、(0, 1, 1)，覆盖所有零元素需要三条线：第 1 列一条垂直线，第 3 列一条垂直线，第 1 行一条水平线。因为 3 = n，所以当前矩阵已达到最优。

If the number of lines is less than n, the solution is not yet optimal and the matrix must be revised.

如果覆盖线数小于 n，则当前解尚不是最优解，必须修改矩阵。

8. Step 4 – Revising the Matrix | 第 4 步——修改矩阵

If the minimum number of covering lines is less than n, find the smallest uncovered entry. Subtract this value from all uncovered entries, and add it to entries at intersections of covering lines. Then repeat the covering test.

如果最少覆盖线数小于 n，找出未被覆盖的最小元素。从所有未被覆盖的元素中减去这个值，并在覆盖线的交叉点元素上加上这个值。然后重新进行覆盖检验。

This adjustment creates additional zeros without destroying existing ones, and it moves the process towards the optimum. The algorithm terminates when the covering line count equals n.

这种调整在保留原有零元素的同时产生新的零元素，从而推动过程向最优解靠近。当覆盖线数等于 n 时，算法终止。

9. Selecting the Optimal Assignment | 选择最优分配

Once the minimum number of covering lines equals n, choose exactly one zero in each row and each column. This set of zeros gives the optimal appointment for the original cost matrix.

一旦最少覆盖线数等于 n，就在每一行和每一列中恰好选择一个零元素。这组零元素就给出了原成本矩阵的最优指派方案。

In the example, the chosen zeros are in row 1 column 2, row 2 column 3, and row 3 column 1. The corresponding original costs are 3, 6, and 4, giving a minimum total cost of 13.

在该例中，选出的零元素位于第 1 行第 2 列、第 2 行第 3 列和第 3 行第 1 列。对应的原始成本分别为 3、6 和 4，因此最小总成本为 13。

The total minimum cost is found by adding the original costs corresponding to the chosen zeros.

将所选零元素对应的原始成本相加，即可得到最小总成本。

10. Strengths of the Appointment Process | 指派过程的优点