加工业中截断切割的优化设计.docx

加工业中截断切割的优化设计1.摘要本文讨论了加工业中截断切割的优化排序策略我们对于不同的切 割方式总数用穷举法得到720种所可行解及其费用并对于原问题建 立了决策模型基于全局静态和局部动态两个思路入手进行优化求解给出三 种更实用的算法并对所给出的算法进行了分析和检验1. 在简化的二维问题中，我们归纳出解决问题的简明法则，并将其类 比到三维空间，从而提出了将面间距统一成判断权重来作为排序准则的算 法，同时证明Te = 0的情况下根据这种简明准则能够实现题目所要求的优化目 标2. 对于e女0时我们对算法1的优化准则改进并结合动态规划思想 提出得到问题最优解的方法3. 然后我们又从组合优化方向出发采用了行之有效的模拟退火法 最后我们结合实际问题将本问题进行了拓展讨论了当最终产品（成 品）在毛坯（待加工长方体）中位置不预定时应如何实施加工方案以达到节省费用和节约资源的目的，使我们的方案适用于更为广阔的领域二问题的重述随着人类的发展自然资源不断地被开发利用科学技术也日新月异而对原材料的加工是工业生产的基础环节是将资源转化为劳动产品的第一步因此采用何种加工方式能使加工费用最少资源最大利用从而降低产品的成本是加工工业中一个重要问题对本题所给出的问题我们首先面临的对加工次序的排序策略然后我们考虑当毛坯和产品位置不预定的时候如何采取策略以达到我们的优化目的1.1工件和刀具的情况从一个长方体中加工出一个已知尺寸位置预定的长方体（这两个长方体的对应表面是平行的）要经过6次截断切割水平切割单位面积的费用是垂直切割单位面积费用的r倍当先后两次垂 直切割的平面不平行时因调整刀具需付出额外费用e另外由于工艺要求与水平工作台接触的长方体底面是事先指定的1.2问题2•考虑不同切割方式的总数•建立数学模型分析如何实现最优切割方式（即安排一种各面加工次序使加工费用最少）•对每次选择一个加工费用最少的待切割面进行切割的加工方式进行评价•对调整刀具e 0的情况下提出简明优化准则•对于给出的实例验证所提出的方法并作讨论（实例数据略）二模型的基本假设和符号说明基本假设1. 切割足够精确每次切割的产品均合格2. 切割刀具为两个一个水平放置一个为垂直放置3. 第一次作垂直切割时不需调整垂直刀具4. 毛坯与水平工作台接触的底面事先指定5. 毛坯正面的水平棱为长侧面水平棱为宽垂直棱为高假设说明1. 切割精度高可以保证最终产品与毛坯对应表面是平行的从而忽略废品情况对加工费用只考虑切割费用和刀具调整费用之和2. 水平方向只需平行移动水平刀具垂直方向只平行移动或调整后 再平行移动刀具因此调整费用e是否付出仅取决于先后两次垂直切割是否平行而不记是否穿插着水平切割3. 第一次垂直切割时刀具不需调整因此只需考虑切割过程中的刀具调整费用符号说明• a ,b, c毛坯的长宽高单位厘米• a槌,C最终产品的长宽高单位厘米• X1, X2, Y1, Y2, Z1, Z2毛坯的左表面右表面前表面后表面上表面下表面• x 1, x2, yl, y2, z1, z2最终产品的左表面右表面前表面后表面上 表面下表面（有时我们为了叙述问题的方便将其依次记为5,6,3,4,1,2）•勺最终产品与毛坯的对应表面的距离j = 1,2, L,6• r水平切割单位面积费用与垂直切割单位面积费用之比• e调整垂直刀具的额外费用• p垂直切割单位面积费用• t.加工过程中的第i刀切割第匕个面rT 0 rT = 11 Lt 1 2 6称作切割向量t 11 1 2L 6为1,2,L,6的一个排列•叫第i次切割的切割费用单位元•七第i次切割被切割掉部分的体积单位立方厘米3• Sj第i次切割时切割面积其它变量如果出现则在使用时另行说明三模型的建立通过对原型的分析，产品的加工可以经过平行（毛坯）的表面的前后六刀得到这里我们将称在切割过程中从毛坯到最终产品的序列半成品称为中间产品我们可以将产品的加工看作一个决策过程决策的状态可以由毛坯或各中间产品待切削面的集合表示如再将毛坯表示为状态S = {林y y z z } 12 经1 2 1 2 ,,,・过切割％的中间产品可以由s ={ x y y z z } 2 1 2 1 2,,,,如此等等而最 终产品的状态可以由/来表示这样一个切割方式对应六个状态S D S D S D S D S D S D SS6 = /而从状态Sj至到S. +1的一个决策对应着Sj中的一个元素d. +1且满足S S { d }，"f i +i这时可将每一步的切割的费用定义为状态S.与决策df的函数fS d.j(，)+1而一个切割方式所需总费用f .£f(S，d i "0 5至此希望得到总费用最少的决策可以由下列模型刻划min f .=£f(S，d i " 0 5s.t s S.u，S S { d }，"f1+1四模型的求解对二维平而切割问题的讨论我们首先讨论简单的二维问题，例如在一块长方形的钢板(l l) 1 2 x上切割一块面积以知〃 1 2u,且位置确定的小块钢板，每一次切割的费用与切割长度成正比，不妨令其为h,水平切图14割单位长度的费用是垂直切割单位长度费用的，倍,为简化此问题不妨不考虑调整刀具的，并设以底边起逆时针方向四边的序号为1,2,3,4;原尤尤尤 4 3 2 1 »> ；任给一种切割方式(4,3,2,1),然后随意调整两个边的切割次序如2和3,得新的排序(4,2,3,1)这两种切割方式的费用之差为c c x rx —=—2 1 3 2所以若x rx 3 2 > ,贝0C］优于C2若x rx 3 2〈则匕劣与c2同样调整2和1的位置得到(4,3,1,2)费用为匕c c rx x _=—3 1 2 1在x rx 1 2 > 时 c1 劣 于 c3若x rx 1 2〈则c1 优于c3综上我们可以总结得到将应的边距转换成统一的权重，对于水平方向的权重w x尸,垂直方向的权重n rx尸，这样一来得到一个统一标度下的权重;然后对权重w从大到小排序，排列的结果就是对应边的切割次序.以这种统一的权重作为排序的准则的方法可以得到很好的验证：在r=1时用穷举法验证可得到最优的结果（4,3,2,1）,由此我们可以将二维的方法类比推广应用到三维，采用将对应的平行平面的面间距转换为统一的标准权重，作为对各面加工的次序排定的准则.对三维情况的讨论算法一权重设定方法对垂直面 权重w r mtm =•，对于水平面 权重w t mm =名词约定逆序如果m v n 且w w v则称切割向量中存在一个逆序S’ ^n并记n为一个切割向量的逆序数半成品i切割i次后得到的多面体定理切割方案的优越性反比于逆序数n如果n = 0则该切割方案是最优的 证明假设存在一个最优切割方案该方案的切割向量的逆序数n ^ 0则切割向中至少有相邻的两个分量七,+1使得w wtitiv+i现将这两次切割调换次序得到新的切割向量rT'对于rT和T'{} r1 +1 6{} rT t L t t Lt”. i +i 6现在存在着如下事实t.和t. +1以前的加工费用和是不变的对于前i +1切割的组合不变排列变化对于半成品i +1其状态是不受影响的而从一个稳定的状态出发r.和ti+1以后的加工费用和也是不变的所以rT和rT，的优劣只取于t,和%的加工费用和的比较5i).第i刀与第刀i+1交错时不妨设如图2方式的两次切 割第i次为垂直切割第i+1刀 为水平切割两种方案得到第i +1个成品的费用差为(c T ) c(T)r rw b wtiti+1ti + 1C) (Jc、T / c'T，r r'Y 0・•・方案r广得到第i+1个产品的费用Xr) Xr)r ry又因为状态一样后几刀的排列未发生变化所以整个方案来说r广的费用少于r尸的费用ii).第'刀与第,+1平行时显然地得到第i+1个产品的费用没有发生变化对于最终产品r厂的费用等于rT的费用所以r广的费用是不大于T的费用而广的逆序数疗=〃一1即我们降低切割向量的逆序所得新方案的代价不多于原方案对于有限长度的排列长度设为m其最大逆序数为m（m一1）2所以我们可以经过最多m（m-1）2次调整得到一个逆序数n = 0的排列而该排列所对应的切割方案的费用是不大于原方案的至此定理得证而由定理得到的优化准则/y基孑动态规化思想给出的算法（对于e > 0的情况）算法二由电.（毛坯与最终产品的面间距）来判断各个面的加工次序方法简 明易于操作但整修方法的讨论与定理的证明均是基于e = 0的情况下一旦/ > 0就不能保证所得结论是最优方案因此为处理更一般的情况我们应将/y考虑在内我们可以从上面e = 0所给出的优化准则中得到启发当e = 0时我们根据V5i的大小来决定切割次序我们可以看出当每切一刀切得的体积越大 那么 以后切割就可以节省更多的费用实际上匕•是与这个节省费用成正比的而S•则是与当前切割的费用成正比的所以V5••实际上代表的含义就是节省费用费用图26所以对于e >0节省费用仍然与匕•成正比但费用则应该是ps xe . +p为切割单位面积所花费的费用x为一布尔变量当切割时若需要调整垂直刀具则x =1否则x = 0我们利用动态规划思想在每一步决定切割面时计算当前状态所有面的切割权重选择权重最大的一个面进行下一次切割直到得到最终产品特别地判断准则在e = 0的情况下切割权重就变成了前一个方案的判断权重此时两者的判断本质是一样的动态优化问题与静态排序达到 了同样的最优化目标（算法和源程序详见附录）用模拟退大法解决本问题 算法三对于原问题的最一般的方法就是将决策集合Q中所有可能一一穷举 再代入费用函数寻求最优方案对于本题六面体的加工问题其所有可能排列也就〃！ = 720种方案如果面数增加那么可能的排列数就是以/y递增产生组合爆炸为解决这一问题我们参考了神经网络中解决组合优化问题的方法并使用模拟退火算法解决本题我们把每种可行方案rT看成某一物质系统的微观状态而c（T）r看成物质系统在状态rT下的内能并用控制参数F类比温度让F从一个足够高的值缓慢下降模拟出每个F的热平衡态即对当前状态rT作一个随机拢动产生一个新状态丁，计算增昌… (丁,) (丁)/ ' 1/ I 1—| 1=|=1一 A z^" /^> \ / ' / /^> \ / /T f I j^^C — C T ' — C T r r并以概率exp(-眼/ kF)接收S，作为新的当前状态如此重复随机拢动足够次数后状态rT.出现为当前状态的概率服从波尔兹曼分布即f Z(F)e () -“ /kF其中Z(F)()e mc T kFii_Z 1/, k为玻尔兹曼。