[精彩]數(shù)學(xué)建模c題論文(工件加工排序)

1、數(shù)學(xué)建模競(jìng)賽試題：C題：工件加工排序方案排序問題中的車間作業(yè)問題，研究n個(gè)工件在m臺(tái)機(jī)器上有序的加工問題，每個(gè)工件都有完工的日期DD，Due date, 加工的時(shí)間PT，Processing time和工件的價(jià)值VAL，Value if job is selected. 現(xiàn)研究一個(gè)工廠生產(chǎn)工序的方案和安排，需要方案與合理安排各個(gè)工件在這些機(jī)器上加工的先后次序，即擬訂加工工序，通過各個(gè)工件在各種機(jī)器上加工次序的合理安排，使得完成這批工件加工任務(wù)所需的總時(shí)間最省注：總時(shí)間即為各個(gè)零件的加工時(shí)間和加工其他零件時(shí)它們等待時(shí)間之和或要求整個(gè)選擇加工的工件價(jià)值最大。有一個(gè)工廠現(xiàn)在有12種工件編號(hào)為工件1，

2、工件2，工件12需要在車床，鉆床，銑床幾種不同的設(shè)備上加工。考慮下面的工件加工的排序問題：(一) 這12種工件都要求在車床上加工，車床一次只能加工一種工件，這12種工件加工所需時(shí)間，每個(gè)工件的完工時(shí)間和每個(gè)工件的價(jià)值如表1所示：工件加工時(shí)間h完工時(shí)間(h)工件價(jià)值198243151644233510762220717178331197710181211255121118表11) 不考慮工件的完工時(shí)間和工件的價(jià)值，為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。2) 由于工件必須在它們要求的時(shí)間內(nèi)完工，按照表1的數(shù)據(jù)，為該工廠安排選擇加工工件的

3、種類及加工的次序，使得整個(gè)選擇加工的工件價(jià)值最大。建立數(shù)學(xué)模型并給出相應(yīng)的算法。(二) 如果這12種工件都要求先在車床上加工，然后再在鉆床上加工即工件在鉆床加工之前必須先在車床上加工過，每種機(jī)器一次只能加工一種工件，這12種工件加工所需時(shí)間如表2所示： 工件車床加工時(shí)間h鉆床加工時(shí)間(h)142344536789101112 表2為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。 (三) 如果這12種工件都要求先在車床上加工，然后再在鉆床上加工，最后再在銑床上加工，每種機(jī)器一次只能加工一種工件，這12種工件加工所需時(shí)間如表三所示：工件車床加工時(shí)

4、間h鉆床加工時(shí)間(h)銑床加工時(shí)間(h)1432134453627891101112表3為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。建立數(shù)學(xué)模型并給出相應(yīng)的算法。(四) 對(duì)于上述問題你做出的數(shù)學(xué)模型和相應(yīng)的算法給出評(píng)價(jià)。并將模型推廣到n個(gè)工件在m臺(tái)機(jī)器上加工的一般的工件排序問題，給出你的想法和解決問題的思路。解題正文：C題：工件加工排序建模小組成員： AP0308306 陳運(yùn)標(biāo) AP0308307鄧風(fēng)儀 AP0206311 黃深泉 摘要此題根據(jù)數(shù)據(jù)，結(jié)合問題中的具體要求，我們引入0/1變量建立工件排序的數(shù)學(xué)規(guī)劃模型。借助Lingo軟件進(jìn)行求解運(yùn)算，得出其中的最優(yōu)排序方

