截断切割问题论文 Prepared on 22 November 2020题 目 截断切割问题摘要本文研究了实际生产过程中的截断切割问题，求出最优的切割顺序，使得在对待加工的长方体进行切割时，能够花费最少的切割费，得到最大的收益。

根据题中所给的数据，我们发现不同的切割顺序所花费的切割费用是不一样的，所以我们建立模型，通过图论来对其进行求解。

首先，我们建立了一个三维的有向赋权网络图，假设图中的弧表示长方体的切割过程，图中的定点表示长方体切割后所处的状态，并对弧权进行赋值，弧权值表示在切割过程中所花费的切割费用。

然后通过求最短路径来求出最少的切割费用。

我们利用Lingo 软件得出了如下答案：当1,0r e ==时，最少加工费用为：374元；切割次序为：1101322232627------，也就是按照615324M M M M M M -----的顺序切割。

当 1.5,0r e ==时，最少加工费用为：437.5元；切割次序为：141314172627------，也就是按照163254M M M M M M -----的顺序切割。

当8,0r e ==时，最少加工费用为：540.5元；切割次序为：1458171827------，也就是按照132645M M M M M M -----的顺序切割。

（当1.5,215r e =≤≤时，答案较为复杂，请见正文）并且，我们提出了最简明的优化准则，即为“每次选择一个加工费用最少的待切割面进行切割。

”当0e =时的情况下，对长方体进行截断切割时，就能够遵循这条准则对其进行切割，花费最小的切割费。

关键词：截断切割 最优化模型 图论一、问题重述某些工业部门（如贵重石材加工等）采用截断切割的加工方式。

这里“截断切割”是指将物体沿某个切割平面分成两部分。

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割。

设水平切割单位面积的费用是垂直切割单位面积费用的r 倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用e 。

试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。

（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下：1、需考虑的不同切割方式的总数。

2、给出上述问题的数学模型和求解方法。

3、试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。

4、对于0e =的情形有无简明的优化准则。

5、用以下实例数据验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。

垂直切割费用为每平方厘米1元，r 和e 的数据有以下4组：对最后一组数据应给出所有最优解，并进行讨论。

二、模型假设1、假设待加工的长方体与成品长方体的各个对应表面均平行。

2、假设水平工作台台面是整平的。

3、假设加工费用只与切割费用和刀具调整费有关。

4、假设每个待加工的长方体只切割为一个成品长方体，而且每个待加工的长方体至少都需要经过六次切割才能成为成品长方体。

对要求一的分析在这个问题中，加工费用与每一次的切割面积以及总共需要刀具调整次数的有关系，而总的切割面积又与长方体的6个切割面的切割次序有关系，所以这个问题能够利用排列组合的知识来解。

对要求二的分析在对于最优的加工次序的求解过程中，由于切割方式有720种，数据过于庞大，所以我们对这些切割方式先进行初步的优化。

考虑到实际情况，我们经过证明发现（证明过程见下文），对于相对的两个切割面进行切割时，先切割与待加工的长方体的外表面距离较大的切割面，所花的切割费用要较少一些。

所以我们使用这个筛选方法作为初步优化的方案对切割方式做初步的优化筛选。

筛选后的切割方式有90种，然后我们运用图论的方法对其进行求解。

通过建立一个有向赋权网络图进行求解。

然而，因为e值的不同，所以在优化过程中还要分为0e=和0e≠这两种情况去进行分析，建立相应的有向赋权网络图。

然后使用Lingo软件进行编程求解。

对要求三的分析首先，对于某部门的切割方法进行求解，得出结果为：我们对数据进行分析后发现，当0e =时，某部门使用的准则得出的切割费与我们的结果十分接近；但是当0e ≠时，答案与我们得出的就有一定的区别，价格要比我们的答案高一点，而且随着e 的增大而增大，所以很明显，当0e =时，这个准则还是挺适合的；但是在0e ≠的情况下，这个方法就不太明智了。

对要求四的分析其实要求四与要求三的情况是相同的，在要求三中的准则就是对0e =这种情况下的优化方案的一种简化方案。

然后我们通过对答案的验证，来证明要求三中提出的准则在0e =的情况下的合理性。

五、模型的建立与求解要求一的模型建立与求解对于计算不同的切割方式总数，经过分析，我们发现能够用排列组合的知识来解决这个问题。

我们对分别位于前、后、左、右、上、下的切割面进行编号，其相应的编号分别为123456,,,,,M M M M M M ，然而每一种切割方式都是对这6个切割面的一个排列方式，所以总共就有66720A =种排列方式。

所以我们认为，切割总数应该有720种。

要求二的模型建立与求解根据实际情况，当考虑到切割费用时，存在一个局部的优化的方案：在对两个相对的切割面进行切割的时候，切割面与待加工的长方体的外表面距离较大的一个面总是先加工的，这样可以减少总的切割面积，从而节省很多的切割费用。

