板材玻璃下料问题

板材玻璃下料问题摘要排样下料问题在很多工业领域中都有广泛的应用，解决好排样问题，可以提高材料的利用率。本文解决的是玻璃板材的最优化下料策略，不同的下料策略形成不同的线性规划模型。在充分理解题意的基础上，以使用原材料张数最少为目标，采用逐级优化的方法，进行下料方案的筛选。在第一题中，首先选用单一下料两个方向排料优选的下料策略，成品料的长在原材料的长和宽两个方向上分别排列，求出最优解；其次采用单一下料中成品料的长和宽在原材料的长、宽两个方向套裁排料优选，算出所需原材料的块数和利用率；最后按照零件需求量，进行几种零件配套优选，用新易优化板材切割软件求出最优的板材切割方法，列以原材料消耗总张数最少为目标函数的数学模型，用LINGO软件编程，求出最佳下料按照原材料的利用率，筛选出最佳的下料方案为按照零件需求量，进行几种零件的配套优选下料方案，所求需要原材料的块数为548，利用率为95.03%。第二题的求解以第一题相似，当有两种规格的原材料时，在第一题的基础上，用玻璃板材切割软件排出两种原材料的最佳切割方法，建立数学模型，用LINGO软件编程，算出最佳的下料方案。求得需要规格为2100cmX1650cm的原材料532块，需要规格为2000cmX1500cm的原材料16块，共计548块，利用率为95.40%。此模型可以推广到更多板材排样下料领域的应用，通过逐级优化和组合原理，确定各种切割方式，然后再进行线性规格问题的求解。关键词：优化排样板材下料最优化线性规划一・问题重述在大型建筑工程中，需要大量使用玻璃材料，如门窗等。在作材料预算时，需要求出原材料的张数。已知板材玻璃原材料和下料后的成品料均为矩形。由于玻璃材料特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或停顿，即每切一刀均将玻璃板一分为二。切割次序和方法的不同、各种规格搭配（即下料策略）不同，材料的消耗将不同。工程实际需要解决如下问题，在给定一组材料规格尺寸后：（1） 在原材料只有一种规格的情况下（例如长为2100cm，宽1650cm）,给出最优下料策略，时所需要材料张数最少。（2） 在原材料为两种规格的情况下（例如2100cmX1650cm和2000cmX1500cm）,给出最优下料策略，使所需要材料张数最少，且利用率（实际使用总面积与原材料总面积之比）尽量高。（3） 下表是一些成品料及所需块数（长X宽X块数），分别以一种原材料2100cmX1650cm及两种原材料规格2100cmX1650cm、2000cmX1500cm为例，分别给出（1）和（2）的算法及数字结果，并给出两种情况下的利用率。表1：成品料规格及所需块数序号长X宽块数序号长X宽块数1865X857982857X715983804X7461964857X675285857X665286804X6632247804X6613088804X639849804X6315610804X56322411804X53619612804X53539213804X55139214865X4469815762X44619616715X4469817680X44622418675X4462819667X4462820655X4468421647X4465622667X42630823580X44622424552X44619625551X44639226527X426392二・模型假设1、 假设不考虑在切割板材玻璃的过程中的损耗2、 假设不考虑人为的损耗；

