指派問(wèn)題的算法

1、 指派問(wèn)題的算法分析與實(shí)現(xiàn)摘 要在企業(yè)、公司的運(yùn)營(yíng)與管理中，管理者總是希望把人員最佳分派以發(fā)揮其最大工作效率，從而降低成本、提高效益。然而，如果沒(méi)有科學(xué)的方法是很難實(shí)現(xiàn)優(yōu)化管理的，由此我們引入了指派問(wèn)題。指派問(wèn)題多是求項(xiàng)目的工時(shí)最少，而很多情況下人們并不關(guān)心項(xiàng)目總工時(shí)的多少，而只關(guān)心項(xiàng)目能否在最短的時(shí)間內(nèi)完成，即歷時(shí)最少的指派問(wèn)題。這類(lèi)問(wèn)題研究的是n個(gè)人執(zhí)行n項(xiàng)任務(wù)，執(zhí)行每項(xiàng)任務(wù)的人數(shù)以及總的指派人項(xiàng)數(shù)均有限制，要求最優(yōu)指派。在運(yùn)籌學(xué)中求解整數(shù)規(guī)劃的指派問(wèn)題通常是通過(guò)匈牙利算法來(lái)求解，但指派問(wèn)題也可以歸結(jié)為一個(gè)0-1整數(shù)規(guī)劃問(wèn)題，本文先對(duì)指派問(wèn)題進(jìn)行陳述，引出對(duì)實(shí)際問(wèn)題的求解。在指派問(wèn)題的背景

2、、描述中充分理解該問(wèn)題，先運(yùn)用匈牙利算法實(shí)現(xiàn)指派問(wèn)題，然后再建立一個(gè)0-1整數(shù)規(guī)劃模型，并運(yùn)用matlab和lingo編譯程序?qū)?wèn)題進(jìn)行編譯，運(yùn)用軟件解決模型問(wèn)題，最終實(shí)現(xiàn)指派問(wèn)題在實(shí)際問(wèn)題中的運(yùn)用。通過(guò)運(yùn)用匈牙利算法和0-1整數(shù)規(guī)劃同時(shí)對(duì)指派問(wèn)題求解，我們發(fā)現(xiàn)用0-1整數(shù)規(guī)劃的方法來(lái)求解可以更簡(jiǎn)單，也更方便程序的閱讀和理解。與此同時(shí)，我們還對(duì)0-1整數(shù)規(guī)劃問(wèn)題由整數(shù)數(shù)據(jù)深入研究到小數(shù)數(shù)據(jù)。最后通過(guò)實(shí)例來(lái)說(shuō)明運(yùn)用matlab，lingo編譯程序來(lái)解決整數(shù)規(guī)劃問(wèn)題的簡(jiǎn)便和有效性。關(guān)鍵詞：指派問(wèn)題；匈牙利算法；0-1整數(shù)規(guī)劃；matlab模型；lingo模型1. 問(wèn)題陳述指派問(wèn)題又稱(chēng)分配問(wèn)題，其用

3、途非常廣泛，比如某公司指派n個(gè)人去做n件事，各人做不同的事，如何安排人員使得總費(fèi)用最少？若考慮每個(gè)職工對(duì)工作效率（如熟練程度等），怎樣安排會(huì)使總銷(xiāo)量達(dá)到最大？這些都是一個(gè)企業(yè)經(jīng)營(yíng)管理者必須考慮的問(wèn)題，所以該問(wèn)題有重要的應(yīng)用價(jià)值。假設(shè)有n件工作分派給n個(gè)人來(lái)做，每項(xiàng)工作只能由一人來(lái)做，每個(gè)人只能做一項(xiàng)工作。若給出各人對(duì)各項(xiàng)工作所具有的工作效率。問(wèn)應(yīng)該如何安排人選，及發(fā)揮個(gè)人特長(zhǎng)又能使總的效率最大。為此用0-1整數(shù)規(guī)劃來(lái)實(shí)現(xiàn)指派問(wèn)題即如何安排人選。2.背景在現(xiàn)實(shí)生活中，有各種性質(zhì)的指派問(wèn)題（Assignment Problem）。例如，在生產(chǎn)管理中，總希望把人員進(jìn)行最佳分配，以發(fā)揮最大的工作效率；

