指派問題的改進算法

宋雨晴

（浙江海洋學院數(shù)理與信息學院 浙江 舟山 316000）

在生活中，我們經(jīng)常遇到這樣的問題，某單位需要完成n項任務，恰好有n個人可承擔這些任務。又由于每個人的專長不同，各人完成任務所費的時間效率不盡相同。于是產生應指派哪個人去完成哪項任務，使完成n項任務的總效率最高，即所需的時間或所消耗的資金等最小。這類問題稱為指派問題或分派問題（assignment problem）。

1 指派問題的標準形式和數(shù)學模型

例1、有一份說明書，需譯成英、日、德、俄四種文字?，F(xiàn)有甲、乙、丙、丁四個人，他們將說明書譯成不同文字所需的時間如下表所示。問應指派哪個人完成哪項工作，使所需的總時間最少?

表1

有n項任務，n個完成人，第i人完成第j項任務的代價為 cij（i，j＝1，2，…，n）。 為了求得總代價最小的指派方案，引入0-1 型變量 xij，并令

可見指派問題是0-1型整數(shù)規(guī)劃的特例。不難發(fā)現(xiàn)，指派問題也是運輸問題的特例，其產地和銷地數(shù)都為n，各產地的產量和各銷地的銷量都為1。

2 指派問題的求解方法——匈牙利算法

2.1 匈牙利算法

匈牙利算法是基于Hall定理中充分性證明的思想，它是部圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法。其基本思想是修改矩陣的行或列，使得每一行或每一列中至少有一個為零的元素，經(jīng)過修正后，直至在不同行 不同列中至少有一個零元素，從而得到與這些零元素相對應的一個完全分配方案。當它用于效益矩陣時，這個完全分配方案就是一個最優(yōu)分配，它使總的效益為最小。這種方法總是在有限步內收斂于一個最優(yōu)解。該方法的理論基礎是：在效益矩陣的任何行或列中，加上或減去一個常數(shù)后不會改變最有分配。其求解步驟如下：

第一步，使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列都出現(xiàn)0元素。（1）從系數(shù)矩陣的每行元素減去該行的最小元素；（2）再從所得系數(shù)矩陣的每列元素中減去該列的最小元素（若某行或某列中已有0元素，那就不必再減了）。

第二步，進行時指派，以尋求最優(yōu)解。（1）從只有一個0元素的行（列）開始，給這個0元素加圈，記作◎。這表示對這行所代表的人，只有一種任務可指派。然后劃去◎所在列（行）的其他0元素，記作φ。這表示這列所代表的任務已指派完，不必再考慮別人了。（2）給只有一個0元素列（行）的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作φ。（3）反復進行（1），（2）兩步，直到所有0元素都被圈出或劃掉為止。（4）若仍有沒有畫圈的0元素，且同行（列）的0元素至少有兩個（表示對這個可以從兩項任務中指派其一），這可用不同的方案去試探。從剩有0元素最少的行（列）開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈（表示選擇性多的要“禮讓“選擇性少的）。然后劃掉同行同列的其他0元素?？煞磸瓦M行，直到所有0元素都已圈出和劃掉為止。（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m

例2、用匈牙利算法確定例1的最優(yōu)分配方案。

解：這是一個人數(shù)等于任務數(shù)的情況，用匈牙利算法求解過程如圖1。

圖1

此時，◎元素的數(shù)目等于矩陣的階數(shù)，那么這指派問題的最優(yōu)解已經(jīng)得到。

從而得到最優(yōu)指派：

甲→俄

乙→日

丙→英

丁→德

2.2 匈牙利算法改進

在第二步即是指一個完全分配方案中，常規(guī)情況下得到的縮減矩陣是一個n階方陣。但對于人數(shù)和任務數(shù)不相等時，所得到的的縮減矩陣是一個m×n階矩陣（m，n不相等，不妨設m×n），則這個時候所分布在不同行不同列的0元素只要達到m個即可，若不夠則轉下一步。是的覆蓋所有0元素的最少直線數(shù)達到m條即可。這既減少了計算步驟，也簡化了算法。

2.2.1 人數(shù)等于或多于任務數(shù)的情況

