截断切割问题论文

1、题 目 截断切割问题摘要本文研究了实际生产过程中的截断切割问题，求出最优的切割顺序，使得在对待加工的长方体进行切割时，能够花费最少的切割费，得到最大的收益。根据题中所给的数据，我们发现不同的切割顺序所花费的切割费用是不一样的，所以我们建立模型，通过图论来对其进行求解。首先，我们建立了一个三维的有向赋权网络图，假设图中的弧表示长方体的切割过程，图中的定点表示长方体切割后所处的状态，并对弧权进行赋值，弧权值表示在切割过程中所花费的切割费用。然后通过求最短路径来求出最少的切割费用。我们利用软件得出了如下答案：当时，最少加工费用为：元；切割次序为：，也就是按照的顺序切割。当时，最少加工费用为：元；切割

2、次序为：，也就是按照的顺序切割。 当时，最少加工费用为：元；切割次序为：，也就是按照的顺序切割。（当时，答案较为复杂，请见正文）并且，我们提出了最简明的优化准则，即为“每次选择一个加工费用最少的待切割面进行切割。”当时的情况下，对长方体进行截断切割时，就能够遵循这条准则对其进行切割，花费最小的切割费。关键词：截断切割 最优化模型 图论一、问题重述某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过次截断切割。设水平切割单位面积的费用是垂直切割单

3、位面积费用的倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用。试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下：1、需考虑的不同切割方式的总数。2、给出上述问题的数学模型和求解方法。3、试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。4、对于的情形有无简明的优化准则。5、用以下实例数据验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位

4、均为厘米）。垂直切割费用为每平方厘米元，和的数据有以下组：对最后一组数据应给出所有最优解，并进行讨论。二、模型假设1、假设待加工的长方体与成品长方体的各个对应表面均平行。2、假设水平工作台台面是整平的。3、假设加工费用只与切割费用和刀具调整费有关。4、假设每个待加工的长方体只切割为一个成品长方体，而且每个待加工的长方体至少都需要经过六次切割才能成为成品长方体。三、符号说明截断切割时刀具切割所产生的切割面待加工长方体的第个面与成品长方体第个面的距离待加工长方体的长、宽、高成品长方体的长、宽、高总切割费用垂直切割的单位面积切割费正方体在有向图中所表示的第个状态在第个状态下长方体的长、宽、高在有向图

5、中表示第个状态的切割过程所需的切割费四、问题分析4.1对要求一的分析在这个问题中，加工费用与每一次的切割面积以及总共需要刀具调整次数的有关系，而总的切割面积又与长方体的个切割面的切割次序有关系，所以这个问题能够利用排列组合的知识来解。4.2对要求二的分析在对于最优的加工次序的求解过程中，由于切割方式有种，数据过于庞大，所以我们对这些切割方式先进行初步的优化。考虑到实际情况，我们经过证明发现（证明过程见下文5.2），对于相对的两个切割面进行切割时，先切割与待加工的长方体的外表面距离较大的切割面，所花的切割费用要较少一些。所以我们使用这个筛选方法作为初步优化的方案对切割方式做初步的优化筛选。筛选后

6、的切割方式有种，然后我们运用图论的方法对其进行求解。通过建立一个有向赋权网络图进行求解。然而，因为值的不同，所以在优化过程中还要分为和这两种情况去进行分析，建立相应的有向赋权网络图。然后使用软件进行编程求解。4.3对要求三的分析首先，对于某部门的切割方法进行求解，得出结果为：表1：某部门方法切割表数据组切割费元元元元我们对数据进行分析后发现，当时，某部门使用的准则得出的切割费与我们的结果十分接近；但是当时，答案与我们得出的就有一定的区别，价格要比我们的答案高一点，而且随着的增大而增大，所以很明显，当时，这个准则还是挺适合的；但是在的情况下，这个方法就不太明智了。4.4对要求四的分析其实要求四与

7、要求三的情况是相同的，在要求三中的准则就是对这种情况下的优化方案的一种简化方案。然后我们通过对答案的验证，来证明要求三中提出的准则在的情况下的合理性。五、模型的建立与求解5.1要求一的模型建立与求解对于计算不同的切割方式总数，经过分析，我们发现能够用排列组合的知识来解决这个问题。我们对分别位于前、后、左、右、上、下的切割面进行编号，其相应的编号分别为，然而每一种切割方式都是对这个切割面的一个排列方式，所以总共就有种排列方式。所以我们认为，切割总数应该有种。5.2要求二的模型建立与求解5.2.1对数据的初步优化根据实际情况，当考虑到切割费用时，存在一个局部的优化的方案：在对两个相对的切割面进行切

