指派問題的算法分析與實現(xiàn)

1、 編號： 20 運(yùn) 籌 學(xué) 基 礎(chǔ)課 程 設(shè) 計題 目：指派問題的算法分析與實現(xiàn)院 系： 專 業(yè)： 姓名學(xué)號： 指導(dǎo)教師： 日 期： 2011 年 1 月 15 日摘 要在企業(yè)、公司的運(yùn)營與管理中，管理者總是希望把人員最佳分派以發(fā)揮其最大工作效率，從而降低成本、提高效益。然而，如果沒有科學(xué)的方法是很難實現(xiàn)優(yōu)化管理的，由此我們引入了指派問題。指派問題多是求項目的工時最少，而很多情況下人們并不關(guān)心項目總工時的多少，而只關(guān)心項目能否在最短的時間內(nèi)完成，即歷時最少的指派問題。這類問題研究的是n個人執(zhí)行n項任務(wù)，執(zhí)行每項任務(wù)的人數(shù)以及總的指派人項數(shù)均有限制，要求最優(yōu)指派。在運(yùn)籌學(xué)中求解整數(shù)規(guī)劃的指派問題

2、通常是通過匈牙利算法來求解，但指派問題也可以歸結(jié)為一個0-1整數(shù)規(guī)劃問題，本文先對指派問題進(jìn)行陳述，引出對實際問題的求解。在指派問題的背景、描述中充分理解該問題，先運(yùn)用匈牙利算法實現(xiàn)指派問題，然后再建立一個0-1整數(shù)規(guī)劃模型，并運(yùn)用matlab和lingo編譯程序?qū)栴}進(jìn)行編譯，運(yùn)用軟件解決模型問題，最終實現(xiàn)指派問題在實際問題中的運(yùn)用。通過運(yùn)用匈牙利算法和0-1整數(shù)規(guī)劃同時對指派問題求解，我們發(fā)現(xiàn)用0-1整數(shù)規(guī)劃的方法來求解可以更簡單，也更方便程序的閱讀和理解。與此同時，我們還對0-1整數(shù)規(guī)劃問題由整數(shù)數(shù)據(jù)深入研究到小數(shù)數(shù)據(jù)。最后通過實例來說明運(yùn)用matlab，lingo編譯程序來解決整數(shù)規(guī)劃

3、問題的簡便和有效性。關(guān)鍵詞：指派問題；匈牙利算法；0-1整數(shù)規(guī)劃；matlab模型；lingo模型abstractin business, the company's operations and management, managers always want the best distribution of the staff to maximize their efficiency, reduce costs and improve efficiency. however, if there is no scientific method is difficult to achi

4、eve optimal management, which we introduced the assignment problem. multi-assignment problem is to get the project working hours at least, and in many cases people do not care about how much the total project work, but only care about whether the project can be completed within the shortest possible

5、 time, that lasted for at least the assignment problem. such problems is the n individual execution of tasks n, the number of people to perform each task and assign the total number of items are restricted to two people, requiring the optimal assignment. integer programming in operations research fo

6、r solving the assignment problem is usually solved by hungarian algorithm, but the assignment problem can be reduced to a 0-1 integer programming problem, this paper first to make a statement on the assignment problem, leads to the solution of practical problems. assignment problem in the background

7、 to fully understand the problem description, the first assignment problem using hungarian algorithm, and then a 0-1 integer programming model and compiler using matlab and the lingo of the problem to be compiled using the software solution model problem ultimately in the assignment of the applicati

8、on in practical problems. by using the hungarian algorithm and the 0-1 integer programming to solve assignment problems simultaneously, we found that 0-1 integer programming method to solve a more simple and easier to read and understand the program. at the same time, we also 0-1 integer programming

9、 problem in-depth study by the integer data to a decimal data. finally, an example to illustrate the use of matlab, lingo compiler to solve the integer programming problem is simple and effective.keywords: assignment problem; hungarian algorithm; 0-1 integer programming; matlab model; lingo model目錄1