3、假设不考虑切割工艺的不同；4、假设不考虑玻璃厚度的影响；5、假设不考虑刀片的厚度；6、假设切割玻璃的刀片可旋转；7、假设不考虑两种原材料的优先级及成本，只考虑原材料的利用率三・符号说明符号表示意义Li规格为2100cmX1650cm的原材料的长Wi规格为2100cmX1650cm的原材料的宽L2规格为2000cmX1500cm的原材料的长W2规格为2000cmX1500cm的原材料的宽xi成品零件的长，i=l,2,……,26yi成品零件的宽，i=l,2,……,26ni所需成品料的块数，i=l,2,……,26n所需原材料的块数S11规格为2100cmX1650cm的原材料的面积S12规格为2000cmX1500cm的原材料的面积Lx1i第i个成品料的x在L方向上能被排下的个数i 1L1y.第i个成品料的y在L方向上能被排下的个数i 1Wx1i第i个成品料的x在W方向上能被排下的个数i 1Wy1i第i个成品料的y在W方向上能被排下的个数n1只有一种原材料的利用率n2有两种原材料的利用率Si第i个成品料的面积符号表示意义a组成切割矩阵的各个数值bi,j第j种切割方式下X在L方向套裁切割被排下的个数idk,j第j种切割方式下y在L方向套裁切割被排下的个数i5第j种切割方式下长度方向的余料ASj第j种切割方式下余料面积Nj第j种切割方式使用的次数Xn第n种切割方法Ni有两种规格原材料是，所需规格为2100cmX1650cm原材料的块数N2有两种规格原材料是，所需规格为2000cmX1500cm原材料的块数四■问题分析板材玻璃下料问题属于线性规划中的二维下料（板材下料），玻璃最优化切割中，原材料有两个方向（长和宽），在只有一种原材料的时候，令原材料的长为L,宽为W,零件的长为x，宽为y，i=1，2, ，26。从操作方便的角度考虑，一张板材上不宜下ii过多的零件，但一般来说，参加套裁的零件种类越多，材料的利用率越高，在实际玻璃切割中要兼顾这两方面的情况，既要考虑操作的方便，又要考虑材料的利用率，一般我们讨论零件种数最多为3种或4种的情况。而且由于玻璃材料特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或停顿，即每切一刀均将玻璃板一分为二，是一种典型的Guillotine切割，国内外对Guillotine下料问题的研究非常活跃，已取得了不少的研究结论。对剪切下料一般的处理方法有：使用背包算法以保证能实现一刀切的剪切工艺；在一张板材上只排一种规格的零件的单一下料法或只排少数几种的综合套裁法。考虑到本题的实际情况，我们使用第二种方法。当然，在保证利用率不减的情况下，所下的零件数越少越好。既然原材料有长和宽两个方向，零件也有长和宽两个方向，则每个零件的长可在原材料的长和宽方向上排列，宽也可在原材料的长和宽的方向上排列，这就够成了二维下料方式的多样性，当所需下料的零件种类较多时，下料方式也就相应的比较多，这又为二维下料增加了困难，为了克服这个困难，并考虑到采取组成最优化方案的切割方式的材料利用率都不应太低，因此采取逐级优化的方法，进行优化切割方案的筛选。对于第一题中有一种原材料的时候，有以下三种切割方案：（1） 单一下料两个方向排料优选；（2） 单一下料在长、宽两个方向套裁排料优选；（3） 按照零件需求量，进行几种成品料配套优选，选出最佳下料方案。对于第二题中有两种原材料的时候，在只考虑原材料利用率的情况下，我们选用与第一题中只有一种原材料时的第三种切割方案，即按照零件需求量，进行几种零件配套优选，选出最佳下料方案。最后，根据所求的（1）题和（2）题中原材料的数量，算出每种切割方案的利用率，选出最佳切割方案。五■模型的建立与求解下料问题模型主要有密切相关的两部分组成。第一部分为初始切割方式下的优化选取模型，第二部分为下料方案的优化模型。其中，后者是一种大型线性规划模型。问题一模型的建立与求解5.1.1单一下料两个方向排料优选对于一张原材料上仅裁一种零件（即单一下料）的切割方式，每一种零件可以排出两种单一切割方式。第一种，成品料的长在原材料长的方向上排列的下料方式；第二种，成品料的长在原材料宽的方向上排列的下料方式。（1）、单一下料两个方向排料优选数学模型如下:Lx二INT（L/x）,i=l,2,……,26；TOC\o"1-5"\h\z1i 1iLy二INT（L/y）,i=1,2,……,26；li liWx二INT（W/x）,i=1,2,……,26；1i 1iWy二INT（W/y）,i=1,2,……,26；1i 1iS=LXW1111；尹Sxnii耳=j=i x100%1Sxn ；11如第一种零件x在L方向上能排Lx=INT（L/x）=2,y在W方向上仅能排1次，11111111因此能切下第一种零件的总数是2X1=2（个）如图5.1。图5.1另一方面，x在W方向上排1次，y在L方向上能排2次，所以整块玻璃能容纳下1111以一种零件的总数是1X2=2（个）如图5.2。

图5.2图5.2两个方向切割的零件数相等，可任选一种切割方式。若切割第二个零件，情况就有所不同了，x在L方向能排2次，y在W方向上也能排2次，因此能切下第二种零件的2121另一方面，x因此能切下第二种零2121总数是2X2=4（个）如图5.3。另一方面，x因此能切下第二种零2121件的总数是1X2=2（个）如图5.4。综上可以看出，图5.3的切割方式比图5.4的切割方式的利用率要高，所以单一下料也存在比较优选的问题，称作单一下料的初级优化。同理，用Excle对26种材料做单一下料的初级优化后，得到如下的数据：长宽面积成品料所需块数每块原料切割个数所需原材料块数1865857741305982492857715612755984253804746599784196449485767557847528475857667571619284768046635330522246387804661531444308652880463951375684614

