截?cái)嗲懈顔栴}論文

1、截一睜一切割 問 題摘要本文研究了實(shí)際生產(chǎn)過程中的截?cái)嗲懈顔栴}，求出最優(yōu)的切割順序，使得在對(duì)待 加工的長方體進(jìn)行切割時(shí)，能夠花費(fèi)最少的切割費(fèi)，得到最大的收益。根據(jù)題中所給的數(shù)據(jù)，我們發(fā)現(xiàn)不同的切割順序所花費(fèi)的切割費(fèi)用是不一樣的，所以我們建立模型，通過圖論來對(duì)其進(jìn)行求解。首先，我們建立了一個(gè)三維的有向賦權(quán)網(wǎng)絡(luò)圖，假設(shè)圖中的弧表示長方體的切割 過程，圖中的定點(diǎn)表示長方體切割后所處的狀態(tài)，并對(duì)弧權(quán)進(jìn)行賦值，弧權(quán)值表示在 切割過程中所花費(fèi)的切割費(fèi)用。然后通過求最短路徑來求出最少的切割費(fèi)用。我們利用Lingo軟件得出了如下答案：當(dāng)r =1,e=0時(shí)，最少加工費(fèi)用為：374元；切割次序?yàn)椋?-10-13-

2、22-23-26-27, 也就是按照M6 -M1 -M5 -M3 -M2 M4的順序切割。當(dāng)r =1.5,e=0時(shí)，最少加工費(fèi)用為：437.5元；切割次序?yàn)椋?1-4-13-14-17-26-27 ,也就是按照 M1 M6 M3 M 2 M5 M 4 的順序切割。當(dāng)r =8,e = 0時(shí)，最少加工費(fèi)用為：540.5元；切割次序?yàn)椋?-45 817-18-27, 也就是按照M1 一M3M2M6M4Ms的順序切割。（當(dāng)r =1.5,2 EeE15時(shí)，答案較 為復(fù)雜，請(qǐng)見正文）并且，我們提出了最簡明的優(yōu)化準(zhǔn)則，即為“每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割?！碑?dāng)e=0時(shí)的情況下，對(duì)長方體進(jìn)行截?cái)嗲?/p>

3、割時(shí)，就能夠遵循這條準(zhǔn)則 對(duì)其進(jìn)行切割，花費(fèi)最小的切割費(fèi)。關(guān)鍵詞：截?cái)嗲懈钭顑?yōu)化模型圖論一、問題重述某些工業(yè)部門（如貴重石材加工等）采用截?cái)嗲懈畹募庸し绞?。這里“截?cái)嗲懈睢?是指將物體沿某個(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)用 最少。（由工藝要求，與水平工作臺(tái)接觸的長方體底面是事先指

4、定的）詳細(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組：對(duì)最后一組數(shù)據(jù)應(yīng)給出所有最優(yōu)解，并進(jìn)行討論。二、模型假設(shè)1、假設(shè)待加工的長方體與成品長方體的各個(gè)對(duì)應(yīng)表面均平行。2、假設(shè)水平工作臺(tái)臺(tái)面是整平的。

5、3、假設(shè)加工費(fèi)用只與切割費(fèi)用和刀具調(diào)整費(fèi)有關(guān)。4、假設(shè)每個(gè)待加工的長方體只切割為一個(gè)成品長方體，而且每個(gè)待加工的長方體至少 都需要經(jīng)過六次切割才能成為成品長方體。三、符號(hào)說明截?cái)嗲懈顣r(shí)刀具切割所產(chǎn)生的切割面待加工長方體的第i個(gè)面與成品長方體第i個(gè)面的距離待加工長方體的長、寬、高成品長方體的長、寬、高總切割費(fèi)用垂直切割的單位面積切割費(fèi)正方體在啟何圖中所表小的第j, k個(gè)狀態(tài)在第j個(gè)狀態(tài)卜長方體的長、寬、局在肩向圖中表示第jk個(gè)狀態(tài)的切割過程所需的切割費(fèi)四、問題分析4.1 對(duì)要求一的分析在這個(gè)問題中，加工費(fèi)用與每一次的切割面積以及總共需要刀具調(diào)整次數(shù)的有關(guān)系，而總的切割面積又與長方體的 6個(gè)切割面