4、某部門(mén)有n項(xiàng)任務(wù)要完成，而該部門(mén)正好有n個(gè)人可以分別去完成其中任何一項(xiàng)，但由于任務(wù)性質(zhì)和個(gè)人的專(zhuān)長(zhǎng)不同，因此各人完成各項(xiàng)不同任務(wù)的效益（所費(fèi)時(shí)間或所花費(fèi)用）也有差別，如果分配每個(gè)人完成一項(xiàng)任務(wù)且僅為一項(xiàng)任務(wù)，則把每項(xiàng)任務(wù)分配給哪個(gè)人去完成，使完成所有n項(xiàng)任務(wù)的總效益為最高（總時(shí)間、總費(fèi)用為最小或創(chuàng)造的價(jià)值最大）？這是典型的分配問(wèn)題或指派問(wèn)題。又如有n項(xiàng)加工任務(wù)，怎樣指定n臺(tái)機(jī)器分別去完成，以使總的加工時(shí)間最少或總收入最大；有n條航線，怎樣指定n艘船分別航行，使總收入最大，等等，都屬于指派問(wèn)題。3. 指派問(wèn)題的描述3.1 指派問(wèn)題的一般形式指派問(wèn)題的標(biāo)準(zhǔn)形式（以人和事為例）如下。有n個(gè)人和n項(xiàng)任

5、務(wù)，已知第i個(gè)人做第j件事的費(fèi)用為，要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使完成這n項(xiàng)任務(wù)的費(fèi)用最少。一般把目標(biāo)函數(shù)的系數(shù)寫(xiě)為矩陣形式，稱(chēng)矩陣為系數(shù)矩陣（Coefficient Matrix），也稱(chēng)為效益矩陣或價(jià)值矩陣。矩陣的元素（i,j=1,2,n）表示分配第i個(gè)人去完成第j項(xiàng)任務(wù)時(shí)的效益。一般地，以表示給定的資源分配用于給定活動(dòng)時(shí)的有關(guān)效益（時(shí)間，費(fèi)用，價(jià)值等），且3.2 問(wèn)題的數(shù)學(xué)模型一般形式在模型中，約束條件式（2）表示每個(gè)人只能做一件事，約束條件式（3）表示每件事只能由一個(gè)人去做。對(duì)于問(wèn)題的每個(gè)可行解，可用解矩陣來(lái)表示：當(dāng)然，作為可行解，矩陣的每列元素中都有且只有一個(gè)1，以滿足約束

6、條件式（3）。每行元素中也有且只有一個(gè)1，以滿足約束條件（2）。指派問(wèn)題n!個(gè)可行解。3.3 目標(biāo)函數(shù)極大化的指派問(wèn)題求解時(shí)，我們將構(gòu)造一個(gè)新的矩陣，使，其中是一個(gè)足夠大的常數(shù)。一般取中最大的元素作為，求解，所得的解就是原問(wèn)題的解。事實(shí)上，由可的此結(jié)論。4指派問(wèn)題實(shí)現(xiàn)4.1 匈牙利算法4.1.1 匈牙利算法的理論基礎(chǔ)定理1 如果從分配問(wèn)題的效率矩陣的每一行元素中分別減去（或加上）一個(gè)常數(shù)，從每一列中分別減去（或加上）一個(gè)常數(shù)，得到一個(gè)新的效率矩陣，則以為效率矩陣的分配問(wèn)題與以為效率矩陣的分配問(wèn)題具有相同的最優(yōu)解。定理2 若矩陣A的元素可以分為0與非0的兩部分，則覆蓋0元素最少直線數(shù)等于位于不同

