《实用下料的数学模型.pdf》由会员分享，可在线阅读，更多相关《实用下料的数学模型.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第35卷第7期2005年7月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol135No17July,2005实用下料的数学模型陈璐,黄伟健,冯真指导老师:数模指导组(信息工程大学,河南 郑州450004)摘要:考虑到整数规划模型的下料方式数量难以穷尽的问题,本文以原材料最少为目标,采用启发式多级序列线性优化的方法建立一维下料模型.对于二维下料问题,采用降维启发式的方法即通过形成“板条”把二维下料问题化为一维下料问题.关键词:整数规划模型;下料模型;优化1问题分析一维下料问题是组合优化中的一个经典问题,如果要得到理论上的严格全局最优下料方 案,
2、就要求所有可行下料方式都进入线性规划模型的系数矩阵,从计算的复杂性理论上看,这属于N PC(N P完全)难问题,所以,我们放弃常规的整数规划解法,而在以优化选取下料方式的前提下,寻找建立下料方案的模型.本题要求一个好的下料方案在生产能力允许的条件下要满足三个要求:首先,应该使原材料的利用率最大,即用最少数量的原材料;其次要求所采用的不同下料方式尽可能少;还要满足每种零件各自的交货时间.这样,我们可以考虑分层建模:先仅考虑所用原材料最少的模型,再考虑下料方式增加时的方案,最后在解决具体问题时,再进一步考虑对零件加工的时间限制,改进方案以满足要求.对于二维下料问题,我们受一维下料问题处理方式的启发
3、,采用降维启发式方法.即通过形成“板条”而把二维下料问题降为一维下料问题.2 模型建立与求解211 一维下料模型(1)一维下料模型-启发式多级序列线性优化方法该模型的基本思想是在每级求解时,尽可能多的重复使用最优的一种方法进行下料,直到所涉及到的某种零件需求加工完;然后对剩余的零件重复上步的操作,直到所有剩余的零件数目均减小至零为止.原问题的最优解就是各个序列优化问题所求得的最优下料方式的总和.给定m种长度的零件l1,l2,lm,所需的数量分别为b1,b2,bm,已知原材料长度为L.设在最优一种下料方式中,第i件零件的加工数量为ai,由此建立如下模型:maxS=mi=1ailistmi=1ai
4、liL0aibi,i=1,2,m优化参数变量:a1,a2,am均为非负整数,且不同长度的零件种类有限(即该问题中要求的变量个数有限),可用分枝定界法来求解.(2)启发式多级序列线性优化计算方法将上述当前最优下料方式计算求解作为多级序列线性优化计算的子程序,在每级求解中重复调用.完整的求解过程如下:步骤1调用当前最优下料计算子程序,求解得到优化值aili组成的mi=1aili作为第一级下料方式.步骤2计算此种下料方式的重复次数,即此种下料方式所需原材料L的根数d.其中d=m inb1a1,b2a2,bmam.步骤3 计算去掉d根后,余下的每种待切割的零件个数置为:bi=bi-dai.步骤4将bi
5、作为新一级优化计算的给定值,如果所有的bi都已减小至零,则优化计算结束;否则转至步骤1,重新用当前最优下料方式计算子程序,求得新一级的下料方式和重复次数.步骤5 各级最优下料方式及其重复次数的集合即为多级序列线性优化的最终结果.(3)求解一维下料模型及结果分析按照上述步骤进行编程求解,用VC+610外部反复调用L I N GO求解当前最优下料方式,将处理结果在程序中记录并比较,最终得出一种最优方案.对于53种规格的零件来说,能使原材料达到100 利用率的下料方式可达百万种之多,通过分析该程序算法中求取当前最优下料方式步骤中,是按不同规格零件的输入顺序从前向后进行搜索计算,这样得到的那些100
6、利用率的下料方式总是由编号在前的零件组成的.由此得出结论:程序计算出的方案与零件的输入顺序有关.还应综合考虑影响解的各种因素,其中包括零件的加工个数及零件的长度,并且经过经验 证明,在设计方案时应先大后小.由此启发我们综合考虑这两种因素优化零件的输入顺序,并提出两种零件输入原则:1)将加工个数相等或相近的零件放在一起,并把加工个数相等或相近的零件组按递增顺序排列;2)将这种零件组内部的零件按长度递减排列.依据两种原则我们可以定出这53种零件的输入顺序:12、16、1、5、7、13、23、24、27、28、38、46、9、19、8、11、14、15、17、22、36、41、42、43、40、26
7、、53、21、30、31、37、25、4、20、40、39、52、6、44、47、29、3、33、45、35、32、2、48、50、51、18、34、49.按此序号顺序将零件输入程序,解得:下料方式(n):56种;所需原材料(C):798块;废料总长度:2304mm;原材料利用率:9919%.由符合这样两个原则的零件输入序列所得的方案应是兼顾原材料最少和下料方式最少的最优方案.(4)按时间限制优选方案判断某种方案是否可以满足时间限制要求可以采取如下方法:设4天内完成的零件标号为集合P(4)=p(4)h(h=1,2,11),6天内完成的零件标号为另一个集合Q(6)=q(6)k(k=1,2,9);
8、求出该方案中包含P(4)集合元素的所有下料方957期陈璐,等:实用下料的数学模型式所切的原材料块数相加之和CP,比较CP与400的大小:若CP400块,则说明在生产能力容许的范围内;若CP 400,则超出了企业最大的生产能力,即无法满足这些零件的时间要求.对零件有6天要求的同理,只是这时在求该方案中包含Q(6)集合元素的所有下料方式时要减去即包含P(4)集合又包含Q(6)集合元素的下料方式,剩下的是只包含Q(6)集合元素的下料方式,算出这些下料方式所切的原材料的块数CQ,比较(CQ+CP)与600的大小即可.若(CQ+CP)600块,则在生产能力容许的范围内,道理同上.若(CQ+CP)600块
9、,则超出最大生产能力,该方案无法满足这些零件的时间要求.(5)最优解的选择如何在原材料最少和下料方式最少这两个目标中取舍呢?由于每增加一种下料方式相当于使原材料总损耗增加0108,设有方案i-(ci,ni),ci为方案i的原材料数量,ni为方案i的下料方式数和方案j-(cj,nj),这时会出现四种情况:(1)cicj,ninj;(2)cicj,ninj;(3)cicj,ninj;(4)cicj,ninj;对于情况(1)和情况(4)都好理解,对于情况(2)和情况(3),就需要用题中所给的“增加一种下料方式大致相当于使原材料总损耗增加0108”这个原则进行比较判断.如对于情况(2):计算H=cj3
10、(nj-ni)30108-(ci-cj),若H 0,则方案j优于方案i;若HW.其中,li为零件长度,W为原材料的宽度,所以零件只能以顺着原材料长的方向切割.2)宽度只有20、30、35、50mm四种.且原材料宽度固定为100mm,手工即可算出排满原材料宽度的5种组合方式:(50+50)、(35+35+30)、(50+20+30)、(20+30+20+30)、(20+20+20+20+20).在实施过程中,如果无法排满就考虑最接近的情况,这种情况下可能的组合为:(35+35+20)、(30+30+30)、(50+20+20)、(20+20+20+30)四种.3)将零件按宽度的大小分成4组,统计
11、每组中的零件种类数目和所需零件总个数见下表宽度零件种类数待加工个数总数宽度零件种类数待加工个数总数5062703020348435262420157112因为每组的种类数,总个数是影响该组和其它规格零件组合优劣的两个重要因素,所以我们将种类数与总个数的乘积作为该组灵活性的衡量标准,即调整时的选择标准.灵活性从低到高依次为35,50,30,20.在方案的制定中,我们将从灵活性较低的一组开始.经求解,我们得到结果如下:下料方式(n):49种;所需原材料(C):453块.3 模型评价对于一维下料问题,当零件规格很多时,下料方式数量是巨大的,因此常规的整数规划求解方法不可行,我们采用启发式多级序列线性
12、优化方法,其特点是运算速度快,空间小,不足的是可能无法得出严格全局最优解.在处理加工零件的时间限制问题时,本文采用的是在由仅考虑原材料最少这种目标求出的若干种方案中先进行计算,选出即满足原材料消耗少又满足4、6天时间要求的方案,再进入下一层关于下料方式少这一目标的建模.这样就避免了在找到兼顾原材料和下料方式两者利益的最优解后,却由于无法达到4、6天的时间要求而不得不加以改进,其实改进也可以说是一定程度上的放弃,所以,在这点上还可以多加考虑.我们在求解满足一维下料问题的三个要求(原材料最少,满足时间要求,下料方式最少)26数学的实践与认识35卷的最优方案时,采用的是分层建模,即逐层解决一个要求.
13、其中,在第三层模型中,对下料方式少的要求转化成“每增加一种下料方式相当于原材料总损耗增加0108”这样一个判断最优的原则.0108 是很小的一个数值,当我们把它作为一个变量 来考虑这层模型时,复杂性就会大大加大,最后得到的最优解也会随 的取值大小而改变.当 较大时,下料方式的多少对其影响会很大,而随着 的减小,下料方式对最终解的影响会越来越小于原材料的利用率对其的影响.参考文献:1闵仲求.合理下料的实用数学模型及其计算机软件的研究J.系统工程理论与实践,1982,4.2刘勇彪.等界面长条类材料下料方案的最优化设计J.机械设计与制造,1994,5.3运筹学.北京:清华大学出版社,1990,61.
14、TheMathematicalM odels on thePractical Cutting Stock ProblemCHEN L u,HUAN GW ei2jian,FEN G Zhen(The Information Engineering U niversity,Zhengzhou 450004,China)Abstract:In consideration of the unli m ited ways to cut the stock by the general integer pro2gramm ing model,In this paper,w ith the goal of
15、 m ini m izing the original material,we build upthe 12di mensional cutting2stock model by inspiring multilevel2sequences2linear approach.A s tothe 22di mensional cutting2stock problem,we adopt the algorithm of inspireing decline of the di2mensions tobatten,by which we can descend the 22di mensional problem to 12di mensionals.Keywords:integer programm ing model;cutting2stock model;opti m ize367期陈璐,等:实用下料的数学模型