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

加工业中截断切割的优化设计1.摘要本文讨论了加工业中截断切割的优化排序策略我们对于不同的切割方式总数用穷举法得到720种所可行解及其费用并对于原问题建立了决策模型基于全局静态和局部动态两个思路入手进行优化求解给出三种更实用的算法并对所给出的算法进行了分析和检验1.在简化的二维问题中,我们归纳出解决问题的简明法则,并将其类比到三维空间,从而提出了将面间距统一成判断权重来作为排序准则的算法,同时证明了e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,b,c最终产品的长宽高单位厘米X1,X2,Y1,Y2,Z1,Z2毛坯的左表面右表面前表面后表面上表面下表面x1,x2,y1,y2,z1,z2最终产品的左表面右表面前表面后表面上表面下表面(有时我们为了叙述问题的方便将其依次记为5,6,3,4,1,2)dj最终产品与毛坯的对应表面的距离j1,2,L,6r水平切割单位面积费用与垂直切割单位面积费用之比e调整垂直刀具的额外费用p垂直切割单位面积费用ti加工过程中的第i刀切割第ti个面rTrTttLt126称作切割向量ttt12L6为1,2,L,6的一个排列wi第i次切割的切割费用单位元vi第i次切割被切割掉部分的体积单位立方厘米3si第i次切割时切割面积其它变量如果出现则在使用时另行说明三模型的建立通过对原型的分析,产品的加工可以经过平行(毛坯)的表面的前后六刀得到这里我们将称在切割过程中从毛坯到最终产品的序列半成品称为中间产品我们可以将产品的加工看作一个决策过程决策的状态可以由毛坯或各中间产品待切削面的集合表示如再将毛坯表示为状态Sxxyyzz121212,,,,,经过切割x1的中间产品可以由Sxyyzz21212,,,,如此等等而最终产品的状态可以由f来表示这样一个切割方式对应六个状态SSSSSSS123456S6f而从状态Si到Si1的一个决策对应着Si中的一个元素di1且满足SSdiii11这时可将每一步的切割的费用定义为状态Si与决策di1的函数fSdii(,)1而一个切割方式所需总费用fif(S,dii+1)05至此希望得到总费用最少的决策可以由下列模型刻划minfif(S,dii+1)05s.tSSi,SSdiii11四模型的求解对二维平面切割问题的讨论我们首先讨论简单的二维问题,例如在一块长方形的钢板ll12上切割一块面积以知ll12,且位置确定的小块钢板,每一次切割的费用与切割长度成正比,不妨令其为h,水平切图14割单位长度的费用是垂直切割单位长度费用的r倍,为简化此问题不妨不考虑调整刀具的,并设以底边起逆时针方向四边的序号为1,2,3,4;且xxxx4321;任给一种切割方式(4,3,2,1),然后随意调整两个边的切割次序如2和3,得新的排序(4,2,3,1)这两种切割方式的费用之差为ccxrx2132所以若xrx32,则c1优于c2若xrx32则c1劣与c2同样调整2和1的位置得到(4,3,1,2)费用为c3ccrxx3121在xrx12时c1劣于c3若xrx12则c1优于c3综上我们可以总结得到将应的边距转换成统一的权重,对于水平方向的权重wxii,垂直方向的权重nrxii,这样一来得到一个统一标度下的权重;然后对权重w从大到小排序,排列的结果就是对应边的切割次序.以这种统一的权重作为排序的准则的方法可以得到很好的验证:在r=1时用穷举法验证可得到最优的结果(4,3,2,1),由此我们可以将二维的方法类比推广应用到三维,采用将对应的平行平面的面间距转换为统一的标准权重,作为对各面加工的次序排定的准则.对三维情况的讨论算法一权重设定方法对垂直面权重wrtmtm,对于水平面权重wttmm名词约定逆序如果mn且wwtmtn则称切割向量中存在一个逆序并记n为一个切割向量的逆序数半成品i切割i次后得到的多面体定理切割方案的优越性反比于逆序数n如果n0则该切割方案是最优的证明假设存在一个最优切割方案该方案的切割向量的逆序数n0则切割向中至少有相邻的两个分量ttii,1使得wwtiti1现将这两次切割调换次序得到新的切割向量rT对于rT和rTrTtLttLtii116,,,,,rTtLttLtii116,,,,,现在存在着如下事实ti和ti1以前的加工费用和是不变的对于前i1次切割的组合不变排列变化对于半成品i1其状态是不受影响的而从一个稳定的状态出发ti和ti1以后的加工费用和也是不变的所以rT和rT的优劣只取于ti和ti1的加工费用和的比较5i).第i刀与第刀i1交错时不妨设如图2方式的两次切割第i次为垂直切割第i1刀为水平切割两种方案得到第i1个成品的费用差为cTcTwbwtitirr1Qwwtiti1cTcTrr0方案rT得到第i1个产品的费用cTcTrr又因为状态一样后几刀的排列未发生变化所以整个方案来说rT的费用少于rT的费用ii).第i刀与第i1平行时显然地得到第i1个产品的费用没有发生变化对于最终产品rT的费用等于rT的费用所以rT的费用是不大于rT的费用而T的逆序数nn1即我们降低切割向量的逆序所得新方案的代价不多于原方案对于有限长度的排列长度设为m其最大逆序数为mm12所以我们可以经过最多mm12次调整得到一个逆序数n0的排列而该排列所对应的切割方案的费用是不大于原方案的至此定理得证而由定理得到的优化准则/y基于动态规化思想给出的算法(对于e0的情况)算法二由dj(毛坯与最终产品的面间距)来判断各个面的加工次序方法简明易于操作但整修方法的讨论与定理的证明均是基于e0的情况下一旦i0就不能保证所得结论是最优方案因此为处理更一般的情况我们应将/y考虑在内我们可以从上面e0所给出的优化准则中得到启发当e0时我们根据vsii的大小来决定切割次序我们可以看出当每切一刀切得的体积越大那么以后切割就可以节省更多的费用实际上vi是与这个节省费用成正比的而si则是与当前切割的费用成正比的所以vsii实际上代表的含义就是节省费用费用图26所以对于e0节省费用仍然与vi成正比但费用则应该是psxeip为切割单位面积所花费的费用x为一布尔变量当切割时若需要调整垂直刀具则x1否则x0我们利用动态规划思想在每一步决定切割面时计算当前状态所有面的切割权重选择权重最大的一个面进行下一次切割直到得到最终产品特别地判断准则在e0的情况下切割权重就变成了前一个方案的判断权重此时两者的判断本质是一样的动态优化问题与静态排序达到了同样的最优化目标(算法和源程序详见附录)用模拟退火法解决本问题算法三对于原问题的最一般的方法就是将决策集合D中所有可能一一穷举再代入费用函数寻求最优方案对于本题六面体的加工问题其所有可能排列也就n!720种方案如果面数增加那么可能的排列数就是以/y递增产生组合爆炸为解决这一问题我们参考了神经网络中解决组合优化问题的方法并使用模拟退火算法解决本题我们把每种可行方案rT看成某一物质系统的微观状态而cTr看成物质系统在状态rT下的内能并用控制参数F类比温度让F从一个足够高的值缓慢下降模拟出每个F的热平衡态即对当前状态rT作一个随机拢动产生一个新状态rT计算增量ccTcTrr并以概率expc/kF接收S作为新的当前状态如此重复随机拢动足够次数后状态rTi出现为当前状态的概率服从波尔兹曼分布即fZFecTi/kF其中ZFecTkFii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我们给出的算法得出结果是24312413,,,,,,或42314213,,,,,,它的算法可以得到同样的结果说明它的准则在某些特殊情况是有效的对于图2我们的算法给出的最优排序是13241342,,,,,,或31243142,,,,,,而原题给出的算法得出结果却是2,4,1,3或4,2,1,3分析原因它的准则在处理第一次切割时选择加工费用最少的待切割面实际上是由毛坯的外形决定的而与最终产品在毛坯中的相对位置无关所以对于给定的毛坯它的第一次切割永不会