1、數學建模截斷切割問題學號：1443205000041姓名：楊德升學號：1443205000108姓名：李春紅學號：1443205000088姓名：楊建明問題描述:某些工業部門（如貴重石材加工等）采用截斷切割的加工方式。這里“截斷切割”是指將物體沿某個切割平面分成兩部分。從一個長方體中加工出一個已知尺寸、位置預定的長方體（這兩個長方體的對應表面是平行的），通常要經過6次截斷切割。設水平切割單位面積的費用是垂直切割單位面積費用的r倍，且當先后兩次垂直切割的平面（不管它們之間是否穿插水平切割）不平行時，因調整刀具需額外費用e。試為這些部門設計一種安排各面加工次序（稱“切割方式”）的方法，使加工費用最

2、少。（由工藝要求，與水平工作臺接觸的長方體底面是事先指定的）詳細要求如下：1、需考慮的不同切割方式的總數。2、給出上述問題的數學模型和求解方法。3、試對某部門用的如下準則作出評價：每次選擇一個加工費用最少的待切割面進行切割。4、對于e=0的情形仃無簡明的優化準貝匕5、用以下實例數據驗證你的方法：待加工長方體和成品長方體的長、寬、高分別為10、14.5、19和3、2、4,二者左側面、正面、底面之間的距離分別為6、7、9（單位均為厘米）,垂直切割費用為每平方厘米1元，r和e的數據有以下4組：ar=1e=0;br=1.5e=0;cr=8e=0;dr=1.52<=e<=15;對最后一組數據

3、應給出所有最優解，并進行討論。解：（1）對于計算不同的切割方式總數，經過分析，能夠用排列組合的知識來解決這個問題。我們對分別位于前、后、左、右、上、下的切割面進行編號，其相應的編號分別為1M,2M,M3,M4,M5,M6,然而每一種切割方式都是對這6個切割面的一個排列方式，所以總共就6!=720種排列方式。但是相繼切割一對平行面時，交換切割次序，不影響切割費用，把費用相同的一項歸到一類，最終的切割總數為：720-3x5!+3x4!-3!=426種（4）（5）符號說明：a0,b0,c0分別表示待加工長方體的長、寬、高。a,b,c分別表示成品長方體的長、寬、高。1M、2M、3M、4M、5M、6M表

4、示左、右、前、后、上、下，1u,2u,3u,4u,5u,6u分別表示待加工長方體與成品長方體。有向圖頂點是vi,坐標為（xi,yi,zi）,xi,yi,zi分別代表側面（左右面）、正（前后面）、水平面（上下面）的切割次數。其中xi,yi,zi都在0.1.2中取值。ai,bi,ci分別表示在iv時，長方體左右、前后、上下面的距離。有向弧(vi,vj)代表一個從vi至vj的切割步驟，模型建立：考慮不同切割方式的總數，設待加工長方體的左右面、前后面、上下面問的距離分別為a。、b0、cl六個切割面分別位于左、右、前、后、上、下，將它們相應編號為1M、2M、3M、4M、5M、6M,這六個面與待加工長方體

5、相應外側面的邊距分別為1u、2u、3u、4u、6u、5uo這樣，一種切割方式就是六個切割面的一個排列，共有6!=720種切割方式當考慮到切割費用時，顯然有局部優化準則：兩個平行待切割面中，邊距較大的待切割面總是先加工。由此準則，只需考慮6!/(2!x2!x2!)=90種切割方式。即在求最少加工費用時，只需在90個滿足準則的切割序列中考慮。不失一般性，設1u2u13u4u15u6u,故只考慮1M在2M前、3M在4M前、6M在5M前的切割方式。H、根據不同情況建立數學模型1、e=0的情況為簡單起見，先考慮e=0的情況。構造如圖所示的一個有向賦權網絡圖G(V,E)為了表示切割過程的有向性，在網絡圖上

