建筑工地人員規(guī)劃問題111

1、建筑工地人員規(guī)劃問題摘要本文針對建筑工地上為使結構安裝總成本最低，而涉及的結構安裝工的人員規(guī)劃問題，采用了數(shù)學建模中的純整數(shù)線性規(guī)劃（PILP）的相關知識，以及符號無限制變量的轉(zhuǎn)化方法進行建模并采用單純形法及分支界定法（此步由Lingo軟件執(zhí)行）進行計算得出了在題中所要求的四種情況下，各自所需的最小成本以及在最小成本的條件下各月人員的借調(diào)，離開，多余和缺少人人數(shù)等結果。在第一個問題中根據(jù)所建模型經(jīng)過Lingo軟件計算得到的人員規(guī)劃結果為：三月，四月，五月分別借調(diào)1,2,1名工人，其余月份不借調(diào)，五月，七月，八月月末時分別離開2,1，1名工人，在此種情況下的最小成本為1600元，且還可以知道每月

2、實際多余或缺少的人數(shù)（見附錄中的v,u值）。第二個問題當七月安裝工的需求量變?yōu)槲迕麜r，由于在建立的模型中的目標方程：（其中的符號說明見后面）中沒有涉及到各月需求人數(shù)，只是在約束條件中出現(xiàn)，故將其中的相關的約束條件中出現(xiàn)的七月所需人數(shù)改變即可，然后由Lingo軟件解出規(guī)劃方法 最后的規(guī)劃方式為：三月，四月分別借調(diào)1,2名工人，其他月份不借調(diào)，五月，七月分別離開2,1名工人，其他月份不離開，在此種情況下最小成本變?yōu)?200元，同樣可以得知每月多于或者缺少人數(shù)。經(jīng)過與第一題的規(guī)劃進行對比可知此種情況最小成本更小且其余的人數(shù)安排也不一樣。第三個問題中,當借調(diào)一名安裝工的費用支出由100元變?yōu)?00元，

3、由整數(shù)線性規(guī)劃的在建模中的應用，可知只需要將模型中的表示借調(diào)的未知數(shù)的系數(shù)改變?yōu)?00即可達到題中所要求，最后的結果為：三月，四月各借調(diào)1名和2名安裝工，其他月份不借調(diào)。五月，七月，八月月末時各離開1名安裝工，其他月份不離開，在此種情況下，最小成本為1900元，對于各月多于或缺少人數(shù)見附件，同樣經(jīng)過對比可知道最小成本已經(jīng)更高而且人員的規(guī)劃已經(jīng)改變。第四個問題中，正是得益于本模型中的特別之處：巧妙的將工地實際人數(shù)與所需人數(shù)之間的差值，符號無限制變量（冗員時為負值，缺員時為正值）轉(zhuǎn)化成，因此只需要將模型方程式中前系數(shù)改變成相應的缺員支出費用即可，最后的結果為：三月,四月，五月分別借調(diào)1名，2名，1

4、名工人，其他月份不借調(diào)，五月，七月，八月分別離開1名，2名，1名工人，其他月份不離開，在此種情況下最后的最小成本為1600元。本文最大的特色在于先根據(jù)題中表述建立基本模型，然后將基本模型進一步深化，得到一個更加優(yōu)越的模型，其次巧妙的將工地實際人數(shù)與所需人數(shù)之間的差值，符號無限制變量進行轉(zhuǎn)化也是本文一大特色。關鍵詞：純整數(shù)線性規(guī)劃（PILP）符號無限制變量 Lingo計算 深化一、問題提出在建筑工地上負責架設高層建筑的鋼結構的建筑工人稱為鋼結構安裝工。表1列出了某個工地上在六個月內(nèi)對鋼結構安裝工的需求人數(shù)。在每個月第一天可以從其它工地向此工地借調(diào)工人，每借調(diào)一名工人需要支出100元；在每個月的最