6、的切割次序有關(guān)系，所以這個(gè)問題能夠 利用排列組合的知識(shí)來解。4.2 對(duì)要求二的分析在對(duì)于最優(yōu)的加工次序的求解過程中，由于切割方式有720種，數(shù)據(jù)過于龐大，所以我們對(duì)這些切割方式先進(jìn)行初步的優(yōu)化?？紤]到實(shí)際情況，我們經(jīng)過證明發(fā)現(xiàn)（證明過程見下文5.2）,對(duì)于相對(duì)的兩個(gè)切割面進(jìn)行切割時(shí)，先切割與待加工的長方體的外表面距離較大的切割面，所花的切割 費(fèi)用要較少一些。所以我們使用這個(gè)篩選方法作為初步優(yōu)化的方案對(duì)切割方式做初步 的優(yōu)化篩選。篩選后的切割方式有90種，然后我們運(yùn)用圖論的方法對(duì)其進(jìn)行求解。通過建立一 個(gè)有向賦權(quán)網(wǎng)絡(luò)圖進(jìn)行求解。然而，因?yàn)閑值的不同，所以在優(yōu)化過程中還要分為 e = 0和e#0這

7、兩種情況去進(jìn) 行分析，建立相應(yīng)的有向賦權(quán)網(wǎng)絡(luò)圖。然后使用Lingo軟件進(jìn)行編程求解4.3對(duì)要求三的分析首先，對(duì)于某部門的切割方法進(jìn)行求解，得出結(jié)果為：表1:某部門方法切割表數(shù)據(jù)組切割費(fèi)374元437.5元540.5元437.5+3e=443.5482.5 元我們對(duì)數(shù)據(jù)進(jìn)行分析后發(fā)現(xiàn)，當(dāng)e = 0時(shí)，某部門使用的準(zhǔn)則得出的切割費(fèi)與我們 的結(jié)果十分接近；但是當(dāng)e#0時(shí)，答案與我們得出的就有一定的區(qū)別，價(jià)格要比我們 的答案高一點(diǎn)，而且隨著e的增大而增大，所以很明顯，當(dāng)e=0時(shí)，這個(gè)準(zhǔn)則還是挺適合的；但是在 e/0的情況下，這個(gè)方 法就不太明智了。4.4 對(duì)要求四的分析其實(shí)要求四與要求三的情況是相同的

8、，在要求三中的準(zhǔn)則就是對(duì)e=0這種情況下的優(yōu)化方案的一種簡化方案。然后我們通過對(duì)答案的驗(yàn)證，來證明要求三中提出的準(zhǔn) 則在e = 0的情況下的合理性。五、模型的建立與求解5.1 要求一的模型建立與求解對(duì)于計(jì)算不同的切割方式總數(shù)，經(jīng)過分析，我們發(fā)現(xiàn)能夠用排列組合的知識(shí)來解 決這個(gè)問題。我們對(duì)分別位于前、后、左、右、上、下的切割面進(jìn)行編號(hào)，其相應(yīng)的 編號(hào)分別為Mi,M2,M3,M4,M5,M6,然而每一種切割方式都是對(duì)這 6個(gè)切割面的一個(gè) 排列方式，所以總共就有A： =720種排列方式。所以我們認(rèn)為，切割總數(shù)應(yīng)該有 720種。5.2 要求二的模型建立與求解根據(jù)實(shí)際情況，當(dāng)考慮到切割費(fèi)用時(shí)，存在一個(gè)局

9、部的優(yōu)化的方案：在對(duì)兩個(gè)相 對(duì)的切割面進(jìn)行切割的時(shí)候，切割面與待加工的長方體的外表面距離較大的一個(gè)面總 是先加工的，這樣可以減少總的切割面積，從而節(jié)省很多的切割費(fèi)用。優(yōu)化方案確立的證明如下：假設(shè)待加工的長方體的長寬高分別為a0%,比 ,成品長方體長寬高分別為 a27,b27,C27,待加工長方體的第i個(gè)面與成品長方體第i個(gè)面的距離為li,如下圖所示： 圖1:面M 5俯視圖圖中l(wèi)ll2, I3AI4,我們以切割面Mi,M2為例：方案一，依次切割Mi,M3,M2,切割費(fèi)用為：而方案二為依次切割M2,M3,Mi,切割費(fèi)用為：因?yàn)?1 >12 ,所以12 Ti <0 ,又因?yàn)镃0, p&g

