Site Overlay

运筹学:匈牙利法(求解指派问题)详解

感受:

typora\20201225233212_b9d0008e0e004ab5fbb5ab7e666ade75.png

【例子】效率矩阵为

$$
\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}
$$

第一行最小值是 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}
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}
$$

(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}
$$

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}
$$

再次执行 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}
$$

再次执行 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}
$$

再次执行 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}
$$

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

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

示范:

$\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}
$$

对 √ 行含 $\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}
$$

对 √ 列含 $\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}
$$

对 √ 行含 $\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}
$$

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

$$
\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}
$$

(增加 $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}
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}
$$

可以发现各行各列都存在唯一的 $\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}
$$

这就是最优解的指派。

发表评论

电子邮件地址不会被公开。 必填项已用*标注