5、后一天，工人可以離開去其它工地，此時每有一名工人離開需要支出100元；工人過多或者過少都會帶來額外支出，每缺員1人需要額外支出200元（如果人員不足出現(xiàn)缺員，則其他工人需要加班，因此有額外支出），每冗員1人需要多支出200元。同時，根據(jù)工作協(xié)議：每天加班時間不能超過正常工作時間的25%；每個月至多只能新來3名工人；每個月底離開此工地去其它工地的工人數(shù)不能超過總?cè)藬?shù)的。假定在2月底此工地上已經(jīng)有了3名鋼結構安裝工，且在2月底沒有人離開，并且要求在8月底此工地上仍然有3名鋼結構安裝工。請建立模型解決：（1）確定每個月初到來和月底離開的工人數(shù)的人員規(guī)劃，使總成本最低？（2）如果7月的安裝工人需求量變

6、為5名，是否改變已有的規(guī)劃？（3） 如果借調(diào)一名安裝工所需要支出由100元變成200元，是否改變已有的規(guī)劃？（4） 如果每缺員1人的額外支出費用由200元/人變成三月：200元/人、四月：300元/人、五月300元/人、六月250元/人、七月300元/人、八月200元/人，試確定新的人員規(guī)劃。表1 每月鋼結構安裝工需求量三月四月五月六月七月八月467462二、基本假設1、假設三月至八月時間內(nèi)沒有任何其他因素迫使工人人數(shù)非正常變化（即不按照題中所設條件變化如，工人因故無法工作等）；2、假設三月至八月該工地上每月的鋼結構安裝工的需求量不會非正常變化（即該工地的工作量在這幾個月內(nèi)不會相對于題中條件增

7、加或減少）；3、假設每月都能夠成功從別處借調(diào)工人過來；4、假設二月底此工地上已經(jīng)有了三名鋼結構安裝工，且在二月底沒有離開；5、假設此期間不會發(fā)生任何意外增加工地的各種成本；6、假設八月底一部分工人在離開后還有三名工人；7、假設工人的加班時間始終不會超過正常工作時間的25%；8、假設每月借調(diào)的工人數(shù)不會超過3名；9、假設每月底離開的工人數(shù)不會超過該月實際工人總數(shù)的1/3。三、符號說明符號意義單位備注第i個月從其他工地借調(diào)人數(shù)，i=38名正整數(shù)第i個月月末離開此工地人數(shù)，i=38名正整數(shù)第i個月此工地缺員人數(shù)，i=38名正整數(shù)第i個月此工地冗員人數(shù)，i=38名正整數(shù)此工地三至八月剛結構安裝工總成本

8、元正數(shù)此工地需求工人數(shù)與工地每月實際工人數(shù)的差值，i=38名符號不確定四、問題分析由第一問中，確定每個月初到來和月底離開的工人數(shù)的人員規(guī)劃，使總成本最低，而根據(jù)題中的條件，鋼結構安裝總成本應該等于借調(diào)人員支出，離開人員支出，缺員人員支出，冗員人員支出的總和，因而可由此設各影響成本的未知數(shù)分別為， ，再將各未知數(shù)與各自系數(shù)乘積相加即可得到總成本。由于為此工地需求工人數(shù)與工地每月實際工人數(shù)的差值，而實際工人數(shù)相對于需求工人數(shù)必有多有少，故符號不確定（也即是符號無限制變量，可正可負），故可將寫成，此時缺少與多余人數(shù)均可表示出來了。另外，第二題，三題，四題均是在總成本最低的前提下，因而此模型均可使用，

