2．假定某企業(yè)有趙、錢、孫、李四位員工，需要在一定的生產(chǎn)技術(shù)組織條件下完成A、B、C、D四項任務(wù)，每位員工完成每項工作所耗費(fèi)的時間是不同的，如下表所示：計算：根據(jù)匈牙利法，四位員工與任務(wù)之間應(yīng)該如何配置才能保證完成任務(wù)的時間最短。不同員工從事不同工作的耗時
解：計算步驟如下：
（1）建立矩陣
105918(-5)
1318612(-6)
3244(-2)
1891016(-9)
（2）對以上矩陣進(jìn)行行約減，即每一行數(shù)據(jù)減去本行數(shù)據(jù)中的最小數(shù)，得新矩陣如下：
50413
71206
1022
9017
(-1)(-2)
矩陣中第一列和第四列都不含“0”，因此轉(zhuǎn)入第三步，進(jìn)行列約減。
（3）對以上矩陣進(jìn)行列約減，即每一行數(shù)據(jù)減去本行數(shù)據(jù)中的最小數(shù)，得新矩陣如下：
40411
61204
0020
8015
（4）在上述矩陣中畫“蓋0”線。即畫最少的線將矩陣三中的0全部覆蓋住。
“蓋0”線只有3條，小于矩陣的維數(shù)4, 因此轉(zhuǎn)入第五步,進(jìn)行數(shù)據(jù)轉(zhuǎn)換。
（5）數(shù)據(jù)轉(zhuǎn)換。上述矩陣中未被“蓋0”線覆蓋的最小數(shù) 為1,將矩陣中未被“蓋0”線覆蓋的數(shù)減去1, “蓋0”線交叉點(diǎn)處的數(shù)加1, 得新矩陣如下：
30310
61304
0120
7004
（6）在上述矩陣中畫“蓋0”線。“蓋0”線只有3條，小于矩陣的維數(shù)4, 因此轉(zhuǎn)入第七步,進(jìn)行數(shù)據(jù)轉(zhuǎn)換。
（7）數(shù)據(jù)轉(zhuǎn)換。上述矩陣中未被“蓋0”線覆蓋的最小數(shù) 為3,將矩陣中未被“蓋0”線覆蓋的數(shù)減去3, “蓋0”線交叉點(diǎn)處的數(shù)加3, 得新矩陣如下：
0
037
31301
0450
4001
(8) 在上述矩陣中畫“蓋0”線。“蓋0”線有4條，等于矩陣的維數(shù)4，因此轉(zhuǎn)入第九步，求解。
(9) 求解。
① 最后一列只含有一個“0”，將該列中的“0”打“√”。
② 將第三行中另外一個“0”打“ ”。
③ 將第一列中另外一個“0”打“√”。
④ 將第一行中另外一個“0”打“ ”。
⑤ 將第二列中另外一個“0”打“√”。
⑥ 將第四行中另外一個“0”打“ ”。
⑦ 將第三列中另外一個“0”打“√”。
最終結(jié)果見以下矩陣
0√0×37
3130√1
0×450√
40√0×1
得到解如下：趙——A；錢——D；孫——B；李——C。
對照工時消耗表，完成任務(wù)的總時間為10＋9＋6＋4＝29
趙 |
錢 |
孫 |
李 | |
A |
10 |
5 |
9 |
18 |
B |
13 |
18 |
6 |
12 |
C |
3 |
2 |
4 |
4 |
D |
18 |
9 |
10 |
16 |
解：計算步驟如下：
（1）建立矩陣
105918(-5)
1318612(-6)
3244(-2)
1891016(-9)
（2）對以上矩陣進(jìn)行行約減，即每一行數(shù)據(jù)減去本行數(shù)據(jù)中的最小數(shù)，得新矩陣如下：
50413
71206
1022
9017
(-1)(-2)
矩陣中第一列和第四列都不含“0”，因此轉(zhuǎn)入第三步，進(jìn)行列約減。
（3）對以上矩陣進(jìn)行列約減，即每一行數(shù)據(jù)減去本行數(shù)據(jù)中的最小數(shù)，得新矩陣如下：
40411
61204
0020
8015
（4）在上述矩陣中畫“蓋0”線。即畫最少的線將矩陣三中的0全部覆蓋住。
“蓋0”線只有3條，小于矩陣的維數(shù)4, 因此轉(zhuǎn)入第五步,進(jìn)行數(shù)據(jù)轉(zhuǎn)換。
（5）數(shù)據(jù)轉(zhuǎn)換。上述矩陣中未被“蓋0”線覆蓋的最小數(shù) 為1,將矩陣中未被“蓋0”線覆蓋的數(shù)減去1, “蓋0”線交叉點(diǎn)處的數(shù)加1, 得新矩陣如下：
30310
61304
0120
7004
（6）在上述矩陣中畫“蓋0”線。“蓋0”線只有3條，小于矩陣的維數(shù)4, 因此轉(zhuǎn)入第七步,進(jìn)行數(shù)據(jù)轉(zhuǎn)換。
（7）數(shù)據(jù)轉(zhuǎn)換。上述矩陣中未被“蓋0”線覆蓋的最小數(shù) 為3,將矩陣中未被“蓋0”線覆蓋的數(shù)減去3, “蓋0”線交叉點(diǎn)處的數(shù)加3, 得新矩陣如下：
0
037
31301
0450
4001
(8) 在上述矩陣中畫“蓋0”線。“蓋0”線有4條，等于矩陣的維數(shù)4，因此轉(zhuǎn)入第九步，求解。
(9) 求解。
① 最后一列只含有一個“0”，將該列中的“0”打“√”。
② 將第三行中另外一個“0”打“ ”。
③ 將第一列中另外一個“0”打“√”。
④ 將第一行中另外一個“0”打“ ”。
⑤ 將第二列中另外一個“0”打“√”。
⑥ 將第四行中另外一個“0”打“ ”。
⑦ 將第三列中另外一個“0”打“√”。
最終結(jié)果見以下矩陣
0√0×37
3130√1
0×450√
40√0×1
得到解如下：趙——A；錢——D；孫——B；李——C。
對照工時消耗表，完成任務(wù)的總時間為10＋9＋6＋4＝29