资源描述：
《材料切割优化问题的特殊解法.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机与现代化2010年第3期JISUANJIYUXIANDAIHUA总第175期文章编号:100622475(2010)0320173203材料切割优化问题的特殊解法12施佳琦,魏祖宽(1.电子科技大学软件学院,四川成都610054;2.电子科技大学计算机科学与工程学院,四川成都610054)摘要:材料切割优化问题是平时生活中经常会碰到的一类问题。所谓“材料切割”就是采用切割的办法对具有一定形状和尺寸的型材、板材进行利用。为了节省材料,必须选用合适的切割方案使得用料最少。对于大规模的材料切割问题,本文用解有限列子问题的方法逐步逼近问题的最优解(列生成法
2、)。最后,把一维材料切割模型推广到更一般的情况。关键词:材料切割;大规模线性规划;列生成法;推广中图分类号:TP301.6文献标识码:Adoi:10.3969/j.issn.100622475.2010.03.049MaterialCuttingOptimizationQuestionSpecialSolution12SHIJia2qi,WEIZu2kuan(1.SchoolofSoftware,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054,China;2.Schoolof
3、ComputerScienceandTechnology,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054,China)Abstract:Thematerialcuttingoptimizationquestionisakindofquestingwhichusuallyappearsinlife.So2calledmaterialcuttingmeanstohavesectionsandplatestocertainshapeandsizewithusingcuttingwa
4、y.Inordertosavematerials,theappropriatecut2tingplanmustbeselectedtomakeconsumedtheleastmaterials.Regardingthelarge2scalematerialcuttingquestion,thispapergraduallyapproximatestheproblem’soptimalsolutionwiththewayofsolvingthelimitedrowsubproblems(arowgeneratormeth2od).Finally,thisp
5、aperpromotestheunidimensionalmaterialcuttingmodeltoamorecommonsituation.Keywords:materialcutting;large2scalelinearprogramming;rowgeneratormethod;promotion标作为衡量原材料最省的指标,也可以通过余料最少0引言来实现原材料最省,笔者认为后者方法只能保证余料由于原材料长度和毛坯长度通常不成倍数关系最省,而不能很好地保证原材料最省。而产生部分余料,即便经过余料的再次或多次利用对于大规模的问题,变量数n远远超过约
6、束数目后,仍产生较大比例的残料。材料切割优化是解决这m(n>>m)。在这种线性规划里,A的列在数学上有很一问题的有效方法。采用优化材料切割方法可明显好的定义,但是A的列的数目实在太大,几乎不能完整降低原材料消耗,对提高经济效益和最大限度地杜绝地把约束系数矩阵A=(aij)存放到计算机的存贮器废料对环境的污染都有重要意义。里;实际上,即使想整个写出A矩阵也是十分困难的。原问题可以叙述为:有长为L的材料(线材),切2基本假设和符号说明割成各种长度的数目不定的许多段,使得长度为li的至少有bi段,即目标是满足要求bi,i=1,2,⋯,I,并问题假设:使必须切割
7、的原材的总件数极小化。(1)所有的适于切割的段的长度不大于原材的总长度,则问题有解;1问题分析(2)一切因切割造成的误差可忽略;本问题是一个一维材料切割问题,要求使所用的(3)每次切割不会对余料造成破坏;原材料最省,可以选择使使用的原材料件数最少的目(4)不考虑原材的长度的误差。收稿日期:2009202227作者简介:施佳琦(19842),男,浙江余杭人,电子科技大学软件学院硕士研究生,研究方向:GIS,多媒体技术,运筹学。174计算机与现代化2010年第3期T符号说明:向量,b=(b1,b2,⋯,bm),称之为有限列主导问题。[3]i:第i种需要的钢材
8、,i=1,2,⋯,m;如果xj必须为整数,这个问题是非常难解的。但j:第j种套材