7、行不同列的0元素的最大個(gè)數(shù)。4.1.2匈牙利算法的實(shí)現(xiàn)步驟第一步：找出矩陣每行的最小元素，分別從每行中減去這個(gè)最小元素；第二步：再找去矩陣每列的最小元素，分別從各列減去這個(gè)最小元素；第三步：經(jīng)過(guò)這兩步變換后，矩陣的每行每列至少都有了一個(gè)零元素，接著根據(jù)以下準(zhǔn)則進(jìn)行試指派，找出覆蓋上面矩陣中所有零元素至少需要多少條直線；（1）從第一行開(kāi)始，若該行只有一個(gè)零元素打上（）號(hào)。對(duì)打（）號(hào)零元素所在列劃一條直線。若該行沒(méi)有零元素或有兩個(gè)以上零元素（已劃去的不計(jì)在內(nèi)），則轉(zhuǎn)下一行，一直到最后一行為止；（2）從第一列開(kāi)始，若該列只有一個(gè)零元素就對(duì)這個(gè)零元素打上（）號(hào)（同樣不考慮已劃去的零元素），對(duì)打（）號(hào)零

8、元素所在行劃一條直線。若該列沒(méi)有零元素或 還有兩個(gè)以上零元素，則轉(zhuǎn)下一列，并進(jìn)行到最后一列；（3）重復(fù)（1）、（2）兩個(gè)步驟，可能出現(xiàn)三種情況： 矩陣每行都有一個(gè)打（）號(hào)零元素，很顯然，按照上述步驟得到的打（）的零元素都位于不同行不同列，因此就找到了問(wèn)題的答案； 有多于兩行或兩列存在兩個(gè)以上零元素，即出現(xiàn)了零元素的閉回路，這個(gè)時(shí)候可順著閉回路的走向，對(duì)每個(gè)間隔的零元素打上（）號(hào)，然后對(duì)所有打（）號(hào)零元素或所有列或所在行劃一條直線。 矩陣中所有零元素或打上（）號(hào)，或被劃去，但打（）號(hào)零元素個(gè)數(shù)小于m。第四步：為了設(shè)法使每行都有一個(gè)打（）的零元素，就要繼續(xù)對(duì)矩陣進(jìn)行變換；（1）從矩陣未被直線覆蓋的

9、元素找出最小元素k；（2）對(duì)矩陣的每行，當(dāng)該行有直線覆蓋時(shí)，令=0，無(wú)直線覆蓋的，令=k；（3）對(duì)矩陣的每列，當(dāng)該列有直線覆蓋時(shí)，令=-k，無(wú)直線覆蓋的，令=0；（4）得列一個(gè)變換后的矩陣，其中每個(gè)元素=-。第五步：回到第三步，反復(fù)進(jìn)行，一直到矩陣中每一行都有一個(gè)打（）的零元素為止，即找到最優(yōu)分配方案為止。4.1.3 匈牙利算法實(shí)現(xiàn)指派問(wèn)題為了便于對(duì)模型進(jìn)行求解與分析，假設(shè)有4件事4個(gè)人去做，各變量對(duì)應(yīng)的數(shù)據(jù)假設(shè)如表1。表1 每個(gè)人完成各項(xiàng)任務(wù)需要的時(shí)間人任務(wù)ABCD甲25293142乙39382620丙34272840丁24423623用匈牙利算法求解過(guò)程如下： Min -1 -1 -1 -

