数学建模竞赛承诺书

1、精品文档五一数学建模竞赛承诺书我们仔细阅读了五一数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题C我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们授权五一数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其

2、他媒体进行正式或非正式发表等）。参赛题号（从A/B/C中选择一项填写）：B参赛组别（研究生、本科、专科、高中）：所属学校（学校全称）：参赛队员：队员1姓名：XXX队员2姓名：XXX队员3姓名：XXX联系方式：Email:联系电话：日期：年月日（除本页外不允许出现学校及个人信息）五一数学建模竞赛题目：木料切割最优化问题关键词：矩形件下料切割问题guillotine摘要：随着社会的发展、人们对环境资源的重视，提高材料的利用率、获得最大利润就成了不可避免的问题，而解决这个问题的关键就是对产品的生产进行紧凑型的布局。本文旨在解决家具厂木料的切割问题，由一维问题（或者说是1.5维问题）递推到二维问题，通

3、过寻找合适的切割方法（采用guillotine,贪心启发式算法的多目标二维切割），使得我们从目标木板上切割出的所需产品的面积和最大或者利润最大，后对方案进行优化处理，最终得出最优方案。问题一用guillotine方法切割可得一块木板上P1最多能切割59个。问题二在问题一的基础上，通过迭代的方法，分析得出前三甲利用率分别为99.64%,99.23%和99.03%的最佳方案。问题三又在问题二的基础上，引入了生产任务作为限制因素，并结合贪心启发式算法的多目标二维切割和问题使问题得到解决。问题四在问题三的基础上，又增添了两个长宽不同的矩形件，用lingo找寻它的最下限后，用循环得出最大利用率为99.6

4、4%,这时候使用的木板数为359块。问题五改变了问题四的目标函数，消除了生产任务对木块切割的限制。在这种情形下，得到最优方案是在一块木板上切割59块矩形件P1,从而得出最大利润为1174100元，木板的利用率为98.2979%。1欢迎下载精品文档五一数学建模竞赛题目：木料切割最优化问题关键词：矩形件下料切割问题guillotine摘要：随着社会的发展、人们对环境资源的重视，提高材料的利用率、获得最大利润就成了不可避免的问题，而解决这个问题的关键就是对产品的生产进行紧凑型的布局。本文旨在解决家具厂木料的切割问题，由一维问题（或者说是L5维问题）递推到二维问题，通过寻找合适的切割方法（采用guil

5、lotine,贪心启发式算法的多目标二维切割），使得我们从目标木板上切割出的所需产品的面积和最大或者利润最大，后对方案进行优化处理，最终得出最优方案。问题一用guillotine方法切割可得一块木板上P1最多能切割59个。问题二在问题一的基础上，通过迭代的方法，分析得出前三甲利用率分别为99.64%,99.23%和99.03%的最佳方案。问题三又在问题二的基础上，引入了生产任务作为限制因素，并结合贪心启发式算法的多目标二维切割和问题使问题得到解决。问题四在问题三的基础上，又增添了两个长宽不同的矩形件，用lingo找寻它的最下限后，用循环得出最大利用率为99.64%,这时候使用的木板数为359块

6、。问题五改变了问题四的目标函数，消除了生产任务对木块切割的限制。在这种情形下，得到最优方案是在一块木板上切割59块矩形件P1,从而得出最大利润为1174100元，木板的利用率为98.2979%o2欢迎下载精品文档7欢迎下载hi表示第i种方案所用原料木板的数量模型建立与优化1、问题一(1)算法分析分析第一题，其采用单一材料形式进行分割，我们通过guillotine切割方案进行初步求解，其采用“一刀切”的形式对问题进行求解，得出在一块木板上P1切割的最大数为56,但是(相对误差比较大)利用率比较低。后通过贪心算法再次对问题进行优化求解，得出切割的最大数为60,接近于木板切割(装载)的上限，针对于该

7、问题，贪心策略能得到较好的解，但它不适用于其他问题。图例1:贪心算法(2)模型建立建立一个1.5维的切割问题模型来求近似解nminLW1州区i1'st.lx、L,i=1,.,n:Wn二一y-或者'stlx二W,i=1,nLn二一_W1(3)模型求解P1的数量木板利用率5998.29793%2、问题二(1)算法分析在第一题的基础上，继续贪心找到了每种产品的上限，通过guillotine切割进行迭代分析求出不同方案的木板利用率，经过对比分析，选取了三种利用率最高的方案。(2)模型建立minLW-I1w1x1-l3w3x3s.t.LW.I1w1x1l3w3x3x1,x3都为非负整数(

8、3)切割P1和P3的全部方案方案编号P1的数量P3的数量木板利用率14450.996428400.9597312380.9850416330.9484520310.9737624260.9370728250.9830832210.9670936190.99231040140.95571144120.9810124870.9443135260.9903145600.9330(4)模型求解根据上面的方案，进行利用率的排序，易得三种最佳方案方案编号P1的数量P3的数量木板利用率14450.9964936190.9923135260.99033、问题三(1)算法分析可结合问题一，得出在一块木板上分别切

