建模工件安裝問題.doc

作業(yè)三：工件的安裝與排序問題（鐘建忠，汪靈枝，劉琳嵐）摘要：本文以實(shí)際工件的安裝為背景，討論了工件的排序問題。通過認(rèn)真分析工件安裝時的工藝要求，針對相鄰扇區(qū)重量和的差不大于一定值的限制條件，考慮各扇區(qū)重量和的值波動范圍較小和較大的兩種情況，分別建立了模型。模型I主要是根據(jù)對工件的重量的要求為約束條件，以及借助0-1變量Xij（序列號為i的工件放入J區(qū)間），建立了規(guī)劃模型I 。約束條件為相鄰區(qū)間的重量和不超過一個定值m.借助軟件進(jìn)行求解滿足條件的解。問題二是按重量和體積進(jìn)行工件排序。建立模型二；定義0-1變量Z（I,k）（表示序列號為i的工件放入第K個位置）。約束條件為（）相鄰區(qū)間的重量和不超過一個定值m ；（）相鄰的工件體積之差不小于一定值p。借助軟件進(jìn)行求解。問題三。當(dāng)無法通過內(nèi)部調(diào)試來滿足要求時，我們詳細(xì)討論了更換新工件的各種情況，并提出了具體的解決方案，給出了更換新工件重量和體積的范圍。如： 當(dāng)被更換工件的重量為時，新工件的重量的范圍： 當(dāng)被更換工件的體積為時，新工件的體積的范圍： 建立的模型能有效的解決工件的安裝和排序問題。對實(shí)際運(yùn)用具有指導(dǎo)意義。3.1問題的重述3.1.1 問題的由來由于工件的重量和體積不同，安裝時需要按工藝要求重新排序。3.1.2 問題的要求1）設(shè)備的24個工件均勻分布在等分成六個扇形區(qū)域的一圓盤的邊緣上，放在每個扇形區(qū)域的4個工件總重量與相鄰區(qū)域的4個工件總重量之差不允許超過一定值（如4g）。 2）.工件的排序不僅要對重量差有一定的要求，還要滿足體積的 當(dāng)工件確實(shí)不滿足上述要求時，允許更換少量工件。要求，即兩相鄰工件的體積差應(yīng)盡量大，使得相鄰工件體積差不小于一定值（如3 ）；3）當(dāng)工件確實(shí)不滿足上述要求時，允許更換少量工件3.1.3問題的提出請按上述要求給出：問題時，1按重量排序算法； 問題2按重量和體積排序算法； 問題3當(dāng)工件不滿足要求指出所更換工件及新工件的重量和體積值范圍，并輸出排序結(jié)果。 請按下面兩組工件數(shù)據(jù)（重量單位：g ，體積單位： ），進(jìn)行實(shí)時計算： 序號重量體積序號重量體積1348101.51358.510323521022357.5103334710533551034349105.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.59820330972034496.521332.59921339.59822331.59822341.59623331.596.523341962433294.524345973.2基本假設(shè)模型一的假設(shè)；1）24片葉片均勻分布在圓盤上。2）不考慮每個象限內(nèi)的排序。3）不考慮葉片的體積等其他因素。模型二的假設(shè)；（1）24片葉片均勻分布在圓盤上。（2）葉片排序不僅要保證重量差，兩相鄰葉片的體積差因盡量大，使相鄰的葉片體積差不小于一定值。（3）只要滿足重量差。體積差即可。不考慮其他約束條件，無需考慮最優(yōu)的排序方案。3.3符號的約定1) xij-表第i件工件是否在第j扇區(qū)上，在為1，不在為0；2）Mj表示第j扇區(qū)的總重量。mi表示序列號為i的重量。3) 表示相鄰扇區(qū)的總重量之差不超過的定值4）表示相鄰工件的體積之差不小于的定值5）Z(i，k)表示將序列號為i的工件放入第k個位置。6)Mj表示第J區(qū)間的總重量。Mi表示序列號為i的重量。7)Vi表示序列號為i的體積3.4問題的分析3.4.1 問題的分析問題一：針對問題一按工件的重量排序的算法。題目要求每個相鄰的象限的總重量差值不能超過某個數(shù)值（m）但主要問題是對工件的安排如何將這些工件分配到各個象限，此時我們引入0-1變量來確定第幾個工件是否放到第幾象限，最后通過一些約束條件來建立規(guī)劃模型即可進(jìn)行求解。問題二：在考慮重量排序的情況下，我們還必須使得相鄰的兩個工件的體積相差不小于一個定值。定義0-1規(guī)劃；Z(i，k)表示將i序列號的工件放入k位置，第一對重量條件進(jìn)行約束|Mj-Mj+1|=得出滿足約束條件的排序解。列出一組滿足排序的排序法進(jìn)行驗(yàn)證。問題三：考慮三種情況下的更換條件；1只考慮重量時，不滿足條件；2同時考慮重量和體積時；（1）重量不滿足；（2）體積不滿足；3重量和體積都不滿足要求時；用相鄰工件的體積之差不小于一定值，相鄰區(qū)間重量和不大于一定值進(jìn)行約束。得出更換工件的范圍。3.5模型的建立與求解（1）模型I 規(guī)劃模型 本模型通過對已知條件各個象限的總重量的要求的分析給出了對重量的約束條件，并且引進(jìn)了0-1變量，進(jìn)而建立了模型I。(2)模型II 規(guī)劃模型 本模型通過對已知條件各個象限的總重量的要求的分析給出了對重量的約束條件和相鄰工件體積差的約束條件。引入0-1變量。3.5.1問題一的分析與求解1 對每個象限的總質(zhì)量的差的取值的分析由已知條件要求相鄰的每個象限的總重量不得超過一個定值m可得出一個約束條件：（1） 每個相鄰象限工件總重量的約束條件： Mj-Mj+1 (j=1,2,3,4,5) M6-M1 2對每個工件被放到第幾象限的分析（1） 首先要引進(jìn)一個0-1變量 （j=1,2,3,4,5,6）扇區(qū)工件重量 123456m1=1m2=1mi=1m24=1=4=4=4=4=4=4(2)由于每個工件都要放到其中一個象限中去，為了確保滿足上述條件則有以下式子成立 =1(3)由已知條件有總共有6個象限每個象限要有4個工件。為確保滿足上述條件則有以下式子成立 =4 （j=1,2,3,4,5,6）3 模型I一 模型的建立按重量排序算法可以建立模型I條件：（1）每個相鄰象限的工件的總重量的差的約束條件： Mj-Mj+1 (j=1,2,3,4,5) M6-M1 (2)0-1變量的條件： =1 = 1（j=1,2,3,4,5,6）二 模型的求解。 使用Lingo軟件，對模型I進(jìn)行求解（具體程序見附錄）三模型的結(jié)果分析；令=4得到其中之一排序如下表所示一二三四五六第一組工件；序號重量序號重量序號重量序號重量序號重量序號重量334743495347.56 347134823521132912331.57330/8329932910327.51634817347.51834813348.51434715346.5193332033021332.522331.523331.524332每象限的重量之和相差2.5第二組工件；令=4得到其中之一排序如下表所示一二三四五六第一組工件；序號重量序號重量序號重量序號重量序號重量序號重量22341.52357.51358.518 352.5335519342.51735663574341/834293401034416356.5734111342.513357.55355.515353.52334121339.512343.520339.52434514355相鄰象限的重量和之差為0.53.5.2問題二的分析與求解1對相鄰工件體積的差值的分析2對相鄰扇區(qū)重量的差值的分析3模型II一 模型的建立按重量和體積的排法可建立模型II定義0-1變量；Z(i，k)= 0 1 將序列號為i的工件放入第k個位置。條件：=1 Z(i,k)=1(j=1.24)體積差約束條件；當(dāng)k為1-23是；|Z(i,k)*V(i)- Z(i,k+1)*V(i)|= (i=124)當(dāng)k為24是；|Z(i,24)*V(i)- Z(i,1)*V(i)|= 重量差約束條件；|-|=(n=15)|-|=二 模型的求解 用lingo軟件進(jìn)行求解三 模型II結(jié)論第一組排序；一二三四五六第一組工件；序號體積序號體積序號體積序號體積序號體積序號體積210214105610412 991101.55106199721992494.5310522982396.515107.54105.513104.58981710418104.51098.511989100.516104.52097794重量和13591357.51356.51355.513571357第二組排序；（最小體積差為4.5.扇區(qū)重量差為2）一二三四五六第二組工件；序號體積序號體積序號體積序號體積序號體積序號體積1103210331034 103.55103.56102896.5995.510971195.11296.57961410315103.516103.517103.51810413102.52096.5219822962396249719983.5.3對問題三的分析與求解1只考慮重量時，不滿足條件；2同時考慮重量和體積時；（1）重量不滿足；（2）體積不滿足；3重量和體積都不滿足要求時；一 模型的建立(一)只考慮重量時，不滿足條件：設(shè)第扇區(qū)和第扇區(qū)之間的重量和不滿足條件（與扇區(qū)相鄰, 與扇區(qū)相鄰，其重量分別為,），只需更換其中一個扇區(qū)中某一工件。不妨設(shè)更換第 個扇區(qū)中的一個工件，記該工件的重量為, 這樣，更換后第扇區(qū)的重量和為，則需滿足： | | 解得： + + 即： 令 = 則 的范圍： 設(shè)新工件的重量為=+，所以新工件的重量范圍為： （二）同時考慮重量和體積時 當(dāng)體積滿足要求，重量不滿足要求時，在更換時，我們只需按上述(一)的方法只更換工件的重量而保持其體積不變。 當(dāng)重量滿足要求，體積不滿足要求時，我們可以按照上述(一)的思想方法進(jìn)行更換，具體更換方法如下： 我們假設(shè)第個工件和第個工件之間的體積不滿足條件（與工件相鄰, 與 工件相鄰，其體積分別為,），只需更換，中某一工件。不妨更換第 個工件。 這樣，更換后第個工件的體積為 ,則需滿足： | | 解得： + 或 + 或 即： 或 （三）當(dāng)重量和體積都不滿足要求時，我們可以分步更換： 先不考慮體積，只考慮重量，則可以按上述(一)的方法將其重量更換為滿足重量要求的情形。然后再按照(二)的方法將其體積更換為滿足體積要求的情形。 若先不考慮重量，只考慮體積， (二)- 的方法將其體積更換為滿足體積要求的情形。然后再按照(二)- 的方法將其重量更換為滿足重量要求的情形。 三 對模型結(jié)論的分析當(dāng)工件不滿足要求指出所更換工件及新工件的重量和體積值范圍時有如下結(jié)果； 當(dāng)被更換工件的重量為時，新工件的重量的范圍： 當(dāng)被更換工件的體積為時，新工件的體積的范圍： 六模型的評價與推廣1模型的優(yōu)點(diǎn)：（1）推廣容易。模型一和二運(yùn)用數(shù)學(xué)軟件找出可行方案比人工推算簡便，有較強(qiáng)的推廣價值。（2） 實(shí)用性強(qiáng)。便于準(zhǔn)確的按要求安裝。（3） 條理清晰。2模型的缺點(diǎn)：（1）模型一只考慮重量約束。模型二只考慮葉片重量和體積對葉片進(jìn)行排序。與實(shí)際使用的排序有一定的差別。七參考文獻(xiàn)1.數(shù)學(xué)建模案例分析 中國水利水電出版社2.數(shù)學(xué)建模教程 江蘇教育出版社3.運(yùn)籌學(xué) 高等教育出版社4.數(shù)學(xué)模型 高等教育出版社八附錄第一問：第一組數(shù)據(jù)：model:sets:yuanjian/1.24/:X;qu/1.6/:V;links(qu,yuanjian):Y;endsetsfor(qu(i):sum(yuanjian(j):Y(i,j)=4);for(yuanjian(j):sum(qu(i):Y(i,j)=1);for(qu(i):V(i)=sum(yuanjian(j):X(j)*Y(i,j);for(qu(i)|i #lt# 6:(V(i)-V(i+1)=-m);V(1)-V(6)=-m;sum(links:Y)=24;for(links:bin(Y);data:m=0.5;X=ole(F:Book1.xls,weigh1);enddataend第二問： model:sets:yuanjian/1.24/:V;xuhou/1.24/:;paixu(yuanjian,xuhou):Y;endsetsfor(yuanjian(i):sum(xuhou(j):Y(i,j)=1);for(xuhou(j):sum(yuanjian(i):Y(i,j)=1);abs(sum(paixu(i,j)|j #lt# 24 :Y(i,j)*V(i)-sum(paixu(i,j)|j #lt# 23 :Y(i,j+1)*V(i)=P;abs(sum(yuanjian(i):Y(i,24)*V(i)-sum(yuanjian(i):Y(i,1)*V(i)=P;for(paixu(i,j):bin(Y(i,j);data:P=3;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;enddataend第一組數(shù)據(jù)運(yùn)行結(jié)果： P=3， Y( 1, 6) 1.000000 Y( 2, 24) 1.000000 Y( 3, 8) 1.000000 Y( 4, 12) 1.000000 Y( 5, 15) 1.000000 Y( 6, 13) 1.000000 Y( 7, 1) 1.000000 Y( 8, 17) 1.000000 Y( 9, 9) 1.000000 Y( 10, 20) 1.000000 Y( 11, 16) 1.000000 Y( 12, 5) 1.000000 Y( 13, 11) 1.000000 Y( 14, 10) 1.000000 Y( 15, 21) 1.000000 Y( 16, 23) 1.000000 Y( 17, 18) 1.000000 Y( 18, 22) 1.000000 Y( 19, 19) 1.000000 Y( 20, 14) 1.000000 Y( 21, 7) 1.000000 Y( 22, 3) 1.000000 Y( 23, 4) 1.000000 Y( 24, 2) 1.000000model:sets:yuanjian/1.24/:V;xuhou/1.24/:;paixu(yuanjian,xuhou):Y;endsetsfor(yuanjian(i):sum(xuhou(j):Y(i,j)=1);for(xuhou(j):sum(yuanjian(i):Y(i,j)=1);abs(sum(paixu(i,j)|j #lt# 24 :Y(i,j)*V(i)-sum(paixu(i,j)|j #lt# 23 :Y(i,j+1)*V(i)=P;abs(sum(y