一種求解指派問題的進步算法

王竹芳，潘雪

（沈陽工業大學管理學院，遼寧沈陽110870）

一種求解指派問題的進步算法

王竹芳，潘雪

（沈陽工業大學管理學院，遼寧沈陽110870）

通過對運籌學中的兩類經典問題：指派問題和最短路問題的對比分析，發現并證明了兩者之間存在一定的聯系，并試著借用這種聯系用解最短路的解法解決指派問題，最終證明了這種進步算法的有效性和效率性。

運籌學；指派問題；最短路

引言

線性規劃是運籌學中最主要的一個分支，其理論最完善、方法最成熟，應用也最廣泛，涉及的很多問題都是經典的問題，如運輸問題、指派問題、最短路問題、最小費用流問題等。在運籌學學習過程中，我們發現這些問題中存在著許多的相似，利用這些相似，我們可以用不同的解法解決同種問題，也可以用某一種解法解決所有相似問題，這對我們將來研究線性規劃的算法有很大的幫助。本文正是試圖發現并證明最短路問題與指派問題之間的相似性，并利用解最短路的算法解決指派問題。

1　問題及數學模型

1.1指派問題

在現實生活中經常會遇到這樣的問題，某單位需完成n項任務，恰好有n個人可承擔這些任務。由于每人的專長不同，個人完成任務不同（或所費時間），效率也不同。于是產生應指派哪個人去完成哪項任務，使完成n項任務的總效率最高（或所需總時間最小）。這類問題稱為指派問題。

指派問題的標準形式是:設有n種工作和n個人，要求每件工作只能由一個人來做；而且每個人也只允許做一件工作；第i個人做第j件工作所需費用（或時間）為Cij（i，j=1，2，…，n），其費用矩陣為：

再設決策變量：

問題的數學模型為:

1.2最短路問題

給定一個有向圖D=（V，A），對每一個弧a=（vi，vj），相應地有權w（a）=wij，又給定D中的兩個頂點vs，vt。設P是D中從vs到vt的一條路，定義路P的權是P中所有弧的權之和，記為w（P）。最短路問題就是要在所有從vs到vt的路中，求一條權最小的路，即求一條從vs到vt的路P0，使

式中對D中所有從vs到vt的路P取最小，稱P0是從vs到vt的最短路。路P0的權稱為vs到vt的距離，記為d（vs，vt）。顯然，d（vs，vt）與d（vt，vs）不一定相等。

問題的數學模型為

1.3關系

定理：假設閉回路D中不存在負回路，令

那么模型I等同于模型II

證明：假設X=｛xij，i=1，2，…，n-1，j=2，3，…，n，i≠j｝是模型I的最優解，定義

顯然X是模型II的可行解，而且

結合（3）（4）我們證明了，在沒有負回路的假設前提下，模型（1）與模型（2）相同，也就是說模型（2）的解就是模型（1）的解。

2　算例

2.1人數與任務數相等的指派問題

有一份說明書，要分別譯成英、日、德、俄四種文字，交甲乙丙丁四個人去完成，因個人專長不同，他們完成翻譯不同文字所需的時間（h）如下表1所示。應如何分配，是這四個人分別完成這四項任務總的時間最小。

表1　四個人分別完成四項任務總的時間h

點wijd（t）（vl，vj）v2v3v4v5t = 1 t = 2 t = 3 v15 7 8 8 5 5 5 v20 1 -1 -2 7 6 6 v32 0 4 2 8 4 4 v45 7 0 0 8 3 3

通過回溯，最短路為1-2-5。即x12=1，x25=1，x33=1，x44=1，其余為0。原指派問題的解甲譯英，乙譯德，丙譯俄，丁譯日。

2.2人數與工作數不等的指派問題

效率矩陣如表2所示，問如何分配使完成任務使總時間最小。

表2　分配使完成任務使總時間h

首先，我們將效率矩陣轉換為

點d（t）（v1，vj）v2v3v4v5v6t = 1 t = 2 t = 3 t = 4 v10 4 6 1 7 1 2 0 0 0 0 v20 -1 -1 3 -1 9 -6 4 -1 -7 -7 v37 0 1 1 3 5 6 -1 3 -1 3 -1 3 v41 4 6 0 -1 3 9 1 7 -1 9 -2 6 -2 6 1 2 -6 -6 -6 w i j

通過回溯，最短路為1-2-4-5，即x12=1，x24=1，x45=1，x33=1，其余為0。原指派問題的解任務甲在機器1上做，任務乙在機器3上做，任務并在機器2上做，任務丁在機器4上做。

3　結語

本文通過對運籌學中的兩類經典問題：指派問題和最短路問題的對比分析，發現并證明了兩者之間的聯系，并借用這種聯系用解最短路的解法解決指派問題。但是如果閉回路中存在負回路就不存在最短路，這種解法就會失效，所以我們需要繼續研究使其更加完美，并把它應用到解決更多特殊的指派問題中。

［1］錢頌迪.運籌學［Ml.北京:清華大學出版社，1996.

［2］謝凡榮.求解指派問題的一個算法［J］.運籌與管理，2004（6）:37-40.

［3］戴儉華，毛學榮.指派問題與最短路徑問題的相互關系［J］.合肥工業大學學報（自然科學版），1992（1）:132-140.

［4］Oh Y H，Hang H，Cha C N，Lee S.A dock-door assignment problem for the Korean mail distribution center［J］.Computers&Industrial Engineering，2006（51）:288-296.

［5］高興佑，張向輝.一種基于伏格爾法的指派問題新算法［J］.曲靖師范學院學報，2008（3）:12-14.

［6］Huang G F，Lin A.A hybrid genetic algorithm for the three index assignment problem［J］.European Journal of Operational Research，2006（172）:249-257.

［7］張勁松.求解指派問題的對角調整法［J］.統計與決策，2007（23）: 164-165.

（編輯：劉楠）

A progressive Algorithm Assignment Problem

Wang Zhufang，Pan Xue
（Management School of Shenyang Industry University，Shenyang Liaoning 110870）

Based on the two types of operations research in the classic question:assignment problem and comparative analysis of the short-circuit problem，we find and prove the existence of certain links between the two，and try to borrow such a link with a solution to solve assignment shortest path method question，the ultimate proof of this progress effectiveness and efficiency.

operations research；the assignment problem；path

O241

A

2095-0748（2015）21-0065-03

10.16525/j.cnki.14-1362/n.2015.21.28

2015-10-06

王竹芳（1972—），女，山東萊州人，博士，副教授，研究方向：經濟管理中的數學方法與系統優化。