|
|
赵 |
钱 |
孙 |
李 |
|
A |
10 |
5 |
9 |
18 |
|
B |
13 |
18 |
6 |
12 |
|
C |
3 |
2 |
4 |
4 |
|
D |
18 |
9 |
10 |
16 |
解：计算步骤如下：
（1）建立矩阵
10 5 9 18 (-5)
13 18 6 12 (-6)
3 2 4 4 (-2)
18 9 10 16 (-9)
（2）对以上矩阵进行行约减，即每一行数据减去本行数据中的最小数，得新矩阵如下：
5 0 4 13
7 12 0 6
1 0 2 2
9 0 1 7
(-1) (-2)
矩阵中第一列和第四列都不含“0”，因此转入第三步，进行列约减。
（3）对以上矩阵进行列约减，即每一行数据减去本行数据中的最小数，得新矩阵如下：
4 0 4 11
6 12 0 4
0 0 2 0
8 0 1 5
（4）在上述矩阵中画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住。
“盖0”线只有3条，小于矩阵的维数4, 因此转入第五步,进行数据转换。
（5）数据转换。上述矩阵中未被“盖0”线覆盖的最小数 为1,将矩阵中未被“盖0”线覆盖的数减去1, “盖0”线交叉点处的数加1, 得新矩阵如下：
3 0 3 10
6 13 0 4
0 1 2 0
7 0 0 4
（6）在上述矩阵中画“盖0”线。“盖0”线只有3条，小于矩阵的维数4, 因此转入第七步,进行数据转换。
（7）数据转换。上述矩阵中未被“盖0”线覆盖的最小数 为3,将矩阵中未被“盖0”线覆盖的数减去3, “盖0”线交叉点处的数加3, 得新矩阵如下：
0
0 3 7
3 13 0 1
0 4 5 0
4 0 0 1
(8) 在上述矩阵中画“盖0”线。“盖0”线有4条，等于矩阵的维数4，因此转入第九步，求最优解。
(9) 求最优解。
① 最后一列只含有一个“0”，将该列中的“0”打“√”。
② 将第三行中另外一个“0”打“ ”。
③ 将第一列中另外一个“0”打“√”。
④ 将第一行中另外一个“0”打“ ”。
⑤ 将第二列中另外一个“0”打“√”。
⑥ 将第四行中另外一个“0”打“ ”。
⑦ 将第三列中另外一个“0”打“√”。
最终结果见以下矩阵
0√ 0× 3 7
3 13 0√ 1
0× 4 5 0√
4 0√ 0× 1
得到最优解如下：赵——A；钱——D；孙——B；李——C。
对照工时消耗表，完成任务的总时间为10＋9＋6＋4＝29
相关推荐：
