建模工件安裝問(wèn)題.doc

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