5、案。使得完成這批工件加工任務(wù)所需要的總時(shí)間最省。在這里，我們通過對(duì)各個(gè)工件排序后完成某項(xiàng)特定工序所需總時(shí)間進(jìn)行求和得到整個(gè)加工任務(wù)所需要的總時(shí)間。而各工件的總時(shí)間包括其機(jī)床加工時(shí)間和加工其他零件時(shí)的等待時(shí)間。模型的假設(shè)：在后面的模型中，我們都假定了忽略工件在轉(zhuǎn)換工序時(shí)的運(yùn)輸時(shí)間。即將整個(gè)工件加工過程簡(jiǎn)化為一個(gè)連續(xù)的過程，只考慮機(jī)床在加工工件時(shí)其他工件的等待時(shí)間。模型的建立：我們的思路是引入0/1變量對(duì)工件進(jìn)行動(dòng)態(tài)排序，根據(jù)問題要求得出排序后的目標(biāo)函數(shù)即數(shù)學(xué)模型。根據(jù)題目的約束條件，利用Lingo軟件算出模型的最優(yōu)解，從而獲得工件的最優(yōu)排序。問題一題目要求：12種工件都要求在車床上加工，車床一次

6、只能加工一種工件。設(shè) i 工件車床加工時(shí)間為A ,規(guī)定完工時(shí)間為B,工件價(jià)值為C1） 不考慮工件的完工時(shí)間和工件的價(jià)值，安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。分析：引入0/1變量，利用目標(biāo)函數(shù)最優(yōu)化工件排序。 設(shè)為i工件實(shí)際完工時(shí)間，所以完成這批工件的總時(shí)間為T=,而 =A+A=A+A+A=A+A+=因此: 建立問題1的目標(biāo)函數(shù)即數(shù)學(xué)模型為Min= 定義x，xx為0/1變量，為原始工件序列下i工件的車床加工時(shí)間；所以A=xa+xa+.+xaA=xa+xa+.+xa . A=xa+xa+.+xax+x+.+x=1x+x+.+x=1.x+x+.+x=1x+x+x+x+x=1