人數(shù)等于或多于任務數(shù)時，要求每一項任務只能由一個人去完成。這是只要按照改進匈牙利算法即可找到m條直線。 如例1、例2。

2.2.2 任務數(shù)多于人數(shù)的情況

任務數(shù)多于人數(shù)時，一般要求每一項任務只能有一個人完成，但一個人可以完成多項任務。這是先按照改進匈牙利算法找到m條直線，如果最后一個效益矩陣中未被分配的任務所在列（行）不含有零元素或者未被分配的任務數(shù)多余1個，則返回到第一步，直到所有的任務都被分配為止;如果最后一個效益矩陣中未被分配的任務所在列（行）只剩下1列（行），且含有0元素，則根據(jù)未被分配的任務所在列（行）中的0元素與原效益矩陣結合，找出完成該項任務的最優(yōu)解。

例3、某班級準備從5名游泳隊員中選擇4人組成接力隊，參加學校的4×50m混合泳接力比賽。5名隊員4種姿勢的50m平均成績如表2所示。問應如何從中選拔一個4×50m混合泳的接力隊，使預期的比賽成績?yōu)樽詈茫▓D表 2）。

表2 5名隊員4種泳姿的50m平均成績

解法1（匈牙利算法）如圖2

圖2

經(jīng)過以上5步得到了最優(yōu)方案：趙——自由泳，錢——蝶泳，王——蛙泳，周——仰泳。這時的最好成績?yōu)椋?9.2＋28.5＋34.7＋35.4＝127.8（s）。

解法2（改進后的匈牙利算法）如圖3

而改進后的匈牙利算法只需2步就得到了我們想要的最優(yōu)方案：趙——自由泳，錢——蝶泳，王——蛙泳，周——仰泳。 這時的最好成績?yōu)椋?9.2＋28.5＋34.7＋35.4＝127.8（s）。

圖3

3 削高排除法

對于最初給定的指派問題矩陣A，可將其理解為圈圓個數(shù)為0的帶圈指派長陣A0。此時自然有minA0＝minA。對于這個A0：

第一步，首先，盡可能多的找出一組屬于不同行不同列的k個行最小元素。將這些行最小元素分別用“ ”圈出來。

第二步，對A0盡可能多的連續(xù)實現(xiàn)ψ變換。ψ變換的實施，不僅有利于找到一組更多的屬于不同行不同列的行最小元素，而且能使許多隱含的非指派元顯露出來。

第三步，對連續(xù)實現(xiàn)ψ變換后的所成矩陣，運用削高排除輔助定理，判定出一組盡可能多的屬于不同行不同列的行最小元素所在裂地集合D。

第四步，在這個連續(xù)實現(xiàn)ψ變換后的所成矩陣上，對其列坐標屬于列坐標集D的格列所在元實施削高排除輔助定理，得一與A0同階的帶圈指派矩陣B0。由于這個B0滿足minB0＝minB，可對這個B0按上述4個步驟繼續(xù)求解，直到最后求出整個問題的解為止。這就是削高消除法的一般求解過程。

例4、求解指派矩陣A所決定的指派問題，這里

解：在A中可以標出4個屬于不同行不同列的行最小元素，這種標定有很多種組合，先去下面的標定：

觀察指派矩陣的行嚴格最小元（小于它所在行中其他各元的元），可確立簡便的同解的矩陣。在這里，我們規(guī)定，用在aij頂上標出常數(shù)c的方法表示在A的第j列各元上同時加上常數(shù) c 的所成矩陣 B。 與 A 同解的指派矩陣 B=ψ1（5，5）ψ5（3，1）（A）（取此標定，不是唯一）

此時，B中存在屬于不同行不同列的5個行最小元。對B進行削高排除法，得一與B同解的帶圈指派矩陣D0。

將矩陣中所在行或所在列中其他非圈元為圈元，最后得到E0與D0同解，

［1］李維錚.運籌學[M].3 版.清華大學出版社，2005，6.

［2］張新輝.任務數(shù)多于人數(shù)的指派問題[J].1997.

［3］張伯生，范君暉，田叔閣.運籌學[M].科學出版社，2008，1.

［4］廖敏.運籌學基礎與應用[M].南京大學出版社，2009，6.

［5］孫麟平.運籌學[M].科學出版社，2005，7.