王立柱，劉 陽(yáng)，石 洋，孫 軍

（1.沈陽(yáng)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽(yáng) 110034；2.中國(guó)人民解放軍93115部隊(duì)，沈陽(yáng) 110034）

0 引 言

非均衡投資收益極大的指派問(wèn)題是指有m個(gè)公司要參與n個(gè)項(xiàng)目的投資，由于每個(gè)公司業(yè)務(wù)能力不同、項(xiàng)目的不同，各公司投資各個(gè)項(xiàng)目的收益也不同，現(xiàn)希望從m個(gè)公司中選出k（0＜k≤gmin｛m，n｝）個(gè)公司去投資n個(gè)項(xiàng)目中的k項(xiàng)，每個(gè)公司只投資一個(gè)項(xiàng)目，每個(gè)項(xiàng)目只由一個(gè)公司完成，使得總收益最大。此類(lèi)問(wèn)題可以看作為投資小于公司和項(xiàng)目數(shù)的非標(biāo)準(zhǔn)極大指派問(wèn)題，記為極大（m，n，k）問(wèn)題。當(dāng)m＝n＝k時(shí)即為標(biāo)準(zhǔn)極大指派問(wèn)題。

對(duì)于極大（m，n，k）問(wèn)題，文獻(xiàn)［1］指出標(biāo)準(zhǔn)極大指派問(wèn)題可以轉(zhuǎn)化為標(biāo)準(zhǔn)指派問(wèn)題（極小指派問(wèn)題），利用經(jīng)典的匈牙利法求解。另外，文獻(xiàn)［2］提出了非方陣極大極小指派問(wèn)題且文獻(xiàn)［3］給出了貪婪算法；文獻(xiàn)［4］中提出了C指派問(wèn)題；文獻(xiàn)［5］任務(wù)數(shù)多于人數(shù)的指派間題；文獻(xiàn)［6］中提出了多目標(biāo)指派問(wèn)題及其在物資供應(yīng)中的應(yīng)用。查閱大量相關(guān)文獻(xiàn)［7－11］，沒(méi)有對(duì)上述問(wèn)題給予好的解法。本文將給出解決此類(lèi)問(wèn)題的相關(guān)理論及重要結(jié)論，并給出解決問(wèn)題的增反點(diǎn)算法。

1 非均衡投資收益極大指派問(wèn)題描述和數(shù)學(xué)模型

假設(shè)有n個(gè)公司且有n個(gè)投資項(xiàng)目，每公司投資不同項(xiàng)目的收益不同。現(xiàn)要從n個(gè)公司中選出k（0＜k≤n）個(gè)投資n個(gè)項(xiàng)目中的k項(xiàng)，求選哪k個(gè)公司投資哪k個(gè)項(xiàng)目才能使總收益最大。即極大（n，n，k）問(wèn)題。

更一般的情形，從m個(gè)公司中選出k（0＜k≤min｛m，n｝）個(gè)公司去投資n個(gè)項(xiàng)目中的k個(gè)項(xiàng)目使得總投資收益最大，即極大（m，n，k）問(wèn)題。極大（n，n，k）與極大（m，n，k）問(wèn)題統(tǒng)稱為非均衡投資收益極大指派問(wèn)題。

其中極大（m，n，k）問(wèn)題的數(shù)學(xué)模型為

（cij）m×n＞0稱為問(wèn)題的系數(shù)矩陣，當(dāng)取m＝n時(shí)，得極大（n，n，k）問(wèn)題的數(shù)學(xué)模型。當(dāng)取m＝n＝k時(shí)，即是標(biāo)準(zhǔn)極大指派問(wèn)題的數(shù)學(xué)模型。

該問(wèn)題實(shí)質(zhì)是求解m×n階系數(shù)矩陣中位于不同行、不同列的k（0＜k≤min ｛m，n｝）個(gè)元素求和最大。當(dāng)k較小時(shí)，問(wèn)題處理較為簡(jiǎn)單；通常對(duì)k較大時(shí)進(jìn)行研究。

2 反點(diǎn)及相關(guān)結(jié)果

