上傳人：5***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：雷**（實(shí)名認(rèn)證）

IP屬地：湖北

IP屬地：湖北 上傳時(shí)間：2021-11-10 格式：DOC 頁數(shù)：10 大?。?10KB 積分：30 舉報(bào) 版權(quán)申訴

1、 數(shù)學(xué)建模 截?cái)嗲懈顔栴} 學(xué)號(hào)：1443205000041 姓名： 楊德升 學(xué)號(hào)：1443205000108 姓名： 李春紅 學(xué)號(hào)：1443205000088 姓名： 楊建明問題描述：某些工業(yè)部門（如貴重石材加工等）采用截?cái)嗲懈畹募庸し绞?。這里“截?cái)嗲懈睢笔侵笇⑽矬w沿某個(gè)切割平面分成兩部分。從一個(gè)長方體中加工出一個(gè)已知尺寸、位置預(yù)定的長方體（這兩個(gè)長方體的對應(yīng)表面是平行的），通常要經(jīng)過6次截?cái)嗲懈睢?#160;設(shè)水平切割單位面積的費(fèi)用是垂直切割單位面積費(fèi)用的r倍，且當(dāng)先后兩次垂直切割的平面(不管它們之間是否穿插水平切割)不平行時(shí)，因調(diào)整刀具需額外費(fèi)用e。 試為這些部門設(shè)計(jì)一種安排各面

2、加工次序（稱“切割方式”）的方法，使加工費(fèi)用最少。（由工藝要求，與水平工作臺(tái)接觸的長方體底面是事先指定的）詳細(xì)要求如下： 1、需考慮的不同切割方式的總數(shù)。 2、給出上述問題的數(shù)學(xué)模型和求解方法。 3、試對某部門用的如下準(zhǔn)則作出評價(jià)：每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割。 4、對于e=0=的情形有無簡明的優(yōu)化準(zhǔn)則。 5、用以下實(shí)例數(shù)據(jù)驗(yàn)證你的方法：待加工長方體和成品長方體的長、寬、高分別為10、14.5、19和3、2、4，二者左側(cè)面、正面、底面之間的距離分別為6、7、9（單位均為厘米）。垂直切割費(fèi)用為每平方厘米1元，r和e的數(shù)據(jù)有以下4組：

3、 a r = 1 e = 0; b r = 1.5 e = 0;c r = 8 e = 0; d r = 1.5 2<= e<=15;=££ 對最后一組數(shù)據(jù)應(yīng)給出所有最優(yōu)解，并進(jìn)行討論。  解： （1）對于計(jì)算不同的切割方式總數(shù)，經(jīng)過分析，能夠用排列組合的知識(shí)來解決這個(gè)問題。我們對分別位于前、后、左、右、上、下的切割面進(jìn)行編號(hào)，其相應(yīng)的編號(hào)分別為1M，2M，M3，M4，M5，M6，然而每一種切割方式都是對這6個(gè)切割面的一個(gè)排列方式，所以總共就6！=720種排列方式。 但是相繼切割一對平行面時(shí)，交換切割次序，不影響

