数学建模-装箱设计及板材玻璃下料问题

...wd......wd......wd...数学建模〔一〕、装箱设计问题〔二〕、板材玻璃下料问题组员：日期：板材玻璃下料问题摘要该问题属于优化问题中的排样问题。排样下料问题在很多工业领域中都有广泛的应用，解决好排样问题，可以提高材料的利用率。本文解决的是玻璃板材的最优化下料策略，不同的下料策略形成不同的线性规划模型。在充分理解题意的根基上，以使用原材料张数最少、材料利用率最高为目标，采用逐级优化的方法，进展下料方案的筛选。在第一题中，对每块原材料进展两个层次的切割。首先按照零件需求量选用由大面积到小面积下料的两个方向排料优选的下料策略，成品料的长在原材料的长和宽两个方向上分别排列，求出最优解；其次采用由大面积到小面积下料中成品料的长和宽在原材料的长、宽两个方向套裁排料优选，而对每次切割的余料按同种方法再进展一次切割。算出所需原材料的块数和利用率，求出最正确下料方案。按照原材料的利用率，筛选出最正确的下料方案为按照零件需求量，进展几种零件的配套优选下料方案，所选方案是原材料的长对成品的宽，所求需要原材料的块数为579，利用率为95.03%。第二题的求解以第一题相似，当有两种规格的原材料时，在第一题的根基上，通过控制第一种规格原材料的根基上，来选取两种材料的最正确组合。求得需要规格为2100cm×1650cm的原材料447块，需要规格为2000cm×1500cm的原材料146块，共计593块，利用率为96.48%。此模型可以推广到更多板材排样下料领域的应用，通过逐级优化和组合原理，确定各种切割方式，然后再进展优化问题的求解。关键词：优化排样板材下料最优化一·问题重述在大型建筑工程中，需要大量使用玻璃材料，如门窗等。在作材料预算时，需要求出原材料的张数。板材玻璃原材料和下料后的成品料均为矩形。由于玻璃材料特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或停顿，即每切一刀均将玻璃板一分为二。切割次序和方法的不同、各种规格搭配〔即下料策略〕不同，材料的消耗将不同。工程实际需要解决如下问题，在给定一组材料规格尺寸后：〔1〕在原材料只有一种规格的情况下〔例如长为2100cm,宽1650cm〕，给出最优下料策略，时所需要材料张数最少。〔2〕在原材料为两种规格的情况下〔例如2100cm×1650cm和2000cm×1500cm〕，给出最优下料策略，使所需要材料张数最少，且利用率〔实际使用总面积与原材料总面积之比〕尽量高。〔3〕下表是一些成品料及所需块数〔长×宽×块数〕，分别以一种原材料2100cm×1650cm及两种原材料规格2100cm×1650cm、2000cm×1500cm为例，分别给出(1)和〔2〕的算法及数字结果，并给出两种情况下的利用率。表1：成品料规格及所需块数序号长×宽块数序号长×宽块数1865×857982857×715983804×7461964857×675285857×665286804×6632247804×6613088804×639849804×6315610804×56322411804×53619612804×53539213804×55139214865×4469815762×44619616715×4469817680×44622418675×4462819667×4462820655×4468421647×4465622667×42630823580×44622424552×44619625551×44639226527×426392二·模型假设假设不考虑在切割板材玻璃的过程中的损耗；假设不考虑人为的损耗；假设不考虑切割工艺的不同；假设不考虑玻璃厚度的影响；假设不考虑刀片的厚度；假设不考虑两种原材料的优先级及成本，只考虑原材料的利用率；三·符号说明符号表示意义m当前原材料的长e当前原材料的宽l(i)成品零件的长，i=1，2，……，26w(i)成品零件的宽，i=1，2，……，26n(i)所需成品料的块数，i=1，2，……，26S1规格为2100cm×1650cm的原材料的面积S2规格为2000cm×1500cm的原材料的面积当前原材料的利用率两种原材料的利用率si第j种切割方式下余料面积zhang有两种规格原材料是，所需规格为2100cm×1650cm原材料的块数zhang1有两种规格原材料是，所需规格为2000cm×1500cm原材料的块数N(i)第i种切割方式使用的次数U有两种规格原材料是，所需总原材料的块数S所需成品料的总面积四·问题分析板材玻璃下料问题属于线性规划中的二维下料〔板材下料〕，玻璃最优化切割中，原材料有两个方向〔长和宽〕，在只有一种原材料的时候，令原材料的长为m，宽为l，零件的长为l(i),宽为w(i)，i=1，2,……，26。从操作方便的角度考虑，一张板材上不宜下过多的零件，但一般来说，参加套裁的零件种类越多，材料的利用率越高，在实际玻璃切割中要兼顾这两方面的情况，既要考虑操作的方便，又要考虑材料的利用率，一般我们讨论零件种数最多为3种的情况。而且由于玻璃材料特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或停顿，即每切一刀均将玻璃板一分为二.在一张板材上可排少数几种的综合套裁法。既然原材料有长和宽两个方向，零件也有长和宽两个方向，则每个零件的长可在原材料的长和宽方向上排列，宽也可在原材料的长和宽的方向上排列，这就够成了二维下料方式的多样性，当所需下料的零件种类较多时，下料方式也就相应的对比多，这又为二维下料增加了困难，为了抑制这个困难，并考虑到采取组成最优化方案的切割方式的材料利用率都不应太低，因此采取逐级优化的方法，进展优化切割方案的筛选。对于第一题中有一种原材料的时候，有以下三种切割方案：第一层次按单一下料成品长对应原材料长，第二层次对余料切割按单一下料在长、宽两个方向套裁排料优选。第一层次按单一下料成品宽对应原材料长，第二层次对余料切割按单一下料在长、宽两个方向套裁排料优选。第一层次按单一下料在长、宽两个方向套裁排料优选，进展几种成品料配套优选，选出最正确下料方案。对于第二题中有两种原材料的时候，在考虑原材料利用率的情况下，我们选用第一题中利用率较高的切割方案，即按照零件需求量，进展几种零件配套优选，选出最正确下料方案。最后，根据所求的〔1〕题和〔2〕题中原材料的数量，算出每种切割方案的利用率，选出最正确切割方案。五·模型的建设与求解下料问题模型主要有密切相关的两局部组成。第一局部为初始切割方式下的优化选取模型，第二局部为下料方案的优化选取。5.1问题一模型的建设与求解5.1.1第一层次按单一下料成品长对应原材料长，第二层次对余料切割按单一下料在长、宽两个方向套裁排料优选。对于一张原材料上仅裁一种零件〔即单一下料〕的切割方式，每一种零件可以排出两种单一切割方式。第一种，成品料的长在原材料长的方向上排列的下料方式；第二种，成品料的长在原材料宽的方向上排列的下料方式。〔1〕、单一下料长对长排料优选数学模型如下:n(i)=n(i)-INT((m/l(i))*(e/w(i)))，i=1，2，……，26；=max(Internet(e/l(i))*Internet(2100/w(i))*l(i)*w(i)/210/e,fix(e/w(i))*fix(2100/l(i))*l(i)*w(i)/210/e)>s〔i〕)Zhang=N(i)如第一种零件l(1)在m方向上能排2次，w(1)在e方向上仅能排1次，因此下第一种零件经这次切割之后所需的总数是n(1)=98-2=96，如图5.1。同样对剩余两块余料再进展一次类似的切割，切割的零件种类图5.1〔2〕、由matlab编程求解可得单一下料长对长排料优选结果如下:通过计算解得，在原材料只有一种规格2100cm×1650cm的情况下，用单一下料两个方向排料优选的方法需要原材料602块，原材料的利用率为数据%。5.1.2第一层次按单一下料成品宽对应原材料长，第二层次对余料切割按单一下料在长、宽两个方向套裁排料优选单一下料宽对长排料优选数学模型如下:n(i)=n(i)-int((m/w(i))*(e/l(i)))，i=1，2，……，26；=max(int(e/w(i))*int(2100/l(i))*l(i)*w(i)/210/e,int(e/l(i))*int(2100/w(i))*l(i)*w(i)/210/e)>s〔i〕)Zhang=N(i)如第一种零件l(1)在e方向上能排2次，w(1)在m方向上仅能排1次，因此下第一种零件经这次切割之后所需的总数是n(1)=98-2=96，如图5.2。同样对剩余两块余料再进展一次类似的切割，切割的零件种类。图5.1单一下料在长、宽两个方向套裁排料优选结果如下：通过计算解得，在原材料只有一种规格2100cm×1650cm的情况下，用单一下料在长、宽两个方向套裁排料优选的方法需要原材料579块，原材料的利用率为78.87%。5.1.3第一层次按单一下料在长、宽两个方向套裁排料优选，进展几种成品料配套优选，选出最正确下料方案。按照零件需求量，进展玻璃套裁下料方式的数学模型表示为：n(i)=n(i)-int((m/w(i))*(e/l(i)))，i=1，2，……，26；=max(int(e/w(i))*int(2100/l(i))*l(i)*w(i)/210/e,int(e/l(i))*int(2100/w(i))*l(i)*w(i)/210/e)>s〔i〕),i=1、2、3……26Zhang=N(i)按照零件需求量，进展几种成品料配套优选结果如下：通过matlab软件，对上述方程进展编程求解，求得在原材料只有一种规格2100cm×1650cm的情况下，用按照零件需求量，进展几种成品料配套优选的方法需要原材料595块，原材料的利用率为95.03%。所以，通过逐级优化，筛选优化切割方案对比得出，按照零件需求量，进展几种成品料配套优选的下料策略原材料的利用率最高，为95.03%，故应采取这种下料策略，所需要原材料张数最少，为579张。5.2问题二模型的建设与求解〔1〕、有两种原材料的最优下料策略的数学模型：在有两种原材料的情况下，采用与5.1.2中按照零件需求量，进展几种成品料配套优选方法同样的数学模型，只是在玻璃板材的切割方案中，增加一种原材料，单一下料宽对长排料优选数学模型如下:当第一种原材料用了K(K≤579)张时，各种成品所需还需块数：n(i)=n(i)-int((m/w(i))*(e/l(i)))，i=1，2，……，26；对个成品还需的块数n(i),用第二种原材料切割。用同样方法可求得需zhang1张。=max(S/〔K*S1+zhang1*S2〕),即可求出K和zhang1的最正确组合。〔K不同时原材料利用率见附录1〕〔2〕、有两种原材料的最优下料策略的结果如下：通过用matlab软件求解，求得在有两种规格2100cm×1650cm和2000cm×1500cm原材料的情况下，用按照零件需求量，进展几种成品料配套优选的方法需要规格为2100cm×1650cm的原材料447，需要规格为2000cm×1500cm的原材料146块，总共594，原材料的利用率为90.81%。虽然总共需要的块数比只有一种原材料大，但规格为2000cm×1500cm的原材料面积比规格为2100cm×1650cm的原材料小，所以原材料的利用率提高了。六·模型的结果分析本模型按照逐级优化的方法，进展下料方案的筛选。当只有一种原材料时，单一下料长对长排料优选的下料策略需要原材料602块，原材料的利用率为72.70%；单一下料在宽对长排料优选的方法需要原材料579块，原材料的利用率为78.87%；按照零件需求量，进展几种成品料配套优选的方法需要原材料595块，原材料的利用率为90.81%。故最优下料策略是第二种，需要规格为2100cm×1650cm的原材料579块。在有两种规格2100cm×1650cm和2000cm×1500cm原材料的情况下，需要规格为2100cm×1650cm的原材料447块，需要规格为2000cm×1500cm的原材料146块，总共594块，原材料的利用率为90.81%。本文采用了两个层次切割，在一定程度提高了利用率。七·模型的评价与补充7.1模型的评价显然，本文主要采用逐级优化的方法，对玻璃板材的最优下料策略进展分析计算的方法是基本成功的。事实上，对于一般的二维下料〔板材下料〕问题，初始切割方式确实定是下料问题中至关重要的内容，如果确定了最优的切割方式，就可以把下料问题化成一个优化组合问题，编程进展计算求解。7.1.1模型的优点通过逐级优化的方法，在分析各种不同切割方式的情况下，对下料方案进展对比筛选，可以选出最优的下料策略。7.1.2模型的缺点虽然所得结果为最优，但利用率相对还是有点低。7.2模型的补充如果考虑到其他Guillotine切割的方法，如用遗传学算法。遗传学算法有几个优点，建模简单；计算量相对的小，可得到近似最优的可行解；材料的利用率高。在实际应用时，可根据具体问题的特点，先用基因遗传算法确定较有前途的假设干下料方法，再自动借用常用模型及其算法，确定以这几种方法为根基最优下料方案。去两种模型之长，避其之短，可能会得到更好的结果。八·模型的改良和推广优化下料，提高材料的利用率，是国内外非常活泼的研究课题。而板材玻璃的下料问题是一类最常见的二维下料问题，就是把一定数量的大矩形板切割成所需要的各种规格大小和数量的小矩形，钢板，木板等的剪切下料也属于此类下料问题。因此，本模型可以推广到钢板，木板等的下料问题。参考文献王秋萍.数学建模讲义[J].西安理工大学，2011.附录1、第一种材料为1:579时原材料利用率0.85660.85510.85620.85600.85580.85560.85540.85520.85630.85490.85590.85450.85550.85530.85510.85490.85480.85460.85560.85420.85520.85380.85480.85460.85320.85430.85290.85390.85370.85350.85330.85310.85300.85400.85260.85360.85220.85320.85300.85290.85270.85250.85230.85330.85190.85290.85150.85140.85120.85100.84960.84940.85040.84900.84890.84990.85090.84950.84930.85030.84890.85000.84860.84960.84940.84800.84900.84760.84860.84850.84710.84690.84670.84770.84750.84740.84600.84580.84680.84540.84640.84510.84610.84470.84330.84550.84650.84630.84730.84710.84820.84800.84900.84760.84740.84720.84820.84690.84670.84650.84750.84730.84710.84810.84800.84900.84880.84860.84960.84940.85040.85030.85010.84990.85090.85070.85170.85030.85260.85120.85220.85200.85420.85280.85390.85370.85470.85330.85550.85410.85640.85500.85600.85700.85680.85660.85770.85750.85850.85710.85810.85800.85900.85880.85860.85840.85820.85800.85780.85890.85870.85850.85830.85810.85920.85900.85880.85860.85840.85940.85920.85910.85890.85870.85970.85950.85930.85910.85900.86000.85980.85960.85940.85920.86030.86010.85990.85970.85950.86050.86040.86020.86000.85980.85960.85940.85920.86020.86010.85990.85970.85950.86050.86030.86010.86000.85980.86080.86060.86040.86020.86000.86110.86090.86070.86050.86030.86140.86120.86100.86080.86060.86160.86140.86130.86110.86090.86190.86170.86150.86130.86110.86220.86200.86180.86160.86140.86250.86230.86210.86190.86170.86270.86260.86240.86220.86200.86180.86160.86140.86240.86230.86210.86190.86170.86270.86250.86230.86220.86200.86300.86280.86260.86240.86220.86330.86310.86290.86270.86250.86230.86210.86190.86300.86280.86260.86370.86350.86330.86430.86410.86390.86500.86480.86580.86690.86670.86650.86760.86740.86720.86820.86800.86910.86890.87000.86980.87080.87060.87170.87150.87260.87360.87350.87450.87430.87540.87520.87630.87610.87720.87700.87800.87910.87890.88000.87980.88090.88070.88180.88160.88270.88250.88360.88470.88450.88560.88540.88650.88630.88740.88720.88830.88810.88920.89030.89010.88990.88970.89080.89060.89040.89150.89130.89110.89090.89200.89180.89160.89140.89250.89230.89210.89320.89300.89280.89260.89370.89350.89330.89310.89420.89400.89380.89500.89480.89450.89430.89550.89530.89510.89480.89600.89580.89560.89670.89650.89630.89610.89720.89700.89680.89660.89770.89750.89730.89840.89820.89800.89650.89760.89740.89720.89700.89810.89790.89770.89880.89860.89840.89820.89930.89910.89890.89870.89980.89960.89940.90060.90030.90010.89990.90240.90220.90200.90180.90290.90270.90250.90370.90350.90320.90300.90420.90400.90380.90350.90470.90450.90430.90410.90520.90500.90480.90460.90570.90550.90530.90510.90630.90600.90580.90560.90680.90660.90630.90610.90730.90710.90690.90670.90780.90760.90740.90720.90700.90810.90650.90770.90610.90730.90570.90680.90530.90640.90480.90600.90440.90560.90400.90520.90360.90470.90320.90430.90270.90390.90230.90350.90190.90300.90150.90130.90110.90090.90060.90040.90020.90000.89980.89960.89940.89920.89900.89880.89860.89840.89810.89790.89770.89750.89730.89710.89690.89670.89650.89630.89610.89590.89570.89540.89520.89500.89480.89460.89440.89420.89400.89380.89360.89340.89320.89300.89280.89260.89240.89220.89200.89170.89150.89130.89110.89090.89070.89050.89030.89010.88990.88970.88950.88930.88910.88890.88870.88850.88830.88810.88790.88900.88880.88860.88970.88950.89060.89040.89020.89130.89110.89090.89200.89180.89290.89270.89250.89360.89340.89320.89430.89410.89530.89510.89480.89600.89580.89560.89670.89650.89760.89740.89720.89830.89810.89790.89900.90020.90000.89980.89960.89932、问题一中最优策略，原材料的长对成品的宽的程序：clear;l=zeros(1,27);w=zeros(1,27);l(1)=865;l(2)=857;l(3)=804;l(4)=857;l(5)=857;l(6)=804;l(7)=804;l(8)=804;l(9)=804;l(10)=804;l(11)=804;l(12)=804;l(13)=804;l(14)=865;l(15)=762;l(16)=715;l(17)=680;l(18)=675;l(19)=667;l(20)=655;l(21)=647;l(22)=667;l(23)=580;l(24)=552;l(25)=551;l(26)=527;w(1)=857;w(2)=715;w(3)=746;w(4)=675;w(5)=665;w(6)=663;w(7)=661;w(8)=639;w(9)=631;w(10)=563;w(11)=536;w(12)=535;w(13)=551;w(14)=446;w(15)=446;w(16)=446;w(17)=446;w(18)=446;w(19)=446;w(20)=446;w(21)=446;w(22)=426;w(23)=446;w(24)=446;w(25)=446;w(26)=426;zhang=0;n=zeros(26,1);n(1)=98;n(2)=98;n(3)=196;n(4)=28;n(5)=28;n(6)=224;n(7)=308;n(8)=84;n(9)=56;n(10)=224;n(11)=196;n(12)=392;n(13)=392;n(14)=98;n(15)=196;n(16)=98;n(17)=224;n(18)=28;n(19)=28;n(20)=84;n(21)=56;n(22)=308;n(23)=224;n(24)=196;n(25)=26;n(26)=392;zhang1=0;s1=0;s2=0;s3=0;s4=0;temp2=0;kk=0;forj=1:26m=2100-w(j)*fix(2100/w(j));e=1650-l(j)*fix(1650/l(j));whilen(j)>0n(j)=n(j)-fix(2100/w(j))*fix(1650/l(j));zhang=zhang+1;kk=0;temp1=0;temp2=0;fori=j:26if(e>w(i)&n(i)>fix(e/l(i))*fix(2100/w(i))&n(i)>fix(e/w(i))*fix(2100/l(i))&n(i)>0)if(max(fix(e/l(i))*fix(2100/w(i))*l(i)*w(i)/210/e,fix(e/w(i))*fix(2100/l(i))*l(i)*w(i)/210/e)>s1)s1=max(fix(e/l(i))*fix(2100/w(i))*l(i)*w(i)/210/e,fix(e/w(i))*fix(2100/l(i))*l(i)*w(i)/210/e);temp1=i;kk=1;endendif(m>w(i)&n(i)>fix(m/l(i))*fix((1650-e)/w(i))&n(i)>fix(m/w(i))*fix((1650-e)/l(i))&n(i)>0)if(max(fix(m/l(i))*fix((1650-e)/w(i))*l(i)*w(i)/((1650-e)*m),fix(m/w(i))*fix((1650-e)/l(i))*l(i)*w(i)/(1650-e)/m)>s2)s2=max(fix(m/l(i))*fix((1650-e)/w(i))*l(i)*w(i)/((1650-e)*m),fix(m/w(i))*fix((1650-e)/l(i))*l(i)*w(i)/(1650-e)/m);temp2=i;kk=1;endendends1=0;s2=0;ifkk~=0if(temp1~=0)n(temp1)=n(temp1)-max(fix(e/l(temp1))*fix(2100/w(temp1)),fix(e/w(temp1))*fix(2100/l(temp1)));endif(temp2~=0)n(temp2)=n(temp2)-max(fix(m/l(temp2))*fix((1650-e)/w(temp2)),fix(m/w(temp2))*fix((1650-e)/l(temp2)));endendendend3.问题二程序：clear;l=zeros(1,27);w=zeros(1,27);l(1)=865;l(2)=857;l(3)=804;l(4)=857;l(5)=857;l(6)=804;l(7)=804;l(8)=804;l(9)=804;l(10)=804;l(11)=804;l(12)=804;l(13)=804;l(14)=865;l(15)=762;l(16)=715;l(17)=680;l(18)=675;l(19)=667;l(20)=655;l(21)=647;l(22)=667;l(23)=580;l(24)=552;l(25)=551;l(26)=527;w(1)=857;w(2)=715;w(3)=746;w(4)=675;w(5)=665;w(6)=663;w(7)=661;w(8)=639;w(9)=631;w(10)=563;w(11)=536;w(12)=535;w(13)=551;w(14)=446;w(15)=446;w(16)=446;w(17)=446;w(18)=446;w(19)=446;w(20)=446;w(21)=446;w(22)=426;w(23)=446;w(24)=446;w(25)=446;w(26)=426;zhang=0;n=zeros(26,1);n(1)=98;n(2)=98;n(3)=196;n(4)=28;n(5)=28;n(6)=224;n(7)=308;n(8)=84;n(9)=56;n(10)=224;n(11)=196;n(12)=392;n(13)=392;n(14)=98;n(15)=196;n(16)=98;n(17)=224;n(18)=28;n(19)=28;n(20)=84;n(21)=56;n(22)=308;n(23)=224;n(24)=196;n(25)=26;n(26)=392;zhang1=0;s1=0;s2=0;s3=0;s4=0;temp2=0;kk=0;forj=1:26m=q-w(j)*fix(q/w(j));e=p-l(j)*fix(p/l(j));while(n(j)>0&zhang>0)n(j)=n(j)-fix(q/w(j))*fix(p/l(j));zhang=zhang-1;kk=0;temp1=0;temp2=0;fori=j:26if(e>w(i)&n(i)>fix(e/l(i))*fix(q/w(i))&n(i)>fix(e/w(i))*fix(q/l(i))&n(i)>0)if(max(fix(e/l(i))*fix(q/w(i))*l(i)*w(i)/210/e,fix(e/w(i))*fix(q/l(i))*l(i)*w(i)/210/e)>s1)s1=max(fix(e/l(i))*fix(q/w(i))*l(i)*w(i)/210/e,fix(e/w(i))*fix(q/l(i))*l(i)*w(i)/210/e);temp1=i;kk=1;endendif(m>w(i)&n(i)>fix(m/l(i))*fix((p-e)/w(i))&n(i)>fix(m/w(i))*fix((p-e)/l(i))&n(i)>0)if(max(fix(m/l(i))*fix((p-e)/w(i))*l(i)*w(i)/((p-e)*m),fix(m/w(i))*fix((p-e)/l(i))*l(i)*w(i)/(p-e)/m)>s2)s2=max(fix(m/l(i))*fix((