10、4 -4 -1 -1所以最優(yōu)解為x11，x23，x32，x44，即甲負(fù)責(zé)任務(wù)A，乙負(fù)責(zé)任務(wù)C，丙負(fù)責(zé)任務(wù)B，丁負(fù)責(zé)任務(wù)D，可以使總花費(fèi)時(shí)間最少。代入求出目標(biāo)函數(shù)值Z=25+26+27+23=101。4.2 0-1整數(shù)規(guī)劃0-1規(guī)劃（0-1 Programming）一種特殊形式的整數(shù)規(guī)劃 。這種規(guī)劃的決策變量?jī)H取值0或1，故稱(chēng)為0-1變量或二進(jìn)制變量 ，因?yàn)橐粋€(gè)非負(fù)整數(shù)都可以用二進(jìn)制記 數(shù)法用若干個(gè)0-1變量表示 。0-1變量可以數(shù)量化地描述諸如開(kāi)與關(guān)、取與棄、有與無(wú)等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及互斥的約束條件 ，因此0-1規(guī)劃非常適合描述和解決如線路設(shè)計(jì) 、工廠選址 、生產(chǎn)計(jì)

11、劃安排、旅行購(gòu)物、背包問(wèn)題、人員安排、代碼選取、可靠性等人們所關(guān)心的多種問(wèn)題。實(shí)際上，凡是有界變量的整數(shù)規(guī)劃都可以轉(zhuǎn)化為0-1規(guī)劃來(lái)處理。當(dāng)然也包括運(yùn)籌學(xué)中的指派問(wèn)題。4.2.1 模型假設(shè)為了便于對(duì)模型進(jìn)行求解與分析，假設(shè)有4件事4個(gè)人去做，各變量對(duì)應(yīng)的數(shù)據(jù)假設(shè)如表1。表1 每個(gè)人完成各項(xiàng)任務(wù)需要的時(shí)間人任務(wù)ABCD甲25293142乙39382620丙34272840丁24423623表2 變量假設(shè)i第i個(gè)人j第j項(xiàng)任務(wù)第i個(gè)人分配第j項(xiàng)任務(wù)=1第i個(gè)人被分配去做第j項(xiàng)任務(wù)=0第i個(gè)人不被分配到第j項(xiàng)任務(wù)4.2.2 模型建立根據(jù)前面的假設(shè)，因此，每個(gè)人只完成一項(xiàng)任務(wù)的約束條件為：每項(xiàng)任務(wù)必有

12、一個(gè)人負(fù)責(zé)的約束條件為： 由此，建立的數(shù)學(xué)模型為： s.t. 或1，i，j=1，2，3，44.2.3 模型求解 用matlab求解根據(jù)上面建立的模型，代入相應(yīng)的數(shù)據(jù)，利用matlab軟件編程求解，具體程序如下：function y,fval=minzp(C) %y為最佳匹配矩陣，fval為目標(biāo)函數(shù)值，C為目標(biāo)函數(shù)系數(shù)矩陣C=C;f=C(:);m,n=size(C);Aeq=zeros(2*n,n*n); %生成2*n行n*n列的等式約束0系數(shù)矩陣for i=1:nAeq(1:n,1+(i-1)*n:i*n)=eye(n,n); %eye表示生成n階單位陣endfor i=1:nAeq(n+i,

13、1+(i-1)*n:i*n)=ones(1,n); %生成1行n列元素為1的向量endbeq=ones(2*n,1); %生成2*n行1列元素為1的等式約束右端項(xiàng)lb=zeros(n*n,1); %生成n*n行1列元素為0的不等式約束左端項(xiàng)ub=ones(n*n,1); %生成n*n行1列元素為1的不等式約束右端項(xiàng)x=linprog(f,Aeq,beq,lb,ub); %求目標(biāo)函數(shù)達(dá)到極小值的x值y=reshape(x,n,n); %將上式求出的x值組成的向量變成n階矩陣y=y;y=round(y); %對(duì)y中的元素取整，生成匹配矩陣sol=zeros(n,n);for i=1:nfor j=

