二、計算題(18分)

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

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

表1 每位員工完成四項工作任務的工時統計表 單位工時

解：

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

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

3)現在為6名員工6個任務，可以使用匈牙利法求解，故此構成以下表格：

使用匈牙利法解：

1、構成矩陣

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

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

3、畫蓋零的直線數等于維數

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

b直線數<維數，將進行數據轉換

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

4求最優解

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

b將其對應的行或列的其它零打×

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

通過與表格數據對照，工作分配如下：

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

（責任編輯：）

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