/題目截?cái)嗲懈顔栴}摘要本文研究了實(shí)際生產(chǎn)過程中的截?cái)嗲懈顔栴}.求出最優(yōu)的切割順序.使得在對(duì)待加工的長(zhǎng)方體進(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è)圖中的弧表示長(zhǎng)方體的切割過程.圖中的定點(diǎn)表示長(zhǎng)方體切割后所處的狀態(tài).并對(duì)弧權(quán)進(jìn)行賦值.弧權(quán)值表示在切割過程中所花費(fèi)的切割費(fèi)用。然后通過求最短路徑來求出最少的切割費(fèi)用。我們利用軟件得出了如下答案：當(dāng)時(shí).最少加工費(fèi)用為：元；切割次序?yàn)椋?也就是按照的順序切割。當(dāng)時(shí).最少加工費(fèi)用為：元；切割次序?yàn)椋?也就是按照的順序切割。當(dāng)時(shí).最少加工費(fèi)用為：元；切割次序?yàn)椋?也就是按照的順序切割。〔當(dāng)時(shí).答案較為復(fù)雜.請(qǐng)見正文并且.我們提出了最簡(jiǎn)明的優(yōu)化準(zhǔn)則.即為"每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割。"當(dāng)時(shí)的情況下.對(duì)長(zhǎng)方體進(jìn)行截?cái)嗲懈顣r(shí).就能夠遵循這條準(zhǔn)則對(duì)其進(jìn)行切割.花費(fèi)最小的切割費(fèi)。關(guān)鍵詞：截?cái)嗲懈钭顑?yōu)化模型圖論一、問題重述某些工業(yè)部門〔如貴重石材加工等采用截?cái)嗲懈畹募庸し绞健＿@里"截?cái)嗲懈?是指將物體沿某個(gè)切割平面分成兩部分。從一個(gè)長(zhǎng)方體中加工出一個(gè)已知尺寸、位置預(yù)定的長(zhǎng)方體〔這兩個(gè)長(zhǎng)方體的對(duì)應(yīng)表面是平行的.通常要經(jīng)過次截?cái)嗲懈?。設(shè)水平切割單位面積的費(fèi)用是垂直切割單位面積費(fèi)用的倍.且當(dāng)先后兩次垂直切割的平面<不管它們之間是否穿插水平切割>不平行時(shí).因調(diào)整刀具需額外費(fèi)用。試為這些部門設(shè)計(jì)一種安排各面加工次序〔稱"切割方式"的方法.使加工費(fèi)用最少。〔由工藝要求.與水平工作臺(tái)接觸的長(zhǎng)方體底面是事先指定的詳細(xì)要求如下：1、需考慮的不同切割方式的總數(shù)。2、給出上述問題的數(shù)學(xué)模型和求解方法。3、試對(duì)某部門用的如下準(zhǔn)則作出評(píng)價(jià)：每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割。4、對(duì)于的情形有無簡(jiǎn)明的優(yōu)化準(zhǔn)則。5、用以下實(shí)例數(shù)據(jù)驗(yàn)證你的方法：待加工長(zhǎng)方體和成品長(zhǎng)方體的長(zhǎng)、寬、高分別為10、14.5、19和3、2、4.二者左側(cè)面、正面、底面之間的距離分別為6、7、9〔單位均為厘米。垂直切割費(fèi)用為每平方厘米元.和的數(shù)據(jù)有以下組：對(duì)最后一組數(shù)據(jù)應(yīng)給出所有最優(yōu)解.并進(jìn)行討論。二、模型假設(shè)1、假設(shè)待加工的長(zhǎng)方體與成品長(zhǎng)方體的各個(gè)對(duì)應(yīng)表面均平行。2、假設(shè)水平工作臺(tái)臺(tái)面是整平的。3、假設(shè)加工費(fèi)用只與切割費(fèi)用和刀具調(diào)整費(fèi)有關(guān)。4、假設(shè)每個(gè)待加工的長(zhǎng)方體只切割為一個(gè)成品長(zhǎng)方體.而且每個(gè)待加工的長(zhǎng)方體至少都需要經(jīng)過六次切割才能成為成品長(zhǎng)方體。三、符號(hào)說明截?cái)嗲懈顣r(shí)刀具切割所產(chǎn)生的切割面待加工長(zhǎng)方體的第個(gè)面與成品長(zhǎng)方體第個(gè)面的距離待加工長(zhǎng)方體的長(zhǎng)、寬、高成品長(zhǎng)方體的長(zhǎng)、寬、高總切割費(fèi)用垂直切割的單位面積切割費(fèi)正方體在有向圖中所表示的第個(gè)狀態(tài)在第個(gè)狀態(tài)下長(zhǎng)方體的長(zhǎng)、寬、高在有向圖中表示第個(gè)狀態(tài)的切割過程所需的切割費(fèi)四、問題分析4.1對(duì)要求一的分析在這個(gè)問題中.加工費(fèi)用與每一次的切割面積以及總共需要刀具調(diào)整次數(shù)的有關(guān)系.而總的切割面積又與長(zhǎng)方體的個(gè)切割面的切割次序有關(guān)系.所以這個(gè)問題能夠利用排列組合的知識(shí)來解。4.2對(duì)要求二的分析在對(duì)于最優(yōu)的加工次序的求解過程中.由于切割方式有種.數(shù)據(jù)過于龐大.所以我們對(duì)這些切割方式先進(jìn)行初步的優(yōu)化?？紤]到實(shí)際情況.我們經(jīng)過證明發(fā)現(xiàn)〔證明過程見下文5.2.對(duì)于相對(duì)的兩個(gè)切割面進(jìn)行切割時(shí).先切割與待加工的長(zhǎng)方體的外表面距離較大的切割面.所花的切割費(fèi)用要較少一些。所以我們使用這個(gè)篩選方法作為初步優(yōu)化的方案對(duì)切割方式做初步的優(yōu)化篩選。篩選后的切割方式有種.然后我們運(yùn)用圖論的方法對(duì)其進(jìn)行求解。通過建立一個(gè)有向賦權(quán)網(wǎng)絡(luò)圖進(jìn)行求解。然而.因?yàn)橹档牟煌?所以在優(yōu)化過程中還要分為和這兩種情況去進(jìn)行分析.建立相應(yīng)的有向賦權(quán)網(wǎng)絡(luò)圖。然后使用軟件進(jìn)行編程求解。4.3對(duì)要求三的分析首先.對(duì)于某部門的切割方法進(jìn)行求解.得出結(jié)果為：表1：某部門方法切割表數(shù)據(jù)組切割費(fèi)元元元元我們對(duì)數(shù)據(jù)進(jìn)行分析后發(fā)現(xiàn).當(dāng)時(shí).某部門使用的準(zhǔn)則得出的切割費(fèi)與我們的結(jié)果十分接近；但是當(dāng)時(shí).答案與我們得出的就有一定的區(qū)別.價(jià)格要比我們的答案高一點(diǎn).而且隨著的增大而增大.所以很明顯.當(dāng)時(shí).這個(gè)準(zhǔn)則還是挺適合的；但是在的情況下.這個(gè)方法就不太明智了。4.4對(duì)要求四的分析其實(shí)要求四與要求三的情況是相同的.在要求三中的準(zhǔn)則就是對(duì)這種情況下的優(yōu)化方案的一種簡(jiǎn)化方案。然后我們通過對(duì)答案的驗(yàn)證.來證明要求三中提出的準(zhǔn)則在的情況下的合理性。五、模型的建立與求解5.1要求一的模型建立與求解對(duì)于計(jì)算不同的切割方式總數(shù).經(jīng)過分析.我們發(fā)現(xiàn)能夠用排列組合的知識(shí)來解決這個(gè)問題。我們對(duì)分別位于前、后、左、右、上、下的切割面進(jìn)行編號(hào).其相應(yīng)的編號(hào)分別為.然而每一種切割方式都是對(duì)這個(gè)切割面的一個(gè)排列方式.所以總共就有種排列方式。所以我們認(rèn)為.切割總數(shù)應(yīng)該有種。5.2要求二的模型建立與求解5.2.1對(duì)數(shù)據(jù)的初步優(yōu)化根據(jù)實(shí)際情況.當(dāng)考慮到切割費(fèi)用時(shí).存在一個(gè)局部的優(yōu)化的方案：在對(duì)兩個(gè)相對(duì)的切割面進(jìn)行切割的時(shí)候.切割面與待加工的長(zhǎng)方體的外表面距離較大的一個(gè)面總是先加工的.這樣可以減少總的切割面積.從而節(jié)省很多的切割費(fèi)用。優(yōu)化方案確立的證明如下：假設(shè)待加工的長(zhǎng)方體的長(zhǎng)寬高分別為.成品長(zhǎng)方體長(zhǎng)寬高分別為.待加工長(zhǎng)方體的第個(gè)面與成品長(zhǎng)方體第個(gè)面的距離為.如下圖所示：圖1：面俯視圖圖中..我們以切割面為例：方案一.依次切割.切割費(fèi)用為：而方案二為依次切割.切割費(fèi)用為：因?yàn)?所以.又因?yàn)?所以.方案一的切割費(fèi)用更小。由此可知.局部?jī)?yōu)化方案是正確的。所以在切割相對(duì)的切割面時(shí).只考慮先切割較大的切割面.再切割另一邊的切割面。同理.對(duì)這四個(gè)面的切割方式也是一樣的。而根據(jù)上述思想.我們需要考慮的切割方式應(yīng)該為種。所以在計(jì)算最少加工費(fèi)用時(shí).我們只需要考慮這個(gè)滿足優(yōu)化方案的切割方案。5.2.2在的情況下的優(yōu)化模型與求解在的情況下.我們構(gòu)造如下圖所示的一個(gè)有向賦權(quán)網(wǎng)絡(luò)圖：圖2：有向賦權(quán)網(wǎng)絡(luò)圖在有向圖中.分別表示長(zhǎng)方體在左右、前后、上下方向上被切割的刀數(shù).每個(gè)節(jié)點(diǎn)表示待加工的長(zhǎng)方體所處的狀態(tài)。而其中每一條弧都表示待加工的長(zhǎng)方體正在被切割的過程.然而相應(yīng)的弧上的權(quán)就是在這個(gè)切割過程中所需花費(fèi)的切割費(fèi)。然后.我們對(duì)權(quán)進(jìn)行賦值。因?yàn)殚L(zhǎng)方體有種不同的狀態(tài).每個(gè)狀態(tài)中的長(zhǎng)、寬、高都不同.直接算各個(gè)切割過程中的切割費(fèi)用比較困難.所以我們先將長(zhǎng)方體處于各個(gè)狀態(tài)下的長(zhǎng)、寬、高計(jì)算出來。由于在上文中.我們提出：在對(duì)兩個(gè)相對(duì)的切割面進(jìn)行切割的時(shí)候.切割面與待加工的長(zhǎng)方體的外表面距離較大的一個(gè)面總是先加工的。所以我們?cè)谶@里就默認(rèn)使用這種方法對(duì)長(zhǎng)方體進(jìn)行切割.利用要求五的數(shù)據(jù)進(jìn)行計(jì)算。計(jì)算結(jié)果如下：表2：各個(gè)狀態(tài)下的長(zhǎng)方體長(zhǎng)、寬、高然后我們對(duì)有向圖進(jìn)行分析.我們發(fā)現(xiàn)：當(dāng)長(zhǎng)方體處于一個(gè)狀態(tài)時(shí).如果要進(jìn)行下一步的切割.必然會(huì)有個(gè)切割過程能夠選擇.也就是這三個(gè)方向。當(dāng)進(jìn)行方向上的切割時(shí).；當(dāng)進(jìn)行方向上的切割時(shí).；當(dāng)進(jìn)行方向上的切割時(shí).。所以我們利用這個(gè)規(guī)律對(duì)權(quán)重進(jìn)行計(jì)算.列出如下公式：最后利用這個(gè)公式求出弧的權(quán)值。得出權(quán)值如下表所示：表3：時(shí)的權(quán)值弧1,21,41,102,32,52,113,63,124,5權(quán)值275.5190145275.576585743.5142.5弧4,74,135,65,85,146,96,157,87,16權(quán)值19075142.576305722.53820弧8,98,179,1810,1110,1310,1911,1211,1411,20權(quán)值38861451001451454058弧12,1512,2113,1413,1613,2214,1514,1714,2315,18權(quán)值3043.5751007575403030弧15,2416,1716,2517,1817,2618,2719,2019,2220,21權(quán)值22.520202086584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27權(quán)值1612304030161288表4：時(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,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.2575100112.575404530弧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)值1612304030161288表5：時(shí)的權(quán)值弧1,21,41,102,32,52,113,63,124,5權(quán)值275.5190116275.57646457248142.5弧4,74,135,65,85,146,96,157,87,16權(quán)值19060142.5762405718038160弧8,98,179,1810,1110,1310,1911,1211,1411,20權(quán)值3864481451001161454046.4弧12,1512,2113,1413,1613,2214,1514,1714,2315,18權(quán)值3034.875100607540230弧15,2416,1716,2517,1817,2618,2719,2019,2220,21權(quán)值18020160206448584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27權(quán)值1612304030161288在有向圖中.從到總共有條有向道路.即有種切割方法對(duì)待加工的長(zhǎng)方體進(jìn)行切割.其中到的最少費(fèi)用的路徑即為最少加工費(fèi)用.其所對(duì)應(yīng)的即為最優(yōu)切割方式。當(dāng)時(shí).最少加工費(fèi)用為：元；切割次序?yàn)椋?也就是按照的順序切割。當(dāng)時(shí).最少加工費(fèi)用為：元；切割次序?yàn)椋?也就是按照的順序切割。當(dāng)時(shí).最少加工費(fèi)用為：元；切割次序?yàn)椋?也就是按照的順序切割。5.2.3在的情況下的優(yōu)化模型與求解當(dāng)?shù)那闆r下.當(dāng)兩次垂直切割的平面不平行時(shí).就必須增加調(diào)整刀具費(fèi)。但是調(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ì)的情況進(jìn)行求解。經(jīng)過討論.在四個(gè)垂直切割的切割次序中.只可能存在三種可能的情況增加調(diào)整刀具費(fèi)：一是：先切割一對(duì)平面.然后再切割一對(duì)平面.變刀一次.總費(fèi)用比之前增加。二是：先切割一個(gè)平面.然后再切割另一對(duì)平面.最后切割與第一次切割的平面相對(duì)的平面.變刀兩次.總費(fèi)用比之前增加。三是：先切割一個(gè)平面.然后再切割與第一個(gè)平面垂直的平面.接著是與第一個(gè)平面平行的平面.最后切割與第二個(gè)平面平行的平面.變刀三次.總費(fèi)用比之前增加。垂直切割的順序安排情況如下表所示：表6：垂直切割順序安排表垂直切割順序有向路路徑我們利用的情況中的有向圖對(duì)其進(jìn)行求解.在圖中的一些弧上增加權(quán)來對(duì)調(diào)整刀具費(fèi)進(jìn)行計(jì)算。但是.我們發(fā)現(xiàn)在這個(gè)情況中.弧是往往是多條路徑公用的.如果在一些弧上增加權(quán).很可能影響到其他的路徑.從而影響解題。所以我們將上表中的六個(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ǔ)的有向圖：圖3：圖4：圖5：圖6：圖7：圖8：然后分別求出有向圖中的最短花費(fèi)路徑.在這六個(gè)值中找出最少的花費(fèi).及其切割次序。最后得出答案如下表所示：表7：時(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)則是存在限制條件的。也就是說.在的這種情況下.這條準(zhǔn)則所執(zhí)行的切割方法是最優(yōu)的切割方法之一.得出的結(jié)果與我們建立模型.以及利用軟件進(jìn)行求解的結(jié)果十分相近；但是當(dāng)?shù)那闆r下.也就是存在調(diào)整刀具費(fèi)的情況下.這條準(zhǔn)則就不是很明智了。在執(zhí)行這條準(zhǔn)則時(shí).并沒有將調(diào)整刀具費(fèi)也計(jì)算進(jìn)去.使得切割費(fèi)最后會(huì)有所增加.而且這種增加量與調(diào)整刀具費(fèi)的大小其實(shí)是成正比關(guān)系的.當(dāng)越大時(shí).最后的切割費(fèi)與最優(yōu)解的差距就越大；當(dāng)越小時(shí).最后的切割費(fèi)與最優(yōu)解的差距就越小。所以我們認(rèn)為.在的情況下采用這條準(zhǔn)則是合理的.在的情況下.這條準(zhǔn)則不能作為最優(yōu)化準(zhǔn)則來使用。5.4要求四的情況的最簡(jiǎn)優(yōu)化在對(duì)要求三的準(zhǔn)則和我們得出的答案進(jìn)行分析后我們發(fā)現(xiàn).在的情況下.的改變勢(shì)必會(huì)引起最佳切割方案的改變。因?yàn)槭桥c水平面的切割有關(guān)的.水平切割的單位面積切割費(fèi)用為垂直切割的倍.然而當(dāng)時(shí).我們發(fā)現(xiàn).我們通過建立模型以及軟件的求解得出的切割方案遵循了"每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割。"這條準(zhǔn)則.而且當(dāng)越大時(shí).我們發(fā)現(xiàn)對(duì)水平切割的切割次序就越往后.但是依然遵循了"每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割。"這條準(zhǔn)則。所以我們認(rèn)為.在要求三中的提出的優(yōu)化準(zhǔn)則.在時(shí)的情況下是成立的.并且能夠作為的情形最簡(jiǎn)明的優(yōu)化準(zhǔn)則。5.5要求五的模型建立與求解對(duì)于要求五.我們利用題目中的數(shù)據(jù)來計(jì)算.得出結(jié)果如下表所示：表8：答案表參數(shù)組切割方案切割費(fèi)103741.50437.580540.51.52443.51.52.54451.53445.51.53.54461.54446.5〔其余見附錄I我們?cè)趯?duì)這種情況進(jìn)行分析時(shí)發(fā)現(xiàn).當(dāng)?shù)闹?/p>