9、只需根據(jù)題中條件將相應的約束條件做相應改動。最后，根據(jù)建立模型的思路可知此規(guī)劃為純整數(shù)線性規(guī)劃（PILP），因而適宜采用Lingo軟件進行計算得出最終結果。五、模型的建立與求解5.1問題一模型的建立與求解5.1.1問題一的分析根據(jù)之前的問題分析，可以知道建筑工地的人員規(guī)劃要使總成本最小，即要使工人的借調(diào)，離開，缺少，冗員費用支出之和最少，而由于在第一題中各項人員流通中每一個人的流通費用均已經(jīng)有題中固定，且各月需求人數(shù)也已經(jīng)固定，所以最終影響總成本的只有人員的借調(diào)，離開，缺少與多余人數(shù)，當然其中的各個代表工人人數(shù)的未知量均為正整數(shù)，因而可以采用純整數(shù)線性規(guī)劃方式進行建模。5.1.2問題一模型的建

10、立與求解符號說明：表示第i月工地上的實際工人數(shù)，表示第i月工地上需求人數(shù)，表示每天每名工人的正常工作時間。根據(jù)對問題一的分析能夠很容易的得出目標方程最小成本因為假設中二月月底已經(jīng)有3名工人，且月底沒有人員離開，所以三月實際人數(shù)應該有：，其中因為借調(diào)人數(shù)不能超過3名所以，而由于假設中有每天加班時間不能超過正常工作時間的25%，所以存在約束條件：，因為每月離開人數(shù)不能超過該月實際人數(shù)的1/3，所以有約束，而三月冗員或者缺少人數(shù)應該為：，相應的可知四月實際人數(shù)應該為三月實際人數(shù)減去三月月末離開人數(shù)加上四月借調(diào)人數(shù)所以有，同樣由于借調(diào)人員人數(shù)限制有，由于加班時間限制有，由于離開人數(shù)的限制有，四月冗員或

11、者缺少人數(shù)應該為，而對于后邊的五月，六月，七月，八月則可以按照相同的思路得出類似的限制條件，因為假設中 最終可以得到如下基本模型： 由建模思想及模型可知，求解此模型宜首先采用單純刑法和分支界定法求解出滿足此模型約束條件的最優(yōu)解，此過程的算法可以簡單描述為：Step1：將原整數(shù)規(guī)劃問題記做P，相應的伴隨線性規(guī)劃問題記做Q，采用單純刑法求解問題Q；Step2：如果問題Q無可行解，計算終止，這時問題P無解；Step3：檢查Q的最優(yōu)解，看他是否符合整數(shù)條件。如果符合，就得P的最優(yōu)解，計算終止；否則轉(zhuǎn)Step4；Step4：在Q的最優(yōu)解中選一非整數(shù)解變量，做兩個分支問題。也就是在問題Q中各增加一個約束條

12、件：（1）（2）；（其中b表示小于b的最大整數(shù)）；不考慮最后整數(shù)條件，解這兩個分支問題得最優(yōu)解或無解。Step5：在有最優(yōu)解的各分支問題中，選擇目標函數(shù)值最優(yōu)的問題，重新記這個問題Q，返回Step3。以上計算過程可以由Lingo軟件執(zhí)行，具體代碼見附錄I，最后軟件得出在這個基本模型下的最優(yōu)解為：Min P=1800元，且人員規(guī)劃為三月四月五月六月七月八月121000011011001010102000 模型的深化與求解當我們返回模型中關于離開人數(shù)的約束時即：可以發(fā)現(xiàn)，每月離開人數(shù)僅僅與該月離開之前的借調(diào)和離開人數(shù)有關，因而在求最優(yōu)解時往往會優(yōu)先考慮之前借調(diào)與離開的人數(shù)產(chǎn)生的費用，恰恰在這個模型

13、中由人員的缺少與冗員產(chǎn)生費用的速率比借調(diào)，離開人數(shù)產(chǎn)生費用的速率大一倍，因而應該優(yōu)先考慮到人員的缺少與冗員對離開人數(shù)的限制，即該約束條件約束條件可以深化為：則深化后的模型為：編寫相應的Lingo代碼（見附錄II），并得到最終結果為：P=1600元，具體人員規(guī)劃為三月四月五月六月七月八月121000002011000010000102：可見深化后的模型更具有可用性。5.1.3模型結果的分析由表中的人員規(guī)劃數(shù)可以知道，在三月初時借調(diào)一名工人后三月實際工人數(shù)有4名，那么三月既不會缺員也不會冗員，而三月末時候沒有工人離開，那么三月產(chǎn)生的費用就應該為100元，四月初在借調(diào)2名工人，那么四月還是不會缺員和

