數(shù)學建模經(jīng)典案例：最優(yōu)截斷切割問題

1、z建模案例：最優(yōu)截斷切割問題zz從一個長方體中加工出一個已知尺寸、位置預定的長方體（這兩個長方體的 對應表面是平行的），通常要經(jīng)過6次截斷切割設水平切割單位面積的費用是 垂直切割單位面積費用的r倍且當先后兩次垂直切割的平面（不管它們之間是 否穿插水平切割）不平行時，因調整刀具需額外費用e.試設計一種安排各面加工次序（稱“切割方式”）的方法，使加工費用最少zz1、假設水平切割單位面積的費用為 r，垂直切割單位面積費用為1;2、當先后兩次垂直切割的平面（不管它們之間是否穿插水平切割）不平行時, 調整刀具需額外費用e;3、第一次切割前，刀具已經(jīng)調整完畢，即第一次垂直切割不加入刀具調整費 用；4、每個

2、待加工長方體都必須經(jīng)過 6次截斷切割.三、模型的建立與求解設待加工長方體的左右面、前后面、上下面間的距離分別為a0、b0、c0 ,六個切割面分別位于左、右、前、后、上、下，將它們相應編號為M1、M2、M3、M4、M5、M6，這六個面與待加工長方體相應外側面的邊距分別為u1、u2、u3、u4、u5、u6這樣，一種切割方式就是六個切割面的一個排列，共有P66二720種切割方式當考慮到切割費用時，顯然有局部優(yōu)化準則：兩個平行待切割面中， 邊距較大的待切割面總是先加工.由此準則，只需考慮P62! 2! 2!90種切割方式即在求最少加工費用時,M5/u5M3c0M4uGMLZ/耐6M2A/ ul / a

3、0_/u2只需在90個滿足準則的切割序列中考慮不失一般性，設u1> u2, u3>u4, u5>u6,故只考慮M1在M2前、M3在M4前、M5在M6前的切割方式1、e=0的情況V25V27為簡單起見，先考慮e=0的情況構造如圖9-13的一個有向賦權網(wǎng)絡圖G(V,E) 為了表示切割過程的有向性，在網(wǎng)絡圖上加上坐標軸x, y,乙圖 9-13 G(V,E)圖G(V,E)的含義為：(1) 空間網(wǎng)絡圖中每個結點 Vi(xi,yi,zi)表示被切割石材所處的一個狀態(tài)頂點坐標xi、yi、zi分別代表石材在左右、前后、上下方向上已被切割的刀數(shù)例如：V24(2,1,2)表示石材在左右方向上已被

4、切割兩刀，前后方向上已被切一刀，上下方向上已被切兩刀，即面 M1、M2、M3、M5、M6均已被切割頂點V1(0,0,0)表 示石材的最初待加工狀態(tài)，頂點V27(2,2,2)表示石材加工完成后的狀態(tài).(2) G的弧(Vi,Vj )表示石材被切割的一個過程，若長方體能從狀態(tài) Vi經(jīng)一 次切割變?yōu)闋顟B(tài)Vj，即當且僅當xi+yi+zi+仁xj+yj+zj時，Vi(xi,yi,zi)到Vj(xj,yj,zj) 有弧(Vi,Vj)，相應弧上的權W(Vi,Vj)即為這一切割過程的費用.W(Vi,Vj)=(xj-xi) x(bixci)+(yj-yi)x(aiyi)+(zj-zi)x(aixbi)漢 r其中，

5、ai、bi、ci分別代表在狀態(tài)Vi時，長方體的左右面、上下面、前后面 之間的距離例如，狀態(tài) V5( 1，1, 0)，a5 = a0-u1,b5 = b0-u3,c5 = c0狀態(tài)V6(2，1, 0) W(V5, V6) = ( b0-u3) c0(3)根據(jù)準則知第一刀有三種選擇，即第一刀應切M1、M3、M5中的某個面，在圖中分別對應的弧為(V1,V2)，(V1,V4)，(V1,V10).圖G中從V1到V27的 任意一條有向道路代表一種切割方式從V1到V27共有90條有向道路，對應著所 考慮的90種切割方式.V1到V27的最短路即為最少加工費用，該有向道路即對應 所求的最優(yōu)切割方式實例：待加工長

