工件的安裝與排序15

1、工件的安裝與排序問題 摘要工件在安裝時需要按工藝要求進(jìn)行排序，在實踐中具有一定的意義。本文討論的是工件在安裝時按重量排序、按重量和，以及在工件不滿足要求時，怎樣更換工件及求出新工件的重量和體積值范圍。問題一要求按重量排序，而且相鄰區(qū)域的4個工件總重量之差不允許超過一定值。對于該問題，我們采用0-1規(guī)劃來選擇滿足分配到各扇形區(qū)的4個工件。問題二是在問題一的基礎(chǔ)上多加了一個要求，即排序還得按體積排序。我們在問題一得到按重量排序的放法，但由于4個工件的順序并沒有確定，所以按重量排序的放法可能不滿足按體積排序的放法。所以在問題二中，我們將圓盤分成24塊區(qū)域，用0-1規(guī)劃選擇第i個工件放在第j塊區(qū)域，且

2、第i個工件只能放在1塊區(qū)域里，1塊區(qū)域只能放一個工件；再根據(jù)重量和體積排序算法確定24個工件的具體放法。問題三是在不滿足前兩個問題的情況下對個別工件進(jìn)行調(diào)整，當(dāng)工件不滿足要求時，允許更換少量的數(shù)據(jù)。根據(jù)前面解決問題的算法可以得出兩種修改策略：一是按重量排序；二是按重量和體積排序。如果只考慮重量，分析了兩種相臨扇區(qū)總重量差最大的情況，通過數(shù)學(xué)分析得出工件調(diào)整幅度，如果綜合考慮重量和體積因素，則不斷修正工件重量和體積，篩選出滿足條件的工件組合。關(guān)鍵詞：按重量排序、按體積排序、0-1規(guī)劃、區(qū)域一、問題重述某設(shè)備由24個工件組成，安裝時需要按工藝要求重新排序。 設(shè)備的24個工件均勻分布在等分成六個扇形

3、區(qū)域的一圓盤的邊緣上，放在每個扇形區(qū)域的4個工件總重量與相鄰區(qū)域的4個工件總重量之差不允許超過一定值（如4g）。 工件的排序不僅要對重量差有一定的要求，還要滿足體積的要求，即兩相鄰工件的體積差應(yīng)盡量大，使得相鄰工件體積差不小于一定值（如3 ）； 當(dāng)工件確實不滿足上述要求時，允許更換少量工件。 問題1按重量排序算法； 問題2按重量和體積排序算法； 問題3當(dāng)工件不滿足要求時，指出所更換工件及新工件的重量和體積值范圍，并輸出排序結(jié)果。 請按下面兩組工件數(shù)據(jù)（重量單位：g ，體積單位： ），進(jìn)行實時計算： 序號重量體積序號重量體積1348101.51358.510323521022357.510333

4、4710533551034349105.54351103.55347.51065355.510363471046357102733094734196832998834296.59329100.5934095.510327.598.51034497113299811342.595.112331.59912343.596.513348.5104.513357.5102.5143471051435510315346.5107.515353.5103.516348104.516356.5103.517347.510417356103.518348104.518352.5104193339719342.

5、59820330972034496.521332.59921339.59822331.59822341.59623331.596.523341962433294.52434597二、問題假設(shè)1、所給的24 個工件的重量在某范圍內(nèi)，相差不大，不會出現(xiàn)很重或很輕的工件2、圓盤足夠大，每個扇形區(qū)域內(nèi)的工件重量無論多大，均能放在扇形區(qū)域內(nèi)，不會影響其他區(qū)域的重量3、存在重量相同但體積不同的工件和體積相同但重量不同的工件供我們更換三、變量說明1、gi第i個工件的重量2、wj第j個扇形區(qū)工件的總重量3、vi未經(jīng)過排序的第i個工件的體積4、V´j已經(jīng)過排序的第j個工件的體積5、相鄰扇區(qū)質(zhì)量和之差的

