板材下料问题

1、精选优质文档-倾情为你奉上板材玻璃的下料问题摘要“下料问题（cutting stock problem）”就是指在给定板材宽度和长度的情况下，如何将具有一定种类和数量的矩形件排放到板材上，使所需的板材数量最少的问题，该问题广泛存在于工业生产中。本文运用优化理论，建立了矩形件优化排样数学模型，并提出了基于启发式算法的一刀切约束条件下二维板材下料算法。关键词 下料 二维下料问题 优化 启发式算法 矩形件排样 一刀切 一、 问题的重述在大型建筑工程中，需要大量使用玻璃材料，如门窗等。在作材料预算时，需要求出原材料的张数。已知板材玻璃原材料和下料后的成品均为矩形。由于玻璃材料的特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或者停顿，即每切一刀均将玻璃板一分为二。切割次序和方法的不同、各种规格搭配（即下料策略）不同，材料的消耗将不同。工程实际需要解决如下问题，在给定一组材料规格尺寸后：（1） 在原材料只有一种规格的情况下（例如长为2100cm，宽为1650），给出最优下料策略，此时所需要材料张数最小。（2） 在原材料为两种规格的情况下（例如2100cm*1650cm和2000cm1500cm）

2、，给出最优下料策略，使所需材料的张数最小，且利用率（实际使用总面积与原材料总面积之比）尽量高。（3） 下表是一些成品料及所需块数（长宽块数）分别以一种原材料2100cm1650cm及两种原材料规格2100cm1650cm,2000cm1500cm为例，分别给出（1）和（2）的算法及数字结果，并给出两种情况下的利用率。二、问题的分析本问题属于二维下料问题，该问题已被证明为是NP完全问题。由于任何NP完全问题都不能用任何已知的多项式算法求解，所以我们建立一个排样的算法模型。由题目要求该算法首先要满足生产工艺，即要满足“一刀切”，即从板材的一端，沿直线方向切割到另一端。其次下料方案应该使原材料的利用率大，从而降低生产成本，提高经济效益。再次应该使用最少的下料方式，可以节省在生产过程因转换下料方式而产生的时间和费用的浪费，提高生产效率。三、模型的假设（一） 切割玻璃时，刀具只能走直线，且中间不能拐弯或者停顿（二） 矩形件允许任意摆放（三） 要求加工矩形件无顺序（四） 切割矩形件时长和宽要与原材料的长和宽平行（五） 不考虑切割时的产生的损耗（六） 矩形件不能重叠，不超过原材料的大小四、符号的说明

3、符号表示意义规格为2100cm1650cm的原材料的长规格为2100cm1650cm的原材料的宽规格为2000cm1500cm的原材料的长规格为2000cm1500cm的原材料的宽矩形件的长，i=1，2，26矩形件的宽，i=1，2，26矩形件的数量，i=1，2，26所需原材料的块数有两种规格原材料是，所需规格为2100cm1650cm原材料的块数有两种规格原材料是，所需规格为2000cm1500cm原材料的块数只有一种原材料的利用率有两种原材料的利用率表示第一块板材的使用数量指在消耗第一块料板的数量为=i时，所生产的第j种产品的数量指所需生产的第j种商品的总量所需的第二块板的数量所需要的第i块板的总数量五、模型的建立与求解5.1 综述从理论上看，该类问题属于具有最高计算复杂性的优化计算问题即NP完全问题。对于这类问题，以目前已成熟的计算理论和算法，或者根本无法求解，或者求解的计算量是爆炸性的。本文从现有算法中，总过比较分析，找到一种基于优化排列的启发式算法。通过实际排列和比对，可以达到较高的原材料利用率，符合实际生产过程的要求。5.2 一种原材料规格下的二维下料算法 本问题属于NP完全

