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

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

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

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

4、切割兩刀，前后方向上已被切一刀，上下方向上已被切兩刀，即面 M1、M2、M3、M5、M6均已被切割頂點(diǎn)V1(0,0,0)表 示石材的最初待加工狀態(tài)，頂點(diǎn)V27(2,2,2)表示石材加工完成后的狀態(tài).(2) G的弧(Vi,Vj )表示石材被切割的一個過程，若長方體能從狀態(tài) Vi經(jīng)一 次切割變?yōu)闋顟B(tài)Vj，即當(dāng)且僅當(dāng)xi+yi+zi+仁xj+yj+zj時，Vi(xi,yi,zi)到Vj(xj,yj,zj) 有弧(Vi,Vj)，相應(yīng)弧上的權(quán)W(Vi,Vj)即為這一切割過程的費(fèi)用.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ù)準(zhǔn)則知第一刀有三種選擇，即第一刀應(yīng)切M1、M3、M5中的某個面，在圖中分別對應(yīng)的弧為(V1,V2)，(V1,V4)，(V1,V10).圖G中從V1到V27的 任意一條有向道路代表一種切割方式從V1到V27共有90條有向道路，對應(yīng)著所 考慮的90種切割方式.V1到V27的最短路即為最少加工費(fèi)用，該有向道路即對應(yīng) 所求的最優(yōu)切割方式實(shí)例：待加工長

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

7、.情況二 先切一個，再切一對平行面，最后割剩余的一個，總費(fèi)用比e=0時的費(fèi)用增加2e情況三 切割面是兩兩相互垂直，總費(fèi)用比e=0時的費(fèi)用增加3e 在所考慮的90種切割序列中，上述三種情況下垂直切割面的排列情形，及在圖G中對應(yīng)有向路的必經(jīng)點(diǎn)如下表：垂直切割面排列情 形有向路必經(jīng)點(diǎn)情況一（一）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)絡(luò)圖中的某些邊上增加權(quán)來進(jìn)行調(diào)刀費(fèi)用增加 的計(jì)算，但由于網(wǎng)絡(luò)圖中的某些邊是多種切割序列所公用的對于某一種切割序列，需要在此邊上增加權(quán)e,但對于另外一種切割序列，就有可能不需要在此邊上增加權(quán)e,這樣我們就不能直接利用圖9-13的網(wǎng)絡(luò)圖進(jìn)行邊加權(quán)這種方法來求 出最短路徑由上表可以看出，三種情況的情形（一）有公共點(diǎn)集 （2,1,z）|z=0,1,2，情形 （二）有公共點(diǎn)集（1,2,z）|z=0,1,

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