6、方體和成品長方體的長、寬、高分別為10、145、19和3、2、 4,兩者左側面、正面、底面之間的距離分別為6、7、9,則邊距如下表：u1u2u3u4u5u66175569r=1 時，求得最短路為 V1 V10 V13 V22 V23 V26 V27，其權為 374 對應的最優(yōu)切割排列為 M5 M3 M6 M1 M4 M2，費用為374元 2、 e 0的情況當e=0時，即當先后兩次垂直切割的平面不平行時，需加調刀費e希望在圖9-13的網(wǎng)絡圖中某些邊增加權來實現(xiàn)此費用增加在所有切割序列中，四個垂直面的切割順序只有三種可能情況：情況一 先切一對平行面，再切另外一對平行面，總費用比e=0時的費用增加e

7、.情況二 先切一個，再切一對平行面，最后割剩余的一個，總費用比e=0時的費用增加2e情況三 切割面是兩兩相互垂直，總費用比e=0時的費用增加3e 在所考慮的90種切割序列中，上述三種情況下垂直切割面的排列情形，及在圖G中對應有向路的必經(jīng)點如下表：垂直切割面排列情 形有向路必經(jīng)點情況一（一）M1 M2 M3 M4(1,0,z),(2,0,z),(2,1,z)情況一（二）M3 M4 M1 M2(0,1,z),(0,2,z),(1,2,z)情況二（一）M3 M1 M2 M4(0,1,z),(1,1,z),(2,1,z)情況二(二) JM1 M3 M4 M2(1,0,z),(1,1,z),(1,2,z

8、)情況三（一）M1 M3 M2 M4(1,0,z),(1,1,z),(2,1,z)情況三（二）M3 M1 M4 M2(0,1,z),(1,1,z),(1,2,z)z=0,1,2我們希望通過在圖9-13的網(wǎng)絡圖中的某些邊上增加權來進行調刀費用增加 的計算，但由于網(wǎng)絡圖中的某些邊是多種切割序列所公用的對于某一種切割序列，需要在此邊上增加權e,但對于另外一種切割序列，就有可能不需要在此邊上增加權e,這樣我們就不能直接利用圖9-13的網(wǎng)絡圖進行邊加權這種方法來求 出最短路徑由上表可以看出，三種情況的情形（一）有公共點集 （2,1,z）|z=0,1,2，情形 （二）有公共點集（1,2,z）|z=0,1,

9、2且情形（一）的有向路決不通過情形（二）的公共點集，情形(二)的有向路也不通過情形(一)的公共點集所以可判斷出這兩部分是獨立的、互補的如果我們在圖G中分別去掉點集(1,2,z)|z=0,1,2和 (2,1,z)|z=0,1,2及與之相關聯(lián)的入弧，就形成兩個新的網(wǎng)絡圖，如圖H1和H 2.這兩個網(wǎng)絡圖具有互補性.對于一個問題來說，最短路線必存在于它們中的某一 個中.由于調整垂直刀具為3次時，總費用需增加3e,故我們先安排這種情況的權 增加值e,每次轉刀時，給其待切弧上的權增加 e增加e的情況如圖9-14中所示再 來判斷是否滿足調整垂直刀具為二次、一次時的情況，我們發(fā)現(xiàn)所增加的權滿足 另外兩類切割序列.綜合上述分析，我們將原網(wǎng)絡圖 G分解為兩個網(wǎng)絡圖H 1和H 2,并在指定邊 上的權增加e,然后分別求出圖H 1和H2中從V1到V27的最短路，最短路的權分 別為：d1,d2則得出整體的最少費用為：d = mi