9804631507324566101080456345265222463811804536430944196633128045354301403926661380455144300439266614865446385790986171576244633985219682516715446318890988131768044630328022492518675446301050289419667446297482289420655446292130849102164744628856256972266742628414230893523580446258680224925245524462461921969222555144624574639294426527426224502392944总计729表5.5通过上述计算求得利用率为：尹SXnii耳=血 x100%=72.70%1Sxn11（2）、单一下料两个方向排料优选结果如下:通过计算解得，在原材料只有一种规格2100cmX1650cm的情况下，用单一下料两个方向排料优选的方法需要原材料729块，原材料的利用率为72.70%。5.1.2单一下料在长、宽两个方向套裁排料优选成品料在原材料L和W方向上套裁下料，x和y可以套裁。但这时应注意，在切11ii割玻璃时，每切一刀将玻璃板一分为二。数学模型与单一下料两个方向排料选优一样，用Excle对26种材料做单一下料的在长、宽两个方向套裁排料优化后，得到如下的数据:长宽面积成品料所需块数切割个数/块原材料所需原材料块数186585774130598249285771561275598425380474659978419644948576755784752856585766757161928566804663533052224638

78046615314443086528804639513756846149804631507324566101080456345265222463811804536430944196728128045354301403927561380455144300439266614865446385790986171576244633985219692216715446318890989111768044630328022410231867544630105028103196674462974822810320655446292130841092164744628856256106226674262841423081031235804462586802241121245524462461921961118255514462457463921136265274262245023921233总计670表5.6通过上述计算求得利用率为：S26Sii=1xnS26Sii=1xni—x100%=78.87%11单一下料在长、宽两个方向套裁排料优选结果如下：通过计算解得，在原材料只有一种规格2100cmX1650cm的情况下，用单一下料在长、宽两个方向套裁排料优选的方法需要原材料670块，原材料的利用率为78.87%。5.1.3按照零件需求量，进行几种成品料配套优选按照零件需求量，进行玻璃套裁下料方式的数学模型表示为;⑴'x+i,ji'i=1 i5 'x+i,ji'i=1 i5 >0.j5 <X口5j i且jSdyk,jk-mjk=m+12)k-mi=l,2, ， m；k二m+l,m+2, ,2m；（3）k-m丰i女口果b>0贝Vb 二0；如果b二0贝Vb >0；(4)i,j m+i,j i,j m+i,ja=bxWy,a=dxWx；(5)i,j i,j 1ik-m k,j 1k-m9AS=LxW-£axxxy；⑹j1 1 i,j iii=lminS二兰NAS；⑺Jjj=1gaN=D；(8)i,jj ij=1N>0且为整数；(9)j上述9个方程组成了玻璃下料问题的数学模型。我们的目的是要求出满足上述9个方程的各种切割方式的张数N。j通过“新易优化板材切割”软件，排出玻璃板材的最优切割方法，共有72种切割方案，每一种切割方案如附录中表1.0所示。建立线性规划方程组：minN=gxjj

