板材玻璃下料问题

板材玻璃下料问题 数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料)，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是(从A/B/C/D中选择一项填写): B 我们的参赛报名号为(如果赛区设置报名号的话): 所属学校(请填写完整的全名): 参赛队员 (打印并签名) :1. 指导教师或指导教师组负责人 (打印并签名): 日期: 2011 年 7 月 18 日 赛区评阅编号(由赛区组委会评阅前进行编号): 2009高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号(由赛区组委会评阅前进行编号): 全国统一编号(由赛区组委会送交全国前编号): 全国评阅编 号(由全国组委会评阅前进行编号): 摘要 在工业生产和日常生活中，由于节省原材料和避免工业损失的需要，经常会遇到下料问题。所谓下料问题，就是指在给定板材宽度和长度的情况下，如何将具有一定种类和数量的矩形件排放到板材上，使需要的板材数量最少，该问题广泛存在于的工业生产中。解决好下料问题可以提高材料的利用率，使原材料得到最大化利用。本文解决的是玻璃板材的最优化下料问题，在一刀切的约束条件下，借助Lingo软件，利用贪婪算法和线性规划相结合的思想，采用逐级优化进行下料的筛选。 对于问题一，我们用离散数学中的线性规划首先建立了整数规划模型，即在原材料的宽度方向上选择成品料宽度的线性组合使得原材料的宽度得到最大化利用，可用Lingo求出这个最优组合。在原材料的长度方向上，利用贪婪算法的思想，在确定成品料宽度的前提下使长度方向利用率最大，即可确定此次的切割方案，余下的部分玻璃又作为新的原材料继续切割。按照这种思想，根据每种原材料的的需求量，进行成品料的配套优化下料方案，求得需要规格为2100×1650cm的原材料552张，利用率为94.33,. 对于问题二，采用了和问题一相似的解法。在第一题排列方案不变的基础上，选择能用第二种原材料替换的配套方案进行原材料的替换。经计算，52张2100×1650cm规格的原材料可用2000×1500cm代替。有两种 原材料时，需要2100×1650cm规格的玻璃共500张，需要2000×1500cm规格的玻璃52张，利用率为95.54 ,. 此模型在原材料的宽度方向运用了线性规划模型，在宽度方向上加入了贪婪算法的思想，通过逐级优化和组合原理确定切割方案，使原材料的利用率最大化，可推广到更多板材排样领域的应用。 关键词:二维下料问题 线性规划 贪婪算法 Lingo 一、 问题重述 在大型建筑工程中，需要大量使用玻璃材料，如门窗等。在作材料预算时， 需要求出原材料的张数。 已知板材玻璃原材料和下料后的成品料均为矩形。由于玻璃材料特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或停顿，即每切一刀均将玻璃板一分为二。切割次序和方法的不同、各种规格搭配(即下料策略)不同，材料的消耗将不同。工程实际需要解决如下问题，在给定一组材料规格尺寸后: (1)在原材料只有一种规格的情况下(例如长为2100cm,宽1650cm)，给出最优下料策略，时所需要材料张数最少。 (2)在原材料为两种规格的情况下(例如2100cm×1650cm和2000cm×1500cm)，给出最优下料策略，使所需要材料张数最少，且利用率(实际使用总面积与原材料总面积之比)尽量高。 (3)下表是一些成品料及所需块数(长×宽×块数)，分别以一种原材料2100cm×1650cm及两种原材料规格2100cm×1650cm、2000cm× 1500cm为例，分别给出(1)和(2)的算法及数字结果，并给出两种情况下的利用率。 二、 变量和符号说明 (1) L:2100×1650的原材料的长; (2) W:2100×1650的原材料的宽; (3) X:2000?1500的原材料的长; (4) Y:2000?1500的原材料的宽; (5) Wj:第j次排列后剩余原材料的宽，j=,1,2,3,„; (6) Lj:第j次排列后剩余原材料的长，j=1,2,3,„; (7) li:第i种成品料的长，i=1，2,3, „，26; (8) wi:第i种成品料的宽，i=1，2,3, „，26; (9) xi:每次排放所需第i种成品料的个数，xi=0，1，2,3, „，i=1，2,3, „， 26; (10)ni:第i种成品料所需的块数，i=1，2,3, „，26; (11)N:只有一种原材料时所需的块数; (12)N1:有两种原材料时所需2100?1650的原材料块数; (13)N2:有两种原材料时所需2000?1500的原材料块数; 三、 模型假设 (1) 假设不考虑刀具的厚度; (2) 假设不考虑在切割板材玻璃的过程中的损耗; (3) 假设不考虑玻璃厚度的影响; (4) 假设不考虑两种原材料的优先级及成本，只考虑原材料的利用率; 四、 问题分析 本问题属于二维下料问题，该问题已被证明为是NP完全问题。由于任何NP完全问题都不能用任何已知的多项式算法求解，所以我们建立一个排样的算法模型。题目要求该算法首先要满足生产工艺，即要满足“一刀切”，即从板材的一端，沿直线方向切割到另一端。从操作方便的角度考虑，一张板材上不宜下过多的零件，但一般来说，参加套裁的零件种类越多，材料的利用率越高，在实际玻璃切割中要兼顾这两方面的情况，既要考虑操作的方便，又要考虑材料的利用率，一般我们讨论零件种数最多为4种或5种的情况其次下料方案应该使原材料的利用率大，从而降低生产成本，提高经济效益。满足上述要求，我们使用线性规划和贪婪算法相结合的思想，在保证利用率不减的情况下，尽量使零件种类减少，一边生产加工。 既然原材料有长和宽两个方向，成品料也有长和宽两个方向，则每个成品料的长可在原材料的长和宽方向上排列，宽也可在原材料的长和宽的方向上排列，这就够成了二维下料方式的多样性，当所需下料的成品料种类较多时，下料方式也就相应的比较多，这又为二维下料增加了困难。为了克服这个困难，仅将成品料的宽在原材料的宽上排列，即在26种成品料中选择适当个数，使其宽度之和最接近原材料的宽，这样就确定了宽度方向的最优化组合。在长度方向，采用贪婪算法的思想，在宽度确定的前提下选择能放下的最大长度进行排放。切割后的 剩余部分作为新的原材料根据上述原理继续进行优化切割方案的组合。 对于第二题有两种原材料，第二种原材料的长度和宽度都比第一种原材料略小，于是我们在第一题的切割方案中选择能被第二种原材料替换的方案进行替换，这样就更能提高原材料的利用率。 最后，根据所求第一题和第二题中原材料的种类和各种原材料所用张数，分别计算出原材料的利用率。 五、 模型的建立与求解 5.1问题一模型的建立与求解 (1)在26种成品料中选择适当个数，使其宽度之和最接近原材料的宽。则目标函数为: 26 min W-?wixi; i?126 s.t. W-?wixi?0; i?1 xi=0,1,2, ?; 经过Lingo求解,当宽为原材料的原始宽度W时，得到最优组合为 x10?1,x11?1,x13?1,然后按三块成品料中最长的边切割下来。 如图1所示 图1 W1=L-max(l10,l11,l13)， (2)左边剩余部分视为一块新的原材料宽 W1长L1。其中，L1=W。将该新原材料再按照(1)中方法进行最优化排列目标函数为: 26 min W1-?wixi; i?1 s.t. W1-?wixi?0; i?126 xi=0,1,2, …; 经求解得:x5?1,x9?1，然后按这两块成品料中最长的边切割下来。结果 如图2所示 图2 (3)将第二次切割剩余部分视为一块新的原材料宽W2长L2。其中，W2=W-max(l5,l9)，L2=W1。将该新原材料再按照(1)中方法进行最优化排列目 标函数为: 26 min W2-?wixi; i?1 26 s.t. W2-?wixi?0; i?1 xi=0,1,2, …; 经求解得:x3?1，然后按这块成品料中最长的边切割下来结果。如图3所示: 图3 (4)第三次切割剩余的材料宽W3=W1?l3=492，长L3?W2=793,其所能放下的最 大成品料只有第15种。如图4所示: 综上所述，上诉切割方法可以将一块原材料(2100?1650)切割为第3、5、9、10、11、13、15种成品料各一块。从这七种成品料的需求块数看出，n5?28最小，所以用28块原材料按上诉方法切割。后面的切割方法为把前面成品料除去后，将剩余的成品料按照第一种切割方法进行切割，得到其余的切割方法，直到所有需求的成品料都被切割完。各种切割方法如下表1所示: 在原材料只有一种规格的情况下(例如长为2100cm,宽1650cm)，共需55226 块。利用率?1??nwii?1iilNWL?100%=94.33%。 5.2问题二的模型与建立 问题二与问题一的不同之处为多了一种原材料规格为2000?1500。如果问题一中的原材料所利用的长的最大值小于等于2000且宽所利用的最大值小于等于1500，则可以用规格为2000?1500的原材料代替2100?1650的原材料。经过计算，只有用第31、32、33种方法切割的2100?1650的原材料可以被2000?1500的原材料代替，以提高利用率。故所需2100?1650 的原材料块数为N1?500，2100?1650 26的原材料块数为N2?52块。原材料的利用率 ?nwliii ?2?i?1N1LW?N2XY?100%?95.54%。 六、模型的评价与推广 6.1模型的评价 6.1.1模型的优点 该模型结合整数线性规划和贪婪算法，在宽度方向上用线性规划方法解除最佳排列方式，在长度方向上用贪婪算法的思想使长度得到最大化利用，从而提高了原材料的利用率。该模型通俗易懂，得到的利用率较高 。 6.1.2 模型的缺点 该模型只主要考虑成品料的宽在原材料的宽上排列，忽略了其他的可能排列方式。由此得到33种切割方法，使得计算量较大。 6.2模型的推广 该模型不仅仅可以用于玻璃的下料，还可以推广到其他类似与玻璃切割的二维下料，例如:钢材、木材。 七、参考文献 [1]赫孝良，戴永红，周义仓.数学建模竞赛赛题简析与论文点评[M].西安:西安交通大学出版社，2002. [2]刘仁云等著.数学建模方法与数学实验[M].北京:中国水利水电出版社,2011. [3]张克，林家恒.二维下料问题的研究进展[R].山东:山东大学. [4]蔡正军，龚坚，刘飞.板材优化下料的数学模型的研究[R].重庆:重庆大学. [5]杨振东.基于数控的玻璃最优化切割的研究[D].山东:山东科技大学机械电子工程，2003.