14、1:nif y(i,j)=1sol(i,j)=C(j,i);endendendfval=sum(sol(:); %求出極小值的目標(biāo)函數(shù)值其中， C=25 29 31 4239 38 26 2034 27 28 4024 42 36 23; y,fval=minzp(C)輸出結(jié)果為：Optimization terminated.y = 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1fval =101用lingo軟件求解根據(jù)上面建立的模型，代入相應(yīng)的數(shù)據(jù)，利用lingo軟件編程求解，具體程序如下：model:sets:ren/1.4/;renwu/1.4/;Assign(ren,

15、renwu):C,X; ！X為最佳匹配矩陣，C為目標(biāo)函數(shù)系數(shù)endsetsdata:C=25 29 31 4239 38 26 2034 27 28 4024 42 36 23;enddatamin=sum(Assign:C*X);！求目標(biāo)函數(shù)極小值FOR(ren(i):sum(renwu(j):X(i,j)=1);！行和為1約束FOR(renwu(j):sum(ren(i):X(i,j)=1);！列和為1約束for(Assign:bin(x);！0-1約束End運(yùn)行結(jié)果為：Global optimal solution found. Objective value: 101.0000 Ext

16、ended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost C( 1, 1) 25.00000 0.000000 C( 1, 2) 29.00000 0.000000 C( 1, 3) 31.00000 0.000000 C( 1, 4) 42.00000 0.000000 C( 2, 1) 39.00000 0.000000 C( 2, 2) 38.00000 0.000000 C( 2, 3) 26.00000 0.000000 C( 2, 4) 20.00000 0.000000 C( 3, 1

17、) 34.00000 0.000000 C( 3, 2) 27.00000 0.000000 C( 3, 3) 28.00000 0.000000 C( 3, 4) 40.00000 0.000000 C( 4, 1) 24.00000 0.000000 C( 4, 2) 42.00000 0.000000 C( 4, 3) 36.00000 0.000000 C( 4, 4) 23.00000 0.000000 X( 1, 1) 0.000000 25.00000 X( 1, 2) 1.000000 29.00000 X( 1, 3) 0.000000 31.00000 X( 1, 4) 0

18、.000000 42.00000 X( 2, 1) 0.000000 39.00000 X( 2, 2) 0.000000 38.00000 X( 2, 3) 0.000000 26.00000 X( 2, 4) 1.000000 20.00000 X( 3, 1) 0.000000 34.00000 X( 3, 2) 0.000000 27.00000 X( 3, 3) 1.000000 28.00000 X( 3, 4) 0.000000 40.00000 X( 4, 1) 1.000000 24.00000 X( 4, 2) 0.000000 42.00000 X( 4, 3) 0.00

19、0000 36.00000 X( 4, 4) 0.000000 23.00000 Row Slack or Surplus Dual Price 1 101.0000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000由以上兩種方法求解的結(jié)果知：甲負(fù)責(zé)任務(wù)A，乙負(fù)責(zé)任務(wù)C，丙負(fù)責(zé)任務(wù)B，丁負(fù)責(zé)任務(wù)D，可以使總花

20、費(fèi)時(shí)間最少。代入求出目標(biāo)函數(shù)值 。5. 問(wèn)題的深入（0-1整數(shù)規(guī)劃）將約束條件由整數(shù)數(shù)據(jù)變?yōu)樾?shù)數(shù)據(jù)且目標(biāo)函數(shù)由最小值化為最大值問(wèn)題的求解。假設(shè)有4件工作分派給4個(gè)人來(lái)做，每項(xiàng)工作只能由一人來(lái)做，每個(gè)人只能做一項(xiàng)工作。下表為各人對(duì)各項(xiàng)工作所具有的工作效率。問(wèn)應(yīng)該如何安排人選，及發(fā)揮個(gè)人特長(zhǎng)又能使總的效率最大。表3 每個(gè)人完成各項(xiàng)任務(wù)需要的時(shí)間 工人人ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.45.1 模型建立設(shè) 表示第i 個(gè)人被安排做第j項(xiàng)工作，則當(dāng)?shù)趇個(gè)人被安排去做第j項(xiàng)工作時(shí)=1；當(dāng)?shù)趇個(gè)人不被安排到第j項(xiàng)工作時(shí)=0。因此

