感受:

typora\20201225233212_b9d0008e0e004ab5fbb5ab7e666ade75.png

【例子】效率矩阵为

$$ <br /> \begin{bmatrix}<br /> 12 & 7 & 9 & 7 & 9 \\<br /> 8 & 9 & 6 & 6 & 6 \\<br /> 7 & 17 & 12 & 14 & 9 \\<br /> 15 & 14 & 6 & 6 & 10 \\<br /> 4 & 10 & 7 & 10 & 9<br /> \end{bmatrix}<br /> $$

试求效率最高的解。

(1)系数矩阵简化

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

$$ <br /> \begin{bmatrix}<br /> \color{red}12 & \color{red}7 & \color{red}9 & \color{red}7 & \color{red}9 \\<br /> 8 & 9 & 6 & 6 & 6 \\<br /> 7 & 17 & 12 & 14 & 9 \\<br /> 15 & 14 & 6 & 6 & 10 \\<br /> 4 & 10 & 7 & 10 & 9<br /> \end{bmatrix}<br /> $$

第一行最小值是 7,减去 7 得到:

$$ <br /> \begin{bmatrix}<br /> \color{red}5 & \color{red}0 & \color{red}2 & \color{red}0 & \color{red}2 \\<br /> 8 & 9 & 6 & 6 & 6 \\<br /> 7 & 17 & 12 & 14 & 9 \\<br /> 15 & 14 & 6 & 6 & 10 \\<br /> 4 & 10 & 7 & 10 & 9<br /> \end{bmatrix}<br /> $$

依次各行如此操作,得到:

$$ <br /> \begin{bmatrix}<br /> 5 & 0 & 2 & 0 & 2 \\<br /> 2 & 3 & 0 & 0 & 0 \\<br /> 0 & 10 & 5 & 7 & 2 \\<br /> 9 & 8 & 0 & 0 & 4 \\<br /> 0 & 6 & 3 & 6 & 5<br /> \end{bmatrix}<br /> $$

依次各列如此操作(其实各列最小值都是 0,无需再减了),得到:

$$ <br /> \begin{bmatrix}<br /> 5 & 0 & 2 & 0 & 2 \\<br /> 2 & 3 & 0 & 0 & 0 \\<br /> 0 & 10 & 5 & 7 & 2 \\<br /> 9 & 8 & 0 & 0 & 4 \\<br /> 0 & 6 & 3 & 6 & 5<br /> \end{bmatrix}<br /> $$

(2)零元素处理

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

$$ <br /> \begin{bmatrix}<br /> 5 & 0 & 2 & 0 & 2 \\<br /> 2 & 3 & 0 & 0 & 0 \\<br /> \color{blue}\enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> 9 & 8 & 0 & 0 & 4 \\<br /> \color{blue}\cancel 0 & 6 & 3 & 6 & 5<br /> \end{bmatrix}<br /> $$

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

$$ <br /> \begin{bmatrix}<br /> 5 & \color{blue}\enclose{circle}0 & 2 & \color{blue}\cancel0 & 2 \\<br /> 2 & 3 & 0 & 0 & 0 \\<br /> \enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> 9 & 8 & 0 & 0 & 4 \\<br /> \cancel 0 & 6 & 3 & 6 & 5<br /> \end{bmatrix}<br /> $$

再次执行 S1:

$$ <br /> \begin{bmatrix}<br /> 5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> 2 & 3 & \color{blue}\cancel0 & 0 & 0 \\<br /> \enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> 9 & 8 & \color{blue}\enclose{circle}0 & 0 & 4 \\<br /> \cancel 0 & 6 & 3 & 6 & 5<br /> \end{bmatrix}<br /> $$

再次执行 S2:

$$ <br /> \begin{bmatrix}<br /> 5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> 2 & 3 & \cancel0 & \color{blue}\enclose{circle}0 & \color{blue}\cancel0 \\<br /> \enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> 9 & 8 & \enclose{circle}0 & 0 & 4 \\<br /> \cancel 0 & 6 & 3 & 6 & 5<br /> \end{bmatrix}<br /> $$

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

$$ <br /> \begin{bmatrix}<br /> 5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> 2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\<br /> \enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> 9 & 8 & \enclose{circle}0 & \color{blue}\cancel0 & 4 \\<br /> \cancel 0 & 6 & 3 & 6 & 5<br /> \end{bmatrix}<br /> $$

(3)以最少的直线覆盖所有 0

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

示范:

$\enclose {circle}{0}$ 行 打 √:

$$ <br /> \begin{bmatrix}<br /> &5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> &2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\<br /> &\enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> &9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\<br /> \checkmark&\cancel 0 & 6 & 3 & 6 & 5\\<br /> &&&&&<br /> \end{bmatrix}<br /> $$

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

$$ <br /> \begin{bmatrix}<br /> &5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> &2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\<br /> &\enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> &9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\<br /> \checkmark&\cancel 0 & 6 & 3 & 6 & 5\\<br /> &\checkmark&&&&<br /> \end{bmatrix}<br /> $$

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

$$ <br /> \begin{bmatrix}<br /> &5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> &2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\<br /> \checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> &9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\<br /> \checkmark&\cancel 0 & 6 & 3 & 6 & 5\\<br /> &\checkmark&&&&<br /> \end{bmatrix}<br /> $$

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

$$ <br /> \begin{bmatrix}<br /> &5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> &2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\<br /> \checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> &9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\<br /> \checkmark&\cancel 0 & 6 & 3 & 6 & 5\\<br /> &\checkmark&&&&<br /> \end{bmatrix}<br /> $$

无操作,循环终止。

划线:

$$ <br /> \begin{bmatrix}<br /> &5 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> &2 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\<br /> \checkmark&\enclose{circle} {0} & 10 & 5 & 7 & 2 \\<br /> &9 & 8 & \enclose{circle}0 & \cancel0 & 4 \\<br /> \checkmark&\cancel 0 & 6 & 3 & 6 & 5\\<br /> &\checkmark&&&&<br /> \end{bmatrix}<br /> $$

typora\20201225233309_d347830b17911930541baf64f400608a.png

(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$:)

$$ <br /> \begin{bmatrix}<br /> 5 & 0 & 2 & 0 & 2 \\<br /> 2 & 3 & 0 & 0 & 0 \\<br /> \color{red}-2 & \color{red}8 & \color{red}3 & \color{red}5 & \color{red}0 \\<br /> 9 & 8 & 0 & 0 & 4 \\<br /> 0 & 6 & 3 & 6 & 5<br /> \end{bmatrix}<br /> $$
$$ <br /> \begin{bmatrix}<br /> 5 & 0 & 2 & 0 & 2 \\<br /> 2 & 3 & 0 & 0 & 0 \\<br /> -2 & 8 & 3 & 5 & 0 \\<br /> 9 & 8 & 0 & 0 & 4 \\<br /> \color{red}-2 & \color{red}4 & \color{red}1 & \color{red}4 & \color{red}3<br /> \end{bmatrix}<br /> $$

(增加 $2$:)

$$ <br /> \begin{bmatrix}<br /> \color{red}7 & 0 & 2 & 0 & 2 \\<br /> \color{red}4 & 3 & 0 & 0 & 0 \\<br /> \color{red}0 & 8 & 3 & 5 & 0 \\<br /> \color{red}11 & 8 & 0 & 0 & 4 \\<br /> \color{red}0 & 4 & 1 & 4 & 3<br /> \end{bmatrix}<br /> $$

得到的矩阵:

$$ <br /> \begin{bmatrix}<br /> 7 & 0 & 2 & 0 & 2 \\<br /> 4 & 3 & 0 & 0 & 0 \\<br /> 0 & 8 & 3 & 5 & 0 \\<br /> 11 & 8 & 0 & 0 & 4 \\<br /> 0 & 4 & 1 & 4 & 3<br /> \end{bmatrix}<br /> $$

对其进行(2)中的零元素处理,得到:

$$ <br /> \begin{bmatrix}<br /> 7 & \enclose{circle}0 & 2 & \cancel0 & 2 \\<br /> 4 & 3 & \cancel0 & \enclose{circle}0 & \cancel0 \\<br /> \cancel0 & 8 & 3 & 5 & \enclose{circle}0 \\<br /> 11 & 8 & \enclose{circle}0 & \cancel0 & 4 \\<br /> \enclose{circle}0 & 4 & 1 & 4 & 3<br /> \end{bmatrix}<br /> $$

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

$$ <br /> \begin{bmatrix}<br /> 12 & \enclose{circle}7 & 9 & 7 & 9 \\<br /> 8 & 9 & 6 & \enclose{circle}6 & 6 \\<br /> 7 & 17 & 12 & 14 & \enclose{circle}9 \\<br /> 15 & 14 & \enclose{circle}6 & 6 & 10 \\<br /> \enclose{circle}4 & 10 & 7 & 10 & 9<br /> \end{bmatrix}<br /> $$

这就是最优解的指派。