非均衡投資收益極大指派問題

王立柱，劉 陽，石 洋，孫 軍

（1.沈陽師范大學 數學與系統科學學院，沈陽 110034；2.中國人民解放軍93115部隊，沈陽 110034）

0 引 言

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

對于極大（m，n，k）問題，文獻［1］指出標準極大指派問題可以轉化為標準指派問題（極小指派問題），利用經典的匈牙利法求解。另外，文獻［2］提出了非方陣極大極小指派問題且文獻［3］給出了貪婪算法；文獻［4］中提出了C指派問題；文獻［5］任務數多于人數的指派間題；文獻［6］中提出了多目標指派問題及其在物資供應中的應用。查閱大量相關文獻［7－11］，沒有對上述問題給予好的解法。本文將給出解決此類問題的相關理論及重要結論，并給出解決問題的增反點算法。

1 非均衡投資收益極大指派問題描述和數學模型

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

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

其中極大（m，n，k）問題的數學模型為

（cij）m×n＞0稱為問題的系數矩陣，當取m＝n時，得極大（n，n，k）問題的數學模型。當取m＝n＝k時，即是標準極大指派問題的數學模型。

該問題實質是求解m×n階系數矩陣中位于不同行、不同列的k（0＜k≤min ｛m，n｝）個元素求和最大。當k較小時，問題處理較為簡單；通常對k較大時進行研究。

2 反點及相關結果

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

定理1 對于n階標準極大指派問題，反點一定不含于最優解中。

證明 以（n＝7）為例，設式（2）為標準極大指派問題的系數矩陣。假設w1＝｛r14，r23，r32，r41，r55，r66，r77｝是標準極大指派問題的最優解，且包含反點r14，記相加之和v1＝r14＋r23＋r32＋r41＋r55＋r66＋r77。

從屬于最優解并且不是反點的元素中任取一元素如r55，現選取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是最優解矛盾。對于n階系數矩陣結論同樣成立，因而結論得證。

定理2 對于n階標準極大指派問題，如果系數矩陣中有k個反點，則最優解中一定有2k個最優點處于此k個反點所在的行與列，剩下的n－2k個最優點一定是由去掉反點所在行、列所得到的n－k階方陣中不同行、列的n－2k個和達到最大的元素組成。

證明 由上面的結論知，反點必不是n階極大指派問題最優解w1中的元素。因為最優解須滿足處于不同的行與列，因而，最優解中必有一個元素處于反點所在的行與列上。所以，最優解w1中必有2k個點處于反點所在的行與列。

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

由定理2可知：對于n階標準極大指派問題，若系數矩陣含有k個反點，則問題最優解就轉化為求劃去反點所在行、列得到的n－k階方陣中位于不同行不同列的n－2k個和最大的點。反之，若求n－k階方陣中位于不同行不同列的n－2k個和最大的點，可以通過增加k個反點轉化為求n階標準極大指派問題。

定理3 對于求解極大（n，n，k）問題，可通過增加n－k個反點求解2n－k階標準極大指派問題得到。

證明 當k＝n時，即為n階標準極大指派問題，當k＜n時，即求n階系數矩陣中位于不同行、列且和最大的k個點的位置，不妨在該n階矩陣的外面增加n－k個反點，此時變成一個2n－k階矩陣，由定理1、2求解此2n－k階標準極大指派問題，便可得到極大（n，n，k）問題的最優解。

定理4 對于求解極大（m，n，k）問題，可通過先將其系數矩陣補成max｛m，n｝階方陣，增加max｛m，n｝－k個反點求解2max｛m，n｝－k階標準極大指派問題得到。

證明 將極大（m，n，k）問題的m×n階系數矩陣（rij）m×n增加行或列的0元素得到max｛m，n｝階方陣，由定理3知，增加 max｛m，n｝－k個反點后 max｛m，n｝階方陣變成2max｛m，n｝－k階方陣，以此方陣為系數的指派問題的最優解中除處于反點上的2（max｛m，n｝－k）個最優點外，其余的最優點組成極大（m，n，k）指派問題的最優解。以m＝3，n＝4，k＝3為例，如（4）所示。先將3×4階系數矩陣增加一行0元素，然后增加一個反點，根據上面的結論知，極大（3，4，3）指派問題的最優解可通過求解5階標準極大指派問題得到。

3 提出的算法

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

第1步 標準化極大派問題的系數矩陣。

1）若求解極大（n，n，k）問題，則系數矩陣不變。

2）若求解極大（m，n，k）問題，則增加行或列的0元素，將系數矩陣變為max｛m，n｝階方陣。

第2步 計算所需增加反點數。

經標準化處理后，得到的依然是n階方陣，在此方陣的外側增加n－k個反點使之變換成2n－k階方陣；極大（m，n，k）問題系數矩陣變為 max｛m，n｝階方陣，在此方陣的外側再增加 max｛m，n｝－k個反點使其變成2max｛m，n｝－k階方陣。

第3步 求解經第2步處理得到的方陣為系數矩陣的標準極大指派問題。

利用匈牙利法［12］或已有的求解標準指派問題的算法求解［13－16］。

第4步 計算最優解。

通過以上3個步驟，可以得到標準指派問題的最優解，然后將此最優解劃去位于反點所在行和列的最優點，剩余的最優點即為非均衡極大（n，n，k）及（m，n，k）指派問題的最優解。

4 Matlab程序及實例

算法的Matlab程序代碼如下：

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

解 此問題是極大（m＝5，n＝4，k＝3）問題，其的系數矩陣是5×4階矩陣，且＝73.6，解決此問題可以補一列0元素且增加2個反點，將系數矩陣處理為R1＝（rij）9×9。以R1為系數矩陣解標準極大指派問題，可得對應極大（m＝5，n＝4，k＝3）問題的最優解矩陣R＊。

表1 投資項目表

運行實例：

5 結 語

本文對極大非均衡投資問題給出了反點算法，此方法通過增加反點使問題變得簡單化、易于處理。此算法同時也應用于具體實例，實驗結果表明了該方法的科學性和有效性。同時也為解決指派問題提供了新思路、新方法。

［1］錢頌迪.運籌學［M］.北京：清華大學出版社，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］白國仲，毛經中.C指派問題［J］.系統工程理論與實踐，2003，23（3）：107－111.

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

［6］宋業新，陳綿云，張暑紅.多目標指派問題及其在軍械物資供應中的應用［J］.系統工程理論與實踐，2001，21（11）：141－144.

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

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

［9］吳艷群，董鵬.求解大規模不對稱指派問題的通用模擬退火算法［J］.蘭州交通大學學報，2008，27（4）：149－153.

［10］胡勁松.模糊指派問題求解方法研究［J］.系統工程理論與實踐，2001，4（9）：94－99.

［11］秦學志，王雪華.一類最優指派問題的動態規劃模型［J］.數學的實踐與認識，1996，26（3）：212－216.

［12］熊燕華.對國內求解指派問題的匈牙利法改進的評述［J］.中國制造信息化，2009，63（04）：63－67.

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

［14］賀學海.單純形法解決LP問題的研究［J］.沈陽師范大學學報：自然科學版，2010，28（1）：45－49.

［15］夏少剛，費威.基于最小調整法求解最短時限指派問題［J］.數學的實踐與認識，2009，39（17）：140－149.

［16］李巖，郭強.非確定型指派問題的求解算法［J］.計算機工程與應用，2009，45（15）：61－65.