信息系統(tǒng)項(xiàng)目管理師計(jì)算題考點(diǎn)：指派問題(匈牙利算法)

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

指派問題一般用匈牙利算法進(jìn)行求解：

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

【例題詳解】

某項(xiàng)目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四項(xiàng)不同任務(wù)，恰有甲、乙、丙、丁四個(gè)人去完成各項(xiàng)不同的任務(wù).由于任務(wù)性質(zhì)及每人的技術(shù)水平不同，他們完成各項(xiàng)任務(wù)所需時(shí)間也不同，具體如下表所示

項(xiàng)目要求每個(gè)人只能完成一項(xiàng)任務(wù)，為了使項(xiàng)目花費(fèi)的總時(shí)間最短，應(yīng)該指派丁完成()任務(wù)。

A.Ⅰ

B.Ⅱ

C.Ⅲ

D.Ⅳ

【答案】C

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

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

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

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

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

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

題目的約束條件為每個(gè)人只能完成一項(xiàng)任務(wù)，那么簡(jiǎn)單來說就是每行每列只能有1個(gè)0元素。

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

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

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

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

特殊情況：

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

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

2、標(biāo)記的0元素個(gè)數(shù)小于n

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

步驟一：

(1）對(duì)沒有標(biāo)記的行打√ ;

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

(3）再對(duì)打有√的列中含有標(biāo)記元素的行打√ ;

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

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

步驟二：增加0元素：

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