6、要求范圍6、相鄰工件體積之差的要求范圍四、問題分析分析問題一：我們通過0-1規(guī)劃來選擇哪個工件應(yīng)該分配在哪個區(qū)，并且每個區(qū)分配4個工件，每個工件只能選一次，不能重復(fù)選。題意要求相鄰區(qū)域的4個工件總重量之差不允許超過一定值，我們假設(shè)這個值為m，我們可以知道×（4個最重工件的重量之和 4個最輕工件的重量之和），即。而且我們通過數(shù)據(jù)表格分析可知，所以數(shù)據(jù)都是0.5的倍數(shù)，所以m最小不能小于0.5g,即。為了得出最佳分配方案，我們以求m的最小值為目標(biāo)函數(shù)建立模型。分析問題二：在問題一中按重量排序可以求得每個扇形區(qū)域所含的4個工件，但4個工件的順序并沒有確定，可能不滿足按體積的排序。所以為了解

7、決問題二，我們將圓盤分成24塊區(qū)域，并且使相鄰的4塊構(gòu)成一個扇形區(qū)域。用0-1規(guī)劃選擇第i個工件放在第j塊區(qū)域，且第i個工件只能放在1塊區(qū)域里，1塊區(qū)域只能放一個工件；同時默認(rèn)第1塊區(qū)域到第4塊區(qū)域構(gòu)成第一個扇形區(qū)域，依次可得到第二、三、四、五、六塊扇形區(qū)域。再根據(jù)重量和體積排序算法確定24個工件的具體放法。分析問題三：明確不滿足的情況有兩大種：（1）只考慮重量時，不滿足重量的要求（2）綜合考慮重量和體積時，分為以下3 種：五、模型建立與求解問題一為解決問題一，我們引入：建立模型目標(biāo)函數(shù):min=m約束條件： 有4個在同一扇區(qū) 6個扇區(qū) ？運用數(shù)學(xué)軟件Lingo對模型求解（運用數(shù)學(xué)軟件Ling

8、o所編的程序在附表一），得到結(jié)果：第一組工件：第一個扇形區(qū)：第6、8、18、19個工件第二個扇形區(qū)：第2、10、15、23個工件第三個扇形區(qū)：第11、13、14、21個工件第四個扇形區(qū)：第4、9、12、16個工件第五個扇形區(qū)：第5、7、17、24個工件第六個扇形區(qū)：第6、3、20、22個工件第二組工件：第一個扇形區(qū)：第1、9、14、22個工件第二個扇形區(qū)：第3、7、12、17個工件第三個扇形區(qū)：第11、13、16、21個工件第四個扇形區(qū)：第6、8、10、18個工件第五個扇形區(qū)：第5、15、23、24個工件第六個扇形區(qū)：第2、4、19、20個工件問題二我們假設(shè)相鄰兩個工件的體積之差不小于h建立模

9、型目標(biāo)函數(shù):min=h/m約束條件：運用數(shù)學(xué)軟件Lingo對模型求解（運用數(shù)學(xué)軟件Lingo所編的程序在附表一），得到結(jié)果：第一組工件：第一個扇形區(qū)：第7、23、1、6第個工件第二個扇形區(qū)：第21、17、20、3個工件第三個扇形區(qū)：第12、15、16、22個工件第四個扇形區(qū)：第2、11、14、9個工件第五個扇形區(qū)：第8、5、24、4、個工件第六個扇形區(qū)：第19、13、10、18個工件第二組工件：第一個扇形區(qū)：第2、11、6、9個工件第二個扇形區(qū)：第1、20、4、12個工件第三個扇形區(qū)：第5、23、13、21個工件第四個扇形區(qū)：第18、8、14、10個工件第五個扇形區(qū)：第15、7、16、19個工

10、件第六個扇形區(qū)：第17、22、3、24個工件問題三(一)只考慮重量時，不滿足條件：設(shè)第j扇區(qū)和第j+1扇區(qū)之間的重量和不滿足條件，只需更換其中一個扇區(qū)中某一工件。不妨設(shè)更換第j 個扇區(qū)中的一個工件，記該工件的重量為w , 這樣，更換后第j扇區(qū)的重量和為w(j+1)，則w(j+1)需滿足： £ e解得：即：令µ= g(j+1) g(j+1)則µ的范圍：設(shè)新工件的重量為w=µ+w，所以新工件的重量范圍為： (二) 同時考慮重量和體積時 當(dāng)體積滿足要求，重量不滿足要求時，在更換時，我們只需按上述(一)的方法只更換工件的重量而保持其體積不變。 當(dāng)重量滿足要求，體

