數學建模獲獎論文工作指派問題

1、河南理工大學2014年數學建模競賽論文答卷編號（競賽組委會填寫）：題目編號：（ F ）論文題目： 工作的安排 參賽隊員信息(必填)： 姓 名專業(yè)班級聯(lián)系電話隊員1機制11-5隊員2機制11-5隊員3計算機11-3 答卷編號（競賽組委會填寫）：評閱情況（學校評閱專家填寫）：評閱1.評閱2.評閱3. 工作的安排摘 要：工作指派問題是日常生活中常見的一類問題。本文所要研究就是在效率與成本的背景下，如何安排每個人員的工作分別達到以下三個要求：1、使得總的工作效率最大。2、使得總的成本最低。3、兼顧工作效率和成本，優(yōu)化工作安排方案。對于問題一，該問題屬于工作指派問題，要求使工作效率最大。為了得到最優(yōu)的安

2、排方案，我們采用0-1規(guī)劃模型，引入0-1變量，即其中一人負責某一項工作記作1，否則為0，然后與之對應的效率相乘，然后把所有的工作安排情況這樣處理后，再求和作為目標函數。此外我們對該問題進行了如下約束：因為六個人剛好六份工作，所以每個人只能被安排一份工作，而且每份工作只允許一人來完成。最后在模型求解中我們應用lingo軟件編程使目標函數值最大化，根據此時對應的0-1變量的所有值，最終得到最優(yōu)安排方案。對于問題二，要求的方案使工作成本最低。該問題與問題一相似，只是求解的是目標函數的最小值，為此我們建立了成本最小化模型，該模型同樣應用了0-1規(guī)劃方法，然后用與問題一中相似的方法建立目標函數，然后應

3、用lingo軟件編程使目標函數值最小，最終得到使成本最小的相應安排方案。對于問題三，該問題兼顧效率與成本,屬于多目標規(guī)劃。首先,數據標準化處理。給出的效率成本數據屬于兩個不同性質的指標，兩個指標之間存在著不可公度性，而且兩項的數值整體大小水平不一樣，會有大數起主導作用的影響，如果不對兩個指標的數據進行標準化，就會得到錯誤的結果，為此我們首先采用極值差方法，用matlab編程對兩項指標數據進行標準化。經過極差變換后，兩項指標值均在0和1之間。 對于此問題的多目標規(guī)劃解決，我們采用理想點方法將多目標規(guī)劃轉化為單目標規(guī)劃，建立了偏離理想點距離模型。所謂的理想點就是只考慮效率時得到的最大效率值為橫坐標

4、，與以只考慮成本時得到的最小成本值為縱坐標組成的點。然后我們再求出任意工作安排方案對應的效率值與成本值組成的點。最后求出這兩點之間的距離表達式，得到我們要求的目標函數。最后,在與問題一問題二相同的約束條件下，我們采用lingo編程使目標函數逐漸向理想點逼近（但永遠達不到理想點），即：使目標函數達到最小值時，此時對應的工作指派方案在問題三情況下是最佳方案。關鍵詞：0-1規(guī)劃；數據標準化；多目標規(guī)劃；偏離理想點距離模型；lingo一、問題重述已知有6個人，可以做6項工作，每個人做每項工作的效率和所用的成本如表中所示。表1：每個人做每項工作的效率工作人員工作1工作2工作3工作4工作5工作6人員135

5、1002人員2643254人員3142212人員4123331人員5213242人員6325466表2：每個人做每項工作的成本工作人員工作1工作2工作3工作4工作5工作6人員1481004人員212753119人員32104425人員4255794人員5527474人員6851081113建立數學模型回答下面的問題：1、 如何安排每個人的工作，使得總的工作效率最大。2、 如何安排每個人的工作，使得總的成本最低。3、 如何兼顧工作效率和成本，優(yōu)化工作安排方案。二、問題分析對于問題一，要安排每個人的工作，使得總的工作效率最大。因為題目中的效率已經經過量化，所以要想反應效率的高低我們也可以通過數值大