优化方案确立的证明如下：假设待加工的长方体的长宽高分别为000,,a b c ，成品长方体长宽高分别为272727,,a b c ，待加工长方体的第i 个面与成品长方体第i 个面的距离为i l ，如下图所示：图1：面5M 俯视图图中12l l >，34l l >，我们以切割面12,M M 为例：方案一，依次切割132,,M M M ，切割费用为：而方案二为依次切割231,,M M M ，切割费用为：因为12l l >，所以210l l -<，又因为0,0c p >，所以120S S -<，方案一的切割费用更小。

由此可知，局部优化方案是正确的。

所以在切割相对的切割面时，只考虑先切割l 较大的切割面，再切割另一边的切割面。

同理，对3456,,,M M M M 这四个面的切割方式也是一样的。

而根据上述思想，我们需要考虑的切割方式应该为6690222A =⨯⨯种。

所以在计算最少加工费用时，我们只需要考虑这90个满足优化方案的切割方案。

0e =的情况下的优化模型与求解在0e =的情况下，我们构造如下图所示的一个有向赋权网络图(,)G V E ：图2：有向赋权网络图在有向图中，,,(1,2)m m m x y z m =分别表示长方体在左右、前后、上下方向上被切割的刀数，每个节点表示待加工的长方体所处的状态。

而其中每一条弧都表示待加工的长方体正在被切割的过程，然而相应的弧,j k v 上的权就是在这个切割过程中所需花费的切割费,j k s 。

然后，我们对权进行赋值。

因为长方体有27种不同的状态，每个状态中的长、宽、高都不同，直接算各个切割过程中的切割费用比较困难，所以我们先将长方体处于各个状态下的长、宽、高计算出来。

由于在上文中，我们提出：在对两个相对的切割面进行切割的时候，切割面与待加工的长方体的外表面距离较大的一个面总是先加工的。

所以我们在这里就默认使用这种方法对长方体进行切割，利用要求五的数据进行计算。

计算结果如下：一步的切割，必然会有1~3个切割过程能够选择，也就是,,x y z 这三个方向。

当进行x 方向上的切割时，1k j -=；当进行y 方向上的切割时，3k j -=；当进行z 方向上的切割时，9k j -=。

所以我们利用这个规律对权重进行计算，列出如下公式：最后利用这个公式求出弧的权值。

得出权值如下表所示：127体进行切割，其中1v 到27v 的最少费用的路径即为最少加工费用，其所对应的即为最优切割方式。

当1,0r e ==时，最少加工费用为：374元；切割次序为：1101322232627------，也就是按照615324M M M M M M -----的顺序切割。

当 1.5,0r e ==时，最少加工费用为：437.5元；切割次序为：141314172627------，也就是按照163254M M M M M M -----的顺序切割。

当8,0r e ==时，最少加工费用为：540.5元；切割次序为：1458171827------，也就是按照132645M M M M M M -----的顺序切割。

0e ≠的情况下的优化模型与求解当0e ≠的情况下，当两次垂直切割的平面不平行时，就必须增加调整刀具费e 。

但是调整刀具费只于垂直切割有关，与是否穿插水平切割无关。

所以在计算刀具费的过程中，只需要考虑四个垂直切割的安排次序。

然后运用上文的有向赋权网络图中的某些弧上增加权来实现费用的增加，从而利用上文的模型对0e ≠的情况进行求解。

经过讨论，在四个垂直切割的切割次序中，只可能存在三种可能的情况增加调整刀具费e ：一是：先切割一对平面，然后再切割一对平面，变刀一次，总费用比之前增加e 。

二是：先切割一个平面，然后再切割另一对平面，最后切割与第一次切割的平面相对的平面，变刀两次，总费用比之前增加2e 。

三是：先切割一个平面，然后再切割与第一个平面垂直的平面，接着是与第一个平面平行的平面，最后切割与第二个平面平行的平面，变刀三次，总费用比之前增加3e 。

垂直切割的顺序安排情况如下表所示：刀具费进行计算。

但是，我们发现在0e =这个情况中，弧是往往是多条路径公用的，如果在一些弧上增加权，很可能影响到其他的路径，从而影响解题。

所以我们将上表中的六个情况分开进行讨论，形成六个新的有向图，而且这六个有向图是互补的，因此最短花费路径必然存在于这六个有向图之中。

我们分别对这六个有向图进行求解，得出六个最少花费路径，然后对这六个值进行比较，最后得出一个最少花费。

综合上述分析，我们将原来的有向赋权网络图分成六个部分，分成如下的六个能够互补的有向图123456,,,,,H H H H H H ：图3：1H 图4：2H图5：3H 图6：4H图7：5H 图8：6H然后分别求出有向图123456,,,,,H H H H H H 中127~v v 的最短花费路径，在这六个值中找出最少的花费，及其切割次序。

最后得出答案如下表所示：经过分析比较，我们发现“每次选择一个加工费用最少的待切割面进行切割。

”这条准则是存在限制条件的。

也就是说，在0e =的这种情况下，这条准则所执行的切割方法是最优的切割方法之一，得出的结果与我们建立模型，以及利用Lingo 软件进行求解的结果十分相近；但是当0e ≠的情况下，也就是存在调整刀具费的情况下，这条准则就不是很明智了。