二、計算題(18分)

某車間產(chǎn)品裝配組有 成成、灰太狼、毛毛、三位員工，現(xiàn)有A、B、C、D四項任務(wù)，在現(xiàn)有生成技術(shù)組織條件下，每位員工完成每項工作所需要的工時如表1所示。由于現(xiàn)在有四項任務(wù)，而只有三個員工，可讓一名效率較高的員工完成2項任務(wù)

請運用匈牙利法求出員工與任務(wù)的配置情況，以保證完成任務(wù)的總時間最短，并求出完成成任務(wù)的最短時間。

表1 每位員工完成四項工作任務(wù)的工時統(tǒng)計表 單位工時

解：

1)因為員工數(shù)小于任務(wù)數(shù)(四項任務(wù)，而只有三個員工)，必有一名員工需要完成2項任務(wù)，故此將每個員工虛設(shè)為2人，即使虛擬的成成′,灰太狼′,毛毛′

2)現(xiàn)在為6名員工,4項任務(wù),任務(wù)數(shù)小于員工數(shù),故此需虛擬2項E和F任務(wù)，完成這兩項任務(wù)的時間為0

3)現(xiàn)在為6名員工6個任務(wù)，可以使用匈牙利法求解，故此構(gòu)成以下表格：

使用匈牙利法解：

1、構(gòu)成矩陣

2、使每行每列至少包含一個零

用每行或每列的數(shù)分別減該行或該列的最小數(shù)即可，得以下矩陣

3、畫蓋零的直線數(shù)等于維數(shù)

a首先從零最多的行或列畫蓋零的直線

b直線數(shù)<維數(shù)，將進行數(shù)據(jù)轉(zhuǎn)換

(找未被直線蓋的最小數(shù)1;所有未被直線蓋的數(shù)-1：兩直線相交點+1)構(gòu)成以下矩陣

4求最優(yōu)解

a找只有一個零的行或列(因為有3名員工虛擬的，故與員工本人數(shù)相同，即同一人的兩個零可看成一個零)，將其打√

b將其對應(yīng)的行或列的其它零打×

c將最后打√的零對應(yīng)的敷(表格中)相加，即為最少工作時間

通過與表格數(shù)據(jù)對照，工作分配如下：

新航道負責c任務(wù)(5小時)，灰太狼負責A任務(wù)(8小時)，毛毛負責B任務(wù)(9小時)與D任務(wù)(13小時)，共完成所有任務(wù)最小時間為5+8+9+13=35小時

（責任編輯：）

共5頁,當前第2頁  第一頁  前一頁  下一頁