资源描述：
《一维优化下料问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第24卷第1期桂林工学院学报Vol.24No.12004年1月JOURNALOFGUILININSTITUTEOFTECHNOLOGYJan12004文章编号:1006-544X(2004)01-0103-04一维优化下料问题张春玲,崔耀东(广西师范大学数学与计算机科学学院,广西桂林541004)摘要:下料问题在生产中普遍存在,优化下料可以提高原材料利用率,是企业增加经济效益的途径之一.对一维下料问题进行了探讨,给出一维下料问题的一些概念和数学模型,讨论解决一维下料问题的常用算法以及算法的适用情况,分析与之
2、相关的一些问题和具体的实际应用.关键词:下料;最优化;整数规划中图分类号:TB11411;O224文献标识码:A随着全球资源的日益匮乏,人们对资源利用太细,会导致增加库存管理的负担.[3]问题的研究愈来愈重视,下料问题就是其中之Dyckoff提出下料问题可以根据4种特征来分[1-3]一.最大限度的节约原材料,提高原材料利类:维度、分配类型、大物件的分类和小项的分用率是生产中提高效益的一个重要手段,在机械类.Dyckoff描述一维下料问题为1/V/D/M:1指行业、造纸、服装、木材等行业,下料问题都有的是一维
3、问题,V指的是所有的小项必须从一大广泛的实际应用.下料问题就是研究怎样在客观物件中产生,D的意思是所有大物件是不同的,M条件和可以接受的时间下优化排样得到最优解或是指小项之间不同.近似理论最优解.下料问题根据维数一般可分为如果原材料是同一长度或只有少数的组(组一维下料和二维下料,本文主要对一维下料问题中长度相近),可得到标准一维下料问题(S1D-进行讨论.CSP),对于S1D-CSP给出切割方案的概念,切割方案是用1根原材料切割各种不同规格的坯料时,1一维下料问题的概念和数学模型保持坯料规格的种类不变,只改
4、变切割数量.将一维下料问题(one2dimensionalcuttingstock有效的切割方案集中起来就是最后的下料方式.problem,简称1CSP)是在已知原材料和顾客需求S1D-CSP问题可以描述如下:坯料的情况下优化下料使原材料的使用率达到最li—坯料长度,i=1,⋯,n;大或废料达到最小.根据原材料长度是否相等,di—每种坯料的需求数量,i=1,⋯,n;一维优化下料可以分为单一型材的优化下料和多Lk—原材料长度,k=1,⋯,P.型材的优化下料.单一型材的优化下料很多文献切割方案c可以用如下一个向
5、量ack来表示:中都已有讨论,而多型材的优化下料在型材类型a1ck,a2ck,⋯,anck;(1)比较多的时候,可以将型材按长度相近进行分组,n先选组,再从组中选择型材下料,由此引发出分满足∑liaick≤Lk,且a1ck≥0,是整数.(2)i=1组问题.分组有利于节约原材料,但是如果分组aick表示li在特定的切割方案中出现的次数,xck表收稿日期:2003-05-12基金项目:广西自然科学基金资助项目(桂科基0236017).作者简介:张春玲(1978-),女,硕士研究生,研究方向:CAD/CAM.10
6、4桂林工学院学报2004年示切割方案c在原材料k上使用的次数,tk表示在原(5,7,10,14,0)方案表示在第1种长度为13材料k上满足(2)式的切割方案的总数,那么将会535cm的原材料上切割5根长度为304cm的坯料,有如下的整数规划模型:7根长度为319cm的坯料,10根长度为397cm的tpk坯料,14根长度为415cm的坯料,不切割长度为min∑∑xckLk,(3)k=1c=1366cm的坯料(为0表示不切割).ptk以需求为导向方法得到的切割量会出现比需s1t1∑∑a1ckxckLk≥di,i
7、=1,⋯,n;(4)k=1c=1求量少的情况,其方法一般是基于启发式算法;xck≥0且为整数,c=1,⋯tk;k=1,⋯,p.(5)以方案为导向方法得到的切割量则会出现比需求从S1D-CSP所对应的数学模型中可知S1D-量多的情况,其方法一般是基于线性规划的.两CSP所优化的目标是最小化被切割的原材料数量.种方法有各自的优缺点,可进行适当的组合得到当原材料的长度全都不同时所建立的数学模型与良好的下料效果.[4]上述模型是有所不同的.如Gradisar等人提出的一维下料的数学模型早在1939年就已由Kan2G
8、1D2CSP(generationone2dimensionalcuttingstockprob2torovich提出.下料问题的求解很大程度上依赖于lem),其数学模型中优化的目标是最小化废料,而模型的建立,可根据具体情况进行模型的补充和且这一模型中原材料的长度全都不同.修改.一维下料问题所建立的数学模型是一个整[3]Dyckoff将优化下料过程分为2类:以需求项数规划问题,求解整数规划问题一般使用分支定为导向
