指派问题

指派问题为每项任务恰好安排一个执行者，同时每名执行者恰好领取一项任务，使总成本最小。它是运输问题中每个供给量、需求量都等于一的情况；关键约束是“一对一”，不能让同一个人用很小的分数同时完成三项任务。

三人三岗的完整算例

三名工作人员 A、B、C 分别完成任务甲、乙、丙所需的成本如下。表内数字只用于演示同一成本单位的比较。

人员	甲	乙	丙
A	4	1	3
B	2	0	5
C	3	2	2

令 $x_{i j} = 1$ 表示人员 $i$ 执行任务 $j$ ，否则为零。每一行、每一列的变量和都等于一，目标是最小化 $\sum_{i, j} c_{i j} x_{i j}$ 。可执行方案与三个任务的一种排列一一对应；因此三人情形共有 $3! = 6$ 种方案。按 A、B、C 所分配任务的次序，它们的费用是：甲乙丙为 $4 + 0 + 2 = 6$ ；甲丙乙为 11；乙甲丙为 $1 + 2 + 2 = 5$ ；乙丙甲为 9；丙甲乙为 7；丙乙甲为 6。故 A 做乙、B 做甲、C 做丙，最低费用为 5。

用行列权重核实答案

大表不宜枚举全部排列。若能找到行权重 $u_{i}$ 和列权重 $v_{j}$ ，使每一格都有 $u_{i} + v_{j} \leq c_{i j}$ ，则任何指派的费用至少是 $\sum_{i} u_{i} + \sum_{j} v_{j}$ ：被选的格子每行每列各出现一次。对本表取 $(u_{A}, u_{B}, u_{C}) = (0, - 1, 0), (v_{甲}, v_{乙}, v_{丙}) = (3, 1, 2) .$ 逐格检验，例如 B—乙格给 $- 1 + 1 = 0 = c_{B, 乙}$ ，C—甲格给 $0 + 3 = 3 = c_{C, 甲}$ ；其余格也不超过表内成本。这些权重的总和为 $- 1 + 3 + 1 + 2 = 5$ ，与已经找到的指派成本相同，故无需再枚举就能证明全局最优。这是线性规划对偶下界在一对一分配中的具体样子。

把每格的折减成本记为 $r_{i j} = c_{i j} - u_{i} - v_{j}$ ，由权重条件可知 $r_{i j} \geq 0$ 。本例三行依次变成 $(1, 0, 1)$ 、 $(0, 0, 4)$ 、 $(0, 1, 0)$ 。在这些零格里，A—乙、B—甲、C—丙刚好覆盖所有行列。选中格的折减成本之和为零，所以总费用恰等于行列权重的下界 5。这也说明匈牙利算法寻找零格匹配的思路：行列权重负责下界，零格中的完整匹配负责达到下界。并不是表里零格多就一定能完成匹配；它们还必须覆盖每一行、每一列且不冲突。

从三人扩展到大规模

一般设人员集 $I$ 、任务集 $J$ ，人数相同为 $n$ 。模型是 $min \sum_{i \in I, j \in J} c_{i j} x_{i j}, \sum_{j \in J} x_{i j} = 1, \sum_{i \in I} x_{i j} = 1, x_{i j} \in {0, 1} .$ 尽管写有二元条件，把它暂时放宽成 $x_{i j} \geq 0$ 也总存在整数最优解；这是指派约束的特殊结构，并不表示所有整数规划都能直接放宽。匈牙利算法利用行列权重与零成本边寻找最优匹配。若人员多于任务，或者允许某人空闲，需要用“至多一项”约束或加入虚拟任务；虚拟任务的成本必须代表真实空闲成本。若一个人能同时做多项任务、每项还要求不同技能组合，就已经不是这里的一对一模型。

若不是每个人都能做每项任务，可把不允许的格子直接排除，而不是随手填一个看似“足够大”的成本。还要检查是否存在完整匹配：例如 A、B 都只能做甲，C 可以做乙或丙，则每项任务看起来都至少有人能做，但 A、B 两人争同一个甲，最终一定有一人和一项任务无法配对。求最小费用之前，先确认可行性；只凭逐行逐列各有一个可用格子，并不能保证全局能分配。

参考资料

MIT 1.224J 第4讲，说明指派问题与运输问题的关系。
MIT 15.066J 网络模型讲义，讨论一对一指派模型。