数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名) ：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期： 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：成品料规格及所需块数序号长×宽块数序号长×宽块数1 865×857 982 857×715 983 804×746 1964 857×675 285 857×665 286 804×663 2247 804×661 308 8 804×639 849 804×631 56 10 804×563 22411 804×536 196 12 804×535 39213 804×551 392 14 865×446 9815 762×446 196 16 715×446 9817 680×446 224 18 675×446 2819 667×446 28 20 655×446 8421 647×446 56 22 667×426 30823 580×446 224 24 552×446 19625 551×446 392 26 527×426 392二、变量和符号说明（1）L：2100×1650的原材料的长；（2）W：2100×1650的原材料的宽；（3）X:15002000 的原材料的长；（4） Y ：15002000⨯的原材料的宽；（5） j W ：第j 次排列后剩余原材料的宽，j=,1,2,3,...； （6） j L ：第j 次排列后剩余原材料的长，j=1,2,3,...； （7） i l ：第i 种成品料的长，i=1，2,3, ...，26； （8） i w ：第i 种成品料的宽，i=1，2,3, (26)（9） i x ：每次排放所需第i 种成品料的个数，i x =0，1，2,3, …，i=1，2,3, …，26；（10）i n ：第i 种成品料所需的块数，i=1，2,3, …，26； （11）N ：只有一种原材料时所需的块数；（12）1N ：有两种原材料时所需16502100⨯的原材料块数； （13）2N ：有两种原材料时所需15002000⨯的原材料块数；三、 模型假设（1） 假设不考虑刀具的厚度；（2） 假设不考虑在切割板材玻璃的过程中的损耗；（3） 假设不考虑玻璃厚度的影响；（4） 假设不考虑两种原材料的优先级及成本，只考虑原材料的利用率；四、 问题分析本问题属于二维下料问题，该问题已被证明为是NP 完全问题。

由于任何NP 完全问题都不能用任何已知的多项式算法求解，所以我们建立一个排样的算法模型。

题目要求该算法首先要满足生产工艺，即要满足“一刀切”，即从板材的一端，沿直线方向切割到另一端。

从操作方便的角度考虑，一张板材上不宜下过多的零件，但一般来说，参加套裁的零件种类越多，材料的利用率越高，在实际玻璃切割中要兼顾这两方面的情况，既要考虑操作的方便，又要考虑材料的利用率，一般我们讨论零件种数最多为4种或5种的情况其次下料方案应该使原材料的利用率大，从而降低生产成本，提高经济效益。

满足上述要求，我们使用线性规划和贪婪算法相结合的思想，在保证利用率不减的情况下，尽量使零件种类减少，一边生产加工。

既然原材料有长和宽两个方向，成品料也有长和宽两个方向，则每个成品料的长可在原材料的长和宽方向上排列，宽也可在原材料的长和宽的方向上排列，这就够成了二维下料方式的多样性，当所需下料的成品料种类较多时，下料方式也就相应的比较多，这又为二维下料增加了困难。

为了克服这个困难，仅将成品料的宽在原材料的宽上排列，即在26种成品料中选择适当个数，使其宽度之和最接近原材料的宽，这样就确定了宽度方向的最优化组合。

在长度方向，采用贪婪算法的思想，在宽度确定的前提下选择能放下的最大长度进行排放。

切割后的剩余部分作为新的原材料根据上述原理继续进行优化切割方案的组合。

对于第二题有两种原材料，第二种原材料的长度和宽度都比第一种原材料略小，于是我们在第一题的切割方案中选择能被第二种原材料替换的方案进行替换，这样就更能提高原材料的利用率。

最后，根据所求第一题和第二题中原材料的种类和各种原材料所用张数，分别计算出原材料的利用率。

五、 模型的建立与求解5.1问题一模型的建立与求解（1）在26种成品料中选择适当个数，使其宽度之和最接近原材料的宽。

则目标函数为：min W-∑=261i i i x w ;s.t. W-∑=261i i i x w ≥0;i x =0,1,2, …;经过Lingo 求解,当宽为原材料的原始宽度W 时，得到最优组合为1,1,1131110===x x x ,然后按三块成品料中最长的边切割下来。