4、切割費(fèi)用，把費(fèi)用相同的一項(xiàng)歸到一類，最終的切割總數(shù)為： 720-3x5!+3x4!-3!=426種(2) (3)(4)(5) 符號(hào)說明： a0,b0,c0分別表示待加工長方體的長、寬、高。  a,b,c分別表示成品長方體的長、寬、高。 1M、2M、3M、4M、5M、6M表示左、右、前、后、上、下， 1u,2u,3u,4u,5u,6u分別表示待加工長方體與成品長方體。  有向圖頂點(diǎn)是vi，坐標(biāo)為（xi,y i,z i），xi,y i,z i分別代表側(cè)面（左右面）、正(前后面）、水平面（上下面）的切割次數(shù)。其中xi,y i,z i都在0.1.2中取值。a i,bi,c i分別表

5、示在iv時(shí)，長方體左右、前后、上下面的距離。 有向?。╲i,v j）代表一個(gè)從vi至v j的切割步驟， 模型建立： 考慮不同切割方式的總數(shù) ，設(shè)待加工長方體的左右面、前后面、上下面間的距離分別為a0、b0、c0。六個(gè)切割面分別位于左、右、前、后、上、下，將它們相應(yīng)編號(hào)為1M、2M、3M、4M、5M、6M，這六個(gè)面與待加工長方體相應(yīng)外側(cè)面的邊距分別為1u、2u、3u、4u、6u、5u。這樣，一種切割方式就是六個(gè)切割面的一個(gè)排列，共有6！=720=種切割方式。當(dāng)考慮到切割費(fèi)用時(shí)，顯然有局部優(yōu)化準(zhǔn)則：兩個(gè)平行待切割面中，邊距較大的待切割面總是先加工。 由此準(zhǔn)則,只需考慮

6、6！/(2!x2!x2!)=90種切割方式。即在求最少加工費(fèi)用時(shí)，只需在90個(gè)滿足準(zhǔn)則的切割序列中考慮。不失一般性，設(shè)1u 2u³、3u 4u³、5u 6u，故只考慮1M在2M前、3M在4M前、6M在5M前的切割方式。   、根據(jù)不同情況建立數(shù)學(xué)模型 1、e=0的情況  為簡單起見,先考慮e=0的情況。構(gòu)造如圖所示的一個(gè)有向賦權(quán)網(wǎng)絡(luò)圖G(V,E)。為了表示切割過程的有向性，在網(wǎng)絡(luò)圖上加上坐標(biāo)軸x，y，z。  圖G(V,E)的含義為：  (1)、空間網(wǎng)絡(luò)圖中每個(gè)結(jié)點(diǎn)Vi（xi,y i,z i）表示被切割石材

7、所處的一個(gè)狀態(tài)。頂點(diǎn)坐標(biāo)ix，y i, z i分別代表石材在左右、前后、上下方向上已被切割的刀數(shù)。頂點(diǎn)1V(0,0,0)表示石材的最初待加工狀態(tài)，頂點(diǎn)27V(2,2,2)表示石材加工完成后的狀態(tài)。  (2)、G的弧（Vi , V j）表示石材被切割的一個(gè)過程，若長方體能從狀態(tài)Vi經(jīng)一次切割變?yōu)闋顟B(tài)V j，即當(dāng)且僅當(dāng)xi+y i+z i+1= x j +y j+z j時(shí)，Vi（xi,y i, z i）到V j（xi,y i, z i）有?。╒i , V j），相應(yīng)弧上的權(quán)W（Vi , V j）即為這一切割過程的費(fèi)用。對于任意相鄰狀態(tài)的點(diǎn)之間的弧的權(quán)值公式如下： ()()()(

8、)()() -´+-´ 其中，a i、b i、c i分別代表在狀態(tài)Vi時(shí)，長方體的左右面、上下面、前后面之間的距離。  (3)、根據(jù)局部優(yōu)化準(zhǔn)則知第一刀有三種選擇，即第一刀應(yīng)切1M、3M、6M中的某個(gè)面，在圖中分別對應(yīng)的弧為(1V,2V)，(1V,4V)，(1V,10V)，圖G中從1V到27V的任意一條有向道路代表一種切割方式。從1V到27V共有90條有向道路，對應(yīng)著所考慮的90種切割方式。1V到27V的最短路即為最少加工費(fèi)用，該有向道路即對應(yīng)所求的最優(yōu)切割方式。 2、e!=0的情況  當(dāng)e!=0時(shí)，即當(dāng)先后兩次垂直切割的平面不平行時(shí)

9、，需加調(diào)刀費(fèi)e。希望在上面的網(wǎng)絡(luò)圖中某些邊增加權(quán)來實(shí)現(xiàn)此費(fèi)用增加。在所有切割序列中，四個(gè)垂直面的切割順序只有三種可能情況（不管它們之間是否穿插水平切割）： <情況一>先切一對平行面，再切另外一對平行面，總費(fèi)用比e=0時(shí)的費(fèi)用增加e。 <情況二>先切一個(gè)，再切一對平行面，最后割剩余的一個(gè)，總費(fèi)用比e=0時(shí)的費(fèi)用增加2e。 <情況三>切割面是兩兩相互垂直，總費(fèi)用比e=0時(shí)的費(fèi)用增加3e。 在所考慮的90種切割序列中，上述三種情況下垂直切割面的排列情形，及在圖G中對應(yīng)有向路的必經(jīng)點(diǎn)如下表（z=0,1,2）： 