10、t;0,所以Si -S2 <0 ,方案一的切割費(fèi)用 更小。由此可知，局部優(yōu)化方案是正確的。所以在切割相對(duì)的切割面時(shí)，只考慮先切割1較大的切割面，再切割另一邊的切割面。同理，對(duì)M3, M 4, M5,M 6這四個(gè)面的切割方式也是一樣的。而根據(jù)上述思想，我們需要考慮的切割方式應(yīng)該為 -6L=90種。所以在計(jì)算最2 2 2少加工費(fèi)用時(shí)，我們只需要考慮這90個(gè)滿足優(yōu)化方案的切割方案。e = 0的情況下的優(yōu)化模型與求解在e = 0的情況下，我們構(gòu)造如下圖所示的一個(gè)有向賦權(quán)網(wǎng)絡(luò)圖G(V,E):圖2:有向賦權(quán)網(wǎng)絡(luò)圖在有向圖中，xm, ym, zm(m = 1,2)分別表示長方體在左右、前后、上下方向上

11、被切割 的刀數(shù)，每個(gè)節(jié)點(diǎn)表示待加工的長方體所處的狀態(tài)。而其中每一條弧都表示待加工的長方體正在被切割的過程，然而相應(yīng)的弧vm上的權(quán)就是在這個(gè)切割過程中所需花費(fèi)的切割費(fèi) Sj,k。然后，我們對(duì)權(quán)進(jìn)行賦值。因?yàn)殚L方體有27種不同的狀態(tài)，每個(gè)狀態(tài)中的長、寬、 高都不同，直接算各個(gè)切割過程中的切割費(fèi)用比較困難，所以我們先將長方體處于各 個(gè)狀態(tài)下的長、寬、高計(jì)算出來。由于在上文中，我們提出：在對(duì)兩個(gè)相對(duì)的切割面進(jìn)行切割的時(shí)候，切割面與待 加工的長方體的外表面距離較大的一個(gè)面總是先加工的。所以我們?cè)谶@里就默認(rèn)使用 這種方法對(duì)長方體進(jìn)行切割，利用要求五的數(shù)據(jù)進(jìn)行計(jì)算。計(jì)算結(jié)果如下：表2:各個(gè)狀態(tài)下的長方體長、

12、寬、局然后我們對(duì)有向圖進(jìn)行分析，我們發(fā)現(xiàn)：當(dāng)長方體處于一個(gè)狀態(tài)時(shí)，如果要進(jìn)行下一步的切割，必然會(huì)有1 3個(gè)切割過程能夠選擇，也就是x,y,z這三個(gè)方向。當(dāng)進(jìn)行 x方向上的切割時(shí)，k-j=1;當(dāng)進(jìn)行y方向上的切割時(shí)，k-j=3;當(dāng)進(jìn)行z方向上 的切割時(shí)，k-j=9。所以我們利用這個(gè)規(guī)律對(duì)權(quán)重進(jìn)行計(jì)算，列出如下公式：最后利用這個(gè)公式求出弧的權(quán)值。得出權(quán)值如下表所示:表3: r =1,e = 0時(shí)的權(quán)值弧12141102 32 52 113 63 1245權(quán)值,.275.1 L190,145,275.,76',585743.5r,2142邨4 74 135 65 85 146 96 157

13、87 16以 權(quán)侑T,190fl ° 75U,U142u,。76U, IT30U,D57M , 1022 5go38,20弧1 V V8 9i u8 17 =.9 1810 1U vJ10 1U f10 1.111n-z111J yJ1125 2388615114515110015114511,114511,140II,.581人1且 弧12 112 2J13 113 11 uu13 21 m14 11 m14 114 215 1權(quán)值10,1301 0,04351 U, 1751 u, 1100u，075If, 175If, 140,0301 u, 130。人1月 麗jj15 210

14、.016 116 21 w J17 117 218 2IV19 219 2jj20 2柯佰15,2 on k16,12016,22017,12017,2818,2619,25819,24020,258弧hh. u20 221222 222 223 223 224 225 226 2J/M.血/古AU,A 4RA 1,000,400,4 /inAU7AAU，。Of ,419fiR>4: r =1.5,e = 0時(shí)的權(quán)指弧1,21,41,102,32,52,113,63,124,5權(quán)值275.5190217.5275.576875765.25142.5弧4,74,135,65,85,146,