6、小來反應工作安排后的效率高低。然而每個人的工作安排有很多種情況，為了簡化問題，采用0-1規(guī)劃模型，引入0-1變量，我們把其中一個人負責某項工作記作1，否則記作0，然后我們便可以把每個人工作安排的所有情況的效率與相應的0-1變量乘積的求和，便得到效率目標函數，而且考慮到lingo軟件的強大優(yōu)化求解能力，于是便可以借助lingo編程來求解實現目標函數的最大化，即工作效率綜合的最大化，根據此時對應的0-1變量的所有值得到的工作安排方案就是最佳的。對于問題二，要求安排每個人的工作，使得總的成本最低，該問題與問題一相似，同樣可以應用0-1規(guī)劃模型，求出目標函數表達式然后應用lingo軟件編程來求解目標函

7、數的最小值，便可得到最優(yōu)工作分派方案。問題三，要兼顧效率與成本這兩個指標，即讓效率盡量最大的同時讓成本也最小，來得到最優(yōu)的分派方案。由于兩個指標的性質不同，同時整體大小水平不一，所以第一步需要進行數據標準化，標準化方法有很多種，這里我們采用極值差方法對兩項指標進行處理，經過極差變換后，兩項指標值均在0和1之間。數據標準化處理處理后，要兼顧效率與成本，則效率和成本就都會偏離問題一、問題二中的最優(yōu)值，如果所給的工作安排方案能使兩者距各自最優(yōu)值的偏移量最小化則就意味著效率和成本都得到了兼顧，而且相對最優(yōu)。為此，我們便引入了理想點法，讓任意安排方案得到的效率值與成本值組成的點距離理想點的距離最小化，而

8、得到最小值對應的工作分配方案，此過程的求解我們同樣可以借助lingo軟件編程來解決，最終能夠實現問題三的要求。三、問題假設1.所有人對每個工作的效率與成本是定值，即不受外界影響；2.所有人都服從相應的安排；3.效率和成本重要程度相同；4只考慮成本與效率兩個指標。四、符號說明:表示第人做第個工作的相應效率表示第人是否負責第個工作，如果負責記為1，否則為0；：表示只考慮效率時所有人的工作效率之和；：表示第人做第個工作的需要的成本；：表示只考慮成本時所有人工作所需成本之和；：表示標準化后的；：表示標準化后的：表示標準化后理想點。其中表示只考慮效率指標時，效率的最大值。 表示只考慮成本時，成本的最小值

9、。：表示任意工作方案對應的坐標。其中表示任意一種工作分配方案得到的效率值，表示任意一種工作分配方案得到的成本值；：表示與的距離：五、模型的建立與求解5.1問題一的模型建立與求解模型的建立首先我們根據題目建立效率矩陣表示第人做第個工作的效率。然后我們建立反應第人是否負責第個工作的0-1變量 由題目可知，六個人負責六項工作，所以每個人只能負責一項工作，而且每個工作只能由一個人來完成。于是便有下面的約束條件: 且則目標函數為總的效率表達式如下：綜上便可得到最終效率模型如下: 51.2 模型求解這是一個0-1優(yōu)化問題，lingo軟件具有強大的優(yōu)化問題解決能力，所以我們通過lingo軟件編程求解出最佳分

10、配方案，根據程序運行結果我們最終得到的最優(yōu)分配方案如下：（lingo程序見附錄，運算結果見附錄）：人員1人員2人員3人員4人員5人員6工作分配方案214356表1 最大效率工作分配方案而且此時的最大效率值為26。5.2問題二的模型建立與求解5.2.1成本最小化模型的建立由題目中給定的成本數據我們建立成本矩陣具體如下：同樣有反應第人是否做第個工作的0-1變量 而且六個人負責六項工作，所以每個人只能負責一項工作，而且每個工作只能由一個人來完成。于是便有下面的約束條件： 且則最終得到只考慮成本總成本的目標函數如下：于是得到完整的成本最小化模型如下： 5.2.2、模型的求解與問題一類似的解法，應用li

11、ngo軟件編程求解使目標函數值最小（即：使成本最?。└鶕绦蜻\行結果（程序及運行結果見附錄，），我們得到的最佳分配方案如下：人員1人員2人員3人員4人員5人員6工作分配方案345162表2 最低成本分配工作方式5.3問題三的模型建立與求解5.3.1多目標規(guī)劃模型的建立第一步：進行數據標準化。由于該問題要求兼顧效率與成本，而這兩項指標卻不是同性質的，而且成本數據都偏大一些，為了防止成本數據影響最終結果，需要對兩項數據進行標準化，標準化方法有很多種，這里我們采用極值差方法對兩項指標進行處理。具體如下： 首先對用極值差方法進行標準化后得:通過matlab編程我們可以得到矩陣,此時矩陣的值均在0和1之

