安潔

摘要： 本文以石材加工為背景，針對截斷切割的問題，采用最短路模型和動態(tài)規(guī)劃模型，借助于Visual C++軟件編程，求解得到了使加工費用最小的切割方式。

Abstract： In this paper， based on the background of stone processing， aiming at the truncation and cutting problem， the shortest path model and the dynamic programming model are adopted. With the aid of Visual C++ software programming， the cutting mode that minimizes the processing cost is obtained.

關(guān)鍵詞： 截斷切割；最短路；動態(tài)規(guī)劃

Key words： truncation and cutting；the shortest path；dynamic programming

中圖分類號：TG481+.2 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2018）10-0216-02

0 引言

我國部分工業(yè)部門在對貴重石材加工時，采用截斷切割的加工方式。這里的“截斷切割”是指將物體沿某個切割平面分成兩部分。從一個長方體中加工出一個已知尺寸、位置預(yù)定的長方體（這兩個長方體的對應(yīng)表面是平行的），通常要經(jīng)過6次截斷切割，且由工藝要求，與水平工作臺接觸的長方體底面是事先指定的。設(shè)水平切割單位面積的費用是垂直切割單位面積費用的r倍，當(dāng)先后兩次垂直切割的平面（不管它們之間是否穿插水平切割）不平行時，因調(diào)整刀具需額外費用e。為了使加工費用最少，需給這些部門設(shè)計一種安排各面加工次序（稱“切割方式”）的方法，解決如下三個問題：問題一，給出切割方式的數(shù)學(xué)模型和求解方法；問題二，對某部門用的如下準(zhǔn)則作出評價：每次選擇一個加工費用最少的待切割面進(jìn)行切割；問題三，分析對于e=0的情形有無簡明的優(yōu)化準(zhǔn)則。

1 條件假設(shè)及符號說明

1.1 條件假設(shè)

假設(shè)從待加工長方體中加工出已知尺寸、位置預(yù)定的長方體且長方體底面是事先指定的，同時這兩個長方體的對應(yīng)表面是平行的；假設(shè)先后兩次垂直切割的平面（不管它們之間是否穿插水平切割）不平行時，因調(diào)整刀具需額外費用；假設(shè)進(jìn)行截斷切割時每次得到兩塊長方體，不考慮產(chǎn)生加工碎屑等情況；忽略刀具切割時產(chǎn)生的熱量及刀具磨損等情況。

1.2 符號說明

各符號的含義如表1所示。

2 問題一的求解

保證在對某一方向（側(cè)面、正面、水平面）切割時，先切割下的應(yīng)是切塊厚度較大的長方體，進(jìn)而對C¹₃C¹₅C¹₂C¹₃C¹₁C¹₁種切割方式進(jìn)行討論，建立最短路模型和動態(tài)規(guī)劃模型，相比較于6×5×4×3×2×1=6！=720種切割方式，計算量大大減少，更容易得到最優(yōu)切割方案，使切割費用最少。

首先，建立空間網(wǎng)絡(luò)圖和有向圖[1]?？臻g網(wǎng)絡(luò)圖和有向圖中每個結(jié)點坐標(biāo)（x，y，z）表示被切割長方體所處的一個狀態(tài)。其中，x表示垂直于x軸切割刀數(shù)，y表示垂直于y軸切割刀數(shù)，z表示垂直于軸切割刀數(shù)；頂點（0，0，0）表示長方體的待加工狀態(tài)，頂點（2，2，2）表示長方體的成品狀態(tài)。問題一即求從（0，0，0）出發(fā)到（2，2，2）結(jié)束的最短路問題[2]。

空間網(wǎng)絡(luò)圖如圖1所示。

有向圖如圖2所示。

由有向圖可知被切割長方體的所有狀態(tài)及所有切割方式。

其次，對有向圖進(jìn)行分析，需求得各有向邊的權(quán)值。由于要得到最小加工費用，故將切割單位面積的費用作為權(quán)值。