15、96,157,87,16權(quán)值190112.5142.576455733.753830弧8,98,179,1810,1110,1310,1911,1211,1411,20權(quán)值38129145100217.51454087弧12,1512,2113,1413,1613,2214,1514,1714,2315,18權(quán)值3065.275100112.7540453055弧15,2416,1716,2517,1817,2618,2719,2019,2220,21權(quán)值33.75203020129584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27權(quán)值16

16、12304030161288表5: r=8,e = 0時(shí)的權(quán)值12141102 32 52 113 63 12451,2 11,41,102,32,52,113,63,124,5權(quán)值275190L11627576L 46457248142ly *4 74 135 65 85 146 96 157 87 164,7,5,65,86,9,7,87,1619060142762405718038160q人1目1 WKJ V.yJ 11 w w0 w1 w8 98 179 1810 110 110 11111111128,918,179,1810,110,1r 10,1 111,111,111,2386

17、448145100L 116 J1454046 41人1且1 1 VF1 1 u1 1 VF1 V“UJI4 9 9A A 1A A 1A A 94 C 4J川12,112,213,113,113,214,114,114,215,1和佶3034 875100607540Q30"區(qū)IMOT.Ot 51 uuUUt 5OU4d Q O1 Q 9ono.J川15,216,116,217,117,2r 18,2 119,219,220,218020160206448584058nnTon 90on non nno nno n0/1 nnc nop 0J川20,22 1,222,222,223

18、,223,224,225,226,2值 權(quán)一 16.12.3040.30.16 128.-8圖和鼠馬：總矍有90猾r/al即設(shè)0；中切1 扁1法對(duì)如:工。長力 體進(jìn)行切割，其中Vi到V27的最少費(fèi)用的路徑即為最少加工費(fèi)用，其所對(duì)應(yīng)的即為最優(yōu) 切割方式。當(dāng)r =1,e=0時(shí)，最少加工費(fèi)用為：374元；切割次序?yàn)?1-10-13-22-23-26-27, 也就是按照M6 -M1 -M5 -M3 -M2 M4的順序切割。當(dāng)r =1.5,e=0時(shí)，最少加工費(fèi)用為：437.5元；切割次序?yàn)椋?1-4-13-14-17-26-27 ,也就是按照 M1 一M6 M3 M2 M5 M4 的順序切割。當(dāng)r =8

19、,e = 0時(shí)，最少加工費(fèi)用為：540.5元；切割次序?yàn)椋?-45 817-18-27, 也就是按照M1 -M3 -M2 -M6 -M4 -M5的順序切割。e # 0的情況下的優(yōu)化模型與求解當(dāng)e#0的情況下，當(dāng)兩次垂直切割的平面不平行時(shí)，就必須增加調(diào)整刀具費(fèi)e。但是調(diào)整刀具費(fèi)只于垂直切割有關(guān)，與是否穿插水平切割無關(guān)。所以在計(jì)算刀具費(fèi)的過程中，只需要考慮四個(gè)垂直切割的安排次序。然后運(yùn)用上文的有向賦權(quán)網(wǎng)絡(luò)圖中的某些弧上增加權(quán)來實(shí)現(xiàn)費(fèi)用的增加，從而利用上文的模型對(duì) e# 0的情況進(jìn)行求解。經(jīng)過討論，在四個(gè)垂直切割的切割次序中，只可能存在三種可能的情況增加調(diào)整 刀具費(fèi)e：一是：先切割一對(duì)平面，然后再切

20、割一對(duì)平面，變刀一次，總費(fèi)用比之前增加e二是：先切割一個(gè)平面，然后再切割另一對(duì)平面，最后切割與第一次切割的平面相對(duì)的平面，變刀兩次，總費(fèi)用比之前增加 2e。三是：先切割一個(gè)平面，然后再切割與第一個(gè)平面垂直的平面，接著是與第一個(gè)平面平行的平面，最后切割與第二個(gè)平面平行的平面，變刀三次，總費(fèi)用比之前增加3e 垂直切割的順序安排情況如下表所示：表6:垂直切割順序安排表垂直切割順序有向路路徑我們利用e = 0的情況中的有向圖對(duì)其進(jìn)行求解，在圖中的一些弧上增加權(quán)來對(duì)調(diào) 整刀具費(fèi)進(jìn)行計(jì)算。但是，我們發(fā)現(xiàn)在e=0這個(gè)情況中，弧是往往是多條路徑公用的, 如果在一些弧上增加權(quán)，很可能影響到其他的路徑，從而影響解

