宋雨晴

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

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

1 指派問題的標(biāo)準(zhǔn)形式和數(shù)學(xué)模型

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

表1

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

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

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

2.1 匈牙利算法

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

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

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

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

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

圖1

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

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

甲→俄

乙→日

丙→英

丁→德

2.2 匈牙利算法改進

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

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

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

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

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

例3、某班級準(zhǔn)備從5名游泳隊員中選擇4人組成接力隊，參加學(xué)校的4×50m混合泳接力比賽。5名隊員4種姿勢的50m平均成績?nèi)绫?所示。問應(yīng)如何從中選拔一個4×50m混合泳的接力隊，使預(yù)期的比賽成績?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)ψ變換后的所成矩陣上，對其列坐標(biāo)屬于列坐標(biāo)集D的格列所在元實施削高排除輔助定理，得一與A0同階的帶圈指派矩陣B0。由于這個B0滿足minB0＝minB，可對這個B0按上述4個步驟繼續(xù)求解，直到最后求出整個問題的解為止。這就是削高消除法的一般求解過程。

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

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

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

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

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

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

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

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

［4］廖敏.運籌學(xué)基礎(chǔ)與應(yīng)用[M].南京大學(xué)出版社，2009，6.

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