12、間，最優(yōu)值為1，最劣值為0。然后對指標數據矩陣用極值差法標準化后得到:同樣可以用matlab編程得到矩陣且值均在0和1之間和 matlab標準化程序及結果見附錄。第二步：多目標規(guī)劃模型的建立由第一問及第二問的基礎我們可以得出兩個規(guī)劃目標函數如下：首先，有總效率的目標函數： 其中表示任意一種工作分配方案得到的效率值。同時有總成本的目標函數: 其中表示任意一種工作分配方案得到的成本值。于是，多目標函數規(guī)劃模型建立如下： 5.3.2多目標規(guī)劃轉化為單目標規(guī)劃模型由于以上所建的多目標規(guī)劃模型問題求解過于復雜，為了簡化問題，我們采用了理想點法，求出任意工作分配方案的效率與成本偏離理想點的距離的目標函數表

13、達式，然后使目標函數表達式的值逼近最小，此時對應的方案就是在兼顧效率與成本的前提下的最優(yōu)工作分配方案，具體步驟如下：第一步：設標準化后理想點。其中表示只考慮效率指標時，效率的最大值。表示只考慮成本時，成本的最小值。、求解可以借助問題一、二中的程序只是將其中的效率，成本中的數據替換成標準化后的和中的數據。、，即理想點為。第二步：求點與理想點之間距離的表達式。其中表示任意一種工作分配方案得到的效率值，表示任意一種工作分配方案得到的成本值。則與的距離表達式如下： （3）然后將多目標規(guī)劃模型中德(1)、（2）式代入（3）式得到最終表達式.第三步：最終單目標規(guī)劃模型建立。六個人負責六項工作，所以每個人只

14、能負責一項工作，而且每個工作只能由一個人來完成。于是便有下面的約束條件如下： 且綜上所述，可以得到偏離理想點距離模型如下： 5.3.3 模型的求解 此模型的求解主要借助lingo編程，使目標函數值逐漸逼近理想點，但達到理想點是不可能的，只需達到目標函數最小值，即最接近理想點的點就是兼顧成本與效率的最佳工作分配方案，此時效率與成本都達到了最優(yōu)。根據程序運行結果，最佳工作分配方案如下（求解模型的lingo程序及運行結果見附錄）：人員1人員2人員3人員4人員5人員6工作分配方案241365表3 兼顧成本與效率下時最優(yōu)工作分配方案此時的最小值為1.695967六、模型的評價與推廣6.1模型的優(yōu)點1、本

15、題中的模型都是有簡單到復雜一步步建立，文章整體邏輯性強，可讀性強。2、對于問題一二的解決中我們應用了0-1規(guī)劃模型大大降低了問題的難度，使目標函數成為求和的形式，便于計算。同時我們應用lingo這一軟件大大減小了解決0-1規(guī)劃模型的計算。 3、問題三中，我們使數據都標準化這樣使得數據才有衡量的標準，防止了因為成本原始數據較大兒在最終結果中起主導影響，此外，我們應用理想點法把多目標規(guī)劃轉化為單目標規(guī)劃使問題得以簡化，同時使用距離這一概念使模型簡單易于理解而且有益于編程計算。 6.2模型的缺點首先就是該模型不能解決當效率與成本的重要性不同時得工作指派問題（即在效率與成本的權重不同時），比如有時決策

16、者希望七成考慮效率，三成考慮成本的情況。而我們的模型只考慮了成本與效率整體下的最優(yōu)解。6.3 模型的推廣如果數據能進一步符合工人的真實情況，那么該模型可以在一定程度上幫助決策者做出最佳的決定。還有其他一些類似的優(yōu)化問題，比如路徑最短問題，原料分配等一些生活中的實際問題中。七、參考文獻1陳東彥，劉鳳秋著，數學建模，北京：科學出版社 ，2013。2蘇金明，阮沈勇著，MATLAB實用教程，北京：電子工業(yè)出版社，2008。3趙東方，數學模型與計算，河北：科學出版社，2007。4穆學文，多目標規(guī)劃，2014.5.30。5謝金星,LINGO優(yōu)化軟件，l, 。附錄問題一 !求解最大效率分配方式的lingo程

