数学建模板材成本控制问题.docx

B题：板材成本控制问题摘要板材下料成本控制对各工业领域来说都是一项很重要的问题，与经济效益有着直接的关系，一般都是根据生产需求尽可能的提高原材料的利用率。本题限定在一定区间范围内的长宽比矩形板材，并且规定了有限的板材与用材的面积比。切割成题设要求的用材，考虑多种切割方案，然后求解最大用材数与原板材长宽比的关系。本文运用优化理论，采用了密集型切割的方式构建了矩形排样数学模型。考虑不同用材的不同对称方式，提出了基于启发式算法的二维板材下料算法。利用matlab、C+等软件求出在限定取值区间内，不同种切割方式的最大用材数和矩形板材长宽比的关系。对于问题一，我们考虑不同用材与板材的位置、对称关系，利用占角策略，构造了用材贴近原板材左上顶角沿右、下两个方向平铺的切割方法，还有用材贴近原板材四边向中心逼近的共两类切割方案。对于问题二，我们利用C+、matlab构造了五种切割方案：(1)圆形用材贴近左上顶点向右、向下平铺切割；(2)圆形用材贴近原矩形板材的上边，第二排圆形用材正切第一排用材，以此类推切割。同时研究了排数分奇、偶两种情况的不同结果；(3)将第二种情况改为圆形用材贴近左边平铺正切切割，也讨论了奇、偶列数的不同结果；(4) 将（2）中的正切改为以一定角度相切，其他同理；（5）将（3）中正切也改为一定角度相切。对于问题三，利用c+构建了用材的长边或者宽边紧贴板材的长边的方案，以及沿对角线或偏离一定角度平铺的共三个切割方案。对于问题四则是在问题三的基础上，讨论用材长宽比在一定范围内的三个方案，去除了问题三中题设条件下的偶然因素，把此算法推广到一般的情况下应用。本文模型适应于矩形板材板材面积长宽比固定、用材形状对称、用材面积限定的小型板材下料问题。对于生产生活中大规模板材、非矩形板材、不规模用材图形则会产生很大浪费，不适合具体生产生活中的板材切割问题。所以对于此则需要引入优化理论、最小包络距、排样方案分析等理论与算法。关键词二维板材下料 矩形排样数学模型 密集型切割 优化 启发式算法 占角策略 对称一、 问题重述现有面积为A，长宽比为l的板材，需要切割成面积为B的用材，A、B关系为；16n=A/B25,n为整数。最大用材数y和l有一定的函数关系，并且不同的条件，会产生许多种切割方案，最大用材数y也会产生变化。根据题意，本文需要解决的问题有：1、当用材为正方形，1l2时，y和l的关系。2、当用材为圆形，1l2时，求解不同的切割方案以及y和l的关系。3、当用材为长宽比为2的矩形，1l2时，求解不同的切割方案以及y和l的关系。4、当用材为长宽比为m的矩形，1l2，1m2时，求解不同的切割方案以及y和l的关系。二、 问题分析这是一个板材下料的问题。我们需要解决的问题难点有；（1）如何找到尽可能多的有意义的板材切割方案；（2）确定不同的二维切割方案使得板材得到更多的利用；（3）不同n、l的值对应的不同切割方案。问题一中的用材为正方形，是中心对称图形，所以当正方形用材与矩形板材边都平行的时候对板材利用率最大。若沿板材左边、上边平行切割后，原板材剩余的长边、宽边的和大于等于，则可以在原有基础上切割出更多的正方形用材。问题二中的用材为圆形,为中心对称图形。排布以圆形用材相切且密集排布为原则，如此切割对原板材利用率较大。可以分为以下几种切割方案1、第一排用材与板材长边相切且密集排列，其他排复制第一排的切割方式；2、第一排圆形用材与板材长边相切，第二排圆形用材与第一排圆形用材正相切，剩余排数复制以上两排切割方案；3、改变2中方案用材与原板材的起始相切边为宽边;4、改变2中方案第二排用材与原板材的相切角度，以及第一排用材之间的间隔；5、将4中的方案改为宽边为起始边。问题三中用材形状是矩形，为轴对称图形。则可以分为用材矩形与板材矩形的长长平行、长宽平行的两种不同方案，以及用材矩形与板材矩形的两长边所在直线有一定夹角的切割方案。由于此矩形长宽比为2，所以容易求得上个步骤的最佳夹角。问题四则是问题三的一般形式展开，把问题三的特例换成了长宽比为m的一般形式推广开来。所用方案基本一致。三、 符号说明La矩形板材的长边Wa矩形板材的宽边l矩形板材的长宽比K矩形板材的宽边长A矩形板材的面积B用材的面积Lbi问题1、3、4中对应用材矩形的长边（i=1、3、4）Wbi问题1、3、4中对应用材矩形的宽边（1=1、3、4）Rb2用材为圆形时，用材的半径Pi矩形板材的宽边上可以切割出用材的个数（i=1、2、3、4）Qi矩形板材的长边上可以切割出用材的个数（i=1、2、3、4）h矩形板材长边切割后剩余的长度j矩形板材宽边切割后剩余的长度第一排相邻两个圆圆心与第二排与之相切的圆心确定的等腰三角形的底角 向下求整函数四、 模型假设（1） 板材可以沿任意方向切割；（2） 用材允许任意摆放；（3） 不考虑切割时产生的损耗；（4） 用材不能重叠，不超过原材料的大小五、 模型建设与求解6.1综述从理论上看，此类问题属于NP完全问题，以目前已成熟的计算机理论和算法，或者无法求解，或者求解结果为爆炸性的。本文从现有算法中，通过比较分析。构造了一种优于现有的优化排列的启发式构造算法。按照一定规则通过实际排列和比对，可以达到较高的原材料利用率，符合实际生产的要求。6.2矩形原材料规格下的二维下料算法本文利用计算机模拟，采用优化排样的方法，考虑用材的对称方式，对不同形状的用材采用不同的排列、平移、翻转策略，得到了不同的排样方案，并且考虑不同方案中特解的情况。更计算出了不同用材、不同方案的最大用材数6.3问题一的建模和求解6.3.1模型图1如图1所示，正方形用材左边、上边贴合矩形板材的左边与上边，并向右向下平行切割。直到不能切割为止。矩形原材面积为A=矩形原材长边La =kl正方形用材面积为：B=正方形边长：Lb1 =通过对p1、q1 求整，确定此种方案的最大用材数y。如图所示，当矩形板材任一顶角的两条临边被切割后剩下的长度总和即h+j大于或等于时，将正方形用材向四周移动，空出原板材的中间位置，可进一步切割。由于正方形是中心对称图形，所以若正方形用材的上边延长线与矩形原材的上边延长线有偏角时，对比前面切割的方式会产生较多的浪费，所以不予考虑此种情况。6.3.2模型求解我们借助C+，把求解的程序编译最终求得所有模拟结果（一）求解的函数部分16n=A/B25，且n为整数，1l2当La Wa Lb1 （p1 q1） ，klK （） q1 = ，p1=y=p1q1=1klK （）y=p1q1=（二）模型求解的数学结果用材为正方形时不同n、l值下对应的用材个数l11.11.21.31.41.51.6n=16y/切割总数16121212121215Z/板材利用率0.59480.44610.44610.44610.44610.44610.5577n=17y16121212121515Z0.55980.41990.41990.41990.41990.52490.5249n=18y16161212151515Z0.52870.52870.39660.39660.49570.49570.4957n=19y16161212151515Z0.50090.50090.37570.37570.46960.46960.4696n=20y16161615151515Z0.47590.47590.47590.44610.44610.44610.4461n=21y16162020151515Z0.45320.45320.56650.56650.42490.42490.4249n=22y16162020151515Z0.43260.43260.54080.54080.40560.40560.4056n=23y16202020201518Z0.41380.51730.51730.51730.51730.38790.4655n=24y16202020202418Z0.39660.49570.49570.49570.49570.59480.4461n=25y25202020202418Z0.59480.47590.47590.47590.47590.5710.4283l1.61.71.81.92n=16y/切割总数1515101010Z/板材利用率0.55770.55770.37180.37180.3718n=17y1515151010Z0.52490.52490.52490.34990.3499n=18y1515151518Z0.49570.49570.49570.49570.5948n=19y1515151818Z0.46960.46960.46960.56350.5635n=20y1515181818Z0.44610.44610.53540.53540.5354n=21y1515181818Z0.42490.42490.50990.50990.5099n=22y1518181818Z0.40560.48670.48670.48670.4867n=23y1818181818Z0.46550.46550.46550.46550.4655n=24y1818181818Z0.44610.44610.44610.44610.4461n=25y1818181821Z0.42830.42830.42830.42830.49976.4问题二的建模和求解6.4.1模型图二（1）方案一如图所示，第一排圆形用材均紧密无缝隙正切于矩形板材，第二排复制第一排并依次向下复制，直至矩形板材空间不够用为止。矩形原材面积为：A=矩形原材长边：La =kl圆形用材面积为：B=圆形用材半径:Rb2= =通过对p1、q1 求整，确定此种方案的最大用材数y。图三（2）方案二如图三所示，第一排圆形用材均紧密无缝隙正切于矩形板材长边，第二排的任一圆形用材正切于第一排临近两个圆形用材，且这个三个圆形用材的圆心确定的三角形为正三角形。剩余的排数复制前两排，直至板材空间不够用为止。需要注意，最终确定的排数分奇、偶两种不同情况讨论。矩形原材面积为:A=矩形原材长边:La =kl圆形用材面积为:B=圆形用材半径：Rb2= =三个圆心确定的三角形的高线为Rb2通过对p1、q1 求整，确定此种方案的最大用材数y。图四（3）方案三如图四所示，只将（2）第一排圆形用材紧密无缝隙正切于矩形宽边。其他不变，也将排数分为奇.偶两种情况讨论。A=矩形原材长边：La =kl圆形用材面积为：B=圆形用材半径：Rb2= =三个圆心确定的三角形的高线为Rb2通过对p1、q1 求整，确定此种方案的最大用材数y。图五（4）方案四如图五所示，第一排圆形用材均正切稀疏于矩形板材长边，第二排的任一圆形用材正切于第一排临近两个圆形用材，且这个三个圆形用材的圆心确定的等腰三角形地角为。剩余的排数复制前两排，直至板材空间不够用为止。需要注意，最终确定的排数分奇、偶两种不同情况讨论。A=矩形原材长边：La =kl圆形用材面积为：B=圆形用材半径：Rb2= =三个圆心确定的三角形的高线为2 Rb2， 底边为4Rb2。通过对p1、q1 求整，确定此种方案的最大用材数y。图六（5）方案五如图六所示，只将（4）中第一排圆形用材稀疏排列正切于矩形宽边。其他不变，也将排数分为奇.偶两种情况讨论。A=矩形原材长边：La =kl圆形用材面积为：B=圆形用材半径Rb2= =三个圆心确定的三角形的高线为2 Rb2， 底边为4Rb2。通过对p1、q1 求整，确定此种方案的最大用材数y。6.4.2模型求解借助C+，把求解的程序编译最终求得所有模拟结果（一）求解的函数部分（1）方案一：16n=A/B25，且n为整数，1l2。Rb2=q2 =2P2 =2y=p2q2=22（2）方案二：16n=A/B25，且n为整数，1l2。Rb2=q2 =P2=1=1=当P2 奇数时，y=p2q2 =2 当P2 偶数时，y=p2q2 = （3）方案三：16n=A/B25，且n为整数，1l2。Rb2=P2 =q2 =+1=+1=+1当q2为奇数时，y=p2q2 =+1 当q2为偶数时，y= p2q2 =+1（4）方案四：16n=A/B25，且n为整数，1l2。Rb2=P2=1=+1q2=+1当P2为奇数时，Y= p2q2 =+1 +1当P2为偶数时，y=p2q2 =+1 +1（5）方案五：16n=A/B25，且n为整数，1l2。Rb2=P2=q2=当q2为奇数时，y=p2q2 =当q2为偶数时，y= p2q2 =（二）模型求解的数学结果由于本模型中计算结果量巨大，无法全部粘贴，故在不同类别方案中分别选出具有代表性的部分数据。用材为圆形时方案一中不同n、l值下对应的用材个数l11.11.21.31.41.51.6n=16y/切割总数99912888Z/板材利用率0.56250.56250.56250.750.50.50.5n=17y9912121288Z0.52940.52940.70590.70590.70590.47060.4706n=18y99121212128Z0.50.50.66670.66670.66670.66670.4444n=19y9121212121212Z0.47370.63160.63160.63160.63160.63160.6316n=20y9121212121215Z0.450.60.60.60.60.60.75n=21y16121212121215Z0.76190.57140.57140.57140.57140.57140.7143n=22y16121212121515Z0.72730.54550.54550.54550.54550.68180.6818n=23y16161212151515Z0.69570.69570.52170.52170.65220.65220.6522n=24y16161212151515Z0.66670.66670.50.50.65220.65220.6522n=25y16161615151515Z0.66670.66670.66670.66670.65220.65220.6522l1.71.81.92n=16Y88810Z0.50.50.50.625n=17y881010Z0.47060.47060.58820.5882n=18y8101010Z0.44440.55560.55560.5556n=19y10101010Z0.52630.52630.52630.5263n=20y15101010Z0.750.50.50.5n=21y15151010Z0.71430.71430.47620.4762n=22y15151510Z0.68180.68180.68180.4545n=23y15151518Z0.65220.65220.65220.7826n=24y15151518Z0.65220.65220.65220.75n=25y15151818Z0.65220.65220.750.75用材为圆形时方案二、四中部分不同n、l值下对应的用材个数langle/角度nyl.00.3 16141714181519152017211722172317241825181.3 0.4 16917918919112011211122182320242025201.5 0.5 166178181319132013211322132315241525151.8 0.8 16817818819112011211122112314241425141.9 0.7 16817818819820821142214231424142514用材为圆形时方案三、五中部分不同n、l值下对应的用材个数langle/角度nyl0.40 16111711181219122012211222142314241425141.30 0.40 16121714181419142014211422142314241725171.50.516111712181219122014211422142314241525151.80.81691791891992011211122112311241125111.90.716111711181119112011211222122312241225126.5问题三的建模和求解6.5.1模型由于矩形为轴对称图形，本模型只考虑矩形用材的长边与矩形用材的的夹角为0或者90的情况。因其他偏角的情况会造成对矩形原材的较多浪费，故不在考虑范围内。图七（1）方案一如图七所示，矩形用材的长边与矩形原材的长边贴合，向右向向下复制切割，直至不能切割为止。A=矩形原材长边La =kl矩形用材宽Wb3=矩形用材长为Lb3=2Wb3=2通过对p1、q1 求整，确定此种方案的最大用材数y。图八（2）方案二如图八所示，矩形用材的长边与矩形原材的长边贴合，向右向下复制切割，直至不能切割为止。A=,矩形原材长边La =kl。矩形用材宽Wb3=矩形用材长为Lb3=2Wb3=2通过对p1、q1 求整，确定此种方案的最大用材数y。6.5.2模型求解借助C+，把求解的程序编译最终求得所有模拟结果（一）求解的函数部分（1）方案一16n=A/B25，且n为整数，1l2。Wb3=Lb3=2P3= =q3=y= P3 q3=（2）方案二16n=A/B25，且n为整数，1l2。Wb3=Lb3=2P3= =q3=y= P3 q3=（二）模型求解的数学结果由于本模型中计算结果量巨大，无法全部粘贴，故在不同类别方案中分别选出具有代表性的部分数据。用材长宽比为2矩形时方案一中部分不同n、l值下对应的用材个数lny利用率lny利用率1.00 16100.63 1.60 16120.75 17100.59 17120.71 18181.00 18120.66 19180.95 19120.63 20180.90 20160.80 21180.85 21200.95 22180.82 22200.90 23180.78 23200.87 24180.75 24200.83 25210.84 25200.80 1.10 16100.63 1.70 16120.75 17150.88 17120.71 18150.83 18120.67 19150.79 19160.84 20180.90 20160.80 21180.86 21160.76 22180.82 22200.91 23180.78 23200.87 24180.75 24200.83 25180.72 25200.80 1.20 16150.94 1.80 16120.75 17150.88 17120.71 18150.83 18160.89 19150.79 19160.84 20150.75 20160.80 21150.71 21160.76 22180.82 22160.73 23180.78 23200.87 24180.75 24200.83 25180.72 25200.80 1.30 16120.75 1.90 16120.75 17150.88 17160.94 18150.83 18160.89 19150.79 19160.84 20150.75 20160.80 21150.71 21160.76 22150.68 22160.73 23150.65 23160.70 24180.75 24200.83 25240.96 25200.80 .用材长宽比为2矩形时方案一中部分不同n、l值下对应的用材个数lny利用率lny利用率1.00 16100.63 1.80 16140.88 17100.59 17140.82 18181.00 18160.89 19180.94 19160.84 20180.90 20160.80 21180.86 21160.76 22180.82 22160.73 23180.78 23180.78 24180.75 24180.75 25210.84 25180.72 1.10 16100.63 1.90 16140.88 17120.71 17160.94 18120.67 18160.89 19120.63 19160.84 20180.90 20160.80 21180.86 21160.76 22180.82 22180.82 23210.91 23180.78 24210.88 24180.75 25210.84 25180.72 1.20 16120.75 2.00 1680.50 17120.71 17160.94 18120.67 18160.88 19120.63 19160.84 20120.60 20160.80 21140.67 21180.86 22210.95 22180.81 23210.91 23180.78 24210.88 24180.75 25210.84 25200.80 1.30 16120.75 1.70 16140.88 17120.71 17140.82 18120.67 18140.78 19140.74 19160.84 20140.70 20160.80 21140.67 21160.76 22140.64 22160.73 23140.61 23160.70 24210.88 24180.75 25240.96 25180.72 .6.6问题四的建模和求解6.6.1模型此模型为6.5所列模型的一般形式扩充，思想、方法基本与6.5所列模型一致。图九（1）方案一方案一如图九所示，矩形用材的长边与矩形原材的长边贴合，向右向向下复制切割，直至不能切割为止。A=矩形原材长边La =kl矩形用材宽Wb4=矩形用材长为Lb4=mWb4=m通过对p1、q1 求整，确定此种方案的最大用材数y。图十（2）方案二如图十所示，矩形用材的长边与矩形原材的长边贴合，向右向下复制切割，直至不能切割为止。A=矩形原材长边La =kl矩形用材宽Wb4=矩形用材长为Lb4=mWb4=m通过对p1、q1 求整，确定此种方案的最大用材数y。6.6.2模型求解借助C+，把求解的程序编译最终求得所有模拟结果（一）求解的函数部分（1）方案一16n=A/B25，且n为整数，1l2。Wb4=Lb4=mP4= =q4=y= P4 q4=（2）方案二16n=A/B25，且n为整数，1l2。Wb4=Lb4=mP4= =q4=y= P4 q4 =（二）模型求解的数学结果由于本模型中计算结果量巨大，无法全部粘贴，故在不同类别方案中分别选出具有代表性的部分数据。用材长宽比为m矩形时方案一中部分不同n、l值下对应的用材个数lnmy1161161.1121.21.31.41.51.6151.7101.81.9.1.1211161.11.21.31.4201.5151.61.71.81.9181.4171121.11.21.31.4161.5121.61.71.81.9用材长宽比为m矩形时方案二中部分不同n、l值下对应的用材个数lnmy1161161.1121.21.31.41.51.6151.71.8101.91.1211161.1201.2151.31.41.51.6181.71.81.91.4191151.11.21.31.4181.51.6121.71.81.914七、模型结果分析与优化通过matlb、c+编程，计算出大量的切割方案。在不同方案中若n、l有微小变化，切割个数就随之产生不同变化。计算结果十分巨大，无法粘贴处所有结果，所以上文仅粘贴部分区间的切割结果。并且发现切割模型与n、l取值密切相关。在本文研究的基础上，引入了板材利用率，使得结果更加直观明确，具有参考性，所以在实际切割过程中一定要着重考虑矩形用材的长宽比以及用材与板材的关系。工厂可以根据实际需求的用材数量结合利用率采取最佳方案。在本文研究的基础上，我们也引入了板材利用率这一新概念，使结果更加直观明确。由于计算量巨大，下文中我们仅代表列举问题一、问题二两种板材利用率。其他问题类此。八、模型优缺点本文模型在实际应用中简单易行、计算快速，可在生产生活中大量应用。并且本模型覆盖切割种类较多，结果更具科学性。但是本模型是基于题设条件下成立，应用广度较窄。并且本模型没考虑到切割浪费、在板材固定位置切割的情况，所以在实际应用中需要根据需求作出具体改变。九、改进方向实际生活中大部分用材是不规则图形，所以可将本文模型作为基础模型。在此基础上，引入多边形的最小包络距，构造成为规格图形的切割。从而在实际生产生活中得到更广泛的应用。也可将本文算法与更智能的算法联系在一起，从而使得本模型更好的推广开来。十、参考文献【1】石景，板材优化下料算法研究，2007.3【2】章绍辉，数学建模，科学出版社，2010【3】杨剑，圆形件优化排样问题研究，2010.4十一、附录问题一matlb程序：n=18;l=1:0.1:2k=1;rb=k*l;rW=k;rB=k*sqrt(l./n)a=rb./rB;b=rW./rB;a1=floor(a);b1=floor(b)y=a1./(1./b1)问题二方案一程序n=16l=1:0.1:2;WA=k;LA=k./(1./l);SA=k.2./(1./l);SB=(1./n)./(1./k).2./(1./l);rB=sqrt(SB/pi)p=floor(WA./(2*rB)q=floor(LA./(2*rB)y=p./(1./q)plot(l,y)问题二的方案二、三、四、五程序#include#include#include#include using namespace std;void main()int n,p,q,h;double a,b,l,angle;const double pi=3.1415;for(l=1;l=2;l=l+0.1)for(angle=0;angle=pi/3;angle=angle+0.1)for(n=16;n=25;n+) b=n*pi; a=sqrt(l/b);q=(l-2*a)/(4*a*cos(angle)+1;p=(1-2*a)/(2*a*sin(angle)+1;h=pow(-1,p);if(h=-1) coutl=l,n=n,angle=angle,resultp*q-(p-1)/2endl; else coutl=l,n=n,angle=angle,resultp*q-p/2endl;#include#include#include#include