11、積不滿足要求時，我們可以按照上述(一)的思想方法進(jìn)行更換，具體更換方法如下：我們假設(shè)第i 個工件和第i+1個工件之間的體積不滿足條件，只需更換i，i+1中某一工件。不妨更換第i+1個工件。這樣，更換后第i+1個工件的體積為v' ( i+1) ,則v' ( i+1)需滿足：解得：即：或當(dāng)重量和體積都不滿足要求時，我們可以分步更換：先不考慮體積，只考慮重量，則可以按上述(一)的方法將其重量更換為滿足重量要求的情形。然后再按照(二)-的方法將其體積更換為滿足體積要求的情形。若先不考慮重量，只考慮體積， (二)- 的方法將其體積更換為滿足體積要求的情形。然后再按照(二)- 的方法將其重

12、量更換為滿足重量要求的情形。六、對模型的評價與推廣1、本論文所建模型運用簡單的數(shù)學(xué)知識和數(shù)學(xué)軟件lingo求解，簡便易懂，具有較強(qiáng)的實踐意義。2、模型在建立過程中綜合考慮了重量、體積對工件排序的影響，使得所建模型更加優(yōu)化、更具有實踐意義。3、整數(shù)規(guī)劃得到的結(jié)果穩(wěn)定，只要給出基本的約束條件就能得到理想的結(jié)果，而約束條件只隨題目的基本情況而改變，便于修改。4、由于m與h所給的范圍較大，lingo程序在運行中，時間過長，故應(yīng)盡量減小 m與h的所給范圍。參考文獻(xiàn)           1唐煥文，數(shù)學(xué)模型引

13、論（第三版） ，北京：高等教育出版社， 2005。2運籌學(xué)教材編寫組，運籌學(xué)（修訂版），北京：清華大學(xué)出版社，1982。3汪曉銀，數(shù)學(xué)軟件與數(shù)學(xué)實驗，北京，科學(xué)出版社，2008。附表一模型程序:model:sets:gongjian/1.24/:g;qu/1.6/:w;paisheng(gongjian,qu):x;endsetsdata:g=348352347349347.5347330329329327.5329331.5348.5347346.5348347.5348333330332.5331.5331.5332;!g=358.5357.5355351355.5357341342340

