最优截断切割问题.doc

B题 截断切割 组号：14 截断切割 摘要 本文讨论的问题是实际生产加工中的截断切割问题，研究了采用何种切割顺序能使得材料切割所用费用最省。根据题中条件，待加工材料和成品均为长方体，且不同的加工顺序使得材料切割费用不同，我们考虑了将三维直角坐标系与有向图相结合的方式构造模型。本文构造的有向图是三维形式的，有向图的顶点坐标（x，y，z）x，y，z3，1，4，5，2，6 （4）当r=1.5，e=2时，最短切割路径为：3，1，5，4，6，2；3，5，1，4，6，2 （1）（2）（3）（4）情况的最少费用分别为：374，437.5，540.5，443.5。（数字1,2,3,4,5,6分别代表切割左右前后上下面） 当然，本文是假设切割是在一定的切割原则，即在两个平行待切割面中，边距较大的待切割面总是先加工这一原则下进行的，这是符合基本的切割作业常识的，也符合截断切割的同类换序定理（在截断切割方式中交换其内相邻同类切割的切割次序，总切割面积不因切割面积的交换而改变；若交换间隔一异类切割的的同类切割的切割次序，则割弃长较大的同类切割面先切割者，其总切割面积较小）。再者，由题意，成品与待切割品的相邻平行面的距离已经给定。那么也可以通过调整相邻平行面的距离而使得切割花费达到更省，这是本题可以改进的一个方向。 关键词：截断切割 最优切割次序 一、问题重述 在某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6 次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r倍。且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e。现今要设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。 从排列组合的角度考虑，切割方法应有种，当然这其中也会有一些方法是等价的，现在我们规定两个平行待切割面中，边距较大的待切割面总是先加工。每一次切割由于会使得相邻面的相应边长减小，所以会影响到下一次切割时所需的切割费用。水平面与竖直面的单位面积加工费用又不相同。所以安排加工面次序的问题就应该转化为多阶段动态问题，而图解法又是解决这一问题的良策。 二、模型假设与符号说明 模型假设 待加工长方体与成品长方体对应表面平行。 工作台是水平的，而且加工工件与水平台的接触面是事先指定好的，不允许改变。 假设水平切割单位面积的费用为r，垂直切割单位面积费用为1； 第一次切割前，刀具已经调整完毕，即第一次垂直切割不加入刀具调整费用； 每个待加工长方体都必须经过6次截断切割. 假设在切割时，遵守这样的准则：两个平行待切割面中，边距较大的待切割面总是先加工。 符号说明 ,,分别表示待加工长方体的长、宽、高。 ,,分别表示成品长方体的长、宽、高。 ,,,,,分别表示待加工长方体与成品长方体。 有向图顶点是，坐标为（,,），,,分别代表侧面（左右面）、正面（前后面）、水平面（上下面）的切割次数。其中,,都在{0.1.2}中取值。 ,,分别表示在时，长方体左右、前后、上下面的距离。 有向弧（,）代表一个从至的切割步骤，弧的权值代表弧所代表的加工步骤需要的加工费。 三、Ⅰ、考虑不同切割方式的总数 设待加工长方体的左右面、前后面、上下面间的距离分别为、、。六个切割面分别位于左、右、前、后、上、下，将它们相应编号为、、、、、，这六个面与待加工长方体相应外侧面的边距分别为、、、、、。这样，一种切割方式就是六个切割面的一个排列，共有种切割方式。当考虑到切割费用时，显然有局部优化准则：两个平行待切割面中，边距较大的待切割面总是先加工。 由此准则,只需考虑种切割方式。即在求最少加工费用时，只需在90个满足准则的切割序列中考虑。不失一般性，设、、，故只考虑在前、在前、在前的切割方式。 Ⅱ、根据不同情况建立数学模型 1、e=0的情况 为简单起见,先考虑e=0的情况。构造如图所示的一个有向赋权网络图G(V,E)。为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z。 G(V,E) 图G(V,E)的含义为： (1)、空间网络图中每个结点（,,）表示被切割石材所处的一个状态。顶点坐标，，分别代表石材在左右、前后、上下方向上已被切割的刀数。顶点(0,0,0)表示石材的最初待加工状态，顶点(2,2,2)表示石材加工完成后的状态。 (2)、G的弧（,）表示石材被切割的一个过程，若长方体能从状态经一次切割变为状态，即当且仅当时，（,,）到(,,)有弧(,)，相应弧上的权(,)即为这一切割过程的费用。对于任意相邻状态的点之间的弧的权值公式如下： 其中，、、分