基于Visual C++軟件對石材加工截?cái)嗲懈钭顑?yōu)問題的分析

安潔

摘要： 本文以石材加工為背景，針對截?cái)嗲懈畹膯栴}，采用最短路模型和動(dòng)態(tài)規(guī)劃模型，借助于Visual C++軟件編程，求解得到了使加工費(fèi)用最小的切割方式。

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)鍵詞： 截?cái)嗲懈睿蛔疃搪?；?dòng)態(tài)規(guī)劃

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

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

0 引言

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

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

1.1 條件假設(shè)

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

1.2 符號(hào)說明

各符號(hào)的含義如表1所示。

2 問題一的求解

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

首先，建立空間網(wǎng)絡(luò)圖和有向圖[1]?？臻g網(wǎng)絡(luò)圖和有向圖中每個(gè)結(jié)點(diǎn)坐標(biāo)（x，y，z）表示被切割長方體所處的一個(gè)狀態(tài)。其中，x表示垂直于x軸切割刀數(shù)，y表示垂直于y軸切割刀數(shù)，z表示垂直于軸切割刀數(shù)；頂點(diǎn)（0，0，0）表示長方體的待加工狀態(tài)，頂點(diǎn)（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)值。由于要得到最小加工費(fèi)用，故將切割單位面積的費(fèi)用作為權(quán)值。

此時(shí)需考慮調(diào)整刀具帶來的額外費(fèi)用，根據(jù)問題假設(shè)分析產(chǎn)生額外費(fèi)用的原因，是因?yàn)榇嬖谌N換刀情況：

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

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

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

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

最后，建立動(dòng)態(tài)規(guī)劃模型[3]，得到加工費(fèi)用表達(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)三種換刀額外費(fèi)用。

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

3 問題二的求解

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

4 問題三的求解

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

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

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

5.1 優(yōu)點(diǎn)

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

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

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

5.2 模型的缺點(diǎn)

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

沒有考慮刀具磨損等加工費(fèi)用。

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

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

參考文獻(xiàn)：

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

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

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