定義1 在階數(shù)為n的方陣中，若某元素所在的行和列的其他元素都是方陣中的最大元素M，則此點(diǎn)稱做反點(diǎn)。如式（1）中r11就是反點(diǎn)，其中·表示n階方陣中的任意元素。

定理1 對(duì)于n階標(biāo)準(zhǔn)極大指派問(wèn)題，反點(diǎn)一定不含于最優(yōu)解中。

證明 以（n＝7）為例，設(shè)式（2）為標(biāo)準(zhǔn)極大指派問(wèn)題的系數(shù)矩陣。假設(shè)w1＝｛r14，r23，r32，r41，r55，r66，r77｝是標(biāo)準(zhǔn)極大指派問(wèn)題的最優(yōu)解，且包含反點(diǎn)r14，記相加之和v1＝r14＋r23＋r32＋r41＋r55＋r66＋r77。

從屬于最優(yōu)解并且不是反點(diǎn)的元素中任取一元素如r55，現(xiàn)選取r15和r54分別替換r14與r55得到新的可行解w2＝｛r15，r23，r32，r41，r54，r66，r77｝，如（3）所示。記相加之和v2＝r15＋r23＋r32＋r41＋r54＋r66＋r77。

由于r15＝M、r54＝M，顯然v1≤v2，這與w1是最優(yōu)解矛盾。對(duì)于n階系數(shù)矩陣結(jié)論同樣成立，因而結(jié)論得證。

定理2 對(duì)于n階標(biāo)準(zhǔn)極大指派問(wèn)題，如果系數(shù)矩陣中有k個(gè)反點(diǎn)，則最優(yōu)解中一定有2k個(gè)最優(yōu)點(diǎn)處于此k個(gè)反點(diǎn)所在的行與列，剩下的n－2k個(gè)最優(yōu)點(diǎn)一定是由去掉反點(diǎn)所在行、列所得到的n－k階方陣中不同行、列的n－2k個(gè)和達(dá)到最大的元素組成。

證明 由上面的結(jié)論知，反點(diǎn)必不是n階極大指派問(wèn)題最優(yōu)解w1中的元素。因?yàn)樽顑?yōu)解須滿足處于不同的行與列，因而，最優(yōu)解中必有一個(gè)元素處于反點(diǎn)所在的行與列上。所以，最優(yōu)解w1中必有2k個(gè)點(diǎn)處于反點(diǎn)所在的行與列。

去掉這k個(gè)反點(diǎn)所在的行與列的元素，得到n－k階方陣。由于n階標(biāo)準(zhǔn)極大指派問(wèn)題的最優(yōu)解w1中含有n個(gè)位于不同行、列的元素，其中2k個(gè)處于反點(diǎn)所在的行列，剩余n－2k個(gè)最優(yōu)點(diǎn)必落在未被去掉的n－k階矩陣中，且位于不同行、列和最大的n－2k個(gè)點(diǎn)。倘若剩余的n－2k個(gè)最優(yōu)點(diǎn)不是n－k階方陣中位于不同行、列和最大的n－2k個(gè)點(diǎn)，則與w1是最優(yōu)解矛盾。定理得證。

由定理2可知：對(duì)于n階標(biāo)準(zhǔn)極大指派問(wèn)題，若系數(shù)矩陣含有k個(gè)反點(diǎn)，則問(wèn)題最優(yōu)解就轉(zhuǎn)化為求劃去反點(diǎn)所在行、列得到的n－k階方陣中位于不同行不同列的n－2k個(gè)和最大的點(diǎn)。反之，若求n－k階方陣中位于不同行不同列的n－2k個(gè)和最大的點(diǎn)，可以通過(guò)增加k個(gè)反點(diǎn)轉(zhuǎn)化為求n階標(biāo)準(zhǔn)極大指派問(wèn)題。

定理3 對(duì)于求解極大（n，n，k）問(wèn)題，可通過(guò)增加n－k個(gè)反點(diǎn)求解2n－k階標(biāo)準(zhǔn)極大指派問(wèn)題得到。