7、x+x+x+x+x=1.x+x+x+x+x=1Lingo程序：附wenti(1).lg4文件model: !不考慮完工時(shí)間和工件價(jià)值的排序問題;sets: gongjian/g1.g12/:shijian; !屬性為原始排序下各個(gè)工件的機(jī)床加工時(shí)間; shunxu/s1.s12/:time,fin_time; !屬性為重新排序后各工件的機(jī)床加工時(shí)間和完成車工序的時(shí)間; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù)：求各個(gè)工件的加工總時(shí)間和最小; min=sum(shunxu(I):fin_time(I); !重新排序后各工件的機(jī)床加工時(shí)間; for(sh

8、unxu(J): time(J)=sum(gongjian(I):shijian(I)*note(I,J); ); !排序后各個(gè)工件的加工總時(shí)間; for(shunxu(I): fin_time(I)=sum(shunxu(J)|J#le#I:time(J); ); !每個(gè)順序位只能有一個(gè)工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每個(gè)工件只能排在一個(gè)順序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; ); !定義0/1變量; for(links:bin(note);data:!輸出

9、數(shù)據(jù)到Excel文檔;OLE(D:liebiao.XLS)=time,fin_time; !原始排序下各個(gè)工件的機(jī)床加工時(shí)間; shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7;enddataend結(jié)果數(shù)據(jù)：工件加工時(shí)間完成時(shí)間T6391075128114412總計(jì)： 表1-1 所以最優(yōu)排序是639107512811412完成這批工件加工任務(wù)所需的最省總時(shí)間2) 分析：由于工件必須在它們要求的時(shí)間內(nèi)完工，即某工件在任務(wù)開始起到該工件加工完畢之間所用的總時(shí)間應(yīng)少于該工件的規(guī)定完工時(shí)間。所以要使整個(gè)加工任務(wù)的工件總價(jià)值最大，必須合理選擇加

10、工工件的種類及其加工的次序。 引入0-1變量,假設(shè)選擇i工件加工,那么記Y=0;工件的排序算法同問題1，但約束條件有所不同。在此題中，12種工件不一定都可以入選到最優(yōu)加工序列中即目標(biāo)排序中可能出現(xiàn)工件空缺，所以 (=1, 2, .12)，且 (=1, 2, .12)，為0-1變量。用Lingo進(jìn)行編程，工件集參加原始排序下車床加工時(shí)間，完工時(shí)間和工件價(jià)值屬性；順序集參加重新排序后車床加工時(shí)間，完工時(shí)間和工件價(jià)值屬性；因此該模型為：目標(biāo)函數(shù): Max= 在排序算法及程序中已隱含有工件選擇： (=1, 2, .12)， (=1, 2, .12)完工時(shí)間約束： (=1, 2, .12)Lingo程序

11、：wenti(2).lg4文件model: !考慮完工時(shí)間和工件價(jià)值的排序問題;sets: gongjian/g1.g12/:shijian,endtime,gj_value; ! 屬性為原始排序下各個(gè)工件的機(jī)床加工時(shí)間，完工時(shí)間，工件價(jià)值; shunxu/s1.s12/:time,overtime,fin_value; ! 屬性為重新排序后各個(gè)工件的機(jī)床加工時(shí)間，完工時(shí)間，工件價(jià)值; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù); max=sum(shunxu(I):fin_value(I);!從新排序后各工件的機(jī)床加工時(shí)間可能為零，即表示未選中工件;

12、 for(shunxu(I): time(I)=sum(gongjian(J):shijian(J)*note(I,J);!從新排序后各工件的完工時(shí)間可能為零，即表示未選中工件;for(shunxu(I): overtime(I)=sum(gongjian(J):endtime(J)*note(I,J); );!從新排序后各工件的工件價(jià)值可能為零，即表示未選中工件;for(shunxu(I): fin_value(I)=sum(gongjian(J):gj_value(J)*note(I,J); ); !每個(gè)順序位只能有一個(gè)工件或者沒有工件; for(shunxu(I): sum(gongji

13、an(J): note(I,J)=1); !每個(gè)工件只能排在一個(gè)順序位上; for(gongjian(J):sum(shunxu(I): note(I,J)=1); !各工件的完工時(shí)間約束; for(shunxu(I): sum(shunxu(J)|J#le#I:time(J)=overtime(I); ); !定義0/1變量; for(links:bin(note);data: !原始排序下各個(gè)工件的機(jī)床加工時(shí)間; shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7; !原始排序下各個(gè)工件的完工時(shí)間; endtime=9,7.5,15

14、,23,10,22,17,33,7,18,25,11; !原始排序下各個(gè)工件的工件價(jià)值; gj_value=8,4,16,3,7,20,17,11,7,12,5,18;enddataend模型結(jié)果：導(dǎo)出列表：工件順序車床加工時(shí)間規(guī)定的完工時(shí)間各工件價(jià)值000000 198 577 121118 101812 31516 62220 71717 24233 11255 83311總價(jià)值：117 表1-2 由上表可知，最優(yōu)方案是選擇工件1512103672118，并按此順序進(jìn)行加工。從而獲得最大的工件總價(jià)值為117.關(guān)于問題二，三，四分析：?jiǎn)栴}二要求：如果這12種工件都要求先在車床上加工，然后再在

15、鉆床上加工即工件在鉆床加工之前必須先在車床上加工過，每種機(jī)器一次只能加工一種工件，求工件加工的最優(yōu)排序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。根據(jù)總時(shí)間的定義，某工件從任務(wù)開始時(shí)刻起到完成鉆床工序止所需要的總時(shí)間包括該工件完成車工序的時(shí)間，等待上一個(gè)工件加工完的時(shí)間即從該工件在車床加工完畢時(shí)刻起到其上一個(gè)工件在鉆床上加工完畢這一段時(shí)間，該工件在鉆床上加工的時(shí)間。我們假設(shè)工件在車床加工所需時(shí)間為，在鉆床上加工所需時(shí)間為；工件完成在車床加工的總時(shí)間為；工件完成在鉆床加工的總時(shí)間為，。這里要分兩種情況進(jìn)行分析： 1).當(dāng)時(shí)，即工件完成車工序的總時(shí)間大于或等于工件完成鉆工序的總時(shí)間，此時(shí)工件不需要

16、等待工件而立即就進(jìn)入鉆工序，因此工件完成鉆床工序的總時(shí)間表達(dá)式為+; 2).當(dāng)時(shí)，即工件完成車工序的總時(shí)間小于或等于工件完成鉆工序的總時(shí)間，此時(shí)工件需要等待工件完成鉆床工序才能進(jìn)入鉆床加工。因此工件完成鉆床工序的總時(shí)間表達(dá)式為+。 綜合以上兩種情況，得到工件完成鉆床工序的總時(shí)間計(jì)算公式為 Max，+ 同理，對(duì)于問題三，我們也可以得到類似的計(jì)算公式.，下面是以列表的形式將這一推導(dǎo)公式推廣到工件個(gè)工序的情況：假設(shè)i工件在車床加工所需時(shí)間為；在鉆床上加工所需時(shí)間為；在銑床上加工所需要的時(shí)間為；在后續(xù)的各工序中加工所需要的時(shí)間設(shè)為；下表中內(nèi)容表示i工件從任務(wù)開始時(shí)刻起到完成道工序止所需要的總時(shí)間 工序

17、 順序 工件順序車床鉆床銑床 加工1+ +2+Max，+Max，+ Max，+3Max，+Max，+ Max，+ iMax，+Max，+ Max，+表2-1模型的建立： 根據(jù)表2-1，問題二中要求的完成加工任務(wù)的最省總時(shí)間即為在最優(yōu)排序下各工件完成鉆床加工工序的總時(shí)間之和。即建立問題二的數(shù)學(xué)模型為Max=+ ，+；這里 +；Lingo編程：附錄1wenti(3).lg4文件同理，問題三中要求的完成加工任務(wù)的最省總時(shí)間即為在最優(yōu)排序下各工件完成銑床加工工序的總時(shí)間之和。 建立問題三的數(shù)學(xué)模型為Max=+ ，+；這里 +；Lingo編程：附錄2wenti(4).lg4文件歸納以上算式，推廣到i個(gè)工

18、件j部機(jī)床的工件排序問題， 建立問題四的數(shù)學(xué)模型為Max=+ ，+；這里 +；Lingo編程：略 模型結(jié)果：?jiǎn)栴}二運(yùn)算后導(dǎo)出列表：順序號(hào)工件號(hào)車床加工時(shí)間 鉆床加工時(shí)間完成車床工序總時(shí)間完成鉆床工序總時(shí)間 1 33 2 6 3 7 4 2 5 1013 6 531316 7 9 8 44 9 822 10 14 11 1133 12 1235總時(shí)間：表2-2 由上表可知，最優(yōu)的工件排序?yàn)?67210594811112，完成這批工件加工任務(wù)所需的最省總時(shí)間為224.8。問題三運(yùn)算后導(dǎo)出列表：順序號(hào) 工件號(hào)車床加工時(shí)間 鉆床加工時(shí)間銑床加工時(shí)間 1 3 2 92 3 11 4 10 5 7 6 9

19、1 7 21 8 53 9 8 10 143 11 44 12 12 表2-3順序號(hào)工件號(hào)完成車床工序總時(shí)間完成鉆床工序總時(shí)間完成銑床工序總時(shí)間 1 33 2 9 3 11 4 1012 5 7 6 9 7 2 8 5 9 8 10 1 11 4 12 1235總時(shí)間： 表2-4 從軟件的運(yùn)行情況可知，最優(yōu)的工件排序?yàn)?91110792581412；完成這批工件加工任務(wù)所需的最省總時(shí)間模型評(píng)價(jià)，改良方法，推廣1 在此題的解答過程中所建立的數(shù)學(xué)規(guī)劃模型中，我們始終圍繞一種化整為零的數(shù)學(xué)思想，將整批工件的加工任務(wù)拆分為在最優(yōu)的排序下每個(gè)工件的實(shí)際加工情況來(lái)分析，根據(jù)各工件在加工過程中加工時(shí)間和總時(shí)

20、間之間的聯(lián)系，尋求各工件加工總時(shí)間的具體算法。再利用Lingo軟件進(jìn)行求解模型，得出工件的最優(yōu)排序。其中邏輯嚴(yán)謹(jǐn)，論證充分，算法簡(jiǎn)潔準(zhǔn)確。有效地提高了軟件求解效率。2 由于在模型求解中利用了Lingo軟件，大大簡(jiǎn)化了編程工作，且模型本身結(jié)合軟件的使用就具有很強(qiáng)的可移植性，便于模型的推廣。列如在推廣到m工件n部機(jī)床的情況，只需在程序中的工件，順序集里參加相應(yīng)的屬性；在程序段中參加對(duì)應(yīng)的算法和約束條件就可以完全替換從而解決問題了。參考資料：1 姜啟源 等，數(shù)學(xué)模型第三版，高等教育出版社，2003。2 洪文 吳本忠，Lingo4.0 for windows 最優(yōu)化軟件及應(yīng)用，北京大學(xué)出版社，2001

21、。34 :/ /Forums/1/268/ShowPost.aspx#268 附錄一：model: !工件先車后鉆的排序問題;sets: gongjian/g1.g12/:che_shijian,zuan_shijian; shunxu/s1.s12/:che_time,zuan_time,che_fintime,zuan_fintime; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù); min=sum(shunxu(I):zuan_fintime(I);!從新排序后各工件的車床加工時(shí)間; for(shunxu(I): che_ti

22、me(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!從新排序后各工件的鉆床加工時(shí)間;for(shunxu(I): zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J); ); !每個(gè)順序位只能有一個(gè)工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每個(gè)工件只能排在一個(gè)順序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; );!從新排序后各工件在完成車工序的總時(shí)間;for(shunxu(I

23、): che_fintime(I)=sum(shunxu(J)|J#le#I:che_time(J); );!從新排序后各工件在完成鉆工序的總時(shí)間;for(shunxu(I)| I#gt#1:zuan_fintime(I)=if(che_fintime(I)#ge#zuan_fintime(I-1),che_fintime(I),zuan_fintime(I-1)+zuan_time(I); ); !順序1中的工件在完成鉆工序的總時(shí)間; zuan_fintime(1)=che_fintime(1)+zuan_time(1); !定義0/1變量; for(links:bin(note); dat

24、a: !原始排序下各個(gè)工件的車床加工時(shí)間; che_shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7; !原始排序下各個(gè)工件的鉆床加工時(shí)間; zuan_shijian=4,1.3,1.8,2.2,3,4.5,1.7,2.5,4.5,2.5,3.8,1.9; enddataend附錄二：model: !工件先車后鉆再銑的的排序問題;sets: gongjian/g1.g12/:che_shijian,zuan_shijian,xi_shijian; shunxu/s1.s12/:che_time,zuan_time,xi_time,ch

25、e_fintime,zuan_fintime,xi_fintime; links(shunxu,gongjian): note;endsets !目標(biāo)函數(shù); min=sum(shunxu(I):xi_fintime(I);!從新排序后各工件的車床加工時(shí)間; for(shunxu(I): che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!從新排序后各工件的鉆床加工時(shí)間;for(shunxu(I): zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J); );!從新排序后各工件的銑床加工時(shí)間;for(shunxu(I): xi_time(I)=sum(gongjian(J):xi_shijian(J)*note(I,J); ); !每個(gè)順序位只能有一個(gè)工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每個(gè)工件只能排在一個(gè)順序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; );!從新排