4、问题，有现有理论知NP完全问题问题具有以下的性质：(1)任何NP完全问题都不能用任何已知的多项式算法求解；(2)若任何一个NP完全问题具有多项式算法，则一切NP完全问题都有多项式算法。基于上述理论通过查阅资料知该问题是属于离散优化问题，归为背包问题一类，背包算法的特点是算法简单，但只是针对数量较多，种类较少的矩形件排样，当矩形件的尺寸差异较大时，并不适合采用该算法。所以我们采用启发式算法。5. 21 优化排样 本文利用计算机模拟，采用优化排样的方法，对所有矩形件进行排样，算出最少的原材料张数。在矩形件优化排样中，待排矩形件的排列先后顺序、矩形件与矩形件之间的排放方式以及矩形件与板材之间的相对排放位置都是十分重要的。本排样算法应用的相应规则如下：（1）排列先后规则：通过比较待排矩形件的面积来建立定序规则，即根据待排矩形件的面积递减的顺序进行排样，它对最终排样结果有着重要的影响。（2）定位规则：确定被选待排矩形件在布局空间中的摆放位置。本算法采用的是占角策略，即将待排矩形件摆放在板材的某一角，采用的是先占左下脚的定位规则。（3）排布规则：矩形件在板材上有沿板材长度方向的横排和竖排、沿板材宽

5、度方向的横排和竖排共4种方式，如图。本算法采用沿宽度方向的横排和竖排的方式。通过计算排后板材剩余边界距离大小来决定横排或竖排。 沿长度方向横排 沿长度方向纵排 沿宽度方向横排 沿宽度方向纵排5.2.2问题一的数学模型 设板材长为L,宽为W，且LW，板材数量不记。第k种矩形件的长为,宽为数量为面积为（1ik），所需要的板材总数为N，则优化的目标函数为，同时每张板材的利用率也要符合工业生产的要求。5.2.3模型的求解我们借助于计算机模拟排样过程，求解出所需的最小张数，模拟过程如下：（一） 将所有的矩形件按从大到小排列并保存，从中找出一个未排的面积最大的矩形件，放在已知板材的左下角。（二） 确定排放方式：按照沿宽度方向排列横排和纵排的原则。设置一下四个参数：A=mod(W, ) B=mod(W, )C=floor(W, ) D=floor(W, )分为一下四种情况：（1） C1，D1此时矩形件横排纵排均可，接着看怎么样排剩余边界距离小，如果BA，同时L则说明沿着宽度方向纵排剩余边界面积小于沿着宽度方向横排，所以采用纵排，反之横排。（2） C1，D1，L则采用纵排（3） C1，D1 L则采用横

6、排（4） C1，D1则无法排列区域1区域2已放排完上述矩形件后，板材被分为三大部分如图 已放区域，未放区域1、未放区域2，这时区域1、区域2被看做新的板材。（三） 再次扫描矩形件，重复（一）（二），直至所有的矩形件被排列完成。输出排样结果。用上述方法对26种矩形件进行排样后，的下列数据：序号利用率序号利用率序号利用率序号利用率178.16%15192.02%30196.33%45186.88%278.16%15292.02%30296.33%45286.47%378.16%15392.02%30396.33%45385.85%478.16%15492.02%30496.33%45485.24%578.16%15592.02%30596.33%45584.31%678.16%15692.02%30696.33%45684.31%778.16%15792.02%30796.33%45784.31%878.16%15892.02%30896.33%45884.31%978.16%15992.02%30994.06%45984.31%1078.16%16092.02%31094.06%4608

7、4.31%1178.16%16192.02%31194.06%46184.31%1278.16%16292.02%31294.06%46284.31%1378.16%16392.02%31394.06%46383.28%1478.16%16492.02%31494.06%46483.28%1578.16%16592.02%31594.06%46583.28%1678.16%16692.02%31694.06%46683.28%1778.16%16792.02%31794.06%46783.28%1878.16%16892.02%31894.06%46874.57%1978.16%16992.02%31994.06%46982.00%2078.16%17092.02%32094.06%47082.00%2178.16%17192.02%32194.06%47182.00%2278.16%17292.02%32294.06%47282.00%2378.16%17392.02%32394.06%47382.00%2478.16%17492.02%32494.06%47482.00%2578.16%17592.02%32594.06%47582.00%2678.16%17692.02%32694.06%47682.00%2778.16%17792.02%32794.06%47782.00%2878.16%17892.02%32894.06%47882.00%2978.16%17992.02%32994.06%47982.00%3078.16%18092.02%33094.06%48082.00%3178.16%18192.02%33194.06%48182.00%3278.16%18292.02%33294.06%48282.00%3378.16%18392.02%33394.06%48382.00%3478.16%18492.02%33494.06%48482.00%3578.16%18592.02%33594.06%48582.00%3678.16%18692.02%33694.06%48682.00%3778.16%18792.02%33794.06%48782.00%

《板材下料问题》由会员博****1分享，可在线阅读，更多相关《板材下料问题》请在金锄头文库上搜索。