21、，每個(gè)人只完成一項(xiàng)工作的約束條件為每項(xiàng)工作必有一個(gè)人負(fù)責(zé)的約束條件為 數(shù)學(xué)模型為s.t. 或1，i，j=1，2，3，45.2 模型求解5.2.1 用matlab求解問(wèn)題根據(jù)上面建立的模型，利用matlab進(jìn)行求解，具體程序如下：function y,fval=maxzp(M,C) %M為C中元素的最大值m,n=size(C);C=M+zeros(n)-C; %將求極小值的目標(biāo)函數(shù)系數(shù)矩陣轉(zhuǎn)換成求極大值的系數(shù)矩陣M=1.0;C=C;f=C(:);Aeq=zeros(2*n,n*n);for i=1:nAeq(1:n,1+(i-1)*n:i*n)=eye(n,n);endfor i=1:nAeq(

22、n+i,1+(i-1)*n:i*n)=ones(1,n);endbeq=ones(2*n,1);lb=zeros(n*n,1);ub=ones(n*n,1);x=linprog(f,Aeq,beq,lb,ub);y=reshape(x,n,n);y=y;y=round(y);sol=zeros(n,n);for i=1:nfor j=1:nif y(i,j)=1sol(i,j)=C(j,i);endendendfval=sum(sol(:);fval=M*n-fval; %求出極大值的目標(biāo)函數(shù)值其中，C=0.6 0.2 0.3 0.1 0.7 0.4 0.3 0.2 0.8 1.0 0.7 0

23、.3 0.7 0.7 0.5 0.4; y,fval=maxzp(M,C)輸出結(jié)果為：Optimization terminated.y = 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1fval =2.40005.2.2 用lingo求解問(wèn)題根據(jù)上面建立的模型，利用lingo進(jìn)行求解，具體程序如下：model:sets:ren/1.4/;gongzuo/1.4/;Assign(ren,gongzuo):C,X;endsetsdata:C=0.6 0.2 0.3 0.1 0.7 0.4 0.3 0.2 0.8 1.0 0.7 0.3 0.7 0.7 0.5 0.4;enddat

24、amax=sum(Assign:C*X); ！求目標(biāo)函數(shù)極大值FOR(ren(i):sum(gongzuo(j):X(i,j)=1);FOR(gongzuo(j):sum(ren(i):X(i,j)=1);for(Assign:bin(x);end輸出結(jié)果為：Global optimal solution found.Objective value: 2.400000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced Cost C( 1, 1) 0.6000000 0.000000 C( 1, 2)

25、0.2000000 0.000000 C( 1, 3) 0.3000000 0.000000 C( 1, 4) 0.1000000 0.000000 C( 2, 1) 0.7000000 0.000000 C( 2, 2) 0.4000000 0.000000 C( 2, 3) 0.3000000 0.000000 C( 2, 4) 0.2000000 0.000000 C( 3, 1) 0.8000000 0.000000 C( 3, 2) 1.000000 0.000000 C( 3, 3) 0.7000000 0.000000 C( 3, 4) 0.3000000 0.000000 C(

26、 4, 1) 0.7000000 0.000000 C( 4, 2) 0.7000000 0.000000 C( 4, 3) 0.5000000 0.000000 C( 4, 4) 0.4000000 0.000000 X( 1, 1) 0.000000 -0.6000000 X( 1, 2) 0.000000 -0.2000000 X( 1, 3) 1.000000 -0.3000000 X( 1, 4) 0.000000 -0.1000000 X( 2, 1) 1.000000 -0.7000000 X( 2, 2) 0.000000 -0.4000000 X( 2, 3) 0.000000 -0.3000000 X( 2, 4) 0.000000 -0.2000000 X( 3, 1) 0.000000 -0.8000000 X( 3, 2) 1.000000 -1.000000 X( 3, 3) 0.000000 -0.7000000 X( 3, 4) 0.000000 -0.3000000 X( 4, 1) 0.000000 -0.7000000 X( 4, 2) 0.000000 -0.7000000 X(