問答題

【簡答題】 計算題:某車間產(chǎn)品裝配組有王成、趙云、江平、李某四位員工?,F(xiàn)有A、B、C、D四項任務,在現(xiàn)有生產(chǎn)技術組織條件下,每位員工完成每項工作所需要的工時如表2-2-2所示。
請運用匈牙利法求出員工與任務的配置情況,以保證完成任務的總時間最短,并求出完成任務的最短時間。(P96~98)(20分)

計算步驟如下:(8分)
1)建立矩陳

2)對以上矩陣進行約減,即每一行數(shù)據(jù)減去本*行的最小數(shù),得新矩陣為:

矩陣中第一列和第四列都不含“0”,因此轉入第三步,進行列約減。
3)對以上矩陣進行列約減,即第一列約減去本*行數(shù)據(jù)中的最小數(shù),得新矩陣為:

4)在上述矩陣中畫“蓋0”線。即畫最少的線將矩陣中的0全部覆蓋住。
“蓋0”線只有3條,小于矩陣的維數(shù)4,因此轉入第五步,進行數(shù)據(jù)轉換
5)數(shù)據(jù)轉換。上述矩陣中未被“蓋0”線覆蓋的最小數(shù)為1,將矩陣中未被“蓋0”線覆蓋的數(shù)減去1,“蓋0”給交叉點處的數(shù)加1,得新矩陣為:

6)在上述矩陣中畫“蓋0”線,“蓋0”線只有3條,小于矩陣的維數(shù)4,因此轉入第七步,進行數(shù)據(jù)轉換
7)數(shù)據(jù)轉換。上述矩陣中未被“蓋0”線覆蓋的最小數(shù)為3,將矩陣中未被“蓋0”線覆蓋的數(shù)減去3,“蓋0”給交叉點處的數(shù)加3,得新矩陣為:

1)在上述矩陣中畫“蓋0”線。“蓋0”線有4條,等于矩陣的維數(shù)4,因此轉入第九步,示得最化解。
2)求最優(yōu)解。
①最后一列只含有一個“0”,將該列中的“0”打“√”
②將第三行中另外一個“0”打“×”
③將第一列中另外一個“0”打“√”
④將第一行中另外一個“0”打“×”
⑤將第二列中另外一個“0”打“√”
⑥將第四行中另外一個“0”打“×”
⑦將第三列中另外一個“0”打“√”
最終結果見以下矩陣。

參照表2-2-2,最短時間為:(3+2+4+)4小時=3.25小時(12分)
表2-2-2每個員工完成四項工作任務的工時統(tǒng)計表(單位:工時)
工作任務王成趙云江平李某


 

答案: 計算步驟如下:(8分)
1)建立矩陳

2)對以上矩陣進行約減,即每一行數(shù)據(jù)減去本*行的最小數(shù),...
題目列表

你可能感興趣的試題

微信掃碼免費搜題