（模式识别与智能系统专业论文）一维最优下料问题研究.pdf

山东大学硕士学位论文 摘要 近年来，随着国民经济的飞速发展，一维下料问题在建筑、电力、水利 等领域获得了越来越广泛的应用。寻找一种最优的下料方案，不仅可以节省 原材料，降低生产成本，而且能够为企业带来直接的经济效益，促进国民经 济的健康发展。因此，开展对一维下料问题的研究具有重要的理论意义和工 程应用价值。 本文首先深入地分析了维下料问题，提出了一种截切方案的计算机自 动生成的算法，建立了该类问题的数学模型。然后，分别采用三种方法对 维下料问题进行优化求解，并进行了具体算例的比较分析。 1 线性规划。线性规划的单纯形法是求解维下料问题的传统方法。本 文首先应用这种方法对一维下料问题进行优化求解，劳分析了这种方法存在 的缺陷，如：所得的结果不全为整数；或由于问题的规模过大而导致算法失 效，出现病态解甚至无解的情况。 2 遗传算法。本文从应用的角度对遗传算法做了认真的分析和研究，然 后将其应用于一维下料问题的求解，提出了一种基于遗传算法的求解方法。 在求解过程中，给出了遗传算法求解的编码方法、适应度函数的定义、遗传 算子以及关键参数。实际应用表明，采用该方法求解是可行的，并且取得了 较好的寻优效果。 3 遗传模拟退火算法。针对遗传算法存在“过早收敛”的现象及其良好 的兼容性，考虑将模拟退火算法与遗传算法相结合，用来求解一维下料问题。 这是一个新的尝试。该算法首先通过遗传算法来进化生成一个群体，然后利 用模拟退火算法进一步调整优化解。基于算例的求解结果验证了本文所提出 的遗传模拟退火算法的有效性和高效性，其下料结果明显优于线性规划和遗 传算法。 关键词：一维下料问题，线性规划，遗传算法，模拟退火算法 山东大学硕士学位论文 a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n t o fn a t i o n a l e c o n o m yi nr e c e n t l yy e a r s ，t h e o n e - d i m e n s i o n a lc u t t i n gs t o c k p r o b l e m o c c u r si nm a n y i n d u s t r ya r e a s 。l o o k i n gf o r a no p t i m u m c u t t i n gs o l u t i o nc a r ln o to n l ys a v er a w m a t e r i a l sa n dd e c r e a s ep r o d u c t c o s t ，b u ta l s ob r i n gt oi m m e d i a t ee c o n o m i cb e n e f i t sf o re n t e r p r i s e sa n da c c e l e r a t e t h ed e v e l o p m e n to f n a t i o n a le c o n o m y s or e s e a r c ho n t h ep r o b l e mi so f i m p o r t a n c e i nt h e o r ya n d p r a c t i c e f i r s t l y , i n t h i s p a p e r , w es t u d y o n ek i n do fo n e - d i m e n s i o n a l c u t t i n g s t o c k p r o b l e m si ng r e a td e t a i l ，p u t f o r w a r da na l g o r i t h mt h a tl ：a i l g e n e r a t ec u t t i n g p a t t e r n sa u t o m a t i c a l l yb yt h ec o m p u t e r a n d t h em a t h e m a t i c a lm o d e li se s t a b l i s h e d b a s e do nt h e s ep a t t e r n s t h e nt h r e ed i f f e r e n ta l g o r i t h m sa r ea p p l i e dt os o l v i n g o n e - d i m e n s i o n a lc u t t i n gp r o b l e m s ，a n dr e s u l t so fn u m e r i c a le x a m p l e sa r ea l s o g i v e na n d d i s c u s s e d 1 l i n e a rp r o g r a m m i n g s i m p l e xm e t h o do fl p i sat r a d i t i o n a lm e t h o dt os o l v e t h i sp r o n e m t h i s p a p e ra n a l y z ed i s a d v a n t a g e so f t h i sm e t h o d ，f o ri n s t a n c e ： t h es o l u t i o na r en o ta l li n t e g r a ln u m b e r s ，o rw i l lg e tw r o n ge v e nn os o l u t i o n b e c a u s e o f g r e a t s c a l eo f t h ep r o b l e m 2 g e n e t i ca l g o r i t h m g ai sa ni m p o r t a n ti n t e l l i g e n ta l g o r i t h m w eu s et h i s a l g o r i t h m t os o l v et h eo n e d i m e n s i o n a l e u t t i n g s t o c k p r o b l e m a f t e r a n a l y z i n gg a f r o mt h ea n g l eo fa p p l i c a t i o na tt h es a m et i m e ，t h ec o d i n g m e t h o d ，f i t n e s sf u n c t i o nd e f i n i t i o n ，g e n e t i ca l g o r i t h mo p e r a t o r sa n ds o i t l e k e yp a r a m e t e r s a r eg i v e n t h er e s u l t ss h o wt h a tt h ea l g o r i t h mi sf e a s i b l ea n d e f f i c i e n t 3 g e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h m i no r d e rt oo v e r c o m ep r e m a t u r e c o n v e r g e n c e i ng aa p p l i c a t i o n s ，w e p r e s e n t t h a t c o m b i n i n gg e n e t i c a l g o r i t h mw i t hs i m u l a t e da n n e a l i n ga l g o r i t h m b e c a u s eo f g o o dc o m p a t i b i l i t y o fg a s o l v i n gt h eo n e 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 mb y t h i sa l g o r i t h m 山东大学硕士学位论文 i sa ni n n o v a t i v ea t t e m p t t h ef i r s ts t e po ft h eh y b r i da l g o r i t h mw e p r o p o s e d i st og e n e r a t ea g r o u pb yg a t h e n t h eg r o u pw i l lb ea d j u s t e da n d o p t i m i z e d b ys a t h er e s u l t sb a s e do de x a m p l e sd e m o n s t r a t et h ee f f e c t i v e n e s sa n d e f f i c i e n c y o ft h i sg e n e t i cs i m u l a t e d a n n e a l i n ga l g o r i t h m ，w h o s e p e r f o r m a n c e so nt h eo n e d i m e n s i o n a lc u t t i n gs t o c k i n ga r eq u i t eb e _ 【t e rt h a n l pa n d g a k e y w o r d s ：o n e 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 m ，l i n e a rp r o g r a m m i n g ，g e n e t i c a l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h m i i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：墨i li l 日期：塑e 生! 厶 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：王聱藓 导师签名：二塑墨! 圣日期：超丝：正耋 山东大学硕士学位论文 1 1 问题的提出及分类 1 引言 近年来，随着国民经济的飞速发展，下料问题在机械、电力、水利、航 空航天、商业、国防等领域获得了越来越广泛的应用。寻找一种最优的下料 方案，不仅可以节省原材料和加快切割速度，而且能够为企业带来直接的经 济效益，促进国民经济的健康发展。因此，下料问题激起了许多研究者的兴 趣。7 0 年代至今，人们从不同的具体应用、不同的角度、采用不同的方法对 其进行了研究，提出了各种各样解的标准和算法。正是由于下科问题应用的 广泛性与其求解的难度，吸引了众多学者的研究。在1 9 8 8 年的e u r o i x t i m s x x v i i 国际会议上，专门成立了下料问题兴趣小组s i c u p 【i j ( s p e c i a l i n t e r e s tg r o u po nc u t t i n ga n dp a c k i n gp r o b l e m ) 。 下料问题可以分为三大类：材料的切割问题( t r i m l o s sp r o b l e m 或 c u t t i n gs t o c kp r o b l e m ) 、排样问题( a s s o r t m e n tp r o b l e m ) 和装箱问题( b i n p a c k i n gp r o b l e m ) 。材料的切割问题如型材、棒材的下料，建筑业中钢筋、 铝合金的下料，家具制造业中板材的下料：排样问题如印刷业中各种书刊、 报纸的排版，微电子工业中集成电路的排布；而物流业中的集装箱装货，即 如何将货物优化地装入有限空间的集装箱中则属于装箱问题。 就材料的切割问题而言，根据原材料和零件的维数，又可以进一步划分 为一维下料问题、二维下料问题、三维下料问题等。一维下料问题指的是型 材、棒材的下料，二维下料问题则主要指扳材的下料，三维下料问题是指原 材料和所下零件的长、宽、高均有特定要求的情况。本文主要研究一维下料 问题。 在某些以条型材为原材料的生产部门中，经常遇到如下形式的下料问题： 已知f 种性能相同仅长度不同的直条材a ，、a ：，a ，：每种原料长度为上。、 l ，、，；数量为& 、s ，、s ，：要求截成m 种长度不同并能满足需求量 的构件茸、b ：、矗，i 成品长度为f 。、，2 、乇：需求量为d ：、d ：、如。 】 山东大学硕士学位论文 应该采取什么样的下料方案，使得既满足要求，又使下料后的剩余边料总长 最小，从而使材料利用率最大，达到减少材料损失，降低成本，提高经济效 益的目的，这就是所谓的一维最优下料问题。 根据原材料的供应情况，此类问题可简单归结为下列三种基本类型，其 他情况一般可看作这三种基本类型的复合和变型【2 1 。 ( 1 )等长原料下料。即所有构件可通过一种规格的原料截得，原料数量 无限制。 ( 2 )不等长原料下料。即构件可通过几种规格的原料截得，各种规格的 原料均有数量的限制。 ( 3 )随机长度原料下料。即原料长度分布无规律，边测长，边截切， 本文主要讨论第一种类型的一维下料问题，即等长原材料下料的情况。 对于此类问题，传统的解决方法是“单一下料法”，即在每一根原材料上 只下一种规格的零件。在生产中。有时也采用在一根原材料上先下尺寸大的 零件，然后再用剩下的余料下尺寸，j 、的零件，这种下料方法称为“简单套裁 法”。单一下料法可按一种固定不变的方式送料、下料，简单方便，但是，往 往会产生较多的余料，造成每一根原材料的利用率不高；简单套裁法的材料 利用率虽然比单一下料法高，但是，由于对如何下料事先缺乏周密考虑，所 以也很难大幅度地降低余料，材料利用率也不高。即使是由最有经验的工人 师傅下料，材料的利用率也只能达到8 0 。 1 2 一维下料问题的研究进展 二十世纪以来，随着工业技术突飞猛进的发展和资源的日趋紧张，各行 业对节约逐渐重视。人们开始考虑在“下料”这一环节尽可能地使能源得到 充分的利用。第二次世界大战以后，由于军事上的需要，使得运筹学和最优 化的技术迅速发展和完善，这给下料问题的研究提供了理论基础。 国外有关下料问题的研究起步较早。第一个下料问题的著名模型是俄国 经济学家k a n t o r o v i c h 于1 9 3 9 年提出的。接着e i s e m a n n 提出了一个实用 的多根原材料、多台切割机器的一维下料问题的模型，并用线性规划方法 2 山东大- 学硕士学位论文 ( l p ) 求解。但e i s e m a n n 的方法只能用于解决小规模问题，当遇到大规模 问题时。由于一个变量代表某种切割方式的重复使用次数，有许多可以选择 的切割方式满足问题的组合条件。因此，用线性规划来求解变得非常困难。 g ii m o r e 和g o m o r y 【3 6 1 于1 9 6 1 、1 9 6 3 和1 9 6 5 年利用一种切割方式的产生技 巧和线性规划相结合成功地解决了切割方式的选取和问题的求解。这使得大 规模问题的求解成为现实。这一突破性的进展，奠定了一维下料问题求解的 基础。 此后，越来越多的学者投入到这个研究领域中，并提出了各种各样的解 的标准和算法。由于既是整数解又是最优解的答案在实践中很难得到，许多 求解近似解的启发式算法也被广泛应用。具有代表性的是h a e s s l e r 于1 9 7 5 年提出的“在一维切边问题中控制切边方式的改变”的思想 7 1 。另外，还有 随机搜索方法( v a h r e n k a m p ) 【8 l ，包含两个目标函数在动态规划基础上产生 的启发式方法( j a n t o n i o ) g l ，模拟退火启发式方法( c h u e n l u n gs c h e n ) i 4 1 。 近年来，随着计算机和优化技术的发展，人们对于一维下料问题的研究 也在不断深入。不少学者采用智能优化算法来解决下料问题，已经取得了初 步的成果。例如遗传算法 1 0 1 - 1 ”】、模拟退火算法n 4 1 等。针对不同问题的特点， 测试和分析算法的性能，研究如何利用多种算法成为下料问题研究的一个重 要方向。 1 3 论文的主要内容 1 3 1 课题要求 本课题以电力系统架设高压线的铁塔为例，研究一维下料问题，并设计 一个实用的应用软件。 ( 1 ) 现有原材料工4 3 2 0 0 0 m m ，数量不限。 ( 2 ) 截切零件种数埘4 1 0 ，长度，。4 3 2 0 0 0 m m ，数量d 。4 2 0 0 0 根。 3 山东大学硕士学位论文 1 3 2 主要工作 本课题主要工作分为以下几个方面： ( 1 ) 建立数学模型 建立数学模型是问题求解的第一步，也是最为关键的一步。数学模型的 好坏直接关系着优化结果的好坏。在研究规模较小的一维下料r 7 题时，建模 问题不难解决。但当原料品种数和成品品种数均较大时，建立线性规划的数 学模型的工作就变得相当复杂，人工建模更是不可思议的。为此。本文提出 了一种截切方案的计算机自动生成方法，该方法精确给出了下料方式的所有 可能的情形，避免了手工试算的繁琐及遗漏。利用该方法可方便的得到一维 下料问题的数学模型。 ( 2 ) 用运筹学中的线性规划方法求解一维下料问题 从一维下料问题的数学模型看，这是一个整数规划问题。传统的下料求 解方法是将整数变量进行松弛，视为线性规划，采用单纯形方法求解。本文 首先采用这种传统的方法对一维下料问题进行求解，并讨论这种方法的优缺 点。 ( 3 ) 采用智能优化方法对一维下料问题进行求解 近年来，随着计算技术的发展，一些新的智能优化算法( 如遗传算法、 模拟退火算法、禁忌搜索算法) 得到了迅速发展和广泛应用。人们开始研究 用智能优化算法来对一维下料问题进行求解。 本文首先从应用的角度对遗传算法做了认真的分析和研究，然后将其应 用于一维下料问题的求解，提出了一种基于遗传算法的求解方法。在求解过 程中，给出了遗传算法求解的编码方法，适应度函数的定义、遗传算子以及 关键参数。实际应用表明，采用该方法求解是可行的，并且取得了较为理想 的效果。 另外，针对遗传算法存在“过早收敛”的现象和其良好的兼容性，考虑 将模拟退火算法与遗传算法相结合，用来求解一维下料问题。这是一个新的 尝试。本文针对一维下料问题的特点，提出了一种遗传模拟退火算法。该算 法将模拟退火机制引入到遗传算法中，首先通过遗传算法进化生成一群解， 4 山东大学硕士学位论文 然后独立地对种群中的各个个体进行模拟退火过程，在收敛性能和避免局部 极小方面有了较大的改善。 ( 4 ) 试验结果的比较分析 针对具体的下料问题，分别用线性规划和本文所提出的遗传算法、遗传 模拟退火算法进行求解，并在这三种算法的结果上进行分析比较，从中找出 一种适合求解此类问题的较好方法。 1 4 论文的内容安排 论文各章节的内容安排如下： 第二章：主要介绍一维下料问题的截切方案的计算机自动生成方法，以 及由此而建立的数学模型。 第三章：一维下料问题的线性规划求解，试验数据和结论。 第四章：首先简要介绍遗传算法，包括遗传算法的基本结构、特点以及 算法实现的技术问题。然后提出了一种针对一维下料问题的遗传算法，并给 出了编码方法、适应度函数的定义遗传算子和关键参数，以及试验数据和 结论。 第五章：介绍了遗传算法和模拟退火算法相结合的基本思想及其实现。 给出了用于解决一维下料问题的遗传模拟退火算法的具体步骤，最后是试验 数据。并对三种算法所得的试验结果进行了分析与比较。 第六章：结论。 5 山东大学硕士学位论文 2 一维下料问题数学模型的建立 2 1 截切方案的计算机自动生成 2 1 1 一个简单的下料问题 为方便对一维下料问题的理解和建模，首先来看一个简单的下料问题1 ： 某厂有一批长为7 4 公尺的钢管，因生产需要将其截成2 9 、2 1 和1 - 5 公尺不同长度的管料，现3 种规格各需1 0 0 根，问应如何下料，可使用料最 省? 对于一根7 4 公尺的材料较合理的截切方案可能有： 表2 i 合理的截切方案 截切方案2 9 公尺( 根) 2 ，1 公尺( 根) 1 ，5 公尺( 根) 余料( 公尺) 设每种加工方案加工的根数为决策变量x ，( 根) ，i = 1 ，2 ，3 ，4 ，5 。x ，为第f 种 截切方案加工的钢管根数。 总余料应最少： m i n o a x 2 + 0 2 x 3 + o 3 x 4 + 0 8 x 5 ( 2 1 ) 根据产品需要量的约束得到： 2 9 公尺x l + 2 工2 + x 4 = 1 0 0 2 1 公尺 2 x 3 + 2 x 4 + x s = 1 0 0 1 5 公尺3 x l + x 2 + 2 x 3 + 3 x 5 = 1 0 0 非负约束x ， 1 0 ，i = 1 , 2 ，3 ，4 ，5 对于这个简单的一维下料问题，通过计算得到表2 6 ( 2 2 ) 1 ，即较合理的截切方 山东大学硕士学位论文 案，然后根据这些截切方案和每种零件需要1 0 0 根的约束条件，列写出目标 函数( 2 1 ) 和方程组( 2 2 ) 。式( 2 1 ) 和( 2 2 ) 就是该问题的数学模型。 由此可以看出，建立一维下料问题的数学模型可分解为2 步：( 1 ) 从所 有可能的截切方案中确定出较合理的截切方案，并计算相应的余料长度。由 这一步得到数学模型的约束方程组的系数矩阵和目标函数的系数。( 2 ) 根据 每种零件的需求量，列写出数学模型。而截切方案的生成是关键的一步。 2 1 2 算法的基本步骤 对于上述简单的一维下料问题，可能的截切方案的种数不会很多，可以 用人工试算的方法求出每种截切方案所能截得的零件根数及其相应的余料大 小，从而建立数学模型。但当原材料的品种数和成品品种数均较大时，可能 的截切方案的种数将成裂变式增加0 6 ，若用人工方法逐一试算，不但极为费 工费时，而且容易产生遗漏，因此，采用计算机自动确定所有可能的截切方 案是十分必要的。本文给出了一种算法来解决这一问题，该方法的具体步骤 是： 首先。把要截切的零件按其长度由大到小递减排列，并给予相应的编号， 以i 标记之( f = l ，2 ，n ) ；以n u m 。、l e n g t h ，分别表示在原材料上截得的零件i 的数目和所剩的余料。 s t e p l计算一根原材料至多可裁i = 1 号零件的数目n u m 。 s t e p 2 对于截切过n “m 个i 号零件所剩的余料l e n g t h , ，检查是否可以截切f + l 号零件。若可以，计算出可截得的i + 1 号零件的最大数目h u m 。 s t e p 3 令i = i + 1 ，返回s t e p 2 。即依次检查是否还可以截切其他的零件， 直至i ：n 一1 。这样，我们就得到一个长度为n 的数组，数组各元素 值为一根原材料所能截切的各个零件的数量n h t m 。，可作为第一个截 切方案。 s t e p 4 令j = n 一1 ， n u m ， o ， 令h u m = n “川，一1 ，重新计算n “卅j + 1 的值， 得到的新数组可作为一个新的截切方案，直到n u m ，= o 为止。 7 山东大学硕士学位论文 s t e p 5 令，= j 一1 ，h u m j 0 ，令n “埘= n 1 2 m j l ，重新计算”m 川的值 记录当前，的值并返回s t e p 4 ，直到r l u m - - - - 0 为止。 s t e p 6 令- ，= j 一1 ，若h u m 0 ，h u m 2 n 删j - - 1 ，重新计算，z “m 州的值， 记录当前，的值并返回s t e p 5 ，根据新的, r u m 。的值重新计算数组各 后续元素值，直到n u m = 0 为止。 s t e p 7 重复s t e p 4 - - 6 ，当，= l 且h u m ，= o 时，计算结束。 该算法的关键在于通过嵌套循环穷举出所有可能的截切方案，并通过对 每一个方案编码计数器( 即数组中各元素值) 确定上界，有效地去除了不可 能的方案减少了迭代次数，节省了运算时间， 8 ( s t e p1 3 、 ( s t e l 0 4 - 6 ) l 号 2 - 山 1 l 1 一t 山 0 0 2 号 0 。 3 一乩 2 一t 山 1 一乩 3 号 l 0 1 3 0 2 3 0 04 图2 1截切方案的生成过程 余科 0l 03 o9 0 l 1 d2 08 14 以上述简单的一维下料问题为例，说明该算法产生所有可能的截切方案 2 i山v，i山v 山东大学硕士学位论文 的过程。首先对零件进行编号，将2 9 、2 i 和i 5 公尺的零件分别记为i 号、 2 号和3 号。经过s t e p 一3 ，产生的截切方案为 2 ，0 ，l ，0 1 ，并将其作为方 案编码计数器的上界，然后不断重复s t e p 4 - - 6 ，直至满足结束条件。具体过 程如图2 1 所示。 2 1 3 算法的实例验证 该算法给出了一维下料问题的所有可能的截切方案及其对应的余料长 度。这部分采用v i s u a lc + + 6 0 进行编程，系统的输入界面如附录2 中图2 所示。 在初始条件界面中输入所要解决的一维下料问题的具体数据，注意成品 长度一栏要求由大到小依次输入。然后单击 截切方案 按钮，即可得到所有 可能的截切方案，截切方案按其余料长度由小到大依次输出。 对于附录1 中的算例i ，应用该算法可以得到1 9 种截切方案，如图2 2 所示。而对于算例2 。得到的截切方案多达3 4 2 7 0 种，如图2 3 所示。而由算 例3 得到的截切方案有3 5 9 0 种，且每一种方案的余料均为0 ，如图2 4 。 图2 2算例i 的所有截切方案 9 山东大学硕士学位论文 图2 3算例2 的所有截切方案 图2 4 算例3 的所有截切方案 从实例验证可以看出，该算法的突出优点在于：它精确绘出了截切方案 的所有可能的形式，避免了手工试算的繁琐和遗漏；同时有效排除了对不可 1 0 山东大学硕士学位论文 能方案的讨论，大大节省了运算时间；并且为数学模型的建立和问题的优化 求解提供了必要的准备。 2 1 4 截切方案的筛选 实践证明，截切方案的多少直接关系到实际问题的数学模型的繁简优劣。 若单从数学模型的真实性这一角度来看，当然希望所考虑的截切方案越多越 好，但这必然使相应的模型趋于大型化、复杂化，从而增加求解的困难，反 之，若选用的截切方案太少，则相应的模型会变得太粗糙，甚至会把最佳的 方案也漏掉。因此，为了使建立的数学模型既简便又能较真实地反映实际问 题的本质规律，通常耍对所生成的截切方案进行科学的简化【”l 。因此我们考 虑：( 1 ) 去掉余料较大的部分方案，这是因为若某种截切方案所剩余料较大， 则反映在相应的数学模型的解中，按这些方案下料的原材料根数必定很少甚 至为零。( 2 ) 将余料较小的那些方案取出单独考虑。在实际加工过程中让其充 分生产，以满足需要。这是因为在模型的解中，这些方案所对应的原材料根 数必定很多。( 3 ) 考虑到生产施工的实际情况，所筛选的截切方案的种类不宜 过多，这样可以减轻劳动强度和劳动复杂性，有效节省时间。 在数学模型中，约束方程的个数等于零件的个数，即一种零件对应一个 方程。变量的个数等于所选取的截切方案的个数。当变量个数h 约束方程的 个数肌时，方程组有无穷多个解，只有在无穷多个可行解中才能找到一个满 足约束条件的晟优解。因此考虑筛选出”个余料较小的截切方案，来参与模型 的建立。在第三章线性规划的优化求解中，由于l i n d o 软件的求解范围在3 0 0 个变量之内，故对于截切方案较多的情况( 如算例2 和算例3 ) 。筛选出前3 0 0 个余料较小的方案；在后两章用遗传算法及遗传模拟退火算法求解时，由于 遗传算法具有良好的全局搜索能力，则选用全部的截切方案来参与初始种群 的生成。 2 2 建立数学模型 针对一维下料问题，目前大量研究文献已经建立了各种各样的数学模型。 1 1 山东大学硕士学位论文 这些模型归纳起来主要分为两类【1 8 i ：一类是以残料总和最少为目标函数；另 一类是以原材料消耗的总根数最少为目标函数。本文采用了第一种模型。 由上一步，我们得到n 个合理的截切方案。若方案1 中第一种零件下“ 个，第二种零件下口：。个。依此类推，第m 个零件下a 。，个，此时余料记为c 。； 则方案”中各项可依次记为口。、口：。、c l m n 及q 。于是我们得到如下的系 数矩阵 a = 日口1 2 盘h a 2 1口2 2d 2 月 口1口m 2 口m 其中，口。表示用第，种截切方案所能得到的第i 种零件的个数，c ，为每种截切 方案所产生的余料长度。另外，设x ，为用第，种截切方案加工的原材料的根 数，b 为第f 种零件所要求截得的根数。 为了达到最优下料的目的，即使下料后所剩余料最小，材料的利用率最 高，我们将每种截切方案产生的余料c ，作为目标函数的系数，可得 c 1 x 。十c ：x ：+ + c 。x 。，而我们优化的目标是使该目标函数取得最小值；约束 条件由每种零件所要求截得的根数而定，并且理论上要求x ，的取值为整数。 综上i ”】，我们得到一维下料问题的数学模型为 m i n c x ， j = 】 s t 盘g z = b 。( f _ 1 ，2 ， j = l z o 且为整数( j 2 1 ，2 ， ，珊)( 2 3 ) ，n ) 由一维下料问题的数学模型，可以看出这是一个整数规划问题。若采用 针对整数规划求解的分枝定界法求解，只能在变量数目n 较少的情况下适用 1 2 0 。当原材料长度l 和所要截切的零件长度，之比大于一定数值后，得到的 1 2 山东大学硕士学位论文 截切方案很多，此时用分枝定界法难以求解。因此传统的下料优化方法是将 整数变量进行松弛，并视为线性规划，采用单纯形法进行求解。这个方法的 提出使得较大规模的下料问题可以有效求解。 1 3 山东大学硕士学位论文 3 一维下料问题的线性规划求解 3 1 线性规划 线性规划( l i n e a rp r o g r a m m i n g ) 是运筹学中最重要的一个分支，简称 l p 。经过多年不断的研究发展，目前就其理论的完整性、求解方法的多样性 和应用的广泛性等方面。都远较运筹学的其他分支更成熟。1 9 3 9 年，苏联数 学家康脱洛维奇在生产组织与计划的数学方法一书中，首次提出了线性 规划问题，以后美国学者希奇柯克( f l h i t c h c o c k ，1 9 4 1 ) 和柯普曼 ( t c k o o p m a n ，1 9 4 7 ) 又独立地提出了运输问题这样一类特殊的线性规划问 题。特别是在1 9 4 7 年，美国数学家丹捷格( g b d a n t z i g ) 提出了线性规划的 单纯形法和许多有关的理论，为线性规划奠定了理论基础。随着电子计算机 的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和 国防等各个领域“9 。 3 1 1 线性规划的几种形式 概括地说，线性规划问题所研究的数学模型是具有线性约束的线性函数 的极值问题。一般来说，线性规划问题可用以下数学语言描述： m i n c l x l + c 2 x 2 + - + c 。x n ( 3 1 ) s t d 1 1 工l + 口t 2 x 2 + - - + 口h ( = ，) 岛 q 2 x 2 + 口2 2 x 2 + + 口2 。x 。( = ，) 6 2 ( 3 2 ) a 。1 _ + d 。2 x 2 + + 口。x 。( = ，) 6 。 _ o ，= l ，2 ，仃 ( 3 3 ) 式( 3 1 ) 是线性函数，称为线性规划的目标函数( o b j e c t i v e f u n c t i o n ) 。 等式或不等式( 3 2 ) 与( 3 3 ) 称为线性规划的约束条件( c o n s t r a i n t c o n d i t i o n s ) ，其中式( 3 3 ) 又称为非负条件( n o n n e g a t i v e c o n d i t i o n s ) 。 1 4 山东大学硕士学位论文 ! ! = = = = = = = = = = = = = = = = = = = = = ! = ! ! ! ! = = = = = = = = = = = ! ! = ：= = = = = = ! ! ：= 我们称( 3 1 ) 、( 3 2 ) 和( 3 3 ) 为线性规划的一般形式； 当所有的约束条件为等式约束时， r a i n 。 j = 1 月 s t 口f x j = 岛( f = 1 ，2 。，m ) ( 3 4 ) j = i x j 0 ( ，= l ，2 ，n ) 我们称式( 3 4 ) 为线性规划问题的标准形式，其中埘茎n ； 有时标准形式( 3 4 ) 可写为 r a i n e c x i j = l s t a ，x ，= b i ( f _ 1 ，2 ，埘) ( 3 5 ) 1 = 1 j o ( j = 1 ，2 ，玎) 其中a ，= k 护日护，r 是矩阵爿= a 。，a 。，a ，a 。 的第列向量。 若在a 的列向量a i ，a ：，a j , - , 巩中含有? i t 个单位向量并可以合成单 位矩阵，而且所有的右端项非负，则此时的标准线性规划( 3 5 ) 称为线性规划 的典范形式。 于是，线性规划问题可归结为求一组变量x ，x ：，x 。满足约束条件( 3 2 ) 与( 3 3 ) ，使目标函数( 3 1 ) 取得极小值的规划问题。 3 ，1 ，2 单纯形法 单纯形法( s i m p l e xm e t h o d ) 是在认识线性规划解的基本性质的基础上， 由美国数学家丹捷格发明的，它一直是求解各类线性规划的最有效和普遍使 用的方法。已经知道，一个线性规划问题若有最优解，则一定有最优的基本 可行解，而且其基本可行解的个数是有限的1 。因此最容易想到的是：将所 有的基本可行解都找出来，然后逐个进行比较，求出最优解。这正是枚举法 寻优的基本思想。但是当问题的阶数和维数 较大时，枚举法是行不通的。 】5 山东大学硕士学位论文 = = = = = = = = = ! ! = = = = = = = = 竺= ! 竺= = = = = = = ! = ：= = = = = ! - ：= = = = = ：! - 这就导致了单纯形法的出现。单纯形法不是漫无目的的寻找所有的基本可行 解，而是朝着某一预先设定的方向寻找。 单纯形法的基本思路就是从一个基本可行解( 称之为初始基本可行解) 出发，按某一规则转换到另外个基本可行解，使得目标函数值逐次下降( 至 少不上升) 。经过有限次迭代即可找到最优解( 假设存在) 。 单纯形法计算的一般步骤为： s t e p l 建立初始单纯形表。首先将约束条件中的不等式化为等式，建立初始 单纯形表爿，确定初始可行基( 一般选单位矩阵为可行基) ，从而确 定基变量及其值。 s t e ? 2 检验所得的基本可行基是否为最优解。求d ，= m a x p ， ，8 ，为所有 非基变量的检验数。若盯，0 ，则已经得到最优解，停止计算。否 则，若盯， 0 ，转下一步。 s t e p 3 若a i 0 ，则线性规划解无界，计算中止。否则转下一步。 趼e p 4 基交换。求兰- - - = m 。塾l n l 一= 6 ：- - f , 1 7 ， 。 9 由拢确定两为退基变量，t 为 “l ，1j 进基变量。 s t e p s 迸行迭代得到新的单纯形表。以为主元对a 中的所有数据实行换 基运算，产生新的单纯形表，设仍用j 表示，转到s t e p 2 。 3 2l n d o 简介 以上介绍了单纯形法的基本原理及单纯形法求解线性规划问题的主要步 骤。显然当变量个数n 及约束个数m 较大时，用手算是不可能的。现在已经 有了不少用来求解线性规划问题的数学软件，如l i n d o 。l i n d o 是一种专门用 于求解数学规划问题的优化计算软件包，版权现在由美国l r n d o 系统公司 ( l i n d os y s t e mi n c ) 所拥有。l i n d o 软件包的特点是程序执行速度很快，易 于输入、修改、求解和分析一个数学规划( 优化问题) ，因此l i n d o 在教育、 1 6 山东大学硕士学位论文 科研和工业界得到广泛应用。l i n d o 主要用于求解线性规划、整数规划和二次 规划问题，也可用于一些线性和非线性方程组的求解及代数方程的求根等。 l i n d o 中包含了一种建模语言和许多常用的数学模型( 包括大量的概率函数) ， 可供使用者建立数学规划问题模型时调用1 2 2 。 l i n d o 软件包中包括：l i n d o 软件、g i n o 软件、l i n g o ( 包括l i n 6 0n l ) 软 件。其中l i n d o 软件可以用来求解线性规划、整数规划和二次规划。l i n d o 是l i n e a ri n t e r a c t i v ea n dd i s c r e t eo p t i m i z e r 的缩写。它求解线性规划 的过程采用单纯形法，一般是先寻求一个可行解，在有可行解的情况下再寻 求最优解。 本文对下料问题的线性规划求解就采用l i n d o 软件。有关该软件的发行 版本、发行价格和其他最新信息都可以从l i n d o 系统公司的i n t e r n e t 网络站 点h t t p ：w w w 1 i n d o e o m 获取。该站点还提供部分l i n d o 软件的演示 版本或测试版本。学生版和演示版与发行版的主要区别在于对优化问题的规 模( 变量和约束个数) 有不同的限制。本文中所使用的演示版可求解多达3 0 0 个变量和1 5 0 个约束的线性规划问题。 下面以式( 2 1 ) 和( 2 2 ) 构成的线性规划为例，用l i n d o 进行求解，过程 如下： ( 1 ) 打开l i n d o 软件，在u n t i t l e d 窗口输入： 图3 1输入窗口 ( 2 ) 将光标移至回上，单击鼠标左键，得到如图3 2 的运算状态对话框。 1 7 山东大学硕士学位论文 1 8 图3 2 运算状态对话框 0 ，i 一1 ，2 ，埘 这正是线性规划的标准形式，所以传统的方法就是采用线性规划的单纯 形法来求解。本文中采用l o n d 0 软件进行求解。 为了整个优化程序的一致性，本文采用v i s u a lc + 十6 0 建立主程序，在程 1 9 山东大学硕士学位论文 序中调用l i n d o 提供的接口函数根据输入的原始条件和计算得到的初始方 案建立优化模型，求解并得到最终结果。算例的具体数值见附录1 。输出界面 如附录2 中所示。 算例1 表32 算例1 的线性规划求解结果 原材料根数 2 21 81 2 53余料 3 03 0 0 0 00 11 000 3 0 04 0 0 00 oo35 0 3 0 03 0 0 00 00 600 3 00 5 0 0 0 00 202 0 3 03 ，0 0 0 0 l 00 llo 因为所求的解中含有小数，需要人为的进行取整，才能满足实际生产的 需要。调整如下： 表3 3算倒l 调整后的结果 3 0 00 00 350 3 0 00 00 600 3 0 0 00 202 0 3 0 3 1 00 1l0 3 0 l 0 01 31 0 3 0 10 000 22 4 说明：此处将小数结果均取为0 。然后增加了一根原材料，采用依次下o ， 0 ，1 ，3 ，1 的截切方案进行截切，余料为0 。为了满足总量的要求，再增加 一根原材料，从上截取3 m m 的零件2 个a 也就是说，经过人为地对结果进行调整，总共动用8 根原材料，完全消 耗7 根，最后一根原材料剩余2 4 哪，还可以继续进行截切，不算残料。 2 0 山东大学硕士学位论文 = = = = = = = = = = 竺竺= = = = = = = = = = = = = = ! != = = = = ! ：= = = = = 算例2 表3 4 算例2 的线性规划求解结果 原材料根数2 2 0 02 0 0 41 8 9 71 7 2 3 1 6 0 71 4 7 81 3 2 4 1 0 7 4 余料 2 0 0 0 01 6 0 1 661 00 0022 0 2 0 0 0 001 8 1 00 1402 033 0 2 0 0 0 00 3 0 1 510 11801 00 2 0 0 0 05 5 0 0 002 211600 0 2 0 0 0 03 0 5 4 91223 10030 2 0 0 0 04