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

加工业中截断切割的优化设计1. 摘要本文讨论了加工业中截断切割的优化排序策略我们对于不同的切割方式总数用穷举法得到720 种所可行解及其费用并对于原问题建立了决策模型基于全局静态和局部动态两个思路入手进行优化求解给出三种更实用的算法并对所给出的算法进行了分析和检验1.在简化的二维问题中,我们归纳出解决问题的简明法则,并将其类比到三维空间,从而提出了将面间距统一成判断权重来作为排序准则的算法,同时证明了e = 0 的情况下根据这种简明准则能够实现题目所要求的优化目标2.对于e 0 时我们对算法1 的优化准则改进并结合动态规划思想提出得到问题最优解的方法3.然后我们又从组合优化方向出发采用了行之有效的模拟退火法最后我们结合实际问题将本问题进行了拓展讨论了当最终产品(成品)在毛坯(待加工长方体)中位置不预定时应如何实施加工方案以达到节省费用和节约资源的目的,使我们的方案适用于更为广阔的领域二问题的重述随着人类的发展自然资源不断地被开发利用科学技术也日新月异而对原材料的加工是工业生产的基础环节是将资源转化为劳动产品的第一步因此采用何种加工方式能使加工费用最少资源最大利用从而降低产品的成本是加工工业中一个重要问题对本题所给出的问题我们首先面临的对加工次序的排序策略然后我们考虑当毛坯和产品位置不预定的时候如何采取策略以达到我们的优化目的1.1 工件和刀具的情况从一个长方体中加工出一个已知尺寸位置预定的长方体(这两个长方体的对应表面是平行的) 要经过6 次截断切割水平切割单位面积的费用是垂直切割单位面积费用的r 倍当先后两次垂直切割的平面不平行时因调整刀具需付出额外费用e 另外由于工艺要求与水平工作台接触的长方体底面是事先指定的1.2 问题2l 考虑不同切割方式的总数l 建立数学模型分析如何实现最优切割方式(即安排一种各面加工次序使加工费用最少)l 对每次选择一个加工费用最少的待切割面进行切割的加工方式进行评价l 对调整刀具e = 0 的情况下提出简明优化准则l 对于给出的实例验证所提出的方法并作讨论(实例数据略)二模型的基本假设和符号说明基本假设1. 切割足够精确每次切割的产品均合格2. 切割刀具为两个一个水平放置一个为垂直放置3. 第一次作垂直切割时不需调整垂直刀具4. 毛坯与水平工作台接触的底面事先指定5. 毛坯正面的水平棱为长侧面水平棱为宽垂直棱为高假设说明1. 切割精度高可以保证最终产品与毛坯对应表面是平行的从而忽略废品情况对加工费用只考虑切割费用和刀具调整费用之和2. 水平方向只需平行移动水平刀具垂直方向只平行移动或调整后再平行移动刀具因此调整费用e 是否付出仅取决于先后两次垂直切割是否平行而不记是否穿插着水平切割3. 第一次垂直切割时刀具不需调整因此只需考虑切割过程中的刀具调整费用符号说明l a ,b, c 毛坯的长宽高单位厘米l a ,b,c 最终产品的长宽高单位厘米l X1, X2,Y1,Y2,Z1,Z2 毛坯的左表面右表面前表面后表面上表面下表面l x1, x2, y1, y2, z1, z2 最终产品的左表面右表面前表面后表面上表面下表面(有时我们为了叙述问题的方便将其依次记为5,6,3,4,1,2)l d j 最终产品与毛坯的对应表面的距离j = 1,2,L,6l r 水平切割单位面积费用与垂直切割单位面积费用之比l e 调整垂直刀具的额外费用l p 垂直切割单位面积费用l ti 加工过程中的第i 刀切割第ti 个面lrT ( ) rT = t t Lt 1 2 6 称作切割向量t t t 1 2L 6 为1,2,L,6的一个排列l wi 第i 次切割的切割费用 单位元l vi 第i 次切割被切割掉部分的体积 单位立方厘米3l si 第i 次切割时切割面积其它变量如果出现则在使用时另行说明三模型的建立通过对原型的分析,产品的加工可以经过平行(毛坯)的表面的前后六刀得到这里我们将称在切割过程中从毛坯到最终产品的序列半成品称为中间产品我们可以将产品的加工看作一个决策过程决策的状态可以由毛坯或各中间产品待切削面的集合表示如再将毛坯表示为状态S = x x y y z z 1 2 1 2 1 2 , , , , , 经过切割x1 的中间产品可以由S = x y y z z 2 1 2 1 2 , , , , 如此等等而最终产品的状态可以由f来表示这样一个切割方式对应六个状态S S S S S S S 1 2 3 4 5 6S6 = f而从状态Si 到Si +1 的一个决策对应着Si 中的一个元素di +1 且满足S S d i i i = +1 +1这时可将每一步的切割的费用定义为状态Si 与决策di +1 的函数f S d i i ( , ) +1而一个切割方式所需总费用fi= f(S ,d i i+1 )05至此希望得到总费用最少的决策可以由下列模型刻划min fi= f(S ,d i i+1 )05s.t S S i ,S S d i i i = +1 +1四模型的求解对二维平面切割问题的讨论我们首先讨论简单的二维问题,例如在一块长方形的钢板(l l ) 1 2 上切割一块面积以知l l 1 2 ,且位置确定的小块钢板,每一次切割的费用与切割长度成正比,不妨令其为h ,水平切图14割单位长度的费用是垂直切割单位长度费用的r 倍,为简化此问题不妨不考虑调整刀具的,并设以底边起逆时针方向四边的序号为1,2,3,4;且x x x x 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 , 则c1 优于c2若x rx 3 2 时 c1 劣于c3若x rx 1 2 则c1 优于c3综上我们可以总结得到将应的边距转换成统一的权重,对于水平方向的权重w x i i = ,垂直方向的权重n rx i i = ,这样一来得到一个统一标度下的权重;然后对权重w从大到小排序,排列的结果就是对应边的切割次序.以这种统一的权重作为排序的准则的方法可以得到很好的验证:在r=1 时用穷举法验证可得到最优的结果(4,3,2,1),由此我们可以将二维的方法类比推广应用到三维,采用将对应的平行平面的面间距转换为统一的标准权重,作为对各面加工的次序排定的准则.对三维情况的讨论算法一权重设定方法对垂直面 权重w r tm tm = ,对于水平面 权重w t tm m =名词约定逆序如果m n 且w w tm tn 则称切割向量中存在一个逆序并记n 为一个切割向量的逆序数半成品i 切割i 次后得到的多面体定理切割方案的优越性反比于逆序数n 如果n = 0 则该切割方案是最优的证明假设存在一个最优切割方案该方案的切割向量的逆序数n 0则切割向中至少有相邻的两个分量t t i i , +1 使得w w ti ti 1 c(T ) c(T)r r - 0方案rT 得到第i +1个产品的费用c(T ) c(T)r r 0就不能保证所得结论是最优方案因此为处理更一般的情况我们应将/y 考虑在内我们可以从上面e = 0 所给出的优化准则中得到启发当e = 0 时我们根据vsii的大小来决定切割次序我们可以看出当每切一刀切得的体积越大那么以后切割就可以节省更多的费用实际上vi 是与这个节省费用成正比的而si则是与当前切割的费用成正比的所以vsii实际上代表的含义就是节省费用费用图26所以对于e 0 节省费用仍然与vi 成正比但费用则应该是ps xe i +p 为切割单位面积所花费的费用x 为一布尔变量当切割时若需要调整垂直刀具则 x = 1 否则 x = 0我们利用动态规划思想在每一步决定切割面时计算当前状态所有面的切割权重选择权重最大的一个面进行下一次切割直到得到最终产品特别地判断准则在e = 0 的情况下切割权重就变成了前一个方案的判断权重此时两者的判断本质是一样的动态优化问题与静态排序达到了同样的最优化目标(算法和源程序详见附录)用模拟退火法解决本问题算法三对于原问题的最一般的方法就是将决策集合D中所有可能一一穷举再代入费用函数寻求最优方案对于本题六面体的加工问题其所有可能排列也就n! = 720 种方案如果面数增加那么可能的排列数就是以/y 递增产生组合爆炸为解决这一问题我们参考了神经网络中解决组合优化问题的方法并使用模拟退火算法解决本题我们把每种可行方案rT 看成某一物质系统的微观状态而c(T)r看成物质系统在状态rT 下的内能并用控制参数F 类比温度让F 从一个足够高的值缓慢下降模拟出每个F 的热平衡态即对当前状态rT 作一个随机拢动产生一个新状态rT 计算增量Dc = c(T ) - c(T)r r并以概率exp(-Dc / kF) 接收S 作为新的当前状态如此重复随机拢动足够次数后状态rTi 出现为当前状态的概率服从波尔兹曼分布即f Z(F)e ( ) = -c Ti /kF其中 Z(F) ( )e c T kFii= - 1/ , k 为玻尔兹曼常数若F 下降足够慢且F 0 则当前状态将具有最少c(T ) ir的状态模拟退火算法主要由由三部分组成(1).以一定的概率密度跃迁到新状态称该概率密度函数为生成函数(2).以一定的概率密度容忍评估函数的偶然上升称该概率密度函数为容忍函数(3).以一定的冷却方式降低温度这个等效温度是控制参量确定所引入的随机扰动强度我们对于算法的重要参数处理如下(1). F0 的选择为100(2).随机扰动的产生方式从rZ 的邻域产生一个状态我们就是随机地对调了排列中两个相邻分量的位置7(3). F 减小的方式F lF,0 l 1可取l 0.2,0.99(4).算法终止取F 小于阀值0.01(模拟退火法的详细算法和程序实现详见附录)对题目所给准则的评价原题中给出的一项准则每一次选择一个加工费用最少的待切割面进行切割我们认为这种准则是不好的当然它也有适用的时候我们可以从二维的情况来论证并假设 e = 0, r = 1/y对于图1 我们给出的算法得出结果是( )( )2 4 3 12 4 1 3, , , , , 或( )( )4 2 3 14 2 1 3, , , , , 它的算法可以得到同样的结果说明它的准则在某些特殊情况是有效的对于图2 我们的算法给出的最优排序是( )( )1 3 2 41 3 4 2, , , , , 或( )( )3 1 2 43 1 4 2, , , , , 而原题给出的算法得出结果却是(2,4,1,3) 或(4,2,1,3)分析原因它的准则在处理第一次切割时选择加工费用最少的待切割面实际上是由毛坯的外形决定的而与最终产品在毛坯中的相对位置无关所以对于给定的毛坯它的第一次切割永不会改变这显然是极不合理的对于三维的情况更是如此所造成的误差更大所以我们认为题目给出的准则是不可取的五模型的检验和结果分析下表给出我们采用过的四种方法(包括穷举法)对e = 0 时3 个具体点的求解情况算法名称r=1最优解 时间r=1.5最优解 时间r=8最优解 时间算法一2,5,1,3,6,4 374无2,5,3,1,6,4 3745,2,3,6,1,4 437.5无5,3,2,6,1,4 437.55,3,6,2,4,1 540.5无算法二2,5,1,3,6,4 374 0的情况则无能为力2.方法二在e 0时仅能找到近似最优解而且随着e 的增大误差也随着增大3.方法三要求退火速度缓慢因此使程序在解决低阶情况时时间开销较大必须借助计算机进行搜索七模型的改进方向改进方向方法二我们可以在每一次判断时对连续两次切割的结果加以考虑即选择权重时多考虑一步这样就提供了算法的预见性使结果时误差减小但这样也增加了算法的复杂度考虑的步数越多误差就越小复杂也会相应提高方法三对于模拟退火法计算时间相对过长的缺陷可以将其与Hopfield网络(HNN)算法结合起来取长补短提高运行效率而又寻找到全局最优解八模型的实用性扩展对于原问题中最终产品在毛坯中的位置是预定的这对于某些工业部门来说可能因对原材料的质量要求不同因而有此限制条件但对于一般性的加工问题我们不但要求加工费用尽可能小还希望由一块原材料尽可能多的加工出产品因此对于给定尺寸的毛坯和最终产品确定最终产品的位置使得浪费的原材料最少是实际中更值得探讨的问题定理当最终产品(长方体)可以位于毛坯的任意位置时最终产品处于毛坯的某一角上时加工费用最少证明设毛坯各表面依据上下左右前后的顺序分别记为A A B , , , B ,C,C11最终产品各对应表面记为A A B B C C 0 0 0 0 0 0 , , , , , 我们假设产品位置不处于毛坯的任何一角而且此时它的加工费用已达到最小因为它没有处有角上所以毛坯肯定有一对对面与产品的任意一面都不相临不妨假设A0 不贴近A 且A0 也不贴近A对