數(shù)學(xué)建模,獲獎?wù)撐?工作指派問題

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

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

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

4、，與以只考慮成本時得到的最小成本值為縱坐標(biāo)組成的點。然后我們再求出任意工作安排方案對應(yīng)的效率值與成本值組成的點。最后求出這兩點之間的距離表達式，得到我們要求的目標(biāo)函數(shù)。最后,在與問題一問題二相同的約束條件下，我們采用lingo編程使目標(biāo)函數(shù)逐漸向理想點逼近（但永遠達不到理想點），即：使目標(biāo)函數(shù)達到最小值時，此時對應(yīng)的工作指派方案在問題三情況下是最佳方案。關(guān)鍵詞：0-1規(guī)劃；數(shù)據(jù)標(biāo)準(zhǔn)化；多目標(biāo)規(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建立數(shù)學(xué)模型回答下面的問題：1、 如何安排每個人的工作，使得總的工作效率最大。2、 如何安排每個人的工作，使得總的成本最低。3、 如何兼顧工作效率和成本，優(yōu)化工作安排方案。二、問題分析對于問題一，要安排每個人的工作，使得總的工作效率最大。因為題目中的效率已經(jīng)經(jīng)過量化，所以要想反應(yīng)效率的高低我們也可以通過數(shù)值大

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

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

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

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

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

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

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

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

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

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

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

17、o程序;model: !定義; sets: people/1.6/; work/1.6/; match(people, work): efficient,k; endsets data: efficient= 351002643254142212123331213242325466enddata ! 效率矩陣; ! 目標(biāo)函數(shù)：最大效率和; 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運行結(jié)果如下： 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.

19、000000 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 EFFI

20、CIENT( 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.00000

21、0 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.0

23、00000 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.00000

24、0 -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)

25、 0.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

26、K( 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.000

27、000 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: c

28、ost*k);! 目標(biāo)函數(shù)：總共最低成本; 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程序運行結(jié)果：Global optimal solution found. Objective value: 17.00000 Objective bound: 17.00000 Infeasibilities: 0.000000 Extended solver step

29、s: 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

30、COST( 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

31、COST( 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

32、COST( 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,

33、3) 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.00000