8、割的时候，切割面与待加工的长方体的外表面距离较大的一个面总是先加工的，这样可以减少总的切割面积，从而节省很多的切割费用。优化方案确立的证明如下：假设待加工的长方体的长宽高分别为，成品长方体长宽高分别为，待加工长方体的第个面与成品长方体第个面的距离为，如下图所示：图1：面俯视图图中，我们以切割面为例：方案一，依次切割，切割费用为：而方案二为依次切割，切割费用为：因为，所以，又因为，所以，方案一的切割费用更小。由此可知，局部优化方案是正确的。所以在切割相对的切割面时，只考虑先切割较大的切割面，再切割另一边的切割面。同理，对这四个面的切割方式也是一样的。而根据上述思想，我们需要考虑的切割方式应该为种

9、。所以在计算最少加工费用时，我们只需要考虑这个满足优化方案的切割方案。5.2.2在的情况下的优化模型与求解在的情况下，我们构造如下图所示的一个有向赋权网络图：图2：有向赋权网络图在有向图中，分别表示长方体在左右、前后、上下方向上被切割的刀数，每个节点表示待加工的长方体所处的状态。而其中每一条弧都表示待加工的长方体正在被切割的过程，然而相应的弧上的权就是在这个切割过程中所需花费的切割费。然后，我们对权进行赋值。因为长方体有种不同的状态，每个状态中的长、宽、高都不同，直接算各个切割过程中的切割费用比较困难，所以我们先将长方体处于各个状态下的长、宽、高计算出来。由于在上文中，我们提出：在对两个相对的

10、切割面进行切割的时候，切割面与待加工的长方体的外表面距离较大的一个面总是先加工的。所以我们在这里就默认使用这种方法对长方体进行切割，利用要求五的数据进行计算。计算结果如下：表2：各个状态下的长方体长、宽、高然后我们对有向图进行分析，我们发现：当长方体处于一个状态时，如果要进行下一步的切割，必然会有个切割过程能够选择，也就是这三个方向。当进行方向上的切割时，；当进行方向上的切割时，；当进行方向上的切割时，。所以我们利用这个规律对权重进行计算，列出如下公式：最后利用这个公式求出弧的权值。得出权值如下表所示：表3：时的权值弧1,21,41,102,32,52,113,63,124,5权值275.51

11、90145275.576585743.5142.5弧4,74,135,65,85,146,96,157,87,16权值19075142.576305722.53820弧8,98,179,1810,1110,1310,1911,1211,1411,20权值38861451001451454058弧12,1512,2113,1413,1613,2214,1514,1714,2315,18权值3043.5751007575403030弧15,2416,1716,2517,1817,2618,2719,2019,2220,21权值22.520202086584058弧20,2321,2422,2322

12、,2523,2423,2624,2725,2626,27权值1612304030161288表4：时的权值弧1,21,41,102,32,52,113,63,124,5权值275.5190217.5275.576875765.25142.5弧4,74,135,65,85,146,96,157,87,16权值190112.5142.576455733.753830弧8,98,179,1810,1110,1310,1911,1211,1411,20权值38129145100217.51454087弧12,1512,2113,1413,1613,2214,1514,1714,2315,18权值306

13、5.2575100112.575404530弧15,2416,1716,2517,1817,2618,2719,2019,2220,21权值33.75203020129584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27权值1612304030161288表5：时的权值弧1,21,41,102,32,52,113,63,124,5权值275.5190116275.57646457248142.5弧4,74,135,65,85,146,96,157,87,16权值19060142.5762405718038160弧8,98,179,1810,1

14、110,1310,1911,1211,1411,20权值3864481451001161454046.4弧12,1512,2113,1413,1613,2214,1514,1714,2315,18权值3034.875100607540230弧15,2416,1716,2517,1817,2618,2719,2019,2220,21权值18020160206448584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27权值1612304030161288在有向图中，从到总共有条有向道路，即有种切割方法对待加工的长方体进行切割，其中到的最少费用的路径

