截断切割问题论文.doc

摘要
本文研究了实际生产过程中的截断切割问题,求出最优的切割顺序,使得在对待加工的长方体进行切割时,能够花费最少的切割费,得到最大的收益。
根据题中所给的数据,我们发现不同的切割顺序所花费的切割费用是不一样的,所以我们建立模型,通过图论来对其进行求解。
首先,我们建立了一个三维的有向赋权网络图,假设图中的弧表示长方体的切割过程,图中的定点表示长方体切割后所处的状态,并对弧权进行赋值,弧权值表示在切割过程中所花费的切割费用。
然后通过求最短路径来求出最少的切割费用。我们利用软件得出了如下答案:
当时,最少加工费用为:元;切割次序为:,也就是按照的顺序切割。
当时,最少加工费用为:元;切割次序为:,也就是按照的顺序切割。
当时,最少加工费用为:元;切割次序为:,也就是按照的顺序切割。(当时,答案较为复杂,请见正文)
并且,我们提出了最简明的优化准则,即为“每次选择一个加工费用最少的待切割面进行切割。”当时的情况下,对长方体进行截断切割时,就能够遵循这条准则对其进行切割,花费最小的切割费。
关键词:截断切割最优化模型图论
一、问题重述
某些工业部门(如贵重石材加工等)采用截断切割的加工方式。这里“截断切割”
是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体(这两个长方体的对应表面是平行的),通常要经过次截断切割。
设水平切割单位面积的费用是垂直切割单位面积费用的倍,且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时,因调整***需额外费用。
试为这些部门设计一种安排各面加工次序(称“切割方式”)的方法,使加工费用最少。(由工艺要求,与水平工作台接触的长方体底面是事先指定的)详细要求如下:
1、需考虑的不同切割方式的总数。
2、给出上述问题的数学模型和求解方法。
3、试对某部门用的如下准则作出评价:每次选择一个加工费用最少的待切割面进行切割。
4、对于的情形有无简明的优化准则。
5、用以下实例数据验证你的方法:待加工长方体和成品长方体的长、宽、高分别为10、、19和3、2、4,二者左侧面、正面、底面之间的距离分别为6、7、9(单位均为厘米)。垂直切割费用为每平方厘米元,和的数据有以下组:

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

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

在对于最优的加工次序的求解过程中,由于切割方式有种,数据过于庞大,所以我们对这些切割方式先进行初步的优化。
考虑到实际情况,我们经过证明发现(),对于相对的两个切割面进行切割时,先切割与待加工的长方体的外表面距离较大的切割面,所花的切割费用要较少一些。所以我们使用这个筛选方法作为初步优化的方案对切割方式做初步的优化筛选。
筛选后的切割方式有种,然后我们运用图论的方法对其进行求解。通过建立一个有向赋权网络图进行求解。
然而,因为值的不同,所以在优化过程中还要分为和这两种情况去进行分析,建立相应的有向赋权网络图。
然后使用软件进行编程求解。

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

其实要求四与要求三的情况是相同的,在要求三中的准则就是对这种情况下的优化方案的一种简化方案。然后我们通过对答案的验证,来证明要求三中提出的准则在的情况下的合理性。
五、模型的建立与求解