【正文】 南理工大學(xué)2014年數(shù)學(xué)建模競賽論文答卷編號（競賽組委會填寫）：題目編號：（ F ）論文題目： 工作的安排 參賽隊員信息(必填)： 姓 名專業(yè)班級聯(lián)系電話隊員1機(jī)制115隊員2機(jī)制115隊員3計算機(jī)113 答卷編號（競賽組委會填寫）：評閱情況（學(xué)校評閱專家填寫）：評閱1.評閱2.評閱3. 工作的安排摘 要：工作指派問題是日常生活中常見的一類問題。本文所要研究就是在效率與成本的背景下，如何安排每個人員的工作分別達(dá)到以下三個要求：使得總的工作效率最大。兼顧工作效率和成本，優(yōu)化工作安排方案。為了得到最優(yōu)的安排方案，我們采用01規(guī)劃模型，引入01變量，即其中一人負(fù)責(zé)某一項工作記作1，否則為0，然后與之對應(yīng)的效率相乘，然后把所有的工作安排情況這樣處理后，再求和作為目標(biāo)函數(shù)。最后在模型求解中我們應(yīng)用lingo軟件編程使目標(biāo)函數(shù)值最大化，根據(jù)此時對應(yīng)的01變量的所有值，最終得到最優(yōu)安排方案。該問題與問題一相似，只是求解的是目標(biāo)函數(shù)的最小值，為此我們建立了成本最小化模型，該模型同樣應(yīng)用了01規(guī)劃方法，然后用與問題一中相似的方法建立目標(biāo)函數(shù)，然后應(yīng)用lingo軟件編程使目標(biāo)函數(shù)值最小，最終得到使成本最小的相應(yīng)安排方案。首先,數(shù)據(jù)標(biāo)準(zhǔn)化處理。經(jīng)過極差變換后，兩項指標(biāo)值均在0和1之間。所謂的理想點(diǎn)就是只考慮效率時得到的最大效率值為橫坐標(biāo)，與以只考慮成本時得到的最小成本值為縱坐標(biāo)組成的點(diǎn)。最后求出這兩點(diǎn)之間的距離表達(dá)式，得到我們要求的目標(biāo)函數(shù)。關(guān)鍵詞：01規(guī)劃；數(shù)據(jù)標(biāo)準(zhǔn)化；多目標(biāo)規(guī)劃；偏離理想點(diǎn)距離模型；lingo一、問題重述已知有6個人，可以做6項工作，每個人做每項工作的效率和所用的成本如表中所示。 如何安排每個人的工作，使得總的成本最低。二、問題分析對于問題一，要安排每個人的工作，使得總的工作效率最大。然而每個人的工作安排有很多種情況，為了簡化問題，采用01規(guī)劃模型，引入01變量，我們把其中一個人負(fù)責(zé)某項工作記作1，否則記作0，然后我們便可以把每個人工作安排的所有情況的效率與相應(yīng)的01變量乘積的求和，便得到效率目標(biāo)函數(shù)，而且考慮到lingo軟件的強(qiáng)大優(yōu)化求解能力，于是便可以借助lingo編程來求解實現(xiàn)目標(biāo)函數(shù)的最大化，即工作效率綜合的最大化，根據(jù)此時對應(yīng)的01變量的所有值得到的工作安排方案就是最佳的。問題三，要兼顧效率與成本這兩個指標(biāo)，即讓效率盡量最大的同時讓成本也最小，來得到最優(yōu)的分派方案。數(shù)據(jù)標(biāo)準(zhǔn)化處理處理后，要兼顧效率與成本，則效率和成本就都會偏離問題一、問題二中的最優(yōu)值，如果所給的工作安排方案能使兩者距各自最優(yōu)值的偏移量最小化則就意味著效率和成本都得到了兼顧，而且相對最優(yōu)。三、問題假設(shè)，即不受外界影響；；；4．只考慮成本與效率兩個指標(biāo)。其中表示只考慮效率指標(biāo)時，效率的最大值。：表示任意工作方案對應(yīng)的坐標(biāo)。然后我們建立反應(yīng)第人是否負(fù)責(zé)第個工作的01變量 由題目可知，六個人負(fù)責(zé)六項工作，所以每個人只能負(fù)責(zé)一項工作，而且每個工作只能由一個人來完成。由題目中給定的成本數(shù)據(jù)我們建立成本矩陣具體如下：同樣有反應(yīng)第人是否做第個工作的01變量 而且六個人負(fù)責(zé)六項工作，所以每個人只能負(fù)責(zé)一項工作，而且每個工作只能由一個人來完成。由于該問題要求兼顧效率與成本，而這兩項指標(biāo)卻不是同性質(zhì)的，而且成本數(shù)據(jù)都偏大一些，為了防止成本數(shù)據(jù)影響最終結(jié)果，需要對兩項數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化，標(biāo)準(zhǔn)化方法有很多種，這里我們采用極值差方法對兩項指標(biāo)進(jìn)行處理。然后對指標(biāo)數(shù)據(jù)矩陣用極值差法標(biāo)準(zhǔn)化后得到:同樣可以用matlab編程得到矩陣且值均在0和1之間和 matlab標(biāo)準(zhǔn)化程序及結(jié)果見附錄。同時有總成本的目標(biāo)函數(shù): 其中表示任意一種工作分配方案得到的成本值。其中表示只考慮效率指標(biāo)時，效率的最大值。、求解可以借助問題一、二中的程序只是將其中的效率，成本中的數(shù)據(jù)替換成標(biāo)準(zhǔn)化后的和中的數(shù)據(jù)。第二步：求點(diǎn)與理想點(diǎn)之間距離的表達(dá)式。則與的距離表達(dá)式如下： （3）然后將多目標(biāo)規(guī)劃模型中德(1)、（2）式代入（3）式得到最終表達(dá)式.第三步：最終單目標(biāo)規(guī)劃模型建立。于是便有下面的約束條件如下： 且綜上所述，可以得到偏離理想點(diǎn)距離模型如下： 模型的求解 此模型的求解主要借助lingo編程，使目標(biāo)函數(shù)值逐漸逼近理想點(diǎn)，但達(dá)到理想點(diǎn)是不可能的，只需達(dá)到目標(biāo)函數(shù)最小值，即最接近理想點(diǎn)的點(diǎn)就是兼顧成本與效率的最佳工作分配方案，此時效率與成本都達(dá)到了最優(yōu)。對于問題一二的解決中我們應(yīng)用了01規(guī)劃模型大大降低了問題的難度，使目標(biāo)函數(shù)成為求和的形式，便于計算。 問題三中，我們使數(shù)據(jù)都標(biāo)準(zhǔn)化這樣使得數(shù)據(jù)才有衡量的標(biāo)準(zhǔn)，防止了因為成本原始數(shù)據(jù)較大兒在最終結(jié)果中起主導(dǎo)影響，此外，我們應(yīng)用理想點(diǎn)法把多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃使問題得以簡化，同時使用距離這一概念使模型簡單易于理解而且有益于編程計算。而我們的模型只考慮了成本與效率整體下的最優(yōu)解。還有其他一些類似的優(yōu)化問題，比如路徑最短問題，原料分配等一些生活中的實際問題中。[2]蘇金明，阮沈勇著，MATLAB實用教程，北京：電子工業(yè)出版社，2008。[4]穆學(xué)文，多目標(biāo)規(guī)劃。附錄問題一 !求解最大效率分配方式的lingo程序。 sets: people/1..6/。 match(people, work): efficient,k。 ! 目標(biāo)函數(shù)：最大效率和。 for(people(i): sum(work(j): k(i,j))=1)。 for(work(j): sum(people(i): k(i,j))=1)。 for(match:bin(k))。model: !定義。 work/1..6/。 endsets data: cost= 481004127531192104425255794527474851081113enddata ! 成本矩陣。! 目標(biāo)函數(shù)：總共最低成本。 ! m每個人都有且只有一份工作。 !每個工作有且只有一個人做。 !變量k為01變量；end程序運(yùn)行結(jié)果：Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost COST( 1, 1) COST( 1, 2) COST( 1, 3) COST( 1, 4) COST( 1, 5) COST( 1, 6) COST( 2, 1) COST( 2, 2) COST( 2, 3) COST( 2, 4) COST( 2, 5) COST( 2, 6) COST( 3, 1) COST( 3, 2) COST( 3, 3) COST( 3, 4) COST( 3, 5) COST( 3, 6) COST( 4, 1) COST( 4, 2) COST( 4, 3) COST( 4, 4) COST( 4, 5) COST( 4, 6) COST( 5, 1) COST( 5, 2)