14、冗員，且四月沒有工人離開，那么四月產(chǎn)生的費用就應該為200元，五月月初時候借調(diào)一名工人，則五月實際工人數(shù)就應該有7名，既不缺員也不冗員，五月末離開2名工人，則五月產(chǎn)生費用為300元，五月在離開兩名工人后還剩下五名工人，六月既不借調(diào)也不離開，則六月多一人，產(chǎn)生200元費用，七月不借調(diào)，那么七月將缺少一人，產(chǎn)生200元費用，而在月末時候離開一名又產(chǎn)生100元，七月總計產(chǎn)生300元，在七月離開一名后還剩下五名工人，那么八月不借調(diào)，將冗員2名，產(chǎn)生400元費用，由于八月最終只有三名工人，所以八月還要離開一名，最后八月產(chǎn)生的費用為500元，則以上的總費用為100+200+300+200+300+500=

15、1600元。5.2 問題二模型的建立于求解5.2.1 問題二的分析在問題二中由于題目敘述等沒有改變，且同樣是在總成本最小的前提下的人員規(guī)劃，而問題二，如果七月的安裝工人 需求量變?yōu)?名，求人員規(guī)劃，由于在建立模型的過程中，每月安裝工的需求量僅僅是出現(xiàn)在約束條件中，因而只需將原模型中關于七月需求量的約束條件做相應改動即可：將約束改成約束，約束改成，約束改成。52.2 問題二模型的建立與求解根據(jù)以上對問題二的分析可以得出問題二的模型為：同樣適用于Lingo軟件的整數(shù)線性規(guī)劃，代碼見附錄III，最后的結果為P=1200元，人員規(guī)劃為：三月四月五月六月七月八月120000002010001010000

16、0015.2.3 問題二結果的分析由以上的計算結果可知道，如果七月的安裝工的需求量變?yōu)?名，則為使總成本最小，最終的人員規(guī)劃有所改變：三月份應該借調(diào)一名且三月沒有人員的離開，三月的費用為100元，四月應該借調(diào)2名，同樣沒有人員離開，也沒有缺少、多余人員，四月份的費用為200元，五月份不借調(diào)只是要離開2名，則在離開前五月份應該缺少1名工人，則五月份共產(chǎn)生費用400元，六月份既不借調(diào)也不離開人員，那么六月份的費用就應該是0元，七月份離開1名，那么將缺少1名工人，產(chǎn)生300元，八月份不就借調(diào)也不離開，就只會多余一個工人，且剛好是3名工人，產(chǎn)生費用為200元。所以在七月份的需求量變?yōu)?名工人后，規(guī)劃改

17、變，費用減少400元。5.3問題三模型的建立與求解5.3.1 問題三的分析問題三，如果借調(diào)一名安裝工所需要的支出由100元變成200元，是否改變已有規(guī)劃，顯然問題三的建模思想與之前問題一、二一致（主要是將問題一中的模型中x前面的系數(shù)改變?yōu)?00）。5.3.2 問題三模型的建立與求解根據(jù)以上分析以及問題一中的模型可以得到問題三的模型應該為：利用Lingo軟件可以求出結果（代碼見附錄IV），最后的結果為P=1900元，人員規(guī)劃為：三月四月五月六月七月八月1200000010110010100001025.3.3 問題三結果分析當借調(diào)一名工人的費用變?yōu)?00元時，工人的規(guī)劃也應該改變：三月借調(diào)一名，