9、割P1和P3所能得到的最大数，再结合生产任务能得到满足需求的最小木板数，该值为35。假设全部木板都用一种切割方式，并结合贪心启发式算法的多目标二维切割和问题，建立了模型。后进行优化改进，让不同的木板有不同的切割方案，使得木板的利用率达最大。(2)模型建立min LW -I1w1x1 -l3w3x3s.t. Bx1 , d1BX3 _d3LW _l1w1x1 l3w3x3B _35B, x1, x3为非负整数minz=Bs.t.Bx1,d1Bx3一d3LW-11叫x1-l3亚3*3-KB_35B,x1,x3为非负整数(3)模型求解木板S1的数量P1的数量P3的数量木板利用率备注344540.99

10、64每块木板切割方案相同219360.9923116520.9903合计数量：_477741623木板总利用率：0.99479所有产品的总面积木板总利用率=所有木板的总面积问题四(1)算法分析问题四采用了guillotine二维切割方法，通过贪心等启发式算法获取最优解的近似解。同时由于该问题属于NP问题，无法采用多项式方法求解，故只能采用guillotine方法得到部分解。(2)切割方案P1P2P3P4利用率25.000011.00003.00009.00000.947318.000013.00006.00009.00000.952425.00006.00009.00009.00000.921

11、834.0000012.00009.00000.95439.00003.000029.00009.00000.978714.00006.000020.00009.00000.965819.00003.000021.00009.00000.980124.0000022.00009.00000.994329.00003.000013.00009.00000.981434.0000012.00009.00000.954330.000002.000027.00000.961028.000004.000027.00000.969026.000006.000027.00000.977024.000008.

12、000027.00000.985020.0000010.000027.00000.959718.0000012.000027.00000.967716.0000014.000027.00000.97574.00006.000016.000027.00000.996412.0000018.000027.00000.99178.0000020.000027.00000.96644.0000024.000027.00000.982412.00005.00003.000037.00000.986712.00009.00006.000024.00000.966112.00008.000012.00001

13、8.00000.966912.00005.000015.000021.00000.985912.00007.000018.000012.00000.967712.00006.000021.000011.00000.984212.00005.000027.00005.00000.985012.00005.000030.000000.969216.0000028.00007.00000.953916.000014.0000014.00000.902816.0000018.000021.00000.965016.00008.00002.000027.00000.966916.00006.00004.

14、000028.00000.964016.00005.00006.000028.00000.975416.000008.000033.00000.945016.00004.000010.000024.00000.965916.00002.000012.000025.00000.963016.00002.000014.000023.00000.973316.0000016.000024.00000.970316.0000018.000021.00000.9650(3)模型建立kminB八1i=1kst.'hiaj-dj,j=1,2,3,4i1aj,hi为非负整数(4)模型求解k4minLW

15、B八'hiaijljwji=1j=1ks.t.B-%hii=1k“hiaj-dj,j=1,.,4i1LW一ajljwj,i=1,.,kaj,hi为非负整数精品文档木板S1的数量P1的数量P2的数量P3的数量P4的数量木板利用率备注3594616270.9964每块木板切割方案相同合计数量：359774215316231614木板总利用率：_0.9964_木板总利用率=所有产品的总面积所板的总面积问题五(1)算法分析根据第四题所得分割方案，建立数学模型进行求解。(2)模型建立k4max：二工：CjajTj3ks.t.'hiaij_dji14LWJaijljwj,i=1,，kjia

16、ij,hi为非负整数(3)模型求解木板S1的数量P1的数量P2的数量P3的数量P4的数量利润(元)木板利用率备注100590001174.10.982979每块木板切割方案相同木板S1合计数量100总利润:1174100木板总利用率：_0.982979木板总利用率一所有产品的总面积一所有木板的总面积进一步讨论结果表示，分析与检验误差分析上述问题求得的只是近似解，可能还有优化的空间，目前还没有发现此类解决NP问题一劳永逸的算法方案。结语(模型评价，特点优缺点改进方法推广)该数学模型只能得到解的下限，不能直接得出解的结果，一方面是因为该模型选择用面积近似求解而没有考虑到所装载物体的形状，另一方面是

17、因为无法很好的将木板的长宽与变量联系在一起(约束条件的缺少)，因此只能求出可行解的上限或者下限，不能求出精确解。除此之外，上述贪心策略求解切割方案的移植性较差，只能用于解决一些问题，但对于某些问题能得到更好的结果，例如问题一，采用guillotine只能求出装载pl数为56,而采用贪心策略则能求出装载p1数为59,更大得接近此问题的上限装载量60。对于已存在的切割方案的优化求解，可以采用一些智能算法对问题的解空间进行检索，进一步获取较多的切割方案。这种方法也是寻求最优的全局最优解的另一种方式。参考文献1向文欣，荀珂，冉翠翠.基于两段排样方式的剪冲下料优化算法J.锻压技术,2019,44(06):35-40.