如图1所示图1（2）左边剩余部分视为一块新的原材料宽1W 长1L 。

其中，1W =L-max(131110,,l l l )，1L =W 。

将该新原材料再按照（1）中方法进行最优化排列目标函数为：min 1W -∑=261i i i x w ;1011 13s.t. 1W -∑=261i i i x w ≥0;i x =0,1,2, …;经求解得：1,195==x x ，然后按这两块成品料中最长的边切割下来。

结果如图2所示图2（3）将第二次切割剩余部分视为一块新的原材料宽2W 长2L 。

其中，2W =W-max(95,l l )，2L =1W 。

将该新原材料再按照（1）中方法进行最优化排列目标函数为：min 2W -∑=261i i i x w ;s.t. 2W -∑=261i i i x w ≥0;i x =0,1,2, …;经求解得：13=x ，然后按这块成品料中最长的边切割下来结果。

如图3所示：图3（4）第三次切割剩余的材料宽3W =31l W -=492，长=3L 2W =793,其所能放下的最10111351011 135993大成品料只有第15种。

如图4所示：综上所述，上诉切割方法可以将一块原材料（16502100⨯）切割为第3、5、9、10、11、13、15种成品料各一块。

从这七种成品料的需求块数看出，285=n 最小，所以用28块原材料按上诉方法切割。

后面的切割方法为把前面成品料除去后，将剩余的成品料按照第一种切割方法进行切割，得到其余的切割方法，直到所有需求的成品料都被切割完。

各种切割方法如下表1所示:切割方法 生产的成品料 所需原材料块数备注1 3、5、9、10、11、13、15 28生产完第5种成品料2 3、6、9、10、11、13、15 28生产完第9种成品料3 1、3、10、11、13、15、22 98生产完第1种成品料4 3、3、10、11、11、13、15 21生产完第11种成品料5 2、2、7、10、10、22、22 24所需第10种成品料只差一块6 2、7、8、8、10、22、22 1生产完第10种成品料7 2、6、8、8、12、15、22 21生产完第15种成品料8 2、6、8、8、12、16、22 20生产完第8种成品料9 6、12、12、14、16、16、22、22、22 39生产完第16种成品料 10 4、6、12、14、17、26、26、26、26、26 28生产完第4种成品料 11 6、6、12、14、17、26、26、26、26、26 24所需第6种成品料只差一块 12 6、7、12、14、17、26、26、26、26、26 1生产完第6种成品料 13 7、7、12、14、17、26、26、26、26、26 6生产完第14种成品料1011135931514 7、7、12、17、17、24、24、26、26、2632所需第26种成品料只差一块15 7、12、12、17、17、17、22、22、261生产完第22、26种成品料16 2、7、7、12、13、17、17 8 生产完第2种成品料17 7、7、7、12、13、17、17 41 生产完第17种成品料18 7、7、7、12、13、18、18 14 生产完第18种成品料19 7、7、7、12、13、19、19 8 生产完第7种成品料20 12、13、13、13、13、13、19 9 生产完第12种成品料21 13、13、13、13、13、19、19 1 所需第19种成品料只差一块22 13、13、13、13、13、19、20 1 生产完第19种成品料23 13、13、13、13、13、20、20 13 所需第20种成品料只差一块24 13、13、13、13、13、20、21 1 生产完第20种成品料25 13、13、13、13、13、21、21 4 所需第13种成品料只差一块26 13、21、21、21、21、21、21、21、211生产完第13种成品料27 21、21、21、21、21、21、21、21、21、213所需第21种成品料只差九块28 21、21、21、21、21、21、21、21、21、231生产完第21种成品料29 23、23、23、23、23、23、23、23、23、2322所需第23种成品料只差三块30 23、23、23、24、24、24、24、24、24、241生产完第23种成品料31 24、24、24、24、24、24、24、24、24、2412所需第24种成品料只差五块32 23、23、23、23、23、25、25、25、25、251生产完第24种成品料33 25、25、25、25、25、25、25、25、25、2539生产完第25种成品料所需原材料总数552表1在原材料只有一种规格的情况下（例如长为2100cm,宽1650cm ），共需552块。