j=1s.t.sgax>bC=1,2,…,m)s.t.si,jii戸1>0(j=1,2,…,n)整数j求得的利用率为：gSxnii耳= x100%=95.03%1Sxn11按照零件需求量，进行几种成品料配套优选结果如下：通过用LINGO软件，对上述27个线性方程进行编程求解，求得在原材料只有一种规格2100cmX1650cm的情况下，用按照零件需求量，进行几种成品料配套优选的方法需要原材料548块，原材料的利用率为95.03%。所以，通过逐级优化，筛选优化切割方案比较得出，按照零件需求量，进行几种成品料配套优选的下料策略原材料的利用率最高，为95.03%，故应采取这种下料策略，所需要原材料张数最少，为548张。问题二模型的建立与求解（1）、有两种原材料的最优下料策略的数学模型：在有两种原材料的情况下，采用与5.1.3中按照零件需求量，进行几种成品料配套优选方法同样的数学模型，只是在玻璃板材的切割方案中，增加一种原材料，用“新易优化板材切割”软件，排出两种玻璃板材的最优切割方法，建立线性规划方程组，求出所需要原材料的最少张数，根据求得的张数，求出有两种规格原材料的利用率。进行玻璃套裁下料方式的数学模型与5.1.3中的9个方程相同，这里不再重复。通过“新易优化板材切割”软件排出玻璃板材的最优切割方案，共有77种切割方案，其种72种为用规格为2100cmX1650cm的原材料，5种为用规格为2000cmX1500cm的原材料。每一种切割方案如附录中表2.0所示。建立线性规划方程组：n=N+N12minN=£xjjj=1s.t.<兰ax>b(i=1,2,…,m)s.t.<i,jii1>0(j=1,2,…,n)整数j求得的利用率为：工Sxnii耳= i= x100%=95.40%2SxN+SxN111122（2）、有两种原材料的最优下料策略的结果如下：通过用LINGO软件，对上述27个线性方程进行编程求解，求得在有两种规格2100cmX1650cm和2000cmX1500cm原材料的情况下，用按照零件需求量，进行几种成品料配套优选的方法需要规格为2100cmX1650cm的原材料532块，需要规格为2000cmX1500cm的原材料16块，总共548块，原材料的利用率为95.40%。虽然总共需要的块数与只有一种原材料时相同，但规格为2000cmX1500cm的原材料面积比规格为2100cmX1650cm的原材料小，所以原材料的利用率提高了。六■模型的结果分析本模型按照逐级优化的方法，进行下料方案的筛选。当只有一种原材料时，单一下料两个方向排料优选的下料策略需要原材料729块，原材料的利用率为72.70%；单一下料在长、宽两个方向套裁排料优选的方法需要原材料670块，原材料的利用率为78.87%；按照零件需求量，进行几种成品料配套优选的方法需要原材料548块，原材料的利用率为95.03%。故最优下料策略是最后一种，需要规格为2100cmX1650cm的原材料548块。在有两种规格2100cmX1650cm和2000cmX1500cm原材料的情况下，需要规格为2100cmX1650cm的原材料532块，需要规格为2000cmX1500cm的原材料16块，总共548块，原材料的利用率为95.40%。不论是只有一种原材料，还是有两种原材料，所求得的利用率基本都是目前最高的，是一种比较好的最优下料策略。七■模型的评价与补充7.1模型的评价显然，本文主要采用逐级优化的方法，对玻璃板材的最优下料策略进行分析计算的方法是基本成功的。事实上，对于一般的二维下料（板材下料）问题，初始切割方式的确定是下料问题中至关重要的内容，如果确定了最优的切割方式，就可以把下料问题化成一个线性规划问题，也就是要求自动生成线性规划方程的系数矩阵，编程进行计算求解。7.1.1模型的优点通过逐级优化的方法，在分析各种不同切割方式的情况下，对下料方案进行比较筛选，可以选出最优的下料策略。模型的缺点本模型的最大缺点是计算量太大，按照排列组合原理，一次套裁3种零件的切割方式有8种，所以，3个零件的套裁组合方式共有：Ci+[Ci+CixCi+C2]+[C3+C2+Ci+Co]=23（种）3 3 3 2 3 3 3 3 3同理，4种零件的套裁组合方式共有76种。所以，当所要剪切的零件数较多时，计算量太大。7.2模型的补充如果考虑到其他Guillotine切割的方法，如用遗传学算法。遗传学算法有几个优点，建模简单；计算量相对的小，可得到近似最优的可行解；材料的利用率高。在实际应用时，可根据具体问题的特点，先用基因遗传算法确定较有前途的若干下料方法，再自动借用常用模型及其算法，确定以这几种方法为基础最优下料方案。去两种模型之长，避其之短，可能会得到更好的结果。八•模型的改进和推广优化下料，提高材料的利用率，是国内外非常活跃的研究课题。而板材玻璃的下料问题是一类最常见的二维下料问题，就是把一定数量的大矩形板切割成所需要的各种规格大小和数量的小矩形，钢板，木板等的剪切下料也属于此类下料问题。因此，本模型可以推广到钢板，木板等的下料问题。参考文献吴建国.数学建模案例精编•北京：中国水利水电出版社，2005杨振东•基于数控的玻璃最优化切割的研究[D].山东：山东科技大学机械电子工程，2003吴杰君•板材下料优化排样系统研究与实现[D].合肥：合肥工业大学机械电子工程，2004袁忠良，王秀平•板材合理下料[J].天津大学学报，1995,28（4）.蔡正军，龚坚，刘飞•板材优化下料的数学模型的研究[J].重庆大学学报（自然科学版），1996,19（2）.王秋萍•数学建模讲义[J].西安理工大学，2009.附录