6、加上坐標軸x,y,z。BV%忡G (V, E)圖G(V,E)勺含義為：(1)、空間網絡圖中每個結點Vi(xi,yi,zi)表示被切割石材所處的一個狀態。頂點坐標ix,yi,zi分別代表石材在左右、前后、上下方向上已被切割的刀數。頂點1V(0,0,0)表示石材的最初待加工狀態，頂點27V(2,2,2)表示石材加工完成后的狀態。(2)、G的弧(Vi,Vj)表示石材被切割的一個過程，若長方體能從狀態Vi經一次切割變為狀態Vj,即當且僅當xi+yi+zi+1=xj+yj+z時，Vi(xi,yi,z)到Vj(xi,yi,zD有弧(Vi,Vj),相應弧上的權W(Vi,Vj)即為這一切割過程的費用。對于任意

7、相鄰狀態的點之間的弧的權值公式如下：w(xm)=0一與令父%+(力一月)(分%+(4一號)(勺乂峪,其中，ai、bi、ci分別代表在狀態Vi時，長方體的左右面、上下面、前后面之間的距離。(3)、根據局部優化準則知第一刀有三種選擇，即第一刀應切1M、3M、6M中的某個面，在圖中分別對應的弧為(1V,2V)(1V,4V)(1V,10V),圖G中從1V到27V的任意一條有向道路代表一種切割方式。從1V到27V共有90條有向道路，對應著所考慮的90種切割方式。1V到27V的最短路即為最少加工費用，該有向道路即對應所求的最優切割方式。2、e!=0的情況當e!=0時，即當先后兩次垂直切割的平面不平行時，需

8、加調刀費e。希望在上面的網絡圖中某些邊增加權來實現此費用增加。在所有切割序列中，四個垂直面的切割順序只有三種可能情況(不管它們之間是否穿插水平切割)：情況一先切一對平行面，再切另外一對平行面，總費用比e=0時的費用增加e。情況二先切一個，再切一對平行面，最后割剩余的一個，總費用比e=0時的費用增加2e。情況三切割面是兩兩相互垂直，總費用比e=0時的費用增加3e。在所考慮的90種切割序列中，上述三種情況下垂直切割面的排列情形，及在圖G中對應有向路的必經點如下表（z=0,1,2）:垂直切割面排列情形有1可路必經點情況一（一）1234(1,0,z),(2,0»z),(2,l,z)情況一（二

9、）(0,1,2,z),(1,2,z)情況二（-）(0,Lz),(LLz),(2,1")情況二（二）M-M-Af-Af.(1,0.z),(1,Lz),(1,2,z)情況三（一）(1,0,z),(1.ltz),(2.lfz)情況三（-）A/、-(0.1,z)；(l,l,z).(1,2,z)我們希望通過在上面的網絡圖中的某些邊上增加權來進行調刀費用增加的計算，但由于網絡圖中的某些邊是多種切割序列所公用的。對于某一種切割序列，需要在此邊上增加權e,但對于另外一種切割序列，就有可能不需要在此邊上增加權e,這樣我們就不能直接利用上面的網絡圖進行邊加權這種方法來求出最短路徑。由上表可以看出，三種情

10、況的情形（一）有公共點集（2,1,z）|z=0,1,2,情形（二）有公共點集（1,2,z）|z=0,1,2o且情形（一）的有向路決不通過情形（二）的公共點集，情形（二）的有向路也不通過情形（一）的公共點集。所以可判斷出這兩部分是獨立的、互補的。.如果我們在圖G中分別去掉點集（1,2,z）|z=0,1,2和（2,1,z）|z=0,1,2及與之相關聯的入弧，就形成兩個新的網絡圖，如圖H1和H2。這兩個網絡圖具有互補性。對于一個問題來說，最短路線必存在于它們中的某一個中。由于調整垂直刀具為3次時，總費用需增加3e,故我們先安排這種情況的權增加值e,每次轉刀時，給其待切弧上的權增加e。增加e的情況如下

11、圖中所示。再來判斷是否滿足調整垂直刀具為二次、一次時的情況，我們發現所增加的權滿足另外兩類切割序列。綜合上述分析，我們將原網絡圖G分解為兩個網絡圖H1和H2,并在指定邊上的權增加e,然后分別求出圖1H和2H中從1V到27V的最短路，最短路的權分別為：d1,d2.則得出整體的最少費用為：d=min（d1,d2），相應付圖求出的授優切割序列即為其對應的最短路徑圖1H012圖2H田、對“每次選擇一個加工費用最少的待切割面進行切割”這個準則的好壞進行評價評價的標準：最佳切割方式可以不唯一，可是最佳加工費用應等于按照之前的模型求解出的最少加工費用。即：若準則精選出的不同切割方式有很多，而相應的加工費卻不

12、全相同，則其不具備優化準則的基本屬性。同樣，即使精選出的切割方式唯一，但加工費卻非真正意義上的最小，則準則也無最優性可言。根據實例中的數據，在局部最優準則的前提下，假定e=0,r=1時，求出的最佳加工費用為374元，這與用上面的模型求解出的結果相同。假定e=2,r=1.5時，求出的最佳加工費用為490元，這個與用上面的模型求解出的結果443.5不相同,并且比上面的結果大。因此，“每次選擇一個加工費用最少的待切割面進行切割”不能作為最佳優化準則使用，但當e=0忖可以采用這個準則，而當e!=0時不能采用這個準則。Matlab程序fileEditlextQp©ellTols口叱ugdesk

13、topMtfndowHelp-仙+1+JJ,聯啜jQfunction:yl.y2=qigel(r,e)a=TO,14.，19;6,7,9：L軋5,6：3 9 0 12 31 1- 1nn=1;m=z<ros<720,6):%UNTITLEDSuaiiaryofthisfunctiongoeshere、Detailedexplanationeceshersforil=l;6fori2=L6fori3-l：6fori4=l6fori5=l;6fori&=1：6ifili2,!i2-«i31i3il|i4«i51il-i3il-i4lil=i&|i2=

14、iJ|ii=i31i3=i5break:endb-Zi1,i2ti3±i4,i5>iE：ifispl(bl-lk=k+1;ee(a,b3c)；muIk,Jl-b:endend«ndendendend«ndi2=1：foril-1：kif(il)=miniaj;*1(12)11：12-12+1:functiony1,y2=qiegel(r,e)a=10,14.5,19;6,7,9;1,5,5,6;k=0;nn=1;mm=zeros(720,6);%UNTITLEDSummaryofthisfunctiongoeshere%Detailedexplanation

15、goesherefori1=1:6fori2=1:6fori3=1:6fori4=1:6fori5=1:6fori6=1:6ifi1=i2|i2=i3|i3=i4|i4=i5|i1=i3|i1=i4Ii1=i5|i2=i4|i2=i5|i3=i5break;endb=i1,i2,i3,i4,i5,i6;ifispl(b)=1k=k+1;m(l=fee(a,b,c);mm(k,;)=b;endendendendendendendi2=1;fori1=1:kifm(i1)=min(m);m1(i2)=i1;i2=i2+1;endendy1=min(m);y2=mm(m1endfunctionx4=

16、ispl(x)x3=1;forx1=1:5ifx(x1)-x(6)=0x3=0;endendx4=x3;endfunctions=fee(a,b,r,e)c=b;fori=1:6switchb(i)case1b(i尸a(1,2)*a(1,3);a(1,1)=a(1,1)-a(2,1);case 2 b(i)=a(1,2)*a(1,3);a(1,1)=a(1,1)-a(3,1);case 3 b(i)=a(1,2)*a(1,3);a(1,2)=a(1,2)-a(2,2);case 4 b(i)=a(1,2)*a(1,3);a(1,2)=a(1,2)-a(3,2);case 5 b(i)=a(1,2)*a(1,3);a(1,3)=a(1,3)-a(2,3);cas