10、. 問題陳述12. 指派問題的背景13. 指派問題的描述13.1 指派問題的一般形式13.2 問題的數(shù)學(xué)模型一般形式23.3 目標(biāo)函數(shù)極大化的指派問題24指派問題實現(xiàn)34.1 匈牙利算法34.1.1 匈牙利算法的理論基礎(chǔ)34.1.2 匈牙利算法的實現(xiàn)步驟34.1.3 匈牙利算法實現(xiàn)指派問題44.2 0-1整數(shù)規(guī)劃54.2.1 模型假設(shè)54.2.2 模型建立64.2.3 模型求解75. 問題的深入（0-1整數(shù)規(guī)劃）105.1 模型建立105.2 模型求解115.2.1 用matlab求解問題115.2.2 用lingo求解問題126. 結(jié)論146.1 總結(jié)概論146.2 具體分工146.3 個人

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

12、blem）。例如，在生產(chǎn)管理中，總希望把人員進(jìn)行最佳分配，以發(fā)揮最大的工作效率；某部門有n項任務(wù)要完成，而該部門正好有n個人可以分別去完成其中任何一項，但由于任務(wù)性質(zhì)和個人的專長不同，因此各人完成各項不同任務(wù)的效益（所費(fèi)時間或所花費(fèi)用）也有差別，如果分配每個人完成一項任務(wù)且僅為一項任務(wù)，則把每項任務(wù)分配給哪個人去完成，使完成所有n項任務(wù)的總效益為最高（總時間、總費(fèi)用為最小或創(chuàng)造的價值最大）？這是典型的分配問題或指派問題。又如有n項加工任務(wù)，怎樣指定n臺機(jī)器分別去完成，以使總的加工時間最少或總收入最大；有n條航線，怎樣指定n艘船分別航行，使總收入最大，等等，都屬于指派問題。3. 指派問題的描述3

13、.1 指派問題的一般形式指派問題的標(biāo)準(zhǔn)形式（以人和事為例）如下。有n個人和n項任務(wù)，已知第i個人做第j件事的費(fèi)用為，要求確定人和事之間的一一對應(yīng)的指派方案，使完成這n項任務(wù)的費(fèi)用最少。一般把目標(biāo)函數(shù)的系數(shù)寫為矩陣形式，稱矩陣為系數(shù)矩陣（coefficient matrix），也稱為效益矩陣或價值矩陣。矩陣的元素（i,j=1,2,n）表示分配第i個人去完成第j項任務(wù)時的效益。一般地，以表示給定的資源分配用于給定活動時的有關(guān)效益（時間，費(fèi)用，價值等），且3.2 問題的數(shù)學(xué)模型一般形式在模型中，約束條件式（2）表示每個人只能做一件事，約束條件式（3）表示每件事只能由一個人去做。對于問題的每個可行解，

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

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

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

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

18、840丁24423623用匈牙利算法求解過程如下： min -1 -1 -1 -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)時間最少。代入求出目標(biāo)函數(shù)值z=25+26+27+23=101。4.2 0-1整數(shù)規(guī)劃0-1規(guī)劃（0-1 programming）一種特殊形式的整數(shù)規(guī)劃 。這種規(guī)劃的決策變量僅取值0或1，故稱為0-1變量或二進(jìn)制變量 ，因為一個非負(fù)整數(shù)都可以用二進(jìn)制記 數(shù)法用若干個0-1變量表示 。0-1變量可以數(shù)量化地描述諸如開與關(guān)、取與棄、有與無等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及互

19、斥的約束條件 ，因此0-1規(guī)劃非常適合描述和解決如線路設(shè)計 、工廠選址 、生產(chǎn)計劃安排、旅行購物、背包問題、人員安排、代碼選取、可靠性等人們所關(guān)心的多種問題。實際上，凡是有界變量的整數(shù)規(guī)劃都可以轉(zhuǎn)化為0-1規(guī)劃來處理。當(dāng)然也包括運(yùn)籌學(xué)中的指派問題。4.2.1 模型假設(shè)為了便于對模型進(jìn)行求解與分析，假設(shè)有4件事4個人去做，各變量對應(yīng)的數(shù)據(jù)假設(shè)如表1。表1 每個人完成各項任務(wù)需要的時間人任務(wù)abcd甲25293142乙39382620丙34272840丁24423623表2 變量假設(shè)i第i個人j第j項任務(wù)第i個人分配第j項任務(wù)=1第i個人被分配去做第j項任務(wù)=0第i個人不被分配到第j項任務(wù)4.2.

