安洁

摘要： 本文以石材加工为背景，针对截断切割的问题，采用最短路模型和动态规划模型，借助于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.

關键词： 截断切割；最短路；动态规划

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

中图分类号：TG481+.2 文献标识码：A 文章编号：1006-4311（2018）10-0216-02

0 引言

我国部分工业部门在对贵重石材加工时，采用截断切割的加工方式。这里的“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割，且由工艺要求，与水平工作台接触的长方体底面是事先指定的。设水平切割单位面积的费用是垂直切割单位面积费用的r倍，当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e。为了使加工费用最少，需给这些部门设计一种安排各面加工次序（称“切割方式”）的方法，解决如下三个问题：问题一，给出切割方式的数学模型和求解方法；问题二，对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割；问题三，分析对于e=0的情形有无简明的优化准则。

1 条件假设及符号说明

1.1 条件假设

假设从待加工长方体中加工出已知尺寸、位置预定的长方体且长方体底面是事先指定的，同时这两个长方体的对应表面是平行的；假设先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用；假设进行截断切割时每次得到两块长方体，不考虑产生加工碎屑等情况；忽略刀具切割时产生的热量及刀具磨损等情况。

1.2 符号说明

各符号的含义如表1所示。

2 问题一的求解

保证在对某一方向（侧面、正面、水平面）切割时，先切割下的应是切块厚度较大的长方体，进而对C¹₃C¹₅C¹₂C¹₃C¹₁C¹₁种切割方式进行讨论，建立最短路模型和动态规划模型，相比较于6×5×4×3×2×1=6！=720种切割方式，计算量大大减少，更容易得到最优切割方案，使切割费用最少。

首先，建立空间网络图和有向图[1]。空间网络图和有向图中每个结点坐标（x，y，z）表示被切割长方体所处的一个状态。其中，x表示垂直于x轴切割刀数，y表示垂直于y轴切割刀数，z表示垂直于轴切割刀数；顶点（0，0，0）表示长方体的待加工状态，顶点（2，2，2）表示长方体的成品状态。问题一即求从（0，0，0）出发到（2，2，2）结束的最短路问题[2]。

空间网络图如图1所示。

有向图如图2所示。

由有向图可知被切割长方体的所有状态及所有切割方式。

其次，对有向图进行分析，需求得各有向边的权值。由于要得到最小加工费用，故将切割单位面积的费用作为权值。

此时需考虑调整刀具带来的额外费用，根据问题假设分析产生额外费用的原因，是因为存在三种换刀情况：

如果切割了一个垂直面后，再切割与之相平行的那个垂直面，然后再切割另外两个相互平行的垂直面，那么需要换刀一次；

如果切割了一个垂直面后，再切割与之不平行的某个垂直面，然后再切割与第二个被切垂直面相平行的那个垂直面，最后切割与第二个被切垂直面相平行的那个垂直面，那么需要换刀两次；

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

上述三种换刀情况分别产生e、2e、3e的额外费用。

最后，建立动态规划模型[3]，得到加工费用表达式。设（1，0，0）、（0，1，0）、（0，0，1）分别对应刀具垂直于x轴、y轴、z轴切割的状态。

i的取值为1、2、3，ei分别对应三种换刀额外费用。

根据上述方程及表达式即可得到所有切割方式下加工费用的值，最后将所有结果进行比较取得最小值，即为最少加工费用，同时可得相应最短路径即为加工方式。上述过程的实现借助于Visual C++软件进行编程。

3 问题二的求解

对每次选择一个加工费用最少的待切割面进行切割的准则进行分析，由于调整刀具产生的额外费用的存在，若选择加工费用最少的待切割面进行切割，在额外费用较大时，此时得到的加工费用可能不是最小；此准则为局部最优准则但不是全局最优准则，且只有在变量参数满足一定条件时才是成立的。

4 问题三的求解

待加工长方体有三个切割方向，每个方向切下两块，考虑到额外费用为零时，水平切割单位面积的费用是垂直切割单位面积费用的r倍，故定义此时侧面方向、正面方向、水平面方向六块切块的厚度分别为rl1、rl2、rw1、rw2、h1、h2。

由上文可知，在对某一方向（侧面、正面、水平面）切割时，先切割下的应是切块厚度较大的长方体，故此时每次切割时都应切剩余上述定义厚度中最大的切块，即每次切rl1、rl2、rw1、rw2、h1、h2中剩余厚度最大的切块。

5 评价与改进方向

5.1 优点

对需考虑的720种加工方式进行了优化，缩减至90种，大大减少了计算量，能快速找出最少费用及其对应加工方式；

考虑的情况比较全面，对额外费用的有无、额外费用存在的三种情况等进行了分析；

易于编程实现。

5.2 模型的缺点

只适用于待加工物体为长方体的情况，没有很好的普遍性。

没有考虑刀具磨损等加工费用。

5.3 模型的改进方向

针对只适用于待加工物体为长方体的情况，我们可对最短路模型和动态规划模型进行改进，使之适用于任何形状的待加工物体。

参考文献：

[1]徐俊明.图论及其应用[M].安徽：中国科学技术大学出版社，2010.

[2]姜启源.数学模型[M].北京：高等教育出版社，2011.

[3]滕宇.动态规划原理及应用[M].四川：西南交通大学出版社，2011.