18、沒有人員離開，三月產(chǎn)生費用200元，四月借調(diào)2名，沒有人員離開，四月產(chǎn)生費用為400元，五月不借調(diào)，那么五月缺少一人，五月工人不離開，最后產(chǎn)生的費用為300元，六月不借調(diào)也不離開，將會冗員一名，產(chǎn)生費用為200元，七月離開一名，但是不借調(diào)，七月將會缺少一名，產(chǎn)生費用為300元，八月不借調(diào)，但是離開一名工人，在未離開前冗員2名，最終八月產(chǎn)生的費用為500元。5.4 問題四模型建立與求解5.4.1 問題四的分析 分析過程同問題一，最后將問題一中的模型中的表示缺員讓人數(shù)的未知數(shù)系數(shù)根據(jù)題中要求作相應改變。5.4.2 問題四模型的建立與求解根據(jù)以上分析以及問題一中的的模型建立可得問題四的模型為：利用L

19、ingo軟件計算可得結果（代碼見附錄），P=1600元，人員的規(guī)劃為：三月四月五月六月七月八月1210000010210000000002025.4.3 問題四結果分析由以上的計算結果可以知道，在缺員一人的支出費用發(fā)生變化后，其人員的規(guī)劃也發(fā)生改變：三月借調(diào)1名且沒有多余沒有缺少也沒有人員的離開，產(chǎn)生的費用為100元，四月借調(diào)兩名，沒有人員的離開產(chǎn)生的費用為200元，五月借調(diào)一名，同樣不會有人員的缺少、多余，月末離開一名，產(chǎn)生費用為200元，六月既不借調(diào)也不離開，將會有一人多余，產(chǎn)生200元的費用，七月時候不借調(diào)，將不會缺少工人，也不會多余，月末離開兩名，產(chǎn)生費用為200元，八月不借調(diào)，將會有

20、兩名工人多出，不會缺少，月末離開一名后還是有三名，產(chǎn)生的費用為500元。六、模型的評價與推廣6.1 模型的評價這個問題的規(guī)劃，本文提出的模型，一方面考慮到多個變量對總成本的影響，但是其中人員的缺少與冗余均會增加成本，于是將實際人數(shù)與需求人數(shù)的差值進行轉(zhuǎn)化，既方便了以后小題的計算又能夠簡化運算；另一方面，對于剛剛建立的基本模型，考慮到其中的各項變量對總成本的影響不同，而進過深化模型，使對于成本影響大的變量能夠得到優(yōu)先考慮，從而使最后得到的模型更加優(yōu)越！6.2 模型的推廣根據(jù)本模型的建立思想，以及其中采用的無符號限制變量的轉(zhuǎn)化，根據(jù)對最后結果的影響速率確定優(yōu)先等技巧，還可以運用于工廠里生產(chǎn)計劃的指

21、定，超市等貨物的采辦，以及其他類似此題情況的人員的規(guī)劃等等。七、參考文獻【1】姜啟源等, 數(shù)學模型（第三版），高等教育出版社，2003年8月【2】范玉妹等，數(shù)學規(guī)劃及其應用（第三版），冶金工業(yè)出版社，2009年【3】嚴喜祖等，數(shù)學建模及其試驗，科學出版社八、附錄8.1 附錄清單附錄一：問題一的Lingo程序附錄二：問題二的lingo程序附錄三：問題三的Lingo程序附錄四：問題四的Lingo程序8.2 附錄正文附錄一：min =100*x3+100*x4+100*x5+100*x6+100*x7+100*x8+100*y3+100*y4+100*y5+100*y6+100*y7+100*y8+

