感受:
【例子】效率矩阵为
$$
\begin{bmatrix}
12 & 7 & 9 & 7 & 9 \\
8 & 9 & 6 & 6 & 6 \\
7 & 17 & 12 & 14 & 9 \\
15 & 14 & 6 & 6 & 10 \\
4 & 10 & 7 & 10 & 9
\end{bmatrix}
$$
\begin{bmatrix}
12 & 7 & 9 & 7 & 9 \\
8 & 9 & 6 & 6 & 6 \\
7 & 17 & 12 & 14 & 9 \\
15 & 14 & 6 & 6 & 10 \\
4 & 10 & 7 & 10 & 9
\end{bmatrix}
$$
试求效率最高的解。
(1)系数矩阵简化
对于每行,分别减去其行的最小值。之后对列同样操作。
$$
\begin{bmatrix}
\color{red}12 & \color{red}7 & \color{red}9 & \color{red}7 & \color{red}9 \\
8 & 9 & 6 & 6 & 6 \\
7 & 17 & 12 & 14 & 9 \\
15 & 14 & 6 & 6 & 10 \\
4 & 10 & 7 & 10 & 9
\end{bmatrix}
$$
\begin{bmatrix}
\color{red}12 & \color{red}7 & \color{red}9 & \color{red}7 & \color{red}9 \\
8 & 9 & 6 & 6 & 6 \\
7 & 17 & 12 & 14 & 9 \\
15 & 14 & 6 & 6 & 10 \\
4 & 10 & 7 & 10 & 9
\end{bmatrix}
$$
第一行最小值是 7,减去 7 得到:
$$
\begin{bmatrix}
\color{red}5 & \color{red}0 & \color{red}2 & \color{red}0 & \color{red}2 \\
8 & 9 & 6 & 6 & 6 \\
7 & 17 & 12 & 14 & 9 \\
15 & 14 & 6 & 6 & 10 \\
4 & 10 & 7 & 10 & 9
\end{bmatrix}
$$
\begin{bmatrix}
\color{red}5 & \color{red}0 & \color{red}2 & \color{red}0 & \color{red}2 \\
8 & 9 & 6 & 6 & 6 \\
7 & 17 & 12 & 14 & 9 \\
15 & 14 & 6 & 6 & 10 \\
4 & 10 & 7 & 10 & 9
\end{bmatrix}
$$
依次各行如此操作,得到:
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
0 & 10 & 5 & 7 & 2 \\
9 & 8 & 0 & 0 & 4 \\
0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
0 & 10 & 5 & 7 & 2 \\
9 & 8 & 0 & 0 & 4 \\
0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
依次各列如此操作(其实各列最小值都是 0,无需再减了),得到:
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
0 & 10 & 5 & 7 & 2 \\
9 & 8 & 0 & 0 & 4 \\
0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
0 & 10 & 5 & 7 & 2 \\
9 & 8 & 0 & 0 & 4 \\
0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
(2)零元素处理
S1: 寻找零数量最小(但至少一个)的行(该行不能被圈过),圈出其中任意一个 0,然后划掉同列的 0。
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
\color{blue}\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & 0 & 0 & 4 \\
\color{blue}\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
\color{blue}\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & 0 & 0 & 4 \\
\color{blue}\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
S2: 寻找零数量最小(但至少一个)的列(该列不能被圈过),圈出其中任意一个 0,然后划掉同行的 0。
$$
\begin{bmatrix}
5 & \color{blue}\enclose{circle}0 & 2 & \color{blue}\cancel0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & 0 & 0 & 4 \\
\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
\begin{bmatrix}
5 & \color{blue}\enclose{circle}0 & 2 & \color{blue}\cancel0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & 0 & 0 & 4 \\
\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
再次执行 S1:
$$
\begin{bmatrix}
5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
2 & 3 & \color{blue}\cancel0 & 0 & 0 \\
\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & \color{blue}\enclose{circle}0 & 0 & 4 \\
\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
\begin{bmatrix}
5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
2 & 3 & \color{blue}\cancel0 & 0 & 0 \\
\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & \color{blue}\enclose{circle}0 & 0 & 4 \\
\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
再次执行 S2:
$$
\begin{bmatrix}
5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
2 & 3 & \cancel0 & \color{blue}\enclose{circle}0 & \color{blue}\cancel0 \\
\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & \enclose{circle}0 & 0 & 4 \\
\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
\begin{bmatrix}
5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
2 & 3 & \cancel0 & \color{blue}\enclose{circle}0 & \color{blue}\cancel0 \\
\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & \enclose{circle}0 & 0 & 4 \\
\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
再次执行 S1,好吧,已经不剩了。把其余的零划掉。
$$
\begin{bmatrix}
5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & \enclose{circle}0 & \color{blue}\cancel0 & 4 \\
\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
\begin{bmatrix}
5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
9 & 8 & \enclose{circle}0 & \color{blue}\cancel0 & 4 \\
\cancel 0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
(3)以最少的直线覆盖所有 0
- 无 $\enclose{circle}{0}$ 行 打 √
- 对 √ 行含 $\cancel 0$ 列打 √
- 对 √ 列含 $\enclose{circle}0$ 行打 √
- 重复 2,3 直到不能打 √
- 划线于:无 √ 行 或者 有 √ 列
示范:
无 $\enclose{circle}{0}$ 行 打 √:
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&&&&&
\end{bmatrix}
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&&&&&
\end{bmatrix}
$$
对 √ 行含 $\cancel 0$ 列打 √:
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&\checkmark&&&&
\end{bmatrix}
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&\checkmark&&&&
\end{bmatrix}
$$
对 √ 列含 $\enclose{circle}0$ 行打 √:
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&\checkmark&&&&
\end{bmatrix}
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&\checkmark&&&&
\end{bmatrix}
$$
对 √ 行含 $\cancel 0$ 列打 √:
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&\checkmark&&&&
\end{bmatrix}
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&\checkmark&&&&
\end{bmatrix}
$$
无操作,循环终止。
划线:
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&\checkmark&&&&
\end{bmatrix}
$$
\begin{bmatrix}
&5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
&2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\
&9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\checkmark&\cancel 0 & 6 & 3 & 6 & 5\\
&\checkmark&&&&
\end{bmatrix}
$$
(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$:)
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
\color{red}-2 & \color{red}8 & \color{red}3 & \color{red}5 & \color{red}0 \\
9 & 8 & 0 & 0 & 4 \\
0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
\color{red}-2 & \color{red}8 & \color{red}3 & \color{red}5 & \color{red}0 \\
9 & 8 & 0 & 0 & 4 \\
0 & 6 & 3 & 6 & 5
\end{bmatrix}
$$
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
-2 & 8 & 3 & 5 & 0 \\
9 & 8 & 0 & 0 & 4 \\
\color{red}-2 & \color{red}4 & \color{red}1 & \color{red}4 & \color{red}3
\end{bmatrix}
$$
\begin{bmatrix}
5 & 0 & 2 & 0 & 2 \\
2 & 3 & 0 & 0 & 0 \\
-2 & 8 & 3 & 5 & 0 \\
9 & 8 & 0 & 0 & 4 \\
\color{red}-2 & \color{red}4 & \color{red}1 & \color{red}4 & \color{red}3
\end{bmatrix}
$$
(增加 $2$:)
$$
\begin{bmatrix}
\color{red}7 & 0 & 2 & 0 & 2 \\
\color{red}4 & 3 & 0 & 0 & 0 \\
\color{red}0 & 8 & 3 & 5 & 0 \\
\color{red}11 & 8 & 0 & 0 & 4 \\
\color{red}0 & 4 & 1 & 4 & 3
\end{bmatrix}
$$
\begin{bmatrix}
\color{red}7 & 0 & 2 & 0 & 2 \\
\color{red}4 & 3 & 0 & 0 & 0 \\
\color{red}0 & 8 & 3 & 5 & 0 \\
\color{red}11 & 8 & 0 & 0 & 4 \\
\color{red}0 & 4 & 1 & 4 & 3
\end{bmatrix}
$$
得到的矩阵:
$$
\begin{bmatrix}
7 & 0 & 2 & 0 & 2 \\
4 & 3 & 0 & 0 & 0 \\
0 & 8 & 3 & 5 & 0 \\
11 & 8 & 0 & 0 & 4 \\
0 & 4 & 1 & 4 & 3
\end{bmatrix}
$$
\begin{bmatrix}
7 & 0 & 2 & 0 & 2 \\
4 & 3 & 0 & 0 & 0 \\
0 & 8 & 3 & 5 & 0 \\
11 & 8 & 0 & 0 & 4 \\
0 & 4 & 1 & 4 & 3
\end{bmatrix}
$$
对其进行(2)中的零元素处理,得到:
$$
\begin{bmatrix}
7 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
4 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\cancel0 & 8 & 3 & 5 & \enclose{circle}0 \\
11 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\enclose{circle}0 & 4 & 1 & 4 & 3
\end{bmatrix}
$$
\begin{bmatrix}
7 & \enclose{circle}0 & 2 & \cancel0 & 2 \\
4 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\
\cancel0 & 8 & 3 & 5 & \enclose{circle}0 \\
11 & 8 & \enclose{circle}0 & \cancel0 & 4 \\
\enclose{circle}0 & 4 & 1 & 4 & 3
\end{bmatrix}
$$
可以发现各行各列都存在唯一的 $\enclose{circle} 0$。把这些位置的圈圈,对应圈到最初的效率矩阵:
$$
\begin{bmatrix}
12 & \enclose{circle}7 & 9 & 7 & 9 \\
8 & 9 & 6 & \enclose{circle}6 & 6 \\
7 & 17 & 12 & 14 & \enclose{circle}9 \\
15 & 14 & \enclose{circle}6 & 6 & 10 \\
\enclose{circle}4 & 10 & 7 & 10 & 9
\end{bmatrix}
$$
\begin{bmatrix}
12 & \enclose{circle}7 & 9 & 7 & 9 \\
8 & 9 & 6 & \enclose{circle}6 & 6 \\
7 & 17 & 12 & 14 & \enclose{circle}9 \\
15 & 14 & \enclose{circle}6 & 6 & 10 \\
\enclose{circle}4 & 10 & 7 & 10 & 9
\end{bmatrix}
$$
这就是最优解的指派。