17、序;model: !定義; sets: people/1.6/; work/1.6/; match(people, work): efficient,k; endsets data: efficient= 351002643254142212123331213242325466enddata ! 效率矩陣; ! 目標函數：最大效率和; max = sum(match: efficient*k); for(people(i): sum(work(j): k(i,j)=1); ! m每個人都有且只有一份工作; for(work(j): sum(people(i): k(i,j)=1); !每個工作

18、有且只有一個人做; for(match:bin(k); !變量k(i,j)為0-1變量；end運行結果如下： Global optimal solution found. Objective value: 26.00000 Objective bound: 26.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost EFFICIENT( 1, 1) 3.000000 0.000000 EFFICIENT( 1, 2) 5.00

19、0000 0.000000 EFFICIENT( 1, 3) 1.000000 0.000000 EFFICIENT( 1, 4) 0.000000 0.000000 EFFICIENT( 1, 5) 0.000000 0.000000 EFFICIENT( 1, 6) 2.000000 0.000000 EFFICIENT( 2, 1) 6.000000 0.000000 EFFICIENT( 2, 2) 4.000000 0.000000 EFFICIENT( 2, 3) 3.000000 0.000000 EFFICIENT( 2, 4) 2.000000 0.000000 EFFICI

20、ENT( 2, 5) 5.000000 0.000000 EFFICIENT( 2, 6) 4.000000 0.000000 EFFICIENT( 3, 1) 1.000000 0.000000 EFFICIENT( 3, 2) 4.000000 0.000000 EFFICIENT( 3, 3) 2.000000 0.000000 EFFICIENT( 3, 4) 2.000000 0.000000 EFFICIENT( 3, 5) 1.000000 0.000000 EFFICIENT( 3, 6) 2.000000 0.000000 EFFICIENT( 4, 1) 1.000000

21、0.000000 EFFICIENT( 4, 2) 2.000000 0.000000 EFFICIENT( 4, 3) 3.000000 0.000000 EFFICIENT( 4, 4) 3.000000 0.000000 EFFICIENT( 4, 5) 3.000000 0.000000 EFFICIENT( 4, 6) 1.000000 0.000000 EFFICIENT( 5, 1) 2.000000 0.000000 EFFICIENT( 5, 2) 1.000000 0.000000 EFFICIENT( 5, 3) 3.000000 0.000000 EFFICIENT(

22、5, 4) 2.000000 0.000000 EFFICIENT( 5, 5) 4.000000 0.000000 EFFICIENT( 5, 6) 2.000000 0.000000 EFFICIENT( 6, 1) 3.000000 0.000000 EFFICIENT( 6, 2) 2.000000 0.000000 EFFICIENT( 6, 3) 5.000000 0.000000 EFFICIENT( 6, 4) 4.000000 0.000000 EFFICIENT( 6, 5) 6.000000 0.000000 EFFICIENT( 6, 6) 6.000000 0.000

23、000 K( 1, 1) 0.000000 -3.000000 K( 1, 2) 1.000000 -5.000000 K( 1, 3) 0.000000 -1.000000 K( 1, 4) 0.000000 0.000000 K( 1, 5) 0.000000 0.000000 K( 1, 6) 0.000000 -2.000000 K( 2, 1) 1.000000 -6.000000 K( 2, 2) 0.000000 -4.000000 K( 2, 3) 0.000000 -3.000000 K( 2, 4) 0.000000 -2.000000 K( 2, 5) 0.000000

24、-5.000000 K( 2, 6) 0.000000 -4.000000 K( 3, 1) 0.000000 -1.000000 K( 3, 2) 0.000000 -4.000000 K( 3, 3) 0.000000 -2.000000 K( 3, 4) 1.000000 -2.000000 K( 3, 5) 0.000000 -1.000000 K( 3, 6) 0.000000 -2.000000 K( 4, 1) 0.000000 -1.000000 K( 4, 2) 0.000000 -2.000000 K( 4, 3) 1.000000 -3.000000 K( 4, 4) 0

25、.000000 -3.000000 K( 4, 5) 0.000000 -3.000000 K( 4, 6) 0.000000 -1.000000 K( 5, 1) 0.000000 -2.000000 K( 5, 2) 0.000000 -1.000000 K( 5, 3) 0.000000 -3.000000 K( 5, 4) 0.000000 -2.000000 K( 5, 5) 1.000000 -4.000000 K( 5, 6) 0.000000 -2.000000 K( 6, 1) 0.000000 -3.000000 K( 6, 2) 0.000000 -2.000000 K(

26、 6, 3) 0.000000 -5.000000 K( 6, 4) 0.000000 -4.000000 K( 6, 5) 0.000000 -6.000000 K( 6, 6) 1.000000 -6.000000 Row Slack or Surplus Dual Price 1 26.00000 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.00000

27、0 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000-問題二 -!求解最低成本分配方式的lingo程序;model: !定義; sets: people/1.6/; work/1.6/; match(people, work): cost,k; endsets data: cost= 481004127531192104425255794527474851081113enddata ! 成本矩陣; min = sum(match: cos

28、t*k);! 目標函數：總共最低成本; for(people(i): sum(work(j): k(i,j)=1); ! m每個人都有且只有一份工作; for(work(j): sum(people(i): k(i,j)=1); !每個工作有且只有一個人做; for(match:bin(k); !變量k為0-1變量；end程序運行結果：Global optimal solution found. Objective value: 17.00000 Objective bound: 17.00000 Infeasibilities: 0.000000 Extended solver steps:

29、 0 Total solver iterations: 0 Variable Value Reduced Cost COST( 1, 1) 4.000000 0.000000 COST( 1, 2) 8.000000 0.000000 COST( 1, 3) 1.000000 0.000000 COST( 1, 4) 0.000000 0.000000 COST( 1, 5) 0.000000 0.000000 COST( 1, 6) 4.000000 0.000000 COST( 2, 1) 12.00000 0.000000 COST( 2, 2) 7.000000 0.000000 CO

30、ST( 2, 3) 5.000000 0.000000 COST( 2, 4) 3.000000 0.000000 COST( 2, 5) 11.00000 0.000000 COST( 2, 6) 9.000000 0.000000 COST( 3, 1) 2.000000 0.000000 COST( 3, 2) 10.00000 0.000000 COST( 3, 3) 4.000000 0.000000 COST( 3, 4) 4.000000 0.000000 COST( 3, 5) 2.000000 0.000000 COST( 3, 6) 5.000000 0.000000 CO

31、ST( 4, 1) 2.000000 0.000000 COST( 4, 2) 5.000000 0.000000 COST( 4, 3) 5.000000 0.000000 COST( 4, 4) 7.000000 0.000000 COST( 4, 5) 9.000000 0.000000 COST( 4, 6) 4.000000 0.000000 COST( 5, 1) 5.000000 0.000000 COST( 5, 2) 2.000000 0.000000 COST( 5, 3) 7.000000 0.000000 COST( 5, 4) 4.000000 0.000000 CO

32、ST( 5, 5) 7.000000 0.000000 COST( 5, 6) 4.000000 0.000000 COST( 6, 1) 8.000000 0.000000 COST( 6, 2) 5.000000 0.000000 COST( 6, 3) 10.00000 0.000000 COST( 6, 4) 8.000000 0.000000 COST( 6, 5) 11.00000 0.000000 COST( 6, 6) 13.00000 0.000000 K( 1, 1) 0.000000 4.000000 K( 1, 2) 0.000000 8.000000 K( 1, 3)

33、 1.000000 1.000000 K( 1, 4) 0.000000 0.000000 K( 1, 5) 0.000000 0.000000 K( 1, 6) 0.000000 4.000000 K( 2, 1) 0.000000 12.00000 K( 2, 2) 0.000000 7.000000 K( 2, 3) 0.000000 5.000000 K( 2, 4) 1.000000 3.000000 K( 2, 5) 0.000000 11.00000 K( 2, 6) 0.000000 9.000000 K( 3, 1) 0.000000 2.000000 K( 3, 2) 0.000000 10.00000 K( 3, 3) 0.000000 4.000000 K( 3, 4) 0.000000 4.000000 K( 3, 5) 1.000000 2.00