信息系統(tǒng)項目管理師計算題考點：指派問題(匈牙利算法)

指派問題——所謂指派問題是指這樣一類問題：有n項任務，恰好有n個人可以分別去完成其中任何一項，由于任務的性質和每個人的技術專長各不相同，因此，各人去完成不同任務的效率也不一樣。于是提出如下問題：應當指派哪個人去完成哪項任務，才能使總的效率最高?類似的指派問題還有：n臺機床加工n項任務;n條航線安排n艘船或n架客機去航行等。

指派問題一般用匈牙利算法進行求解：

算法本質：變換系數(shù)矩陣，找到n個不同行不同列的0元素，以求解指派問題最有解

【例題詳解】

某項目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四項不同任務，恰有甲、乙、丙、丁四個人去完成各項不同的任務.由于任務性質及每人的技術水平不同，他們完成各項任務所需時間也不同，具體如下表所示

項目要求每個人只能完成一項任務，為了使項目花費的總時間最短，應該指派丁完成()任務。

A.Ⅰ

B.Ⅱ

C.Ⅲ

D.Ⅳ

【答案】C

步驟一：系數(shù)矩陣初等行列變換，使各行各列都出現(xiàn)0元素

1、每行減去該行最小元素，使得每行都出現(xiàn)0元素

2、每列減去該行最小元素，使得每列都出現(xiàn)0元素

注意：有0元素的就不需要減了

 注意：必須先變行 , 然后再變列 , 行列不能同時進行改變 ; 否則矩陣中會出現(xiàn)負數(shù) , 該矩陣中不能出現(xiàn)負數(shù) ;

步驟二：試指派，尋找最優(yōu)解

題目的約束條件為每個人只能完成一項任務，那么簡單來說就是每行每列只能有1個0元素。

1、找只有一個0元素的行，給這個0元素標記下，同時劃去該列其它0元素，這表示這列的任務已經(jīng)派完了

2、找只有一個0元素的列，給這個0元素標記下，同時劃去該行其它0元素。重復1、2兩步，直到所有0元素有標記或被劃去。最終我們可以得到下表，每行每列均標記了1個0元素。

3、上表中剛好每行每列都僅有1個0元素，符合題目要求，所以到此就指派完成了，也就是找到最優(yōu)解了：甲去完成任務IV；乙去完成任務Ⅱ；丙去完成任務I；丙去完成任務Ⅲ所以該題答案選擇C。

溫馨提示：上題中是比較理想的情況，有時候還會出現(xiàn)特殊情況（注：本文就不做詳細的圖文描述了，大家可以網(wǎng)上搜索相關信息看下，最好看看視頻講解）。

特殊情況：

1、出現(xiàn)零元素的閉合回路

在確定0元素時如仍然有沒有標記的零元素，且同行(列)的0元素至少有兩個(表示對這個可以從兩項任務中指派其一)。這時可用不同的方案去試探。從剩有零元素最少的行開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素標記（因為一列中零元素多，說明可派的人選擇較多，我們應派可選擇較少的任務)，然后去掉同行同列的其他0元素?？煞磸瓦M行，直到所有的0元素都已經(jīng)圈出和去掉為止。這種情況一般會出現(xiàn)多個解！

2、標記的0元素個數(shù)小于n

遇到這種情況我們可以進行“畫蓋0線”，即以最少的直線覆蓋所有0元素，確定當前系數(shù)矩陣中能找到的最多的0元素。按以下步驟進行:

步驟一：

(1）對沒有標記的行打√ ;

(2）對已經(jīng)打√行中所有含有劃掉0元素的列打上√ ;

(3）再對打有√的列中含有標記元素的行打√ ;

(4)重復第2,3步，直到無法繼續(xù)打√為止;

(5)對沒有打√的行劃線，對打√的列劃線。這就得到了覆蓋所有0元素的最少直線數(shù)。若直線數(shù)l<n，說明需增加0元素，轉下一步：

步驟二：增加0元素：

對第一步中沒有被直線覆蓋的部分中找出最小元素，然后在打√行各元素中都減去這個最小元素，打√列的各元素多加上這個最小元素，以保證原來的0元素不變。這樣得到的新矩陣（和原來同解)，若得到n個獨立的0元素，則已經(jīng)得到最優(yōu)解，否則需回到上—步重復進行。