數(shù)學(xué)建模經(jīng)典案例：最優(yōu)截?cái)嗲懈顔栴}

1、精選文檔建模案例：最優(yōu)截?cái)嗲懈顔栴}一、 問 題從一個(gè)長(zhǎng)方體中加工出一個(gè)已知尺寸、位置預(yù)定的長(zhǎng)方體（這兩個(gè)長(zhǎng)方體的對(duì)應(yīng)表面是平行的），通常要經(jīng)過6 次截?cái)嗲懈?設(shè)水平切割單位面積的費(fèi)用是垂直切割單位面積費(fèi)用的r倍.且當(dāng)先后兩次垂直切割的平面（不管它們之間是否穿插水平切割）不平行時(shí)，因調(diào)整刀具需額外費(fèi)用e.試設(shè)計(jì)一種支配各面加工次序（稱“切割方式”）的方法，使加工費(fèi)用最少.二、 假 設(shè)、假設(shè)水平切割單位面積的費(fèi)用為r，垂直切割單位面積費(fèi)用為1；、當(dāng)先后兩次垂直切割的平面（不管它們之間是否穿插水平切割）不平行時(shí)，調(diào)整刀具需額外費(fèi)用e；、第一次切割前，刀具已經(jīng)調(diào)整完畢，即第一次垂直切割不加入刀具調(diào)整費(fèi)

2、用；4 、每個(gè)待加工長(zhǎng)方體都必需經(jīng)過6次截?cái)嗲懈?三、 模型的建立與求解 設(shè)待加工長(zhǎng)方體的左右面、前后面、上下面間的距離分別為 a0、b0 、c0 ，六個(gè)切割面分別位于左、右、前、后、上、下，將它們相應(yīng)編號(hào)為M1、M2、M3、M4、M5、M6，這六個(gè)面與待加工長(zhǎng)方體相應(yīng)外側(cè)面的邊距分別為 u1、u2、u3、u4、u5、u6.這樣，一種切割方式就是六個(gè)切割面的一個(gè)排列，共有 種切割方式.當(dāng)考慮到切割費(fèi)用時(shí)，明顯有局部?jī)?yōu)化準(zhǔn)則：兩個(gè)平行待切割面中，邊距較大的待切割面總是先加工. 由此準(zhǔn)則,只需考慮 種切割方式.即在求最少加工費(fèi)用時(shí)，只需在90個(gè)滿足準(zhǔn)則的切割序列中考慮.不失一般性，設(shè)u1u2，u3

3、u4，u5u6，故只考慮M1在M2前、M3在M4前、M5在M6前的切割方式. 1、 e=0 的狀況 為簡(jiǎn)潔起見,先考慮e=0 的狀況.構(gòu)造如圖9-13的一個(gè)有向賦權(quán)網(wǎng)絡(luò)圖G(V,E).為了表示切割過程的有向性，在網(wǎng)絡(luò)圖上加上坐標(biāo)軸x，y，z. 圖9-13 G(V,E)圖G(V,E)的含義為： (1)空間網(wǎng)絡(luò)圖中每個(gè)結(jié)點(diǎn)Vi(xi,yi,zi)表示被切割石材所處的一個(gè)狀態(tài).頂點(diǎn)坐標(biāo)xi、yi、zi分別代表石材在左右、前后、上下方向上已被切割的刀數(shù).例如：V24(2,1,2) 表示石材在左右方向上已被切割兩刀，前后方向上已被切一刀，上下方向上已被切兩刀，即面M1、M2、M3、M5、M6均已被切割.

4、頂點(diǎn)V1(0,0,0) 表示石材的最初待加工狀態(tài)，頂點(diǎn)V27(2,2,2)表示石材加工完成后的狀態(tài). (2)G的?。╒i,Vj）表示石材被切割的一個(gè)過程，若長(zhǎng)方體能從狀態(tài)Vi經(jīng)一次切割變?yōu)闋顟B(tài)Vj，即當(dāng)且僅當(dāng)xi+yi+zi+1=xj+yj+zj時(shí)，Vi(xi,yi,zi)到Vj(xj,yj,zj)有弧(Vi,Vj)，相應(yīng)弧上的權(quán)W(Vi,Vj)即為這一切割過程的費(fèi)用. W(Vi,Vj)=(xj-xi)(bici)+(yj-yi)(aici)+(zj-zi)(aibi)r 其中，ai、bi、ci分別代表在狀態(tài)Vi時(shí)，長(zhǎng)方體的左右面、上下面、前后面之間的距離. 例如，狀態(tài)V5（1，1，0），a5

5、 = 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中的某個(gè)面，在圖中分別對(duì)應(yīng)的弧為( V1,V2)，(V1,V4)，(V1,V10). 圖G中從V1到V27的任意一條有向道路代表一種切割方式.從V1到V27共有90條有向道路，對(duì)應(yīng)著所考慮的90種切割方式.V1到V27的最短路即為最少加工費(fèi)用，該有向道路即對(duì)應(yīng)所求的最優(yōu)切割方式. 實(shí)例：待加工長(zhǎng)方體和成品長(zhǎng)方體的長(zhǎng)、寬、高分別為10、145、19 和3、2、4，兩者左側(cè)面、正面、底面之間的距離分別為6、7、9，則邊

6、距如下表： u1u2u3u4u5u66175569r=1時(shí)，求得最短路為V1V10V13V22V23V26V27，其權(quán)為374 對(duì)應(yīng)的最優(yōu)切割排列為M5M3M6M1M4M2，費(fèi)用為374元. 2、 e0的狀況 當(dāng)e0時(shí)，即當(dāng)先后兩次垂直切割的平面不平行時(shí)，需加調(diào)刀費(fèi)e.期望在圖9-13的網(wǎng)絡(luò)圖中某些邊增加權(quán)來實(shí)現(xiàn)此費(fèi)用增加.在全部切割序列中，四個(gè)垂直面的切割挨次只有三種可能狀況： <狀況一>先切一對(duì)平行面，再切另外一對(duì)平行面，總費(fèi)用比e=0時(shí)的費(fèi)用增加e. <狀況二>先切一個(gè)，再切一對(duì)平行面，最終割剩余的一個(gè)，總費(fèi)用比e=0時(shí)的費(fèi)用增加2e. <狀況三>切割

7、面是兩兩相互垂直，總費(fèi)用比e=0時(shí)的費(fèi)用增加3e. 在所考慮的90種切割序列中，上述三種狀況下垂直切割面的排列情形，及在圖G中對(duì)應(yīng)有向路的必經(jīng)點(diǎn)如下表：垂直切割面排列情形有向路必經(jīng)點(diǎn)狀況一 （一）M1M2M3M4(1,0,z),(2,0,z),(2,1,z)狀況一 （二）M3M4M1M2(0,1,z),(0,2,z),(1,2,z)狀況二 （一）M3M1M2M4(0,1,z),(1,1,z),(2,1,z)狀況二 （二）M1M3M4M2(1,0,z),(1,1,z),(1,2,z)狀況三 （一）M1M3M2M4(1,0,z),(1,1,z),(2,1,z)狀況三 （二）M3M1M4M2(0,1

8、,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ò)圖中的某些邊是多種切割序列所公用的.對(duì)于某一種切割序列，需要在此邊上增加權(quán)e，但對(duì)于另外一種切割序列， 就有可能不需要在此邊上增加權(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,2.且情形（一）的有向路決不通過情形（二）的公共點(diǎn)集，情形（二）的有向路也不通過情形（一）的公共點(diǎn)集.所以可推斷出這兩部

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