15、即为最少加工费用，其所对应的即为最优切割方式。当时，最少加工费用为：元；切割次序为：，也就是按照的顺序切割。当时，最少加工费用为：元；切割次序为：，也就是按照的顺序切割。 当时，最少加工费用为：元；切割次序为：，也就是按照的顺序切割。5.2.3在的情况下的优化模型与求解当的情况下，当两次垂直切割的平面不平行时，就必须增加调整刀具费。但是调整刀具费只于垂直切割有关，与是否穿插水平切割无关。所以在计算刀具费的过程中，只需要考虑四个垂直切割的安排次序。然后运用上文的有向赋权网络图中的某些弧上增加权来实现费用的增加，从而利用上文的模型对的情况进行求解。经过讨论，在四个垂直切割的切割次序中，只可能存在三

16、种可能的情况增加调整刀具费：一是：先切割一对平面，然后再切割一对平面，变刀一次，总费用比之前增加。二是：先切割一个平面，然后再切割另一对平面，最后切割与第一次切割的平面相对的平面，变刀两次，总费用比之前增加。三是：先切割一个平面，然后再切割与第一个平面垂直的平面，接着是与第一个平面平行的平面，最后切割与第二个平面平行的平面，变刀三次，总费用比之前增加。垂直切割的顺序安排情况如下表所示：表6：垂直切割顺序安排表垂直切割顺序有向路路径我们利用的情况中的有向图对其进行求解，在图中的一些弧上增加权来对调整刀具费进行计算。但是，我们发现在这个情况中，弧是往往是多条路径公用的，如果在一些弧上增加权，很可能

17、影响到其他的路径，从而影响解题。所以我们将上表中的六个情况分开进行讨论，形成六个新的有向图，而且这六个有向图是互补的，因此最短花费路径必然存在于这六个有向图之中。我们分别对这六个有向图进行求解，得出六个最少花费路径，然后对这六个值进行比较，最后得出一个最少花费。综合上述分析，我们将原来的有向赋权网络图分成六个部分，分成如下的六个能够互补的有向图：图3： 图4：图5： 图6：图7： 图8：然后分别求出有向图中的最短花费路径，在这六个值中找出最少的花费，及其切割次序。最后得出答案如下表所示：表7：时的答案表数据组切割费切割方案1.52443.51.52.54451.53445.51.53.5446

18、1.54446.55.3要求三对准则的评价经过分析比较，我们发现“每次选择一个加工费用最少的待切割面进行切割。”这条准则是存在限制条件的。也就是说，在的这种情况下，这条准则所执行的切割方法是最优的切割方法之一，得出的结果与我们建立模型，以及利用软件进行求解的结果十分相近；但是当的情况下，也就是存在调整刀具费的情况下，这条准则就不是很明智了。在执行这条准则时，并没有将调整刀具费也计算进去，使得切割费最后会有所增加，而且这种增加量与调整刀具费的大小其实是成正比关系的，当越大时，最后的切割费与最优解的差距就越大；当越小时，最后的切割费与最优解的差距就越小。所以我们认为，在的情况下采用这条准则是合理的

19、，在的情况下，这条准则不能作为最优化准则来使用。5.4要求四的情况的最简优化在对要求三的准则和我们得出的答案进行分析后我们发现，在的情况下，的改变势必会引起最佳切割方案的改变。因为是与水平面的切割有关的，水平切割的单位面积切割费用为垂直切割的倍，然而当时，我们发现，我们通过建立模型以及软件的求解得出的切割方案遵循了“每次选择一个加工费用最少的待切割面进行切割。”这条准则，而且当越大时，我们发现对水平切割的切割次序就越往后，但是依然遵循了“每次选择一个加工费用最少的待切割面进行切割。”这条准则。所以我们认为，在要求三中的提出的优化准则，在时的情况下是成立的，并且能够作为的情形最简明的优化准则。5.5要求五的模型建立与求解对于要求五，我们利用题目中的数据来计算，得出结果如下表所示：表8：答案表参数组切割方案切割费103741.50437.580540.51.52443.51.52.54451.53445.51.53.54461.54446.5（其余见附录I）我们在对这种情况进行分析时发现，当的值较小时，随