《板材玻璃下料问题》由会员分享，可在线阅读，更多相关《板材玻璃下料问题（10页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置
2、报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年 7 月 18 日赛区评阅编号（由赛区组委会评阅前进行编号）：2009高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：板材玻璃下料问题摘要在工业生产和日常生活中，由于节省原材料和避免工业损失的需要，经常会遇到下料问题。所谓下料问题，就是指在给定板材宽度和长度
3、的情况下，如何将具有一定种类和数量的矩形件排放到板材上，使需要的板材数量最少，该问题广泛存在于的工业生产中。解决好下料问题可以提高材料的利用率，使原材料得到最大化利用。本文解决的是玻璃板材的最优化下料问题，在一刀切的约束条件下，借助Lingo软件，利用贪婪算法和线性规划相结合的思想，采用逐级优化进行下料方案的筛选。对于问题一，我们用离散数学中的线性规划首先建立了整数规划模型，即在原材料的宽度方向上选择成品料宽度的线性组合使得原材料的宽度得到最大化利用，可用Lingo求出这个最优组合。在原材料的长度方向上，利用贪婪算法的思想，在确定成品料宽度的前提下使长度方向利用率最大，即可确定此次的切割方案，
4、余下的部分玻璃又作为新的原材料继续切割。按照这种思想，根据每种原材料的的需求量，进行成品料的配套优化下料方案，求得需要规格为21001650cm的原材料552张，利用率为94.33.对于问题二，采用了和问题一相似的解法。在第一题排列方案不变的基础上，选择能用第二种原材料替换的配套方案进行原材料的替换。经计算，52张21001650cm规格的原材料可用20001500cm代替。有两种原材料时，需要21001650cm规格的玻璃共500张，需要20001500cm规格的玻璃52张，利用率为95.54 . 此模型在原材料的宽度方向运用了线性规划模型，在宽度方向上加入了贪婪算法的思想，通过逐级优化和组
5、合原理确定切割方案，使原材料的利用率最大化，可推广到更多板材排样领域的应用。关键词：二维下料问题 线性规划 贪婪算法 Lingo 一、 问题重述在大型建筑工程中，需要大量使用玻璃材料，如门窗等。在作材料预算时，需要求出原材料的张数。已知板材玻璃原材料和下料后的成品料均为矩形。由于玻璃材料特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或停顿，即每切一刀均将玻璃板一分为二。切割次序和方法的不同、各种规格搭配（即下料策略）不同，材料的消耗将不同。工程实际需要解决如下问题，在给定一组材料规格尺寸后：（1）在原材料只有一种规格的情况下（例如长为2100cm,宽1650cm），给出最优下料策略，时所需要
6、材料张数最少。（2）在原材料为两种规格的情况下（例如2100cm1650cm和2000cm1500cm），给出最优下料策略，使所需要材料张数最少，且利用率（实际使用总面积与原材料总面积之比）尽量高。（3）下表是一些成品料及所需块数（长宽块数），分别以一种原材料2100cm1650cm及两种原材料规格2100cm1650cm、2000cm1500cm为例，分别给出(1)和（2）的算法及数字结果，并给出两种情况下的利用率。表1：成品料规格及所需块数序号长宽块数序号长宽块数1865857982857715983804746196485767528585766528680466322478046613
7、088804639849804631561080456322411804536196128045353921380455139214865446981576244619616715446981768044622418675446281966744628206554468421647446562266742630823580446224245524461962555144639226527426392二、 变量和符号说明（1） L：21001650的原材料的长；（2） W：21001650的原材料的宽；（3） X:的原材料的长；（4） Y：的原材料的宽；（5） ：第j次排列后剩余原材料的宽，j=
8、,1,2,3,；（6） ：第j次排列后剩余原材料的长，j=1,2,3,；（7） ：第i种成品料的长，i=1，2,3, ，26；（8） ：第i种成品料的宽，i=1，2,3, ，26；（9） ：每次排放所需第i种成品料的个数，=0，1，2,3, ，i=1，2,3, ，26；（10） ：第i种成品料所需的块数，i=1，2,3, ，26；（11） N：只有一种原材料时所需的块数；（12） ：有两种原材料时所需的原材料块数；（13） ：有两种原材料时所需的原材料块数；三、 模型假设（1） 假设不考虑刀具的厚度；（2） 假设不考虑在切割板材玻璃的过程中的损耗；（3） 假设不考虑玻璃厚度的影响；（4） 假设
9、不考虑两种原材料的优先级及成本，只考虑原材料的利用率；四、 问题分析本问题属于二维下料问题，该问题已被证明为是NP完全问题。由于任何NP完全问题都不能用任何已知的多项式算法求解，所以我们建立一个排样的算法模型。题目要求该算法首先要满足生产工艺，即要满足“一刀切”，即从板材的一端，沿直线方向切割到另一端。从操作方便的角度考虑，一张板材上不宜下过多的零件，但一般来说，参加套裁的零件种类越多，材料的利用率越高，在实际玻璃切割中要兼顾这两方面的情况，既要考虑操作的方便，又要考虑材料的利用率，一般我们讨论零件种数最多为4种或5种的情况其次下料方案应该使原材料的利用率大，从而降低生产成本，提高经济效益。满
10、足上述要求，我们使用线性规划和贪婪算法相结合的思想，在保证利用率不减的情况下，尽量使零件种类减少，一边生产加工。既然原材料有长和宽两个方向，成品料也有长和宽两个方向，则每个成品料的长可在原材料的长和宽方向上排列，宽也可在原材料的长和宽的方向上排列，这就够成了二维下料方式的多样性，当所需下料的成品料种类较多时，下料方式也就相应的比较多，这又为二维下料增加了困难。为了克服这个困难，仅将成品料的宽在原材料的宽上排列，即在26种成品料中选择适当个数，使其宽度之和最接近原材料的宽，这样就确定了宽度方向的最优化组合。在长度方向，采用贪婪算法的思想，在宽度确定的前提下选择能放下的最大长度进行排放。切割后的剩
11、余部分作为新的原材料根据上述原理继续进行优化切割方案的组合。对于第二题有两种原材料，第二种原材料的长度和宽度都比第一种原材料略小，于是我们在第一题的切割方案中选择能被第二种原材料替换的方案进行替换，这样就更能提高原材料的利用率。最后，根据所求第一题和第二题中原材料的种类和各种原材料所用张数，分别计算出原材料的利用率。 五、 模型的建立与求解5.1问题一模型的建立与求解 （1）在26种成品料中选择适当个数，使其宽度之和最接近原材料的宽。则目标函数为： min W-;s.t. W-0;=0,1,2, ;经过Lingo求解,当宽为原材料的原始宽度W时，得到最优组合为,然后按三块成品料中最长的边切割下
12、来。如图1所示 101113 图1 （2）左边剩余部分视为一块新的原材料宽长。其中，=L-max()，=W。将该新原材料再按照（1）中方法进行最优化排列目标函数为：min -;s.t. -0;=0,1,2, ; 经求解得：，然后按这两块成品料中最长的边切割下来。结果如图2所示91011135 图2（3） 将第二次切割剩余部分视为一块新的原材料宽长。其中，=W-max()，=。将该新原材料再按照（1）中方法进行最优化排列目标函数为：min -;s.t. -0;=0,1,2, ;经求解得：，然后按这块成品料中最长的边切割下来结果。如图3所示：391011135 图3（4） 第三次切割剩余的材料宽=
13、492，长=793,其所能放下的最大成品料只有第15种。如图4所示：91531011135 综上所述，上诉切割方法可以将一块原材料（）切割为第3、5、9、10、11、13、15种成品料各一块。从这七种成品料的需求块数看出，最小，所以用块原材料按上诉方法切割。后面的切割方法为把前面成品料除去后，将剩余的成品料按照第一种切割方法进行切割，得到其余的切割方法，直到所有需求的成品料都被切割完。各种切割方法如下表1所示:切割方法生产的成品料所需原材料块数备注13、5、9、10、11、13、1528生产完第5种成品料23、6、9、10、11、13、1528生产完第9种成品料31、3、10、11、13、15、2298生产完第1种成品料43、3、10、11、11、13、1521生