22、200*u3+200*u4+200*u5+200*u6+200*u7+200*u8+200*v3+200*v4+200*v5+200*v6+200*v7+200*v8;x3=3;x4=3;x5=3;x6=3;x7=3;x8=3;1-x3=u3-v3;3-x3+y3-x4=u4-v4;4-x3+y3-x4+y4-x5=u5-v5;1-x3+y3-x4+y4-x5+y5-x6=u6-v6;3-x3+y3-x4+y4-x5+y5-x6+y6-x7=u7-v7;-1-x3+y3-x4+y4-x5+y5-x6+y6-x7+y7-x8=u8-v8;y3=(4-u3+v3)/3;y4=(6-u4+v4)/3

23、;y5=(7-u7+v7)/3;y6=(4-u6+v6)/3;y7=(6-u7+v7)/3;y8-v8/3=1/5;x3-y3+x4=9/5;x3-y3+x4-y4+x5=13/5;x3-y3+x4-y4+x5-y5+x6=1/5;x3-y3+x4-y4+x5-y5+x6-y6+x7=9/5;gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(x8);gin(y3);gin(y4);gin(y5);gin(y6);gin(y7);gin(y8);gin(u3);gin(u4);gin(u5);gin(u6);gin(u7);gin(u8);gin(v3);g

24、in(v4);gin(v5);gin(v6);gin(v7);gin(v8);附錄二：min =100*x3+100*x4+100*x5+100*x6+100*x7+100*x8+100*y3+100*y4+100*y5+100*y6+100*y7+100*y8+200*u3+200*u4+200*u5+200*u6+200*u7+200*u8+200*v3+200*v4+200*v5+200*v6+200*v7+200*v8;x3=3;x4=3;x5=3;x6=3;x7=3;x8=3;1-x3=u3-v3;3-x3+y3-x4=u4-v4;4-x3+y3-x4+y4-x5=u5-v5;1-x

25、3+y3-x4+y4-x5+y5-x6=u6-v6;2-x3+y3-x4+y4-x5+y5-x6+y6-x7=u7-v7;-1-x3+y3-x4+y4-x5+y5-x6+y6-x7+y7-x8=u8-v8;y3=(4-u3+v3)/3;y4=(6-u4+v4)/3;y5=(7-u7+v7)/3;y6=(4-u6+v6)/3;y7=(5-u7+v7)/3;y8-v8/3=1/5;x3-y3+x4=9/5;x3-y3+x4-y4+x5=13/5;x3-y3+x4-y4+x5-y5+x6=1/5;x3-y3+x4-y4+x5-y5+x6-y6+x7=1;gin(x3);gin(x4);gin(x5)

26、;gin(x6);gin(x7);gin(x8);gin(y3);gin(y4);gin(y5);gin(y6);gin(y7);gin(y8);gin(u3);gin(u4)gin(u5);gin(u6);gin(u7);gin(u8);gin(v3);gin(v4);gin(v5);gin(v6);gin(v7);gin(v8);附錄三：min =200*x3+200*x4+200*x5+200*x6+200*x7+200*x8+100*y3+100*y4+100*y5+100*y6+100*y7+100*y8+200*u3+200*u4+200*u5+200*u6+200*u7+200*

27、u8+200*v3+200*v4+200*v5+200*v6+200*v7+200*v8;x3=3;x4=3;x5=3;x6=3;x7=3;x8=3;1-x3=u3-v3;3-x3+y3-x4=u4-v4;4-x3+y3-x4+y4-x5=u5-v5;1-x3+y3-x4+y4-x5+y5-x6=u6-v6;3-x3+y3-x4+y4-x5+y5-x6+y6-x7=u7-v7;-1-x3+y3-x4+y4-x5+y5-x6+y6-x7+y7-x8=u8-v8;y3=(4-u3+v3)/3;y4=(6-u4+v4)/3;y5=(7-u7+v7)/3;y6=(4-u6+v6)/3;y7=(6-u7+v7)/3;y8-v8/3=1/5;x3-y3+x4=9/5;x3-y3+x4-y4+x5=13/5;x3-y3+x4-y4+x5-y5+x6=1/5;x3-y3+x4-y4+x5-y5+x6-y6+x7=9/5;gin(x3);gin