木材最优切割

五一数学建模竞赛承诺书我们仔细阅读了五一数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们授权五一数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。参赛题号（从A/B/C中选择一项填写）：B参赛队号：参赛组别（研究生、本科、专科、高中）：所属学校（学校全称）：参赛队员：队员1姓名：XXX队员2姓名：XXX队员3姓名：XXX联系方式：Email：联系电话：日期：年月日（除本页外不允许出现学校及个人信息）五一数学建模竞赛题目：木料切割最优化问题关键词：矩形件下料切割问题guillotine摘要：随着社会的发展、人们对环境资源的重视，提高材料的利用率、获得最大利润就成了不可避免的问题，而解决这个问题的关键就是对产品的生产进行紧凑型的布局。本文旨在解决家具厂木料的切割问题，由一维问题（或者说是1.5维问题）递推到二维问题，通过寻找合适的切割方法（采用guillotine，贪心启发式算法的多目标二维切割），使得我们从目标木板上切割出的所需产品的面积和最大或者利润最大，后对方案进行优化处理，最终得出最优方案。问题一用guillotine方法切割可得一块木板上P1最多能切割59个。问题二在问题一的基础上，通过迭代的方法，分析得出前三甲利用率分别为99.64%，99.23%和99.03%的最佳方案。问题三又在问题二的基础上，引入了生产任务作为限制因素，并结合贪心启发式算法的多目标二维切割和问题使问题得到解决。问题四在问题三的基础上，又增添了两个长宽不同的矩形件，用lingo找寻它的最下限后，用循环得出最大利用率为99.64%，这时候使用的木板数为359块。问题五改变了问题四的目标函数，消除了生产任务对木块切割的限制。在这种情形下，得到最优方案是在一块木板上切割59块矩形件P1，从而得出最大利润为1174100元，木板的利用率为98.2979%。问题的提出优化问题重述与分析本题可简化为给你一块已知长宽的矩形木板，和一些知道长宽的矩形产品的生产目标和利润，要求你设计一个最优切割方案，使木板的利用率最高。在本题中，限制因素可以为生产目标、木板的面积、切割一块产品所得的利润。当然，对于这种二维下料问题，还需要考虑零件长、宽两个方向上的限制。问题一可以看成一个1.5维的切割问题，通过贪心算法我们可以轻易地得出木板切割的近似解，随后利用迭代的思路与方法，逐渐接近它的上限。问题二除了问题一所涉及的变量P1外增添了新的变量P3，求资源利用率最高的前三种方案。但问题一和问题二都只涉及一块原材料木板。问题三引入了生产目标作为限制因素，并且要求每块木板上的切割方案相同，目标还是达到最高的利用率。问题四在问题三的基础上加入P2和P4，因为木板的切割方案相同，实际问题就转化成了一块木板上的切割方案。根据在每块木板上切割同一种的产品，可得到一个需要原材料木板的最低数量，同时可以得出一个生产的优先级，可以根据这个优先级着重安排生产方案，在满足需求的条件下，使木料使用的数量达到最小（这时不一定木板的利用率最大）。后在这个可行解的情形下，找寻最优解。（然后又在不同切割方案下，找寻最佳的木板利用率。）问题五和问题四类似，在每块木板切割方案一致时，可以转化为一块木板上的最大利润问题。但是问题五放宽了每个产品的需求数量（即生产任务），在给定木板数100的情形下，目标函数变为最大的利润。条件假设1、假设在木板上采用guillotine的切割方案2、采用直线切割3、合理的切割模式：通常建设一个合理的切割模式的余料不应大于或者等于需要板材的最小尺寸。4、假设每次切割都精准符号说明符号说明),,(BWL原料木板的长、宽和数量),,,(iiiicdwl第i个产品的长、宽、生产任务和利润ix第i个产品在一块木板上切割后的数量'ix从第i个条形木板上切割出长度为1l的成材数K自定义的一个期望内的木材的利用率，可以被人为的改动k表示切割方案个数，即有k种切割方案ija表示在第i种切割方案下第j种规格板材所切割的数量ih表示第i种方案所用原料木板的数量模型建立与优化1、问题一（1）算法分析分析第一题，其采用单一材料形式进行分割，我们通过guillotine切割方案进行初步求解，其采用“一刀切”的形式对问题进行求解，得出在一块木板上P1切割的最大数为56，但是（相对误差比较大）利用率比较低。后通过贪心算法再次对问题进行优化求解，得出切割的最大数为60，接近于木板切割（装载）的上限，针对于该问题，贪心策略能得到较好的解，但它不适用于其他问题。（2）模型建立建立一个1.5维的切割问题模型来求近似解1'11'11'11,...,1,..,...,1,..minwLnniWxltswWnniLxltsxwlLWiinii或者（3）模型求解P1的数量木板利用率5998.29793%2、问题二（1）算法分析图例1：贪心算法图例2：guillotine切割在第一题的基础上，继续贪心找到了每种产品的上限，通过guillotine切割进行迭代分析求出不同方案的木板利用率，经过对比分析，选取了三种利用率最高的方案。（2）模型建立都为非负整数31333111333111,..minxxxwlxwlLWtsxwlxwlLW（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）算法分析可结合问题一，得出在一块木板上分别切割P1和P3所能得到的最大数，再结合生产任务能得到满足需求的最小木板数，该值为35。假设全部木板都用一种切割方式，并结合贪心启发式算法的多目标二维切割和问题，建立了模型。后进行优化改进，让不同的木板有不同的切割方案，使得木板的利用率达最大。（2）模型建立为非负整数313331113311333111,,35..minxxBBxwlxwlLWdBxdBxtsxwlxwlLW为非负整数313331113311,,35..minxxBBKxwlxwlLWdBxdBxtsBz（3）模型求解木板S1的数量P1的数量P3的数量木板利用率备注344540.9964每块木板切割方案相同219360.9923116520.9903合计数量：___47_____7741623木板总利用率:___0.99479___木板总利用率=问题四（1）算法分析问题四采用了guillotine二维切割方法，通过贪心等启发式算法获取最优解的近似解。同时由于该问题属于NP问题，无法采用多项式方法求解，故只能采用guillotine方法得到部分解。（2）切割方案P1P2P3P4利用率25.000011.00003.00009.00000.947318.000013.00006.00009.00000.952425.00006.00009.00009.00000.921834.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.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.000018.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.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）模型建立为非负整数iijkijijikiihajdahtshB,4,3,2,1,..min11为非负整数iijjjijkijijikiikijjjijihakiwlaLWjdahhBtswlahLWB,,..,1,4,..,1,..min11141（4）模型求解木板S1的数量P1的数量P2的数量P3的数量P4的数量木板利用率备注3594616270.9964每块木板切割方案相同合计数量：___359____774215316231614木板总利用率:__0.9964__木板总利用率=问题五（1）算法分析根据第四题所得分割方案，建立数学模型进行求解。（2）模型建立为非负整数iijjjjijkijijikijijjhakiwlaLWdahtsac,,...,1,..max411141（3）模型求解木板S1的数量P1的数量P2的数量P3的数量P4的数量利润（元）木板利用率备注100590001174.10.982979每块木板切割方案相同木板S1合计数量100总利润:1174100木板总利用率:_0.982979_木板总利用率进一步讨论结果表示，分析与检验误差分析上述问题求得的只是近似解，可能还有优化的空间，目前还没有发现此类解决NP问题一劳永逸的算法