10、60; 我們希望通過在上面的網(wǎng)絡(luò)圖中的某些邊上增加權(quán)來進(jìn)行調(diào)刀費(fèi)用增加的計(jì)算，但由于網(wǎng)絡(luò)圖中的某些邊是多種切割序列所公用的。對于某一種切割序列，需要在此邊上增加權(quán)e，但對于另外一種切割序列，就有可能不需要在此邊上增加權(quán)e，這樣我們就不能直接利用上面的網(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)集。所以可判斷出這兩部分是獨(dú)立的、互補(bǔ)的。.如果我們在圖G中分別去掉點(diǎn)集

11、(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ǔ)性。對于一個(gè)問題來說，最短路線必存在于它們中的某一個(gè)中。  由于調(diào)整垂直刀具為3次時(shí)，總費(fèi)用需增加3e，故我們先安排這種情況的權(quán)增加值e，每次轉(zhuǎn)刀時(shí)，給其待切弧上的權(quán)增加e。增加e的情況如下圖中所示。再來判斷是否滿足調(diào)整垂直刀具為二次、一次時(shí)的情況，我們發(fā)現(xiàn)所增加的權(quán)滿足另外兩類切割序列。 綜合上述分析，我們將原網(wǎng)絡(luò)圖G分解為兩個(gè)網(wǎng)絡(luò)圖1和2，并在指定邊上的權(quán)增加e，然后分別求出圖1H和2H中從1V到27V的最短路，最短路的權(quán)分別為：d1,

12、d2.則得出整體的最少費(fèi)用為：d = min(d1 ,d2)=，相應(yīng)的圖求出的最優(yōu)切割序列即為其對應(yīng)的最短路徑。   圖1H  圖2H 、對“每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割”這個(gè)準(zhǔn)則的好壞進(jìn)行評價(jià)  評價(jià)的標(biāo)準(zhǔn)：最佳切割方式可以不唯一，可是最佳加工費(fèi)用應(yīng)等于按照之前的模型求解出的最少加工費(fèi)用。即：若準(zhǔn)則精選出的不同切割方式有很多，而相應(yīng)的加工費(fèi)卻不全相同，則其不具備優(yōu)化準(zhǔn)則的基本屬性。同樣，即使精選出的切割方式唯一，但加工費(fèi)卻非真正意義上的最小，則準(zhǔn)則也無最優(yōu)性可言。 根據(jù)實(shí)例中的數(shù)據(jù)，在局部最優(yōu)準(zhǔn)則的前提下，假定e =0

13、,r= 1時(shí)，求出的最佳加工費(fèi)用為374元，這與用上面的模型求解出的結(jié)果相同。假定e= 2, r = 1.5時(shí)，求出的最佳加工費(fèi)用為490元，這個(gè)與用上面的模型求解出的結(jié)果443.5不相同，并且比上面的結(jié)果大。因此，“每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割”不能作為最佳優(yōu)化準(zhǔn)則使用，但當(dāng)e=0=時(shí)可以采用這個(gè)準(zhǔn)則，而當(dāng)e!=0¹時(shí)不能采用這個(gè)準(zhǔn)則。 Mat l a b程序 function y1,y2 = qiegel( r,e )a = 10,14.5,19;6,7,9;1.5,5,6;k= 0;nn = 1;mm =zeros(720,6);%UNTITLED Su

14、mmary of this function goes here% Detailed explanation goes herefor i1=1:6 for i2=1:6 for i3=1:6 for i4=1:6 for i5=1:6 for i6=1:6 if i1=i2|i2=i3|i3=i4|i4=i5|i1=i3|i1=i4 |i1=i5|i2=i4|i2=i5|i3=i5 break; end b=i1,i2,i3,i4,i5,i6; if ispl(b)=1 k = k+1; m(k)=fee(a,b,c); mm(k,;)=b; end end end end end ende

15、nd i2 =1; for i1 = 1:k if m(i1)=min(m); m1(i2)=i1; i2= i2+1; end end y1 = min(m); y2 = mm(m1,;);end function x4 = ispl(x) x3 =1; for x1 =1:5 if x(x1)-x(6)=0 x3=0; end end x4=x3; end function s =fee(a,b,r,e) c=b; for i=1:6 switch b(i) case 1 b(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); case 6 b(i)=a(1,2)*a(1,3); a(1,3)=a(1,3)-a(3