14、344342.5343.5357.5355353.5356.5356352.5342.5344339.5341.5341345;enddatamin=m;for(qu(j):sum(gongjian(i):x(i,j)=4);for(gongjian(i):sum(qu(j):x(i,j)=1);for(qu(j):sum(gongjian(i):g(i)*x(i,j)=w(j);for(qu(j)|j#le#5:abs(w(j+1)-w(j)<m);abs(w(6)-w(1)<m;m<27.6;m>0.5;for(paisheng:bin(x);End模型結(jié)果:Glo

15、bal optimal solution found. Objective value: 0.5000000 Objective bound: 0.5000000 Infeasibilities: 0.5684342E-13 Extended solver steps: 378 Total solver iterations: 5017 Variable Value Reduced Cost M 0.5000000 0.000000 W( 1) 1357.000 0.000000 W( 2) 1357.500 0.000000 W( 3) 1357.000 0.000000 W( 4) 135

16、7.500 0.000000 W( 5) 1357.000 0.000000 W( 6) 1356.500 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 0.000000 X( 1, 3) 0.000000 0.000000 X( 1, 4) 0.000000 0.000000 X( 1, 5) 0.000000 0.000000 X( 1, 6) 1.000000 0.000000 X( 2, 1) 0.000000 0.000000 X( 2, 2) 1.000000 0.000000 X( 2, 3) 0.000000 0.0

17、00000 X( 2, 4) 0.000000 0.000000 X( 2, 5) 0.000000 0.000000 X( 2, 6) 0.000000 0.000000 X( 3, 1) 0.000000 0.000000 X( 3, 2) 0.000000 0.000000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 0.000000 0.000000 X( 3, 5) 0.000000 0.000000 X( 3, 6) 1.000000 0.000000 X( 4, 1) 0.000000 0.000000 X( 4, 2) 0.000000 0.0000

18、00 X( 4, 3) 0.000000 0.000000 X( 4, 4) 1.000000 0.000000 X( 4, 5) 0.000000 0.000000 X( 4, 6) 0.000000 0.000000 X( 5, 1) 0.000000 0.000000 X( 5, 2) 0.000000 0.000000 X( 5, 3) 0.000000 0.000000 X( 5, 4) 0.000000 0.000000 X( 5, 5) 1.000000 0.000000 X( 5, 6) 0.000000 0.000000 X( 6, 1) 1.000000 0.000000

19、X( 6, 2) 0.000000 0.000000 X( 6, 3) 0.000000 0.000000 X( 6, 4) 0.000000 0.000000 X( 6, 5) 0.000000 0.000000 X( 6, 6) 0.000000 0.000000 X( 7, 1) 0.000000 0.000000 X( 7, 2) 0.000000 0.000000 X( 7, 3) 0.000000 0.000000 X( 7, 4) 0.000000 0.000000 X( 7, 5) 1.000000 0.000000 X( 7, 6) 0.000000 0.000000 X(

20、8, 1) 1.000000 0.000000 X( 8, 2) 0.000000 0.000000 X( 8, 3) 0.000000 0.000000 X( 8, 4) 0.000000 0.000000 X( 8, 5) 0.000000 0.000000 X( 8, 6) 0.000000 0.000000 X( 9, 1) 0.000000 0.000000 X( 9, 2) 0.000000 0.000000 X( 9, 3) 0.000000 0.000000 X( 9, 4) 1.000000 0.000000 X( 9, 5) 0.000000 0.000000 X( 9,

21、6) 0.000000 0.000000 X( 10, 1) 0.000000 0.000000 X( 10, 2) 1.000000 0.000000 X( 10, 3) 0.000000 0.000000 X( 10, 4) 0.000000 0.000000 X( 10, 5) 0.000000 0.000000 X( 10, 6) 0.000000 0.000000 X( 11, 1) 0.000000 0.000000 X( 11, 2) 0.000000 0.000000 X( 11, 3) 1.000000 0.000000 X( 11, 4) 0.000000 0.000000

22、 X( 11, 5) 0.000000 0.000000 X( 11, 6) 0.000000 0.000000 X( 12, 1) 0.000000 0.000000 X( 12, 2) 0.000000 0.000000 X( 12, 3) 0.000000 0.000000 X( 12, 4) 1.000000 0.000000 X( 12, 5) 0.000000 0.000000 X( 12, 6) 0.000000 0.000000 X( 13, 1) 0.000000 0.000000 X( 13, 2) 0.000000 0.000000 X( 13, 3) 1.000000

23、0.000000 X( 13, 4) 0.000000 0.000000 X( 13, 5) 0.000000 0.000000 X( 13, 6) 0.000000 0.000000 X( 14, 1) 0.000000 0.000000 X( 14, 2) 0.000000 0.000000 X( 14, 3) 1.000000 0.000000 X( 14, 4) 0.000000 0.000000 X( 14, 5) 0.000000 0.000000 X( 14, 6) 0.000000 0.000000 X( 15, 1) 0.000000 0.000000 X( 15, 2) 1

24、.000000 0.000000 X( 15, 3) 0.000000 0.000000 X( 15, 4) 0.000000 0.000000 X( 15, 5) 0.000000 0.000000 X( 15, 6) 0.000000 0.000000 X( 16, 1) 0.000000 0.000000 X( 16, 2) 0.000000 0.000000 X( 16, 3) 0.000000 0.000000 X( 16, 4) 1.000000 0.000000 X( 16, 5) 0.000000 0.000000 X( 16, 6) 0.000000 0.000000 X(

25、17, 1) 0.000000 0.000000 X( 17, 2) 0.000000 0.000000 X( 17, 3) 0.000000 0.000000 X( 17, 4) 0.000000 0.000000 X( 17, 5) 1.000000 0.000000 X( 17, 6) 0.000000 0.000000 X( 18, 1) 1.000000 0.000000 X( 18, 2) 0.000000 0.000000 X( 18, 3) 0.000000 0.000000 X( 18, 4) 0.000000 0.000000 X( 18, 5) 0.000000 0.00

26、0000 X( 18, 6) 0.000000 0.000000 X( 19, 1) 1.000000 0.000000 X( 19, 2) 0.000000 0.000000 X( 19, 3) 0.000000 0.000000 X( 19, 4) 0.000000 0.000000 X( 19, 5) 0.000000 0.000000 X( 19, 6) 0.000000 0.000000 X( 20, 1) 0.000000 0.000000 X( 20, 2) 0.000000 0.000000 X( 20, 3) 0.000000 0.000000 X( 20, 4) 0.000

27、000 0.000000 X( 20, 5) 0.000000 0.000000 X( 20, 6) 1.000000 0.000000 X( 21, 1) 0.000000 0.000000 X( 21, 2) 0.000000 0.000000 X( 21, 3) 1.000000 0.000000 X( 21, 4) 0.000000 0.000000 X( 21, 5) 0.000000 0.000000 X( 21, 6) 0.000000 0.000000 X( 22, 1) 0.000000 0.000000 X( 22, 2) 0.000000 0.000000 X( 22,

28、3) 0.000000 0.000000 X( 22, 4) 0.000000 0.000000 X( 22, 5) 0.000000 0.000000 X( 22, 6) 1.000000 0.000000 X( 23, 1) 0.000000 0.000000 X( 23, 2) 1.000000 0.000000 X( 23, 3) 0.000000 0.000000 X( 23, 4) 0.000000 0.000000 X( 23, 5) 0.000000 0.000000 X( 23, 6) 0.000000 0.000000 X( 24, 1) 0.000000 0.000000

29、 X( 24, 2) 0.000000 0.000000 X( 24, 3) 0.000000 0.000000 X( 24, 4) 0.000000 0.000000 X( 24, 5) 1.000000 0.000000 X( 24, 6) 0.000000 0.000000附表二模型程序:model:sets:gongjian/1.24/:g,v;qu/1.6/:w;kuai/1.24/:;paisheng(gongjian,kuai):x;endsetsdata:g=348 352 347 349 347.5 347 330 329 329 327.5 329 331.5 348.5

30、347 346.5 348 347.5 348 333 330 332.5 331.5 331.5 332;!g=358.5357.5355351355.5357341342340344342.5343.5357.5355353.5356.5356352.5342.5344339.5341.5341345;v=101.5 102 105 105.5 106 104 94 98 100.5 98.5 98 99 104.5 105 107.5 104.5 104 104.5 97 97 99 98 96.5 94.5;!v=103103103103.51031029696.595.59795.1

31、96.5102.5103103.5103.5103.51049896.598969697;enddatamax=h/m;for(kuai(j): sum(gongjian(i):x(i,j)=1);for(gongjian(i): sum(kuai(j):x(i,j)=1);sum(kuai(j)|j#le#4: sum(gongjian(i):g(i)*x(i,j)=w(1);sum(kuai(j)|j#ge#5#and#j#le#8: sum(gongjian(i):g(i)*x(i,j)=w(2);sum(kuai(j)|j#ge#9#and#j#le#12: sum(gongjian(i):g(i)*x(i,j)=w(3);sum(kuai(j)|j#ge#13#and#j#le#16: sum(gongjian(i):g(i)*x(i,j)=w(4);sum(kuai(j)|j#ge#17#and#j#le#20: sum(gongjian(i):g(i)*x(i,j)=w(5);sum(kuai(j)|j#ge#21#and#j#le#24: sum(gongjian(i):g(i)*x(i,j)=w(6);abs(w(1)-w(2)<m;abs(w(3)-w(4)<m;abs(w(5)-w(6)&