此時需考慮調(diào)整刀具帶來的額外費用，根據(jù)問題假設(shè)分析產(chǎn)生額外費用的原因，是因為存在三種換刀情況：

如果切割了一個垂直面后，再切割與之相平行的那個垂直面，然后再切割另外兩個相互平行的垂直面，那么需要換刀一次；

如果切割了一個垂直面后，再切割與之不平行的某個垂直面，然后再切割與第二個被切垂直面相平行的那個垂直面，最后切割與第二個被切垂直面相平行的那個垂直面，那么需要換刀兩次；

如果切割了一個垂直面后，再切割與之不平行的某個垂直面，然后再切割與第二個被切垂直面不平行的那個垂直面，最后切割與第二個被切垂直面相平行的那個垂直面，那么需要換刀三次。

上述三種換刀情況分別產(chǎn)生e、2e、3e的額外費用。

最后，建立動態(tài)規(guī)劃模型[3]，得到加工費用表達(dá)式。設(shè)（1，0，0）、（0，1，0）、（0，0，1）分別對應(yīng)刀具垂直于x軸、y軸、z軸切割的狀態(tài)。

i的取值為1、2、3，ei分別對應(yīng)三種換刀額外費用。

根據(jù)上述方程及表達(dá)式即可得到所有切割方式下加工費用的值，最后將所有結(jié)果進(jìn)行比較取得最小值，即為最少加工費用，同時可得相應(yīng)最短路徑即為加工方式。上述過程的實現(xiàn)借助于Visual C++軟件進(jìn)行編程。

3 問題二的求解

對每次選擇一個加工費用最少的待切割面進(jìn)行切割的準(zhǔn)則進(jìn)行分析，由于調(diào)整刀具產(chǎn)生的額外費用的存在，若選擇加工費用最少的待切割面進(jìn)行切割，在額外費用較大時，此時得到的加工費用可能不是最??；此準(zhǔn)則為局部最優(yōu)準(zhǔn)則但不是全局最優(yōu)準(zhǔn)則，且只有在變量參數(shù)滿足一定條件時才是成立的。

4 問題三的求解

待加工長方體有三個切割方向，每個方向切下兩塊，考慮到額外費用為零時，水平切割單位面積的費用是垂直切割單位面積費用的r倍，故定義此時側(cè)面方向、正面方向、水平面方向六塊切塊的厚度分別為rl1、rl2、rw1、rw2、h1、h2。

由上文可知，在對某一方向（側(cè)面、正面、水平面）切割時，先切割下的應(yīng)是切塊厚度較大的長方體，故此時每次切割時都應(yīng)切剩余上述定義厚度中最大的切塊，即每次切rl1、rl2、rw1、rw2、h1、h2中剩余厚度最大的切塊。

5 評價與改進(jìn)方向

5.1 優(yōu)點

對需考慮的720種加工方式進(jìn)行了優(yōu)化，縮減至90種，大大減少了計算量，能快速找出最少費用及其對應(yīng)加工方式；

考慮的情況比較全面，對額外費用的有無、額外費用存在的三種情況等進(jìn)行了分析；

易于編程實現(xiàn)。

5.2 模型的缺點

只適用于待加工物體為長方體的情況，沒有很好的普遍性。

沒有考慮刀具磨損等加工費用。

5.3 模型的改進(jìn)方向

針對只適用于待加工物體為長方體的情況，我們可對最短路模型和動態(tài)規(guī)劃模型進(jìn)行改進(jìn)，使之適用于任何形狀的待加工物體。

參考文獻(xiàn)：

[1]徐俊明.圖論及其應(yīng)用[M].安徽：中國科學(xué)技術(shù)大學(xué)出版社，2010.

[2]姜啟源.數(shù)學(xué)模型[M].北京：高等教育出版社，2011.

[3]滕宇.動態(tài)規(guī)劃原理及應(yīng)用[M].四川：西南交通大學(xué)出版社，2011.