资源描述：
《实用下料优化问题模型建立及解法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第35卷第7期数学的实践与认识Vol135No172005年7月MATHEMATICSINPRACTICEANDTHEORYJuly,2005实用下料优化问题模型建立及解法李丹俊, 曾 锐, 孙 伟指导教师:唐建宁(解放军理工大学工程兵工程学院,南京 210007)摘要:“下料问题(cuttingstockproblem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题,此类问题在工程技术和工业生产中有着重要和广泛的应用.本文首先以材料最省为原则建立模型,采用分层基因算法模型求解出模型的解,若此结果不符合时间限制条件,则通过以客户时间需
2、求为第一目标的分组抽样模型处理后,再借助分层基因算法给出该模型的最优解.关键词:下料;基因算法;二维下料问题;分组抽样1 问题的提出(省略)2 问题的分析这是一个典型的多目标决策优化问题.首先,一个好的下料方案应该使原材料的利用率最大,从而减少损失,降低成本,提高经济效益.其次,要求所采用的不同下料方式尽可能少,即希望用最少的下料方式来完成任务.因为在生产中转换下料方式需要费用和时间,既提高成本,又降低效率.此外,由题意知每种零件有各自的交货时间,每天下料的数量又受到企业生产能力的限制.因此实用下料问题的目标是在生产能力容许的条件下,以最少数量的原材料,
3、尽可能按时完成需求任务,同时下料方式数也尽量地少.为顺利解决该下料问题,根据该问题的特点,我们先从最基本的单目标决策问题入手,以材料损耗最少为目标,通过不同的数学原理建立多个单目标决策的最优化模型,得出最初的结果,并加以比较分析.然后逐步增加其约束条件——最小的下料方式数,并根据该约束条件进一步完善我们的最优化模型,得到损耗最少,下料方式数又小的结果.接下来检验在所得下料方式的排列中,是否存在可以满足时间条件限制的排列方式.若存在,则该结果即为最优解;若不存在,则这个结果就不符合题意,必须重新构建多目标决策的最优化模型,在新模型中以客户时间需求为第一目标
4、,材料损耗最少,下料方式最少为第二目标.因此,在下料时就应该优先生产那些有时间限制要求的零件,并且求出在需求的时间段内下料方式和损耗的最优结果,紧接着再求出剩余板材下料方式和损耗的最优结果,从而最终得出既满足时间条件限制又满足损耗少、下料方式数小的最优结果.具体流程图如下:3 符号的约定11L——原材料的长度21W——原材料的宽度31I——板料用量44数 学 的 实 践 与 认 识35卷图1 总体流程图41J——加工零件的种类51K——下料方式种类61lj——第j种零件的长度(j=1,⋯,J)71wj——第j种零件的宽度(j=1,⋯,J)81dj——第j
5、种零件的加工个数(j=1,⋯,J)91M——以向量形式表示问题中所要求各种零件的个数,即M(j)=dj101b——锯缝宽度111Di——第i块板料利用率121xij——第i根的板材上截取长度规格为lj的根数(i=1,⋯,I;j=1,⋯,J)131ajk——第k种下料方式下第j种零件的个数(j=1,⋯,J;k=1,⋯,K)131bk——第k种下料方式产生的余料141xk——使用第k种下料方案需要切割原材料的数目4 模型的假设11切割时的锯缝可以是直的也可以是弯的,切割所引起的锯缝损耗忽略不计.21零件非定向:这里的‘定向’是指在有纹路的面板上下料时是否允许
6、将零件既能横着排又可转个方向竖着排,对于定向取材的零件,零件的长度与宽度尺寸不能随便互换,等到下料图出来后还应该仔细检查一下这零件的纹路方向是否正确.而对于本题,我们假设不存在这个问题,即零件非定向.31除了要求在四天和六天内完成所需零件外,不要求其余零件加工排列顺序.41切割时零件的长和宽要与原材料的长或宽平行.51增加一种下料方式大致相当于使原材料总损耗增加0108à.5 模型的建立与求解实用下料问题模型的建立,从计算的复杂性上来讲,这是一个NP(NondeterministicPolynomial)难题,很难精确求解.通常所用的近似算法有3种:①F
7、F(FirstFit)近似算法,即:将m种零件顺次加工,对于任一个零件,它总是按顺序从第一块能加工它的板材中切割下来.②BF(BestFit)近似算法,即:把零件顺次加工,要求板材加工完零件后,所剩下的材料最小.③FFD(FirstFitDecreasing)或BFD(BestFirstDecreasing)近似算法,即:在加7期李丹俊,等:实用下料优化问题模型建立及解法45工零件之前先把零件按大小降次排列,然后再利用FF(或BF)近似算法.我们经过先期的尝试性试验,发现这些近似算法的求解结果与给定的数据有很大的关系,效果不理想.于是我们采用先进的优化算
8、法:EPFF算法和遗传基因算法来计算我们的模型,虽然过程较为复杂,而且处理的数据
