截断切割问题论文

题目截断切割问题摘要本文研究了实际生产过程中的截断切割问题，求出最优的切割顺序，使得在对待加工的长方体进行切割时，能够花费最少的切割费，得到最大的收益。根据题中所给的数据，我们发现不同的切割顺序所花费的切割费用是不一样的，所以我们建立模型，通过图论来对其进行求解。首先，我们建立了一个三维的有向赋权网络图，假设图中的弧表示长方体的切割过程，图中的定点表示长方体切割后所处的状态，并对弧权进行赋值，弧权值表示在切割过程中所花费的切割费用。然后通过求最短路径来求出最少的切割费用。我们利用Lingo软件得出了如下答案：当1,0re时，最少加工费用为：374元；切割次序为：1101322232627，也就是按照615324MMMMMM的顺序切割。当1.5,0re时，最少加工费用为：437.5元；切割次序为：141314172627，也就是按照163254MMMMMM的顺序切割。当8,0re时，最少加工费用为：540.5元；切割次序为：1458171827，也就是按照132645MMMMMM的顺序切割。（当1.5,215re时，答案较为复杂，请见正文）并且，我们提出了最简明的优化准则，即为“每次选择一个加工费用最少的待切割面进行切割。”当0e时的情况下，对长方体进行截断切割时，就能够遵循这条准则对其进行切割，花费最小的切割费。关键词：截断切割最优化模型图论1一、问题重述某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割。设水平切割单位面积的费用是垂直切割单位面积费用的r倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用e。试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下：1、需考虑的不同切割方式的总数。2、给出上述问题的数学模型和求解方法。3、试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。4、对于0e的情形有无简明的优化准则。5、用以下实例数据验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。垂直切割费用为每平方厘米1元，r和e的数据有以下4组：.1,0.1.5,0arebre.8,0.1.5,215credre对最后一组数据应给出所有最优解，并进行讨论。二、模型假设1、假设待加工的长方体与成品长方体的各个对应表面均平行。2、假设水平工作台台面是整平的。3、假设加工费用只与切割费用和刀具调整费有关。4、假设每个待加工的长方体只切割为一个成品长方体，而且每个待加工的长方体至少都需要经过六次切割才能成为成品长方体。三、符号说明(1,2,...,6)iMi截断切割时刀具切割所产生的切割面il待加工长方体的第i个面与成品长方体第i个面的距离000,,abc待加工长方体的长、宽、高272727,,abc成品长方体的长、宽、高S总切割费用p垂直切割的单位面积切割费,(,1,2,...,30)jkvvjk正方体在有向图中所表示的第,jk个状态,,jjjabc在第j个状态下长方体的长、宽、高,jks在有向图中表示第~jk个状态的切割过程所需的切割费2四、问题分析4.1对要求一的分析在这个问题中，加工费用与每一次的切割面积以及总共需要刀具调整次数的有关系，而总的切割面积又与长方体的6个切割面的切割次序有关系，所以这个问题能够利用排列组合的知识来解。4.2对要求二的分析在对于最优的加工次序的求解过程中，由于切割方式有720种，数据过于庞大，所以我们对这些切割方式先进行初步的优化。考虑到实际情况，我们经过证明发现（证明过程见下文5.2），对于相对的两个切割面进行切割时，先切割与待加工的长方体的外表面距离较大的切割面，所花的切割费用要较少一些。所以我们使用这个筛选方法作为初步优化的方案对切割方式做初步的优化筛选。筛选后的切割方式有90种，然后我们运用图论的方法对其进行求解。通过建立一个有向赋权网络图进行求解。然而，因为e值的不同，所以在优化过程中还要分为0e和0e这两种情况去进行分析，建立相应的有向赋权网络图。然后使用Lingo软件进行编程求解。4.3对要求三的分析首先，对于某部门的切割方法进行求解，得出结果为：表1：某部门方法切割表数据组切割费1,0re374元1.5,0re437.5元8,0re540.5元1.5,215re437.53=443.5~482.5e元我们对数据进行分析后发现，当0e时，某部门使用的准则得出的切割费与我们的结果十分接近；但是当0e时，答案与我们得出的就有一定的区别，价格要比我们的答案高一点，而且随着e的增大而增大，所以很明显，当0e时，这个准则还是挺适合的；但是在0e的情况下，这个方法就不太明智了。4.4对要求四的分析其实要求四与要求三的情况是相同的，在要求三中的准则就是对0e这种情况下的优化方案的一种简化方案。然后我们通过对答案的验证，来证明要求三中提出的准则在0e的情况下的合理性。五、模型的建立与求解5.1要求一的模型建立与求解对于计算不同的切割方式总数，经过分析，我们发现能够用排列组合的知识来解决这个问题。我们对分别位于前、后、左、右、上、下的切割面进行编号，其相应的编号分别为123456,,,,,MMMMMM，然而每一种切割方式都是对这6个切割面的一个排列方式，所以总共就有66720A种排列方式。所以我们认为，切割总数应该有720种。35.2要求二的模型建立与求解5.2.1对数据的初步优化根据实际情况，当考虑到切割费用时，存在一个局部的优化的方案：在对两个相对的切割面进行切割的时候，切割面与待加工的长方体的外表面距离较大的一个面总是先加工的，这样可以减少总的切割面积，从而节省很多的切割费用。优化方案确立的证明如下：假设待加工的长方体的长宽高分别为000,,abc，成品长方体长宽高分别为272727,,abc，待加工长方体的第i个面与成品长方体第i个面的距离为il，如下图所示：图1：面5M俯视图图中12ll，34ll，我们以切割面12,MM为例：方案一，依次切割132,,MMM，切割费用为：100010030()()Sacpblcpalcp而方案二为依次切割231,,MMM，切割费用为：200020030()()Sacpblcpalcp12010020210()()()SSblcpblcpllcp因为12ll，所以210ll，又因为0,0cp，所以120SS，方案一的切割费用更小。由此可知，局部优化方案是正确的。所以在切割相对的切割面时，只考虑先切割l较大的切割面，再切割另一边的切割面。同理，对3456,,,MMMM这四个面的切割方式也是一样的。而根据上述思想，我们需要考虑的切割方式应该为6690222A种。所以在计算最少加工费用时，我们只需要考虑这90个满足优化方案的切割方案。5.2.2在0e的情况下的优化模型与求解在0e的情况下，我们构造如下图所示的一个有向赋权网络图(,)GVE：4图2：有向赋权网络图在有向图中，,,(1,2)mmmxyzm分别表示长方体在左右、前后、上下方向上被切割的刀数，每个节点表示待加工的长方体所处的状态。而其中每一条弧都表示待加工的长方体正在被切割的过程，然而相应的弧,jkv上的权就是在这个切割过程中所需花费的切割费,jks。然后，我们对权进行赋值。因为长方体有27种不同的状态，每个状态中的长、宽、高都不同，直接算各个切割过程中的切割费用比较困难，所以我们先将长方体处于各个状态下的长、宽、高计算出来。由于在上文中，我们提出：在对两个相对的切割面进行切割的时候，切割面与待加工的长方体的外表面距离较大的一个面总是先加工的。所以我们在这里就默认使用这种方法对长方体进行切割，利用要求五的数据进行计算。计算结果如下：5表2：各个状态下的长方体长、宽、高1(10,14.5,19)V10(10,14.5,10)V19(10,14.5,4)V2(4,14.5,19)V11(4,14.5,10)V20(4,14.5,4)V3(3,14.5,19)V12(3,14.5,10)V21(3,14.5,4)V4(10,7.5,19)V13(10,7.5,10)V22(10,7.5,4)V5(4,7.5,19)V14(4,7.5,10)V23(4,7.5,4)V6(3,7.5,19)V15(3,7.5,10)V24(3,7.5,4)V7(10,2,19)V16(10,2,10)V25(10,2,4)V8(4,2,19)V17(4,2,10)V26(4,2,4)V9(3,2,19)V18(3,2,10)V27(3,2,4)V然后我们对有向图进行分析，我们发现：当长方体处于一个状态时，如果要进行下一步的切割，必然会有1~3个切割过程能够选择，也就是,,xyz这三个方向。当进行x方向上的切割时，1kj；当进行y方向上的切割时，3kj；当进行z方向上的切割时，9kj。所以我们利用这个规律对权重进行计算，列出如下公式：,,,(1)(3)()(9)jkjjjkjjjkjjsbcpkjsacpkjsabprkj最后利用这个公式求出弧的权值。得出权值如下表所示：表3：1,0re时的权值弧1,21,41,102,32,52,113,63,124,5权值275.5190145275.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,2523,2423,2624,2725,2626,27权值16123040301612886表4：1.5,0re时的权值弧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权值3065.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：8,0re时的权值弧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.57624