一種求解指派問(wèn)題的進(jìn)步算法

王竹芳，潘雪

（沈陽(yáng)工業(yè)大學(xué)管理學(xué)院，遼寧沈陽(yáng)110870）

一種求解指派問(wèn)題的進(jìn)步算法

王竹芳，潘雪

（沈陽(yáng)工業(yè)大學(xué)管理學(xué)院，遼寧沈陽(yáng)110870）

通過(guò)對(duì)運(yùn)籌學(xué)中的兩類經(jīng)典問(wèn)題：指派問(wèn)題和最短路問(wèn)題的對(duì)比分析，發(fā)現(xiàn)并證明了兩者之間存在一定的聯(lián)系，并試著借用這種聯(lián)系用解最短路的解法解決指派問(wèn)題，最終證明了這種進(jìn)步算法的有效性和效率性。

運(yùn)籌學(xué)；指派問(wèn)題；最短路

引言

線性規(guī)劃是運(yùn)籌學(xué)中最主要的一個(gè)分支，其理論最完善、方法最成熟，應(yīng)用也最廣泛，涉及的很多問(wèn)題都是經(jīng)典的問(wèn)題，如運(yùn)輸問(wèn)題、指派問(wèn)題、最短路問(wèn)題、最小費(fèi)用流問(wèn)題等。在運(yùn)籌學(xué)學(xué)習(xí)過(guò)程中，我們發(fā)現(xiàn)這些問(wèn)題中存在著許多的相似，利用這些相似，我們可以用不同的解法解決同種問(wèn)題，也可以用某一種解法解決所有相似問(wèn)題，這對(duì)我們將來(lái)研究線性規(guī)劃的算法有很大的幫助。本文正是試圖發(fā)現(xiàn)并證明最短路問(wèn)題與指派問(wèn)題之間的相似性，并利用解最短路的算法解決指派問(wèn)題。

1　問(wèn)題及數(shù)學(xué)模型

1.1指派問(wèn)題

在現(xiàn)實(shí)生活中經(jīng)常會(huì)遇到這樣的問(wèn)題，某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)。由于每人的專長(zhǎng)不同，個(gè)人完成任務(wù)不同（或所費(fèi)時(shí)間），效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高（或所需總時(shí)間最小）。這類問(wèn)題稱為指派問(wèn)題。

指派問(wèn)題的標(biāo)準(zhǔn)形式是:設(shè)有n種工作和n個(gè)人，要求每件工作只能由一個(gè)人來(lái)做；而且每個(gè)人也只允許做一件工作；第i個(gè)人做第j件工作所需費(fèi)用（或時(shí)間）為Cij（i，j=1，2，…，n），其費(fèi)用矩陣為：

再設(shè)決策變量：

問(wèn)題的數(shù)學(xué)模型為:

1.2最短路問(wèn)題

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

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

問(wèn)題的數(shù)學(xué)模型為

1.3關(guān)系

定理：假設(shè)閉回路D中不存在負(fù)回路，令

那么模型I等同于模型II

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

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

結(jié)合（3）（4）我們證明了，在沒(méi)有負(fù)回路的假設(shè)前提下，模型（1）與模型（2）相同，也就是說(shuō)模型（2）的解就是模型（1）的解。

2　算例

2.1人數(shù)與任務(wù)數(shù)相等的指派問(wèn)題

有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文字，交甲乙丙丁四個(gè)人去完成，因個(gè)人專長(zhǎng)不同，他們完成翻譯不同文字所需的時(shí)間（h）如下表1所示。應(yīng)如何分配，是這四個(gè)人分別完成這四項(xiàng)任務(wù)總的時(shí)間最小。

表1　四個(gè)人分別完成四項(xiàng)任務(wù)總的時(shí)間h

點(diǎn)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

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

2.2人數(shù)與工作數(shù)不等的指派問(wèn)題

效率矩陣如表2所示，問(wèn)如何分配使完成任務(wù)使總時(shí)間最小。

表2　分配使完成任務(wù)使總時(shí)間h

首先，我們將效率矩陣轉(zhuǎn)換為

點(diǎn)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

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

3　結(jié)語(yǔ)

本文通過(guò)對(duì)運(yùn)籌學(xué)中的兩類經(jīng)典問(wèn)題：指派問(wèn)題和最短路問(wèn)題的對(duì)比分析，發(fā)現(xiàn)并證明了兩者之間的聯(lián)系，并借用這種聯(lián)系用解最短路的解法解決指派問(wèn)題。但是如果閉回路中存在負(fù)回路就不存在最短路，這種解法就會(huì)失效，所以我們需要繼續(xù)研究使其更加完美，并把它應(yīng)用到解決更多特殊的指派問(wèn)題中。

［1］錢頌迪.運(yùn)籌學(xué)［Ml.北京:清華大學(xué)出版社，1996.

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

［3］戴儉華，毛學(xué)榮.指派問(wèn)題與最短路徑問(wèn)題的相互關(guān)系［J］.合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），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］高興佑，張向輝.一種基于伏格爾法的指派問(wèn)題新算法［J］.曲靖師范學(xué)院學(xué)報(bào)，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］張勁松.求解指派問(wèn)題的對(duì)角調(diào)整法［J］.統(tǒng)計(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—），女，山東萊州人，博士，副教授，研究方向：經(jīng)濟(jì)管理中的數(shù)學(xué)方法與系統(tǒng)優(yōu)化。