基于Visual C++軟件對石材加工截斷切割最優(yōu)問題的分析

2018-04-04 05:55:14安潔

價值工程 2018年10期

安潔

摘要：本文以石材加工為背景，針對截斷切割的問題，采用最短路模型和動態(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 文獻標(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)則作出評價：每次選擇一個加工費用最少的待切割面進行切割；問題三，分析對于e=0的情形有無簡明的優(yōu)化準(zhǔn)則。

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

1.1 條件假設(shè)

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

1.2 符號說明

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

2 問題一的求解

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

首先，建立空間網(wǎng)絡(luò)圖和有向圖[1]。空間網(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)及所有切割方式。

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

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

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

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

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

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

最后，建立動態(tài)規(guī)劃模型[3]，得到加工費用表達式。設(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ù)上述方程及表達式即可得到所有切割方式下加工費用的值，最后將所有結(jié)果進行比較取得最小值，即為最少加工費用，同時可得相應(yīng)最短路徑即為加工方式。上述過程的實現(xiàn)借助于Visual C++軟件進行編程。

3 問題二的求解

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