上傳人：唯***

認(rèn)證信息

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

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

IP屬地：河北

IP屬地：河北 上傳時(shí)間：2022-03-04 格式：DOCX 頁數(shù)：10 大?。?99.59KB 積分：12 舉報(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è)長方體的對(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)用最

2、少。（由工藝要求，與水平工作臺(tái)接觸的長方體底面是事先指定的）詳細(xì)要求如下：1、需考慮的不同切割方式的總數(shù)。2、給出上述問題的數(shù)學(xué)模型和求解方法。3、試對(duì)某部門用的如下準(zhǔn)則作出評(píng)價(jià)：每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割。4、對(duì)于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組：ar=1e=0;br=1.5e=0;cr=8e=0;dr=1.52<=e<=15;對(duì)最后一組數(shù)據(jù)

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

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

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

6、加上坐標(biāo)軸x,y,z。BV%忡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)ix,yi,zi分別代表石材在左右、前后、上下方向上已被切割的刀數(shù)。頂點(diǎn)1V(0,0,0)表示石材的最初待加工狀態(tài)，頂點(diǎn)27V(2,2,2)表示石材加工完成后的狀態(tài)。(2)、G的弧(Vi,Vj)表示石材被切割的一個(gè)過程，若長方體能從狀態(tài)Vi經(jīng)一次切割變?yōu)闋顟B(tài)Vj,即當(dāng)且僅當(dāng)xi+yi+zi+1=xj+yj+z時(shí)，Vi(xi,yi,z)到Vj(xi,yi,zD有弧(Vi,Vj),相應(yīng)弧上的權(quán)W(Vi,Vj)即為這一切割過程的費(fèi)用。對(duì)于任意

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

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

10、況的情形（一）有公共點(diǎn)集（2,1,z）|z=0,1,2,情形（二）有公共點(diǎn)集（1,2,z）|z=0,1,2o且情形（一）的有向路決不通過情形（二）的公共點(diǎn)集，情形（二）的有向路也不通過情形（一）的公共點(diǎn)集。所以可判斷出這兩部分是獨(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ò)圖，如圖H1和H2。這兩個(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的情況如下

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

12、全相同，則其不具備優(yōu)化準(zhǔn)則的基本屬性。同樣，即使精選出的切割方式唯一，但加工費(fèi)卻非真正意義上的最小，則準(zhǔn)則也無最優(yōu)性可言。根據(jù)實(shí)例中的數(shù)據(jù)，在局部最優(yōu)準(zhǔn)則的前提下，假定e=0,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忖可以采用這個(gè)準(zhǔn)則，而當(dāng)e!=0時(shí)不能采用這個(gè)準(zhǔn)則。Matlab程序fileEditlextQp©ellTols口叱ugdesk

13、topMtfndowHelp-仙+1+JJ,聯(lián)啜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