21、題。所以我們將上表中的六個(gè)情況分開進(jìn)行討論，形成六個(gè)新的有向圖，而且這六個(gè) 有向圖是互補(bǔ)的，因此最短花費(fèi)路徑必然存在于這六個(gè)有向圖之中。我們分別對(duì)這六 個(gè)有向圖進(jìn)行求解，得出六個(gè)最少花費(fèi)路徑，然后對(duì)這六個(gè)值進(jìn)行比較，最后得出一 個(gè)最少花費(fèi)。綜合上述分析，我們將原來的有向賦權(quán)網(wǎng)絡(luò)圖分成六個(gè)部分，分成如下的六個(gè)能夠互補(bǔ)的有向圖H1,H2, h3,h4,h5,h6 :圖 3:H1圖 4:H2圖 5:H3圖 6:H4圖 7:H5圖 8:H6然后分別求出有向圖Hi,H2,H3,H4,H5,H6中Vi V27的最短花費(fèi)路徑，在這六個(gè)值 中找出最少的花費(fèi)，及其切割次序。最后得出答案如下表所?。罕?: e#0

22、時(shí)的答案表數(shù)據(jù)組切割費(fèi)切割方案1.52443.51.52.54451.53445.51.53.54461.54446.55.3要求三對(duì)準(zhǔn)則的評(píng)價(jià)經(jīng)過分析比較，我們發(fā)現(xiàn)“每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割。”這條準(zhǔn)則是存在限制條件的。也就是說，在e=0的這種情況下，這條準(zhǔn)則所執(zhí)行的切割方法是最優(yōu)的切割方法 之一，得出的結(jié)果與我們建立模型，以及利用 Lingo軟件進(jìn)行求解的結(jié)果十分相近；但是當(dāng)e卉0的情況下，也就是存在調(diào)整刀具費(fèi)的情況下，這條準(zhǔn)則就不是很明智 了。在執(zhí)行這條準(zhǔn)則時(shí)，并沒有將調(diào)整刀具費(fèi)e也計(jì)算進(jìn)去，使得切割費(fèi)最后會(huì)有所增 加，而且這種增加量與調(diào)整刀具費(fèi)e的大小其實(shí)是成正比關(guān)系

23、的，當(dāng)e越大時(shí)，最后的 切割費(fèi)與最優(yōu)解的差距就越大；當(dāng)e越小時(shí)，最后的切割費(fèi)與最優(yōu)解的差距就越小。所以我們認(rèn)為，在e = 0的情況下采用這條準(zhǔn)則是合理的，在 e00的情況下，這條 準(zhǔn)則不能作為最優(yōu)化準(zhǔn)則來使用。5.4 要求四e = 0的情況的最簡優(yōu)化在對(duì)要求三的準(zhǔn)則和我們得出的答案進(jìn)行分析后我們發(fā)現(xiàn)，在e= 0的情況下，r的改變勢(shì)必會(huì)引起最佳切割方案的改變。因?yàn)閞是與水平面的切割有關(guān)的，水平切割的單位面積切割費(fèi)用為垂直切割的r倍，然而當(dāng)r =1時(shí)，我們發(fā)現(xiàn)，我們通過建立模型以及Lingo軟件的求解得出的切割方 案遵循了 “每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割?！边@條準(zhǔn)則，而且當(dāng)r越 大時(shí)，我們發(fā)現(xiàn)對(duì)水平切割的切割次序就越往后，但是依然遵循了 “每次選擇一個(gè)加 工費(fèi)用最少的待切割面進(jìn)行切割?！边@條準(zhǔn)則。所以我們認(rèn)為，在要求三中的提出的優(yōu)化準(zhǔn)則，在 e = 0時(shí)的情況下是成立的，并 且能夠作為e = 0的情形最簡明的優(yōu)化準(zhǔn)則。5.5 要求五的模型建立與求解對(duì)于要求五，我們利用題目中的數(shù)據(jù)來計(jì)算，得出結(jié)果如下表所示：表8:答案表參數(shù)組