馬 曉 娜

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

1 預(yù)備知識(shí)

1.1 標(biāo)準(zhǔn)指派問題[3]

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

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

1.2 標(biāo)準(zhǔn)指派問題的匈牙利算法[4]

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

1.3 非標(biāo)準(zhǔn)型指派問題

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

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

2 主要結(jié)論

2.1 差額法的算法

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

第2步：在差額矩陣中尋找最大元素，用符號(hào)標(biāo)記出來，同時(shí)劃去該元所在列的其他元素。

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

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

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

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

2.2 實(shí)例分析

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

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

解這是一個(gè)非標(biāo)準(zhǔn)型的指派問題(目標(biāo)為min型，費(fèi)用系數(shù)矩陣為非方陣)。

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

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

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

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

第4步：同樣再在差額矩陣剩余的列中尋找最大元素，此處是二行四列元素7，用標(biāo)出，同時(shí)劃去該元所在列的其他元素，然后再在系數(shù)矩陣中找出產(chǎn)生此最大差額的對(duì)應(yīng)兩個(gè)元素，在二者中選出最小元素，此處是三行四列元素13，用(13)3標(biāo)出，同時(shí)劃去其所在行列的其他元素(因?yàn)榇巳瞬荒茉俪袚?dān)兩項(xiàng)任務(wù)了)。

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

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

解：

(2)

(3)

(4)

(5)

3 總 結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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