资源描述：
《实用下料的数学模型.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第35卷第7期数学的实践与认识Vol135No172005年7月MATHEMATICSINPRACTICEANDTHEORYJuly,2005实用下料的数学模型陈璐,黄伟健,冯真指导老师:数模指导组(信息工程大学,河南郑州450004)摘要:考虑到整数规划模型的下料方式数量难以穷尽的问题,本文以原材料最少为目标,采用启发式多级序列线性优化的方法建立一维下料模型.对于二维下料问题,采用降维启发式的方法即通过形成“板条”把二维下料问题化为一维下料问题.关键词:整数规划模型;下料模型;优化1问题分析一维下
2、料问题是组合优化中的一个经典问题,如果要得到理论上的严格全局最优下料方案,就要求所有可行下料方式都进入线性规划模型的系数矩阵,从计算的复杂性理论上看,这属于NPC(NP完全)难问题,所以,我们放弃常规的整数规划解法,而在以优化选取下料方式的前提下,寻找建立下料方案的模型.本题要求一个好的下料方案在生产能力允许的条件下要满足三个要求:首先,应该使原材料的利用率最大,即用最少数量的原材料;其次要求所采用的不同下料方式尽可能少;还要满足每种零件各自的交货时间.这样,我们可以考虑分层建模:先仅考虑所用原材料
3、最少的模型,再考虑下料方式增加时的方案,最后在解决具体问题时,再进一步考虑对零件加工的时间限制,改进方案以满足要求.对于二维下料问题,我们受一维下料问题处理方式的启发,采用降维启发式方法.即通过形成“板条”而把二维下料问题降为一维下料问题.2模型建立与求解211一维下料模型(1)一维下料模型-启发式多级序列线性优化方法该模型的基本思想是在每级求解时,尽可能多的重复使用最优的一种方法进行下料,直到所涉及到的某种零件需求加工完;然后对剩余的零件重复上步的操作,直到所有剩余的零件数目均减小至零为止.原问题
4、的最优解就是各个序列优化问题所求得的最优下料方式的总和.给定m种长度的零件l1,l2,⋯,lm,所需的数量分别为b1,b2,⋯,bm,已知原材料长度为L.设在最优一种下料方式中,第i件零件的加工数量为ai,由此建立如下模型:mmaxS=∑ailii=1m∑aili≤Lsti=10≤ai≤bi,i=1,2,⋯,m7期陈璐,等:实用下料的数学模型59优化参数变量:a1,a2,⋯,am均为非负整数,且不同长度的零件种类有限(即该问题中要求的变量个数有限),可用分枝定界法来求解.(2)启发式多级序列线性优化
5、计算方法将上述当前最优下料方式计算求解作为多级序列线性优化计算的子程序,在每级求解中重复调用.完整的求解过程如下:m步骤1调用当前最优下料计算子程序,求解得到优化值aili组成的∑aili作为第一级i=1下料方式.步骤2计算此种下料方式的重复次数,即此种下料方式所需原材料L的根数d.其中b1b2bmd=min,,⋯,.a1a2am步骤3计算去掉d根后,余下的每种待切割的零件个数置为:bi=bi-dai.步骤4将bi作为新一级优化计算的给定值,如果所有的bi都已减小至零,则优化计算结束;否则转至步骤1
6、,重新用当前最优下料方式计算子程序,求得新一级的下料方式和重复次数.步骤5各级最优下料方式及其重复次数的集合即为多级序列线性优化的最终结果.(3)求解一维下料模型及结果分析按照上述步骤进行编程求解,用VC++610外部反复调用LINGO求解当前最优下料方式,将处理结果在程序中记录并比较,最终得出一种最优方案.对于53种规格的零件来说,能使原材料达到100à利用率的下料方式可达百万种之多,通过分析该程序算法中求取当前最优下料方式步骤中,是按不同规格零件的输入顺序从前向后进行搜索计算,这样得到的那些10
7、0à利用率的下料方式总是由编号在前的零件组成的.由此得出结论:程序计算出的方案与零件的输入顺序有关.还应综合考虑影响解的各种因素,其中包括零件的加工个数及零件的长度,并且经过经验证明,在设计方案时应先大后小.由此启发我们综合考虑这两种因素优化零件的输入顺序,并提出两种零件输入原则:1)将加工个数相等或相近的零件放在一起,并把加工个数相等或相近的零件组按递增顺序排列;2)将这种零件组内部的零件按长度递减排列.依据两种原则我们可以定出这53种零件的输入顺序:12、16、1、5、7、13、23、24、27
8、、28、38、46、9、19、8、11、14、15、17、22、36、41、42、43、40、26、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%.由符合这样两个原则的零件输入序列所得的方案应是兼顾原材料最少和下料方式最少的最优