表1.02、求解一种玻璃套裁下料的LINGO程序min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x46+x47+x48+x49+x50+x51+x52+x53+x54+x56+x57+x58+x59+x60+x61+x62+x63+x64+x65+x66+x67+x68+x69+x70+x71+x72;x20+x29+x35+x43+x51+x56+x58+x59+x60+x72>=98;x16+2*x27+x48+x51+x56+2*x57+x59>=98;2*x3+2*x7+x12+2*x13+2*x25+2*x27+2*x19+2*x25+2*x27+2*x28+2*x32+2*x34+2*x36+2*x39+2*x43+2*x46+x49+2*x50+2*x51+x55+2*x58+x59+x60+x68>=196;2*x3+3*x50+4*x55+3*x67>=28;x2+2*x13+2*x25+x32>=28;x10+2*x16+2*x20+2*x29+2*x38+2*x39+2*x45+x47+x49+2*x62+4*x65+x72>=224;x2+2*x4+2*x6+x10+2*x14+2*x21+2*x30+4*x34+2*x37+x39+2*x40+2*x42+x46+x47+x49+2*x52+2*X56+2*x57+2*x61+2*x67>=308;4*x9+4*x11+2*x22+2*x24+x39+x59>=84;2*x10+2*x31+2*x35+2*x65>=56;x7+x11+2*x16+2*x22+x23+2*x29+2*x31+2*x62+x72>=224;2*x2+2*x4+2*x7+2*x11+3*x12+2*x18+4*x19+2*x20+2*x21+3*x23+2*x24+2*x30+x36+2*x37+2*x53>=196;2*x6+2*x7+x9+3*x10+x14+x19+2*x26+x44+x45+3*x46+x47+3*x48+4*x54+x59+4*x63+2*x64>=392;6*x1+6*x5+6*x8+2*x9+2*x18+2*x23+4*x26+6*x33+2*x35+6*x41+2*x44+4*x45+4*x47+3*x49+2*x70>=392;x1+2*x4+2*x6+2*x15+2*x16+3*x17+x24+x33+x43+x52>=98;x1+3*x3+2*x4+2*x6+3*x13+2+x17+2*x20+2*x25+x29+2*x35+3*x38+3*x40+x41+3*x42+2*x51+x66+2*x72>=196;x12+x15+x17+x25+x27+x28+3*x32+x42+3*x43+2*x52+5*x68+x71>=98;3*x21+3*x22+6*x28+3*x31+2*x32+3*x37+6*x62+10*x69>=224;x14+x41+x50+3*x57+x62+7*x66>=28;3*x14+2*x27>=28;3*x52+x61+4*x64+3*x68>=84;4*x12+2*x15+x21+x24+x33+x67+x71+x72>=56;4*x18+x29+x42+3*x44+3*x48+4*x53+x55+x59+3*x60+2*x70>=308;x22+x26+x31+x36+x37+4*x54+3*x56+x58+x62+x63>=224;3*x2+2*x5+2*x15+x22+x31+x46+x49+x52+4*x70>=196;2*x8+x18+2*x23+3*x24+3*x30+4*x36+2*x44+2*x48+4*x53+4*x58+4*x60+3*x63+2*x70+9*x71>=392;3*x2+x5+x8+3*x14+x18+x21+x23+2*x26+3*x30+2*x36+x37+x53+2*x54+2*x63+x64+3*x66>=392;3、有两种原材料时，进行玻璃套裁下料的77种最优切割方案如表2.0

表2.04、有两种原材料时，求解玻璃套裁下料的LINGO程序min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x46+x47+x48+x49+x50+x51+x52+x53+x54+x56+x57+x58+x59+x60+x61+x62+x63+x64+x65+x66+x67+x68+x69+x70+x71+x72+x73+x74+x75+x76+x77;x5+x8+x9+x13+x29+x37+x49+x51+x60+x61+x65+x67+x70+2*x72>=98;x5+x8+x9+2*x44+2*x46+x49+x51+x60+2*x63+x77>=98;2*x4+2*x14+2*x17+2*x20+2*x28+x30+2*x32+2*x36+2*x37+2*x38+2*x40+x49+x51+2*x54+x70+x72>=196;2*x4+x37+x67>=28;2*x17+2*x28+x64+3*x69+2*x74>=28;2*x1+x5+x8+x11+x15+2*x24+2*x27+2*x31+x41+2*x44+2*x45+x48+2*x50+x57+6*x58+3*x59+x62+2*x63+2*x67+2*x69>=224;x9+x11+2*x12+2*x13+x15+2*x30+2*x35+4*x36+4*x40+x41+2*x46+x48+2*x52+x57+3*x57+2*x60+5*x62+2*x66+x77>=308;4*x10+x15+x16+x18+x21+2*x25+2*x39+2*x47+x53+x66+x72>=84;2*x1+2*x15+x18+2*x19+x21+2*x29+2*x34+x53>=56;x1+2*x3+x10+2*x16+2*x19+2*x22+2*x25+2*x26+2*x29+