“人少任務多”型指派問題的一種新算法*

馬 曉 娜

(宿州學院 數(shù)學與統(tǒng)計學院，安徽 宿州 234000)

1 預備知識

1.1 標準指派問題[3]

標準指派問題是經(jīng)濟計劃工作中經(jīng)常遇到的一個問題。當指派個人去完成項任務時，要求滿足以下3個前提假設(shè)：人數(shù)等于任務數(shù)；每個人必須且只需完成一項任務；每項任務必須且只需一人去完成。價值系數(shù)Cij為第i個人完成第j項任務所消耗的資源(目標函數(shù)求極小)或所得到的利益(目標函數(shù)求極大)則其數(shù)學模型如下:

對于上述最佳指派問題的線性規(guī)劃問題，可用單純形法求解。然而，由于指派問題的特殊性，用這種方法求解要比匈牙利法復雜得多。匈牙利法是目前求解標準指派問題行之有效且比較簡單的解法。

1.2 標準指派問題的匈牙利算法[4]

標準指派問題的匈牙利算法大致為4步驟：變換價值系數(shù)矩陣，使各行各列都出現(xiàn)0元素；進行試指派，以尋求最優(yōu)解；做最少的直線覆蓋當前所有0元素；對上述所得矩陣進行變換，以增加其0元素。

1.3 非標準型指派問題

對于前述標準指派問題要求滿足3個前提假設(shè)，但在實際應用中，大多的指派問題并不具備第一個假設(shè)，而第二個假設(shè)又顯然不符合當今引進競爭機制后的企業(yè)、部門及社會要求，在生活實際和生產(chǎn)安排中，經(jīng)常會遇到非標準指派問題。常見的有3種類型：系數(shù)矩陣中有空位置；“人少任務多”型；“人多任務少”型。

在解決非標準指派問題時，常采用的方法是將其先轉(zhuǎn)化為標準指派問題，然后再采用匈牙利算法求解，文獻[5-7]對于非標準指派問題均提出了轉(zhuǎn)換方法，但是這種算法比較麻煩，而且不好理解，人們只能機械的按照給出的算法步驟進行求解，并不能完全理解。因此嘗試就第二種情形進一步分析討論，提出了一種新的算法，即差額法。方法簡潔，易懂。對于另外兩種情形也有新的算法，在此不作討論。

2 主要結(jié)論

2.1 差額法的算法

第1步：列出價值系數(shù)矩陣，求出系數(shù)矩陣中任意兩行對應元素之差，將其差額以矩陣的形式列于系數(shù)矩陣右側(cè)。

第2步：在差額矩陣中尋找最大元素，用符號標記出來，同時劃去該元所在列的其他元素。

注意：若有幾個元素同為最大，則需在原系數(shù)矩陣中查到產(chǎn)生這些最大差額的對應元素，選擇最小元素對應的那個最大差額。

第3步：在原系數(shù)矩陣中找出產(chǎn)生此最大差額的兩個對應元素，在兩者中選出較小者，用符號標出，同時劃去該元所在列的其他元素(目的是保證每項任務只能由一個人完成)。

注意：當系數(shù)矩陣中某行有兩個或兩個以上的元素被標出后，將該行在系數(shù)矩陣中劃掉，同時將差額矩陣中與該行元素有關(guān)的行也劃掉(目的是保證此人已完成任務，不再分配任務給他)。

第4步：再在差額矩陣余下的行列中尋找最大元素，其余操作同上，以尋求最優(yōu)解。

2.2 實例分析

下面將結(jié)合實際問題說明一下“人少任務多”型指派問題的新算法的算法實現(xiàn)步驟。

例1 分配甲、乙、丙3人去完成4項任務，每人完成各項任務時間如下所示，由于任務數(shù)多于人數(shù)，故規(guī)定其中有一個人可兼完成兩項任務，其余兩人每人完成一項，試確定總花費時間為最少的指派方案。

解這是一個非標準型的指派問題(目標為min型，費用系數(shù)矩陣為非方陣)。

第1步：求出系數(shù)矩陣任意兩行的對應元素之差，將其差額已矩陣的形式列于行右。

注：此處的列矩陣中的元素表示差額矩陣中對應行中元素是由原系數(shù)矩陣此兩行作差所得。

第2步：在差額矩陣中尋找最大元素，如此處是一行三列元素10，用標出，同時將其所在列的其他元素劃去，然后在系數(shù)矩陣中選出產(chǎn)生此最大差額的對應兩個元素，在兩者中選出最小元素，如此處是二行三列元素5，用(5)1表示，同時劃去其所在列的其他元素。

第3步：再在差額矩陣中剩余的列中尋找最大元素，如此處的是一行一列元素8，用標出，同時劃去該元所在列的其他元素，然后再在系數(shù)矩陣中找出產(chǎn)生此最大差額的對應的兩個元素，在二者中選出最小元素，此處是二行一列元素2，用(2)2表示，此時乙已經(jīng)承擔兩項任務了，故不再給他分配任務了，因此劃去該元所在行列的其他元素(這樣乙就可以不再被分配任務了)。同時將差額矩陣中與系數(shù)矩陣中有關(guān)的元素所在的行也劃掉。

第4步：同樣再在差額矩陣剩余的列中尋找最大元素，此處是二行四列元素7，用標出，同時劃去該元所在列的其他元素，然后再在系數(shù)矩陣中找出產(chǎn)生此最大差額的對應兩個元素，在二者中選出最小元素，此處是三行四列元素13，用(13)3標出，同時劃去其所在行列的其他元素(因為此人不能再承擔兩項任務了)。

第5步：對系數(shù)矩陣中未劃去的行列進行操作，因為本題只剩一行二列元素5沒被圈出，所以用(5)4表示。至此得到了問題的最優(yōu)解。

例2 求解如下指派問題，規(guī)定其中有一個人可兼完成兩項任務，其余3人每人完成一項，試確定總花費時間為最少的指派方案。

解：

(2)

(3)

(4)

(5)

3 總 結(jié)

總之，在解決非標準指派問題時，常采用的方法是將其先轉(zhuǎn)化為標準指派問題，然后再采用匈牙利算法求解，因此，對于“人少任務多”型指派問題的解法，提出了一種不同于傳統(tǒng)解法的差額法，算例顯示方法優(yōu)于其他算法，因為方法不必一開始就去用新的矩陣去代替原系數(shù)矩陣，而是可直接在原系數(shù)矩陣上進行求解，但在求解時要注意一些特殊情況。

參考文獻：

[1]張新輝．任務數(shù)多于人數(shù)的指派問題[J]．運籌與管理，1997,6(3)：20-25

[2]王增富．“人少任務多”最小指派問題的一種解法[J]．燕山大學學報，2004,28(5)：467-470

[3]朱德通．最優(yōu)化模型與實驗[M]．上海：同濟大學出版社，2003

[4]錢頌迪．運籌學(修訂版)[M]．北京：清華大學出版社，1990

[5]吳振奎．一類廣義指派問題及其解法[J]．天津商學院學報，1995，15(4)：80-82

[6]白國仲．毛經(jīng)中．C指派問題[J]．系統(tǒng)工程理論與實踐，2003,3(9)：107-111

[7]張世勇．一種新的混合粒子群優(yōu)化算法[J]．重慶工商大學學報：自然科學版，2007，24(3):241-245