證明 當(dāng)k＝n時(shí)，即為n階標(biāo)準(zhǔn)極大指派問(wèn)題，當(dāng)k＜n時(shí)，即求n階系數(shù)矩陣中位于不同行、列且和最大的k個(gè)點(diǎn)的位置，不妨在該n階矩陣的外面增加n－k個(gè)反點(diǎn)，此時(shí)變成一個(gè)2n－k階矩陣，由定理1、2求解此2n－k階標(biāo)準(zhǔn)極大指派問(wèn)題，便可得到極大（n，n，k）問(wèn)題的最優(yōu)解。

定理4 對(duì)于求解極大（m，n，k）問(wèn)題，可通過(guò)先將其系數(shù)矩陣補(bǔ)成max｛m，n｝階方陣，增加max｛m，n｝－k個(gè)反點(diǎn)求解2max｛m，n｝－k階標(biāo)準(zhǔn)極大指派問(wèn)題得到。

證明 將極大（m，n，k）問(wèn)題的m×n階系數(shù)矩陣（rij）m×n增加行或列的0元素得到max｛m，n｝階方陣，由定理3知，增加 max｛m，n｝－k個(gè)反點(diǎn)后 max｛m，n｝階方陣變成2max｛m，n｝－k階方陣，以此方陣為系數(shù)的指派問(wèn)題的最優(yōu)解中除處于反點(diǎn)上的2（max｛m，n｝－k）個(gè)最優(yōu)點(diǎn)外，其余的最優(yōu)點(diǎn)組成極大（m，n，k）指派問(wèn)題的最優(yōu)解。以m＝3，n＝4，k＝3為例，如（4）所示。先將3×4階系數(shù)矩陣增加一行0元素，然后增加一個(gè)反點(diǎn)，根據(jù)上面的結(jié)論知，極大（3，4，3）指派問(wèn)題的最優(yōu)解可通過(guò)求解5階標(biāo)準(zhǔn)極大指派問(wèn)題得到。

3 提出的算法

求解極大（n，n，k）和（m，n，k）問(wèn)題的算法如下：

第1步 標(biāo)準(zhǔn)化極大派問(wèn)題的系數(shù)矩陣。

1）若求解極大（n，n，k）問(wèn)題，則系數(shù)矩陣不變。

2）若求解極大（m，n，k）問(wèn)題，則增加行或列的0元素，將系數(shù)矩陣變?yōu)閙ax｛m，n｝階方陣。

第2步 計(jì)算所需增加反點(diǎn)數(shù)。

經(jīng)標(biāo)準(zhǔn)化處理后，得到的依然是n階方陣，在此方陣的外側(cè)增加n－k個(gè)反點(diǎn)使之變換成2n－k階方陣；極大（m，n，k）問(wèn)題系數(shù)矩陣變?yōu)?max｛m，n｝階方陣，在此方陣的外側(cè)再增加 max｛m，n｝－k個(gè)反點(diǎn)使其變成2max｛m，n｝－k階方陣。

第3步 求解經(jīng)第2步處理得到的方陣為系數(shù)矩陣的標(biāo)準(zhǔn)極大指派問(wèn)題。

利用匈牙利法［12］或已有的求解標(biāo)準(zhǔn)指派問(wèn)題的算法求解［13－16］。

第4步 計(jì)算最優(yōu)解。

通過(guò)以上3個(gè)步驟，可以得到標(biāo)準(zhǔn)指派問(wèn)題的最優(yōu)解，然后將此最優(yōu)解劃去位于反點(diǎn)所在行和列的最優(yōu)點(diǎn)，剩余的最優(yōu)點(diǎn)即為非均衡極大（n，n，k）及（m，n，k）指派問(wèn)題的最優(yōu)解。

4 Matlab程序及實(shí)例

算法的Matlab程序代碼如下：

例1 設(shè)有5個(gè)公司和4個(gè)投資項(xiàng)目，每個(gè)公司投資各個(gè)項(xiàng)目的收益如表1，現(xiàn)希望從這5個(gè)公司中選出3個(gè)投資4個(gè)項(xiàng)目中的3項(xiàng)，問(wèn)選哪3個(gè)公司投資哪3個(gè)項(xiàng)目才能使總收益最大。