20、2 模型建立根據(jù)前面的假設(shè)，因此，每個人只完成一項任務(wù)的約束條件為：每項任務(wù)必有一個人負(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)

21、=eye(n,n); %eye表示生成n階單位陣endfor i=1:naeq(n+i,1+(i-1)*n:i*n)=ones(1,n); %生成1行n列元素為1的向量endbeq=ones(2*n,1); %生成2*n行1列元素為1的等式約束右端項lb=zeros(n*n,1); %生成n*n行1列元素為0的不等式約束左端項ub=ones(n*n,1); %生成n*n行1列元素為1的不等式約束右端項x=linprog(f,aeq,beq,lb,ub); %求目標(biāo)函數(shù)達(dá)到極小值的x值y=reshape(x,n,n); %將上式求出的x值組成的向量變成n階矩陣y=y'y=round(y)

22、; %對y中的元素取整，生成匹配矩陣sol=zeros(n,n);for i=1:nfor j=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ù)

23、，利用lingo軟件編程求解，具體程序如下：model:sets:ren/1.4/;renwu/1.4/;assign(ren,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)行

24、結(jié)果為：global optimal solution found. objective value: 101.0000 extended 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.0000

25、00 c( 2, 3) 26.00000 0.000000 c( 2, 4) 20.00000 0.000000 c( 3, 1) 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

26、x( 1, 2) 1.000000 29.00000 x( 1, 3) 0.000000 31.00000 x( 1, 4) 0.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(

27、4, 1) 1.000000 24.00000 x( 4, 2) 0.000000 42.00000 x( 4, 3) 0.000000 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

28、0.000000 0.000000由以上兩種方法求解的結(jié)果知：甲負(fù)責(zé)任務(wù)a，乙負(fù)責(zé)任務(wù)c，丙負(fù)責(zé)任務(wù)b，丁負(fù)責(zé)任務(wù)d，可以使總花費(fèi)時間最少。代入求出目標(biāo)函數(shù)值 。5. 問題的深入（0-1整數(shù)規(guī)劃）將約束條件由整數(shù)數(shù)據(jù)變?yōu)樾?shù)數(shù)據(jù)且目標(biāo)函數(shù)由最小值化為最大值問題的求解。假設(shè)有4件工作分派給4個人來做，每項工作只能由一人來做，每個人只能做一項工作。下表為各人對各項工作所具有的工作效率。問應(yīng)該如何安排人選，及發(fā)揮個人特長又能使總的效率最大。表3 每個人完成各項任務(wù)需要的時間 工人人abcd甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.45.1

29、模型建立設(shè) 表示第i 個人被安排做第j項工作，則當(dāng)?shù)趇個人被安排去做第j項工作時=1；當(dāng)?shù)趇個人不被安排到第j項工作時=0。因此，每個人只完成一項工作的約束條件為每項工作必有一個人負(fù)責(zé)的約束條件為 數(shù)學(xué)模型為s.t. 或1，i，j=1，2，3，45.2 模型求解5.2.1 用matlab求解問題根據(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=zero

30、s(2*n,n*n);for i=1:naeq(1:n,1+(i-1)*n:i*n)=eye(n,n);endfor i=1:naeq(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=

31、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.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求解問題根據(jù)上面建立的模型，利用lingo進(jìn)行求解，具體程序如下：model:sets:ren/1.4/;gongzuo/1.4/;assign(ren,gongzuo):c,x;ends

32、etsdata: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;enddatamax=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 solve

33、r iterations: 0variable value reduced cost c( 1, 1) 0.6000000 0.000000 c( 1, 2) 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,

34、 2) 1.000000 0.000000 c( 3, 3) 0.7000000 0.000000 c( 3, 4) 0.3000000 0.000000 c( 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.