运筹学：匈牙利法（求解指派问题）详解

感受：

【例子】效率矩阵为

试求效率最高的解。

（1）系数矩阵简化

对于每行，分别减去其行的最小值。之后对列同样操作。

第一行最小值是 7，减去 7 得到：

依次各行如此操作，得到：

依次各列如此操作（其实各列最小值都是 0，无需再减了），得到：

（2）零元素处理

S1: 寻找零数量最小（但至少一个）的行（该行不能被圈过），圈出其中任意一个 0，然后划掉同列的 0。

S2: 寻找零数量最小（但至少一个）的列（该列不能被圈过），圈出其中任意一个 0，然后划掉同行的 0。

再次执行 S1：

再次执行 S2：

再次执行 S1，好吧，已经不剩了。把其余的零划掉。

（3）以最少的直线覆盖所有 0

1. 无 $\enclose {circle}{0}$ 行 打 √
2. 对 √ 行含 $\cancel 0$ 列打 √
3. 对 √ 列含 $\enclose {circle} 0$ 行打 √
4. 重复 2，3 直到不能打 √
5. 划线于：无 √ 行 或者 有 √ 列

示范：

无 $\enclose {circle}{0}$ 行 打 √：

对 √ 行含 $\cancel 0$ 列打 √：

对 √ 列含 $\enclose {circle} 0$ 行打 √：

对 √ 行含 $\cancel 0$ 列打 √：

无操作，循环终止。

划线：

（2）找剩余部分最小元素，进行变换

剩下 $A = [10, 5, 7, 2]$ 和 $B = [6,3,6,5]$，$\min A = 2, \min B = 3$，$\min (A,B) = \min (2,3) = 2$。

在矩阵中，给 $A,B$ 行所有元素减去 $2$，并在划掉的列增加 $2$

（减去 $2$：）

（增加 $2$：）

得到的矩阵：

对其进行（2）中的零元素处理，得到：

可以发现各行各列都存在唯一的 $\enclose {circle} 0$。把这些位置的圈圈，对应圈到最初的效率矩阵：

这就是最优解的指派。