（系统工程专业论文）钢板二维切割问题的研究.pdf

东北大学硕士学位论文摘要 摘要 本文研究的目的在于改进在钢铁企业中二维切割问题的优化模型。所做的 主要工作在于加强模型所能表达的功能和针对优化问题的算法求解的改进。我 们所研究的二维切割问题是十分有意义的，由于当产品的数量比较大的时候， 在进行切割规划时即使微小的改进也能导致节省大量的原材料和能源。 解决此类切割问题，尽管有许多的方法可以使用，但在本文中只研究了一 种针对大规模切割问题非常有效的求解算法列生成。此算法事先产生初始 切割模式并将它作为变量插入到模型中。此算法能考虑到每种可行切割模式， 其最主要的贡献在于当切割模式的数量巨大时，能给出切割模式的长度的界限。 而在其它所提出的算法中，控制切割模式的长度是非常困难的。 通过参考文献给出基准结果。使用列生成算法解决我们所提出的模型，通 过与文献原始问题比较发现在库存板的利用率上有很大提高。另外，在模型中 提出了诸如g u i l l o t i n e 切割和产品优先权等特性。然而，在模型中增加这些特 性会增加收敛时间。 在本文中我们只是利用w a n g 所提出的启发式得到列生成的初始解，应用 动态规划求解二维切割问题的子问题背包问题。实质上，对于其它解决此 类问题的数学启发式做进一步研究是非常有意义的。分类优化理论用于优化切 割模式长度被证明是有价值的。其减少优化时间的贡献主要在于剔除一些不必 要的松弛变量和模型中的不必要约束。因此它能计算出尽可能紧的界，这点非 常重要。然而，太紧的界可能剔除解空间中有用的部分。如果那样，最好也只 能得到次优解。 在p e n t i u m l i i 系列主频1 0 0 0 的计算机上，使用c + + 语言实现了上述全部算 法，并进行实验仿真。实验结果表明列生成算法能够有效地求解二维切割问题。 关键词：= 维切割问题，背包问题，列生成，动态规划，分支定界 i i 东北大学硕士学位论文摘要 a b s t r a c t t h ep u r p o s eo ft h i sr e s e a r c hi st o i m p r o v ea no p t i m i z a t i o nm o d e lo fa t w o d i m e n s i o n a lc u t t i n gs t o c kp r o b l e mi nt h es t e e li n d u s t r y t h ei m p r o v e m e n t s a d d r e s st h ef u n c t i o n a l i t yo f t h em o d e la n ds o l u t i o nt i m e so f t h eo p t i m i z a t i o np r o b l e m t h er e s e a r c hp r o b l e mi si m p o r t a n t ，s i n c ee v e ns m a l li m p r o v e m e n t si nt h ec u t t i n g l a y o u t sr e s u l ti nl a r g es a v i n g so fr a wm a t e r i a la n de n e r g yw h e nt h ea m o u n to f p r o d u c e dm a t e r i a li sh u g e a l t h o u g hn u m e r o u ss o l u t i o nm e t h o d sf o rs o l v i n gc u t t i n gs t o c kp r o b l e m sa r e a v a i l a b l e ，o n l yas p e c i f i ca l g o r i t h m i cm e t h o di sv a l i df o rt h ep a r t i c u l a rp r o b l e mb e i n g s t u d i e di nt h i sr e s e a r c h i nt h i sm e t h o d ，c u t t i n gp a t t e r n sa r eg e n e r a t e db e f o r e h a n da n d i n s e r t e di nt h ef o r m u l a t i o na sp a r a m e t e r s t h i sa p p r o a c hm a k e si tp o s s i b l et ot a k ei n t o a c c o u n te a c hf e a s i b l ec u t t i n gp a t t e r n m o s ti m p o r t a n ta t t r i b u t e sa r eb o u n d so nt h e c u t t i n gp a t t e r nl e n g t h sw h e nt h en u m b e ro fc u t t i n gp a t t e r n si sl a r g e i ns o m eo t h e r r e p r e s e n t a t i o n so fc u t t i n gp a t t e r n s ，c o n t r o l l i n gc u t t i n gp a t t e r nl e n g t h si sm u c hm o r e d i m c u l t t h eb e n c h m a r k e dr e s u l t sa r ep r e s e n t e do no t h e rl i t e r a t u r e t h eu s e f u lr a t i oo ft h e s t o c km a t e r i a lw i l lb ei m p r o v e dw h e nu s i n gc o l u m ng e n e r a t i o na p p r o a c ht os o l v e t w o d i m e n s i o nc u t t i n gs t o c kp r o b l e m i na d d i t i o n ，f e a t u r e sl i k eg u i l l o t i n ec u t t i n go na s i n g l er a wr e e la n dp r i o r i t i z i n gp r o d u c t sw e r ed e v e l o p e d h o w e v e r ，a d d i n gt h e s e f e a t u r e si nt h em o d e li n c r e a s e sc o n v e r g e n c et i m e s w eu s ew a n gh e u r s t i ca l g o r i t ht og e ti n t i t a l i z a t i o nf e a s i b l ec u t t i n gp a t t e r no f c o l u m ng e n e r a t i o na l g o r i t h ma n du s ed y n a m i cp r o g r a m m i n gt os o l v et h es u b p r o b l e m o ft w o d i m e n s i o nc u t t i n gs t o c kp r o b l e m _ l m a p s a c kp r o b l e m i tc o u l db ew o r t h w h i l e t of u r t h e rs t u d yt h ea p p l i c a b i l i t yo fs o m em e t a h e u r i s t i cm e t h o d sf o rs o l v i n gt h e p r o b l e m t o o l so fc l a s s i c a lo p t i m i z a t i o nt h e o r yc o u l dt u r nt ob ev a l u a b l ei nt h e o p t i m i z a t i o no fc u t t i n gp a t t e r nl e n g t h s t h em a j o r i t yo ft h er e d u c t i o ni no p t i m i z a t i o n t i m e sw a sa c h i e v e db yr e m o v i n gu n n e c e s s a r ys l a c kv a r i a b l e sa n dc o n s t r a i n t sf r o mt h e f o r m u l a t i o n h e n c ei tc a l lb ec o n c l u d e dt h a td e f i n i n gb o u n d so nt h ev a r i a b l e sa st i g h t a sp o s s i b l ei si m p o r t a n t h o w e v e r ，t o ot i g h t l yd e f i n e db o u n d sm a yr e m o v es o m e i i i 东北大学硕士学位论文摘要 e s s e n t i a lp a r t sf r o mt h es o l u t i o ns p a c e c o n s e q u e n t l y ，o n l ys u b o p t i m a ls o l u t i o n sc a r ! b eo b t a i n e da tb e s t o nt h ep e n t i u r n i i i1 0 0 0h zc o m p u t e r , a l la l g o r i t h m sa r ei m p l e m e n t e db yc + + l a n g u a g ea n dt h es i m u l a t i o ne x p e r i m e n t sa r ec o n d u c t e d t h ec o m p u t e rr e s u l t ss h o w t h a tt h ec o l u m ng e n e r a t i o na l g o r i t h mc a r l e f f e c t i v e l ys o l v et h et w o d i m e n s i o n c u t t i n gs t o c kp r o b l e m k e y w o r d s ：t w o d i m e n s i o nc u t t i n gs t o c kp r o b l e m ，k n a p s a c kp r o b l e m ，c o l u m n g e n e r a t i o n ，d y n a m i cp r o g r a m m i n g ，b r a n c ha n db o u n d i v 东北大学硕士学位论文声明 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中 取得的研究成果除加以标注和致谢的地方外，不包含其他人已经发 表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 本人签名：巅象 日期：2 。r 2 2 2 - 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的 规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权东北大学可以将学位论文的全部或部分内容编 入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：导师签名： 签字日期签字日期： 东北大学硕士学位论文 第一章绪论 1 1 背景及研究意义 第一章绪论 当从大件切割小条目时，会产生两种问题。第一个问题是分类问题，也就 是选择适当的大件进行切割。第二个问题是锯切损失问题，也就是如何在给定 大件的情况下切割小条目，以保证浪费的原材料最少【l 】。实际上，我们把小条 目称为定单序列，即合同板，把大件称为库存原料。特别是在造纸和钢铁业中， 小条目被成为产品卷，大件被称为原始卷。在钢铁业中，把从厚钢片扎制出来 的称为钢板。在切割问题中，很少会把原始卷正好使用完，因此会产生剩余条 块或者锯切损失。最早把浪费最小化切割称为锯切损失问题，把分类问题和锯 切损失问题组合起来称为切割问题。 在许多产品工业中均存在切割问题。通常库存原料为纸、钢板、玻璃、木 头、塑料和纺织品等【2 1 。本文主要针对钢铁业中的切割问题进行研究。潜在的 经济效益是对切割问题进行研究的强大动力。对该问题高效地求解，可以减少 原材料的浪费，从而降低对产品的加工、存储、劳动力的使用及加工时间等一 系列的生产成本。生产成本的降低可以间接地给客户带来利润。 本文的研究主要从参阅钢铁业和造纸业的切割问题的不同的模型建立和求 解方法的有关文献开始。在此基础上，本文建立了切割问题的数学模型，并应 用列生成算法进行求解。在应用列生成算法求解时，其重点与难点主要是求解 子问题。对于切割问题，与其相对应的予问题是二维背包问题。本文提出了应 用动态规划算法求解二维背包问题，这也是本文创新工作之一。另外，本文也 对模型进行了定扩展，并参阅文献提出的算法进行求解，比较。 1 2 切割问题及其特征 二维切割问题中，二维g u i l l o t i n e 切割是应用最为广泛的下料形式之一。 g u i l l o t i n e 切割可简单的定义为：在板材上的每次切割轨迹是一条边到边的连通 东北大学硕士学位论文第一章缗论 直线。又称为“e d g et oe d g e ”的切割。 切割问题，国外称之为“c u t t i n gs t o c kp r o b l e m ( c s p ) ”。该问题在不同 的刊物上有不同的提法，如“t r i ml o s sp r o b l e m ，“b i np i c k i n gp r o b l e m ”， “a s s o r t m e n tp r o b l e m ”，“l a y o u tp r o b l e m ”等。国内外学者从事这方面的研究主 要因为：一方面由于二维切割在计算机辅助设计和自动化设计应用中所起着较 重要的作用，二维切割研究具有诱人的经济前景，好的二维切割方案每年可以 为制造业节约巨额资金，而且很容易比较出运用合理的切割方法所带来的经济 效益；另一方面由于它涉及面很广，涉及机械、建筑、钢铁、船舶、车辆、玻 璃、造纸、皮革等制造业。 最早关于c s p 研究见于1 9 3 9 年，俄国经济学家k a n t o r o v i c h 3 1 建立了第一 个一维切割模型，尽管他的这种切割模型在1 9 6 0 年才以英文形式出版。但在这 个领域首先取得较重要进展的启发性工作则由g i l m o r e 和g o m o r y 4 5 】【6 】1 7 1 完成， 在他们的文献中，他们提出用列生成技术求解一维c s p ，并对二维问题进行了 开创性探讨，由于当时计算工具的限制，并未引起人们足够的重视。直至7 0 年代，由于高速计算机的出现以及借助于计算机的现代化技术诸如线性规划、 运筹学理论的发展，使得c s p 的研究有可能付诸于生产实践，二维切割问题重 新引起国内外学者的兴趣，这个领域的研究曰趋活跃，己取得了不少研究结论 和成果。从那以后，这个领域不同应用研究的文章数量迅速增长，涉及面不断 拓宽，不断在代表不同学科的杂志期刊上发表。涉及学科有管理科学 ( m a n a g e m e n ts c i e n c e ) 、工程科学( e n g i n e e r i n gs c i e n c e s ) 、信息和计算机科 学( i n f o r m a t i o na n dc o m p u t e rs c i e n c e s ) 、数学( m a t h e m a t i c s ) 等。也是从那时 起，各种切割模式及其各种求解方法迅速出现并蓬勃发展。 切割实际上是切割及装箱问题的一种具体形式，是运筹学的一个分支。从 七十年代开始，有一些研究如b r o w n 、g o l d e r 等已经注意到切割问题与装箱问 题的密切关系，但此时并没有一种系统全面的总结此类问题的方法论。随着日 后研究工作的深入，切割与装箱问题存在着很强烈的对偶关系。也就是，在一 定程度上切割可以看作是将小条块所占的空间组装到大物体所占的空间里去， 而装箱可以看作是将大物体所占的空间切割成由小物体所占用的空间。切割问 题的主要目的是在满足一定合同要求及某些特定工艺约束下，通过确定的切割 模式及执行次数，使某些预定目标达到最优或近优。切割问题是一类组合问题 和调度问题紧密结合的复杂问题。这类问题往往是大规模问题，即切割模式的 数目将是及其庞大，已被证明是n p 一难问题，即非多项式时间可解问题。 2 东北大学硕士学位论文第一章绪论 虽然现实生活中存在着大量的各种各样的切割及装箱问题的应用，但基于 它们共同的逻辑结构，d y c k h o 俨】提出可一种系统地分析切割及装箱问题 ( c & p ) 的类型学方法。根据他的类型学方法，下面将从以下四个内在特征来分 析这类问题，如表1 1 。 通过以上的描述，对切割问题有了个基本的了解。本文所讨论的钢板切割 问题用d y c k h o f f 的类型学方法可表示为2 v d r ，即用些不同大件( 原始材料 板) 切割成大量相同形状而大小不完全相同的小物体的二维切割。 表11c s p 问题特征分析 特征分类 l 、一维 维 2 、二维 数 3 、三维 n 、n 维( n 3 ) 分种( b ) 所有大的物体和一系列所选小条块的匹配 配类 ( v ) 一系列所选大件和所有小条块匹配 ( c ) 一个大件 大的 物分( i ) 许多相同的大件 体类 ( d ) 许多不同的大件 ( f ) 少量的不同形状小条块 丧囊 ( m ) 许多不同形状的小条块 ( r ) 一些相关形状的小条块 ( c ) 许多统一的小条块 在这里，最重要的特征是维数。维数起着非常重要的作用，一维是维数的 最小数量。d y c k h o f f 列举了维数的一些类型，有一维、二维、三维和多维。然 而，还有一些问题介于一维和二维之间，即1 5 维。 最简单的情况就是一维。对一维切割问题的典型例子就是对长度固定的钢 条进行切割。在1 5 维问题中，此时材料有一个固定的维数和一个变量。举个 例子来说，在一个钢板切割问题中，当钢板的宽度为变量，而钢板的长度固定 时即为1 5 维切割。二维就是有两个自由维数的情况，也就是，原材料板和所 要求的小条块都为长方形。 切割问题的另一个重要特征即是分配种类。它至少可分为两类：第一类， 一3 东北大学硕士学位论文第一章绪论 使用了所有的原材料，但并未满足所有的种类要求；第二类，所有的种类要求 都得到了满足，但此时只使用了一部分原材料板。 切割问题的第三种特征可以被分为三类： ( 1 ) 只需要切割一个大物体； ( 2 ) 有许多相同维的大物体； ( 3 ) 有许多不同维的大物体； 当原材料包含有次切割后剩余的小片时，就为最后一种情况。同样，按 同样方式也可以对小物体进行分类：第一类，只有少数不同维的小条块；第二 类，有许多小条块，其中的大多数都有不同的维；第三类，有许多小条块，其 中的大多数都有相同的维；第四类，所有的小条块都有统一的维。 由于即使最简单的c s p 问题也已被证明是n p c o m p l e t e ，因此对于更加复 杂的c s p 问题同样是n p c o m p l e t e 。这就意味着不存在解决此类问题的多项式 时间算法。由于c s p 的复杂性，在钢铁业中被认为是最需要优化的问题。在现 实问题中，不同的启发式算法得到广泛的应用。然而，由于启发式使用了代解 决问题的特定信息，因此不能用于解决其它类似问题 1 】。 c s p 问题的最基本目标就是使锯切损失最小，然而也存在其它一些重要的 目标。s t a i n t o n 8 】列举了五十中影响效益的因素。实际上，影响锯切损失的最基 本的因素是某种切割模式的使用费用以及从一种切割模式到另一种切割模式的 转换费用。 切割模式我们可以简单定义为在一块库存板上切割成合同板的顺序，也就 是合同板在库存板上的布置。在大多数情况下，我们还会考虑方向和或 g u i l l o t i n e 切割的约束。l o d ie t a l 9 1 提出了如下四种可能方案： ( a ) 2 b p i o i g ：合同板需求有方向性( o ) 并且需求g u i l l o t i n ef j j 割( g ) 。 ( b ) 2 b p i r i g ：合同板可以旋转9 0 。( r ) 并且需求g u i l l o t i n e 切割( g ) 。 ( c ) 2 b p ) o i f ：合同板需求有方向性( o ) 并且可以任意切割( f ) 。 ( d ) 2 b p i r f ：合同板可以旋转9 0 。( r ) 并且可以任意切割( f ) 。 我们在本文中所考虑的问题属于2 b p i o i g 类型。按照图1 1 所示，对应 某种类型的算法可以用来解决其它类型的问题，图中a 。，表示对应2 b p i x i y 类 型问题的算法，连线( a x ”2 b p i q i t ) 表示a ) ( y 算法可以确保产生2 b p i q i t 类型 4 东北大学硕士学位论文 第一章绪论 问题的可行解。 2 b p f o f g 2 b p i r g 2 b p l o l f 2 b p ir | f 图11 算法和问题之间的对应关系 1 3 切割问题的解释 在二维问题中可能包含了这样的步骤：先将库存板以直角切割成中间板， 再将中间板进行进一步切割成合同板，这种切割叫做阶段性的二维切割。如果 切割方向与材料板的一边平行，则这种切割被称作平行切割。最后，如果切割 必须延伸到材料板的整个宽度，那么它就是切割机切割。 f 面将介绍几种不同的切割过程。灰色部分代表锯切损失。图1 2 ( a ) 说明是 一维切割问题。在此图中，库存板的长度和宽度都是固定的。在( b ) 图中库存板 的长度是固定的而宽度为变量，即此图说明的是1 5 维问题。在( c ) 图中，原库 存板的长度和宽度均为变量，也就是二维切割问题。图1 2 ( a ) 一( c ) 都是平行切割 机问题，而( d ) 图表示的是非切割机问题。 为了使问题简化，在本文中假设库存板均为长方形。两阶段切割机在不同 切割模式中的切割方向可能是水平的或者是垂直的，在这里假设所有的切割模 式在第阶段、第二阶段分别有相同的切割方向。为了不失一般性，假设第一 阶段的切割方向是水平的，也就是与长度平行。这样，第一阶段切割就是把原 材料板切割成所有的条状或条状模式，这些条状模式可以由i l l 维的整数向量来 表示。两阶段二维的切割模式都可以看作是条状模式的组合。也就是可以将两 阶段切割模式看作是两种一维切割模式的组合。 如图13 所示，先将个固定的材料板切割成条状，然后再将小条切割成 小块，即为两阶段切割。 小块，即为两阶段切割。 5 啡 阱 盯 扦 a a a a 东北大学硕士学位论文 第一章绪论 匡琶 ( 1# 2e 3 ( b ) l 圈匾 f e ， 图1 2 切割问题的分类 l 2 k 。 图1 3 两阶段二维切割模式 1 4 目标和主要工作 下面，主要叙述本文的研究目标以及主要工作，并按照重要程度先后排序。 1 4 1 目标 ( 1 ) 本文最主要的目标是找到解决钢铁业中一维、二维c s p 问题的有效方 法。一些方法被应用到特定的问题中，用程序实现并同文献的结果加以比较。 ( 2 ) 第二个目标就是根据解的质量来判断我们所提出的算法的质量。本文主 要将精力集中在将本算法结果与文献结果以及实际情况进行比较。 6 东北大学硕士学位论文第一章绪论 ( 3 ) 第三个目标就是尽量改进数学模型的质量。也就是，考虑小件和库存原 料的一些特性。这些特性主要有： ( a ) 根据需求级别的不同设立不同的优先权。 ( b ) 尽量把一块库存原料的锯切部分集中在一起，以便下次还可以使用当前 的剩余部分。 1 4 2 主要工作 ( 1 ) 二维g u i l l o t i n e 切割建模技术的研究，分析了一类以锯切损失总和最少 为目标函数的切割问题模型，指出此类数学模型在用于解决某些切割问题时可 能出现无节或虽然有解但原材料利用率低等问题，给出了改进的方法。这也是 本文创新工作之一。 ( 2 ) 分析了造成初始切割模式数量巨大的原因，在切割模型求解的过程中， 引入了列生成算法解决二维c s p 问题，推导了切割问题模型求解得列生成数学 形式，给出了切割模型的列生成迭代求解算法。 ( 3 ) 提出g u i l l o t i n e 切割实际问题的数学模型及其改进模型、提出两阶段切 割模型。 ( 4 ) 研究了切割问题的子问题二维背包问题求解算法，并提出相应的阶 段性动态规划进行求解，这也本文创新工作之一。 ( 5 ) 研究了二维g u i l l o t i n e 切割问题数学模型实用求解算法。结合提出的切 割问题模型的具体情况，给出了初始可行切割模式矩阵的构造方法：提出了改 进对偶单纯形算法。在列生成的算法使用过程中，我们先使用w a n g 4 1 1 提出的启 发式得到尽量好的初始解，然后通过使用自己提出的动态规划得到局部最优， 最后通过列生成迭代以及r o u n d i n g 技术得到全局最优。 ( 6 ) 使用c 语言实现二维背包问题的动态规划程序以及列生成求解 g u i l l o t i n e 切割问题程序。 1 5 研究范围 在切割和装箱问题( c & p ) 中，切割模式起着很重要的作用。d y e k h o f f 2 】 提出了一种系统地分析切割及装箱问题( c & p ) 的类型学方法。装箱问题与切 7 东北大学硕士学位论文 第一章绪论 割问题类似，两者具有对称性。他提出由于模式选择在c & p 中占主导地位，而 其本质是几何组合，因此可以把这类问题划入几何组合学的范畴。从此角度出 发，他对c & p 问题的现象分类进行总结，见图1 4 。 箍鼗唯p 弗 + 韩懦性” 酒搦鲥地： 链褐城堆救勰趣： 慧蛾渣自i 箍 确 赣端 馥舷 攘鹚 绺器 鹫蚓 籍蕊 泰 斑蜕 躺茚 谣燃搿巍撬化 图1 4 切割问题和装箱问题的分类 在装箱问题和切割问题两者之间只是在小件的分类上有所不同：在装箱问 题中，一般来说，小件具有许多不同的尺寸。而对于切割问题来说，一般是许 多小件具有相同的尺寸。在本文主要针对钢铁业二维c s p 问题( t d p ) 作研究， 如果按照d y c k h o f f 的方法可把切割机c s p 问题划分为：2 v i m ，把两阶段c s p 问题划分为：2 v d r 。 1 6 技术路线 首先，通过参阅文献，尽量了解c s p 问题的历史及研究现状。在钢铁业、 造纸业以及其它行业的c s p 问题十分相似，因此，我们在参阅文献时侧重了解 不同文献对于问题的不同数学模型描述和应用不同的算法求解。 其次，我们通过了解经典二维切割问题的特点和数学模型，描述钢板二维 切割问题的特点，并建立数学模型。使用列生成算法进行求解。 - 8 - 东北大学硕士学位论文 第一章绪论 再次，我们在参阅文献的基础上对现有的列生成算法进行改进。主要通过 开发自己的动态规划算法实现。 最后，通过仿真实验，同现有的文献所提供的同规模问题的性能指标进行 比较。 1 7 论文结构 本文主要讨论了钢板二维切割问题。在第二章我们给出了相关文献工作， 主要对二维切割问题建模方法进行总结，着重指出在文献中对二维切割问题建 模所存在的问题，以及造成此问题的原因及解决方法。在第三章，我们结合列 生成算法以及实际钢板切割问题，提出了三种数学模型以及其改进模型。第四 章，我们给出目前解决二维切割问题的相关算法的文献工作，主要介绍了 g u i l l o t i n e 切割和列生成算法以及其它有效算法。第五章我们主要介绍了动态规 划方法求解切割问题的子问题二维背包问题。指出传统动态规划存在的错 误，并提出自己的修正动态规划。在第六章，我们建立通用二维切割问题数学 模型，给出列生成求解切割问题算法流程，并采用算例进行仿真，且对其性能 结果进行分析、比较。 9 一 东北大学硕士学位论文第二章二维切割问题特点与分析 第二章二维切割问题特点与分析 本章的主要工作首先分析了经典二维切割问题的数学模型，通过研究一些 具有代表性的二维切割问题文献，来分析切割问题的共同特点和类别，从而为 钢板切割问题的建模分析提供一些参考和借鉴之处。本章的创新工作之处在于 发现了现有文献中一类以锯切损失总和最少为目标函数的切割问题模型，指出 此类数学模型在用于解决某些切割问题时可能出现无节或者虽然有解但原材料 利用率低等问题，并给出了改进的方法。第2 1 节给出经典二维切割问题的模 型，进行分析、归纳，并提出问题。第2 2 节分析了造成二维g u i l l o t i n e 切割的 初始切割模式数量巨大的原因，并提出规划处理原则。第2 3 节给出了结合列 生成算法的数学模型矩阵形式，并提出列生成算法求解二维切割问题的一般方 法。 2 1 二维切割问题的模型分析 2 1 1 切割模式 二维g u i l l o t i n e 优化切割问题描述为：已知库存板的长，宽为l 、w ，待下 零件( 胚料) 即合同板共有m 种，其长宽分别为( t ，) ，i = 1 ，聊，需求量分别 为鼠，i = l ，m ，问如何切割最节约原材料，且切割模式为g u i l l o t i n e 切割。 正如在第一章所述，我们可以把切割模式简单定义为在一块库存板上切割成合 同板的顺序，即合同板在库存板上的布置。 2 1 2 一类切割数学模型存在的问题及对策 切割问题的数学模型主要由密切相关的两部分组成：第一部分为切割模式 的优化选取模型；第二部分为切割方案的优化模型。 切割模式的优化选取模型主要解决巨大数量初始可行切割模式的优化选取 1 0 东北大学硕士学住论文 第二章二维切割问题特点与分析 问题，切割方案的优化模型则是对所选取的切割模式进行优化组合，从而最终 选取切割模式的最优组合。 目前大量研究文献已建立了各种各样的数学模型，这些模型归纳起来主要 有两类：一类是以原材料消耗的总张数最少为目标函数【1 0 】【1 】【1 2 】 1 3 】【1 4 】：另一类 是以锯切损失总和最少为目标函刻15 】【1 6 】 7 1 。 设共有n 种切割模式，巩为第j 种切割模式所切割出的第i 种合同的数量， 则对应的第j 种切割模式的锯切损失为： 卫 0 = l w 一t 吩 ( 2 1 ) 设按第j 种切割模式切割的库存板的张数为x ，则两类数学模型分别为： ( i ) 原材料消耗的总张数最少模型 m i n _ ( 2 2 ) j = l q f a , j x j 岛，i = 1 ，m ；1 e o ，且为整数， j = 1 ，n 。 ( i i ) 锯切损失总和最少模型 m i n s j x j j = l j t a o x j 包，i - - 1 ，删 户1 _ 0 ，且为整数，= 1 ，月 对于第1 i 类数学模型，有的文献1 6 1 1 1 刀中的约束是等式约束，即： ( i i i ) 等式约束型锯切损失总和最少模型 r a i n o _ j = l s t 嘞_ = 6 ，i = 1 ，坍 ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) 东北大学硕士学位论文 g ：- 章二维切割问题特点与分析 一0 ，且为整数，= 1 ，r ( 2 1 0 ) 从表面看来，两类模型均可，而且似乎模型i i 更吸引人，因为它直接追求 锯切损失最少。但是，经过深入分析研究，将发现模型i i ，包括模型i 是有一 定问题。 2 1 3 问题的发现 让我们先看一个简单的实例，从中我们即可发现一些问题。 某工程需要0 3 m x o 3 m 和o 4 m 0 3 m 的合同钢板零件分别为5 张和1 0 张， 现有一批长宽为l m x 0 3 m 的库存板( 钢板) ，问如何切割最省料? 表2 1 切割模式的说明 模式1模式2模式3需求量 0 3 m 0 3 mo235 0 4 m x 0 3 m2101 0 锯切损失( m 2 )0 2 0 3 0 0 1 0 3 由模型i ，有： m i n x a + 屯+ 码 s t 2 x 2 + 3 x 3 5 2 x a + x 2 1 0 一o ，j = 1 ，2 ，3 ，且为整数 解此模型，可得最优解为x i = 3 ，x 2 = 4 ；所用库存板总张数为7 张 率为7 8 6 。 由模型i i ，有： m i n o 2 x o 3 x a + o 1 x 0 3 x 3 s t ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) r 2 1 4 ) 原材料利用 ( 2 1 5 ) 2 x 2 + 3 x 3 5 ( 2 1 6 ) 2 五十屯1 0 ( 2 1 7 ) 石，2 0 ，= 1 ，2 ，3 ，且为整数 ( 2 1 8 ) 显然最优解为x 2 = 1 0 ，此时目标函数虽达到最小( 为0 ) ，但所用库存板总张 数为1 0 张，原料利用率仅为5 5 。由此可见模型i i 的最优解的原材料利用率 一】2 东北大学硕士学位论文 g ：- 章二维切割问题特点与分析 很低。由模型，有： m i n 0 2 0 3 x i + 0 1 o 3 x 3 s t 2 x 2 + 3 x 3 = 5 2 x i + 恐= 1 0 x ，o ，j = 1 ，2 ，3 ，且为整数 r 2 1 9 ) f 2 2 0 ) f 2 2 1 ) ( 2 2 2 ) 下面证明此模型无解： 对于约束( 2 2 0 ) ，因为2 x 2 只能是偶数或零，而( 2 2 0 ) 的右边是奇数，因此x 3 只能取奇数，且只能取x 3 = 1 ；于是得x 2 = 1 ，即x 2 为奇数；而对于约束( 2 2 1 ) ， x 2 又只能为偶数或0 ；出现的矛盾证明了此模型无解。 总结以上实例，可得出以下结论：以锯切损失总和为目标函数的优化切割 数学模型，在某些情况下其最优解的原材料利用率很低，甚至可能导致根本无 解，因而用其来处理实际切割方案是有一定闯题的。 2 1 4 问题的实质 实际中的优化切割追求的目标应考虑两个目标：一是锯切损失总和要小； 二是配套要好，即满足切割任务要求后不配套的零件或多余的零件的总面积( 本 文称之为锯切损失) 也要小。 下面将前面实例用模型i 和模型i i 得出的两种优化切割方案的锯切损失和 余料作一比较，见表2 2 。 表2 2 模型i 和模型i i 的优化结果比较 最优解 所用库存材料利 余料( 舻)锯切损失剩余总和 x x z x 3 板总张数用率 ( 彬)( m 2 ) 模型i 34o77 8 6 0 9 0 30 6 0 31 5 0 3 模型i i o1 0o1 05 5 4 5 0 3o4 5 0 3 由表2 2 可见，模型“虽然追求了锯切损失最少，但是没有充分考到切割 零件的配套性，因此造成余料数很大，即余料和锯切损失总和较大，从而导致 材料利用率很低，这就是模型i i 的不当之处的实质。 至于模型问题的实质，将前面实例中的模型i i 和模型中的全部约束中 去掉整数这一约束，即得： 1 3 东北大学硕士学位论文 第二章二维切割问题特点与分析 2 x 2 + 3 墨5( 2 2 3 ) 2 五十恐1 0 ( 2 2 4 ) x j o ，j = 1 ，2 ，3 ( 2 2 5 ) 其可行域为一无界立体。将约束中的“”改为“= ”后，其可行解域就由 一无界立体变为一线段，由于可行解域大大缩小，就完全有可能不存在能满足 全部约束条件的整数解。 2 1 5 问题的解决途径 模型i i 的修正关键是要解决目标函数的问题，应该追求两个目标的综合效 益，即余料和锯切损失的总和最小。 设s = 三w ，s = “w ，i = 1 ，2 ，3 。 在模型i i 中，剩余的总面积f 应为： 厂= _ o + ( 墨( _ 一6 f ) ) ( 2 2 6 ) j = l j = l j = l 于是，模型i i 可修正为模型： r a i n 量_ + ( 置( x j 一6 f ) ) ( 2 2 7 ) j = l ，= 1 j = l 呀_ 岛，i = 1 ，卅 产l j ，2 0 ，且为整数，j = 1 ，月。 模型的目标函数即( 2 2 7 ) 可改写为： ，= ( 墨_ 十s a , ，x j ) - s 岛 j = l j = l j 1 1 ，；l = ( s j x j + s , x j ) - 鼢 = ( 譬_ + s i a u x j ) - 墨6 ，= 1 j = l ，= 1 j = l 一1 4 f 2 2 8 ) r 2 2 9 ) 东北大学硕士学位论文 第二章二维切割问题特点与分析 nmm ( s j + s i a 口) x j z s , b j = l i = l l * 1 显然，马+ 墨嘞恰好等于库存板的面积 i = l 效总面积f o ，于是有： 由于s 和f o 是常量，因此有： 月 m i n ( s 了- x j 一五) m i n o j = lj = l ( 2 3 1 ) 可见模型i i 经修正成模型后，完全与模型i 等价。由于摸型i 形式更简 单明了，因而可作为常见切割问题的典型数学模型 至于模型的问题的解决途径，可首先将等式约束改为不等式约束，就将 模型i i i 变成了模型i i ，再将其目标函数改变，就可得到模型i i 或模型i 。 总结以上研究，可得以下几点结论： ( 1 ) 现有许多文献所建立的一类以锯切损失总和为目标函数的数学模型 ( i i 类f d i i i 类) 中，某些情况下i i 类模型存在着最优解的材料利用率很低，而 类模型存在着无解的问题。 ( 2 ) i i 类模型的问题的实质是目标函数中只考虑了锯切损失最少，而没 有体现切割合同的配套性要求，因而可能导致剩余很大即库存板有效利用率很 低。i i i 类模型的问题实质是等式约束条件使得模型可行解域太小，从而导致无 整数解。 ( 3 ) 类模型的问题的解决途径是将等式约束改为不等式约束，从而成 为了i i 类模型。i i 类模型的问题的解决途径是将锯切损失目标函数改为剩余料 目标函数，即修正为模型。 ( 4 ) 模型和模型i 完全等价，且模型i 还具有简单、清楚之优点，因 此在目前已有的几类典型切割数学模型中，模型i 是一种典型适用的模型。 2 2 初始切割模式的研究 定义2 1 合同板待切割的矩形板材我们称之为合同板。 1 5 圳 脯 0 可日需所是、e劫 岛s 。h 而 s 一 专 。一 s i i 矗 一 。闩 = ， 东北大学硕士学位论文第二章二维切割问题特点与分析 定义2 2g u i l l o t i n e 切割模式在库存板上，能保证按照g u i l l o t i n e 切割进行到 底的零件排样方式。 在优化切割问题中，第一阶段就是要确定出在原材料板材上切割出所需的 各种矩形零件，即合同板的顺序，也就是确定合同板在库存板上的布置，称为 确定切割的初始切割模式；第二阶段就是将各种初始切割模式进行排列组合， 求出最优切割方案。 由于切割工艺以及原材料性质的不同，大量的切割需要使用g u i l l o t i n e 切 割。剪板机上薄型板材的剪切及玻璃的切割就是g u i l l o t i n e 切割最典型的例子。 二维g u i l l o t i n e 切割在一般情况下，可行的初始切割模式数量极其巨大，如果 要得到理论上的最优切割方案，就要求所有可行的切割模式都进入优化切割模 型的系数矩阵，但计算机的容量和速度决定了这种方法不可行。因为即使是一 维切割，切割模式的数量也相当巨大，而对于二维切割，切割模式不仅要满足 各切割件面积总和小于原材料板面积，还要满足零件长、宽分别在原材料长、 宽方向上的套裁，因而二维切割模式比一维切割模式复杂且数量大得多。 设某项工程需要m 种规格的零件，其数量分别为( 6 1 ，b 2 ，6 卅) ，其长、宽 分别为( 1 l ，) 、( 1 2 ，心) 、( f f ，) 、(