解 此問(wèn)題是極大（m＝5，n＝4，k＝3）問(wèn)題，其的系數(shù)矩陣是5×4階矩陣，且＝73.6，解決此問(wèn)題可以補(bǔ)一列0元素且增加2個(gè)反點(diǎn)，將系數(shù)矩陣處理為R1＝（rij）9×9。以R1為系數(shù)矩陣解標(biāo)準(zhǔn)極大指派問(wèn)題，可得對(duì)應(yīng)極大（m＝5，n＝4，k＝3）問(wèn)題的最優(yōu)解矩陣R＊。

表1 投資項(xiàng)目表

運(yùn)行實(shí)例：

5 結(jié) 語(yǔ)

本文對(duì)極大非均衡投資問(wèn)題給出了反點(diǎn)算法，此方法通過(guò)增加反點(diǎn)使問(wèn)題變得簡(jiǎn)單化、易于處理。此算法同時(shí)也應(yīng)用于具體實(shí)例，實(shí)驗(yàn)結(jié)果表明了該方法的科學(xué)性和有效性。同時(shí)也為解決指派問(wèn)題提供了新思路、新方法。

［1］錢(qián)頌迪.運(yùn)籌學(xué)［M］.北京：清華大學(xué)出版社，1990：123－204.

［2］PAUL C，JE B.A genetic algorithm for the generalized assignment problem［J］.Comput Opera Res，1997，24（1）：17－23.

［3］SHARKEY T C.Greedy approaches for a class of nonlinear Generalized Assignment Problems［J］.Disc Appl Math，2010，158（1）：559－572.

［4］白國(guó)仲，毛經(jīng)中.C指派問(wèn)題［J］.系統(tǒng)工程理論與實(shí)踐，2003，23（3）：107－111.

［5］張新輝.任務(wù)數(shù)多于人數(shù)的指派問(wèn)題［J］.運(yùn)籌與管理，1997，6（3）：20－25.

［6］宋業(yè)新，陳綿云，張暑紅.多目標(biāo)指派問(wèn)題及其在軍械物資供應(yīng)中的應(yīng)用［J］.系統(tǒng)工程理論與實(shí)踐，2001，21（11）：141－144.

［7］殷人昆，吳陽(yáng)，張晶煒.蟻群算法解決指派問(wèn)題的研究和應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2008，30（4）：43－46.

［8］劉樹(shù)立，于麗英.人數(shù)與任務(wù)數(shù)不相等的指派問(wèn)題［J］.運(yùn)籌與管理，2005，14（2）：64－66.

［9］吳艷群，董鵬.求解大規(guī)模不對(duì)稱指派問(wèn)題的通用模擬退火算法［J］.蘭州交通大學(xué)學(xué)報(bào)，2008，27（4）：149－153.

［10］胡勁松.模糊指派問(wèn)題求解方法研究［J］.系統(tǒng)工程理論與實(shí)踐，2001，4（9）：94－99.

［11］秦學(xué)志，王雪華.一類(lèi)最優(yōu)指派問(wèn)題的動(dòng)態(tài)規(guī)劃模型［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，1996，26（3）：212－216.

［12］熊燕華.對(duì)國(guó)內(nèi)求解指派問(wèn)題的匈牙利法改進(jìn)的評(píng)述［J］.中國(guó)制造信息化，2009，63（04）：63－67.

［13］孫曉雅.一種新的離散粒子群算法在指派問(wèn)題中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2009，26（11）：201－206.

［14］賀學(xué)海.單純形法解決LP問(wèn)題的研究［J］.沈陽(yáng)師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，28（1）：45－49.

［15］夏少剛，費(fèi)威.基于最小調(diào)整法求解最短時(shí)限指派問(wèn)題［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009，39（17）：140－149.

［16］李巖，郭強(qiáng).非確定型指派問(wèn)題的求解算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（15）：61－65.