《板材下料问题.doc》由会员分享，可在线阅读，更多相关《板材下料问题.doc（14页珍藏版）》请在三一文库上搜索。
1、板材玻璃的下料问题摘要“下料问题（cutting stock problem）”就是指在给定板材宽度和长度的情况下，如何将具有一定种类和数量的矩形件排放到板材上，使所需的板材数量最少的问题，该问题广泛存在于工业生产中。本文运用优化理论，建立了矩形件优化排样数学模型，并提出了基于启发式算法的一刀切约束条件下二维板材下料算法。关键词 下料 二维下料问题 优化 启发式算法 矩形件排样 一刀切 一、 问题的重述在大型建筑工程中，需要大量使用玻璃材料，如门窗等。在作材料预算时，需要求出原材料的张数。已知板材玻璃原材料和下料后的成品均为矩形。由于玻璃材料的特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或
2、者停顿，即每切一刀均将玻璃板一分为二。切割次序和方法的不同、各种规格搭配（即下料策略）不同，材料的消耗将不同。工程实际需要解决如下问题，在给定一组材料规格尺寸后：（1） 在原材料只有一种规格的情况下（例如长为2100cm，宽为1650），给出最优下料策略，此时所需要材料张数最小。（2） 在原材料为两种规格的情况下（例如2100cm*1650cm和2000cm1500cm），给出最优下料策略，使所需材料的张数最小，且利用率（实际使用总面积与原材料总面积之比）尽量高。（3） 下表是一些成品料及所需块数（长宽块数）分别以一种原材料2100cm1650cm及两种原材料规格2100cm1650cm,20
3、00cm1500cm为例，分别给出（1）和（2）的算法及数字结果，并给出两种情况下的利用率。二、问题的分析本问题属于二维下料问题，该问题已被证明为是NP完全问题。由于任何NP完全问题都不能用任何已知的多项式算法求解，所以我们建立一个排样的算法模型。由题目要求该算法首先要满足生产工艺，即要满足“一刀切”，即从板材的一端，沿直线方向切割到另一端。其次下料方案应该使原材料的利用率大，从而降低生产成本，提高经济效益。再次应该使用最少的下料方式，可以节省在生产过程因转换下料方式而产生的时间和费用的浪费，提高生产效率。三、模型的假设（一） 切割玻璃时，刀具只能走直线，且中间不能拐弯或者停顿（二） 矩形件允
4、许任意摆放（三） 要求加工矩形件无顺序（四） 切割矩形件时长和宽要与原材料的长和宽平行（五） 不考虑切割时的产生的损耗（六） 矩形件不能重叠，不超过原材料的大小四、符号的说明符号表示意义规格为2100cm1650cm的原材料的长规格为2100cm1650cm的原材料的宽规格为2000cm1500cm的原材料的长规格为2000cm1500cm的原材料的宽矩形件的长，i=1，2，26矩形件的宽，i=1，2，26矩形件的数量，i=1，2，26所需原材料的块数有两种规格原材料是，所需规格为2100cm1650cm原材料的块数有两种规格原材料是，所需规格为2000cm1500cm原材料的块数只有一种原材
5、料的利用率有两种原材料的利用率表示第一块板材的使用数量指在消耗第一块料板的数量为=i时，所生产的第j种产品的数量指所需生产的第j种商品的总量ki所需的第二块板的数量所需要的第i块板的总数量五、模型的建立与求解5.1 综述从理论上看，该类问题属于具有最高计算复杂性的优化计算问题即NP完全问题。对于这类问题，以目前已成熟的计算理论和算法，或者根本无法求解，或者求解的计算量是爆炸性的。本文从现有算法中，总过比较分析，找到一种基于优化排列的启发式算法。通过实际排列和比对，可以达到较高的原材料利用率，符合实际生产过程的要求。5.2 一种原材料规格下的二维下料算法 本问题属于NP完全问题，有现有理论知NP
6、完全问题问题具有以下的性质：(1)任何NP完全问题都不能用任何已知的多项式算法求解；(2)若任何一个NP完全问题具有多项式算法，则一切NP完全问题都有多项式算法。基于上述理论通过查阅资料知该问题是属于离散优化问题，归为背包问题一类，背包算法的特点是算法简单，但只是针对数量较多，种类较少的矩形件排样，当矩形件的尺寸差异较大时，并不适合采用该算法。所以我们采用启发式算法。5. 21 优化排样 本文利用计算机模拟，采用优化排样的方法，对所有矩形件进行排样，算出最少的原材料张数。在矩形件优化排样中，待排矩形件的排列先后顺序、矩形件与矩形件之间的排放方式以及矩形件与板材之间的相对排放位置都是十分重要的。
7、本排样算法应用的相应规则如下：（1）排列先后规则：通过比较待排矩形件的面积来建立定序规则，即根据待排矩形件的面积递减的顺序进行排样，它对最终排样结果有着重要的影响。（2）定位规则：确定被选待排矩形件在布局空间中的摆放位置。本算法采用的是占角策略，即将待排矩形件摆放在板材的某一角，采用的是先占左下脚的定位规则。（3）排布规则：矩形件在板材上有沿板材长度方向的横排和竖排、沿板材宽度方向的横排和竖排共4种方式，如图。本算法采用沿宽度方向的横排和竖排的方式。通过计算排后板材剩余边界距离大小来决定横排或竖排。 沿长度方向横排 沿长度方向纵排 沿宽度方向横排 沿宽度方向纵排5.2.2问题一的数学模型 设板
8、材长为L,宽为W，且LW，板材数量不记。第k种矩形件的长为,宽为数量为面积为（1ik），所需要的板材总数为N，则优化的目标函数为，同时每张板材的利用率也要符合工业生产的要求。5.2.3模型的求解我们借助于计算机模拟排样过程，求解出所需的最小张数，模拟过程如下：（一） 将所有的矩形件按从大到小排列并保存，从中找出一个未排的面积最大的矩形件，放在已知板材的左下角。（二） 确定排放方式：按照沿宽度方向排列横排和纵排的原则。设置一下四个参数：A=mod(W, ) B=mod(W, )C=floor(W, ) D=floor(W, )分为一下四种情况：（1） C1，D1此时矩形件横排纵排均可，接着看怎么
9、样排剩余边界距离小，如果BA，同时L则说明沿着宽度方向纵排剩余边界面积小于沿着宽度方向横排，所以采用纵排，反之横排。（2） C1，D1，L则采用纵排（3） C1，D1 L则采用横排（4） C1，D1则无法排列区域1区域2已放排完上述矩形件后，板材被分为三大部分如图 已放区域，未放区域1、未放区域2，这时区域1、区域2被看做新的板材。（三） 再次扫描矩形件，重复（一）（二），直至所有的矩形件被排列完成。输出排样结果。用上述方法对26种矩形件进行排样后，的下列数据：序号利用率序号利用率序号利用率序号利用率178.16%15192.02%30196.33%45186.88%278.16%15292.
10、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%46084.31%1178.1
11、6%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%
12、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%178
13、92.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
14、.00%3778.16%18792.02%33794.06%48782.00%3878.16%18892.02%33894.06%48882.00%3978.16%18992.02%33994.06%48982.00%4078.16%19092.02%34094.06%49082.00%4178.16%19192.02%34193.97%49182.00%4278.16%19292.02%34294.10%49282.00%4378.16%19392.02%34394.10%49382.00%4478.16%19492.02%34494.10%49482.00%4578.16%19592.02
15、%34594.10%49582.00%4678.16%19692.02%34694.10%49682.00%4778.16%19792.02%34794.10%49782.00%4878.16%19892.02%34894.10%49882.00%4978.16%19988.96%34994.10%49974.89%5095.37%20088.96%35094.10%50082.12%5195.37%20188.96%35194.10%50182.12%5295.37%20288.96%35294.10%50282.12%5395.37%20388.96%35394.10%50382.12%5
16、495.37%20488.96%35494.10%50482.12%5595.37%20588.96%35594.10%50582.12%5695.37%20688.96%35694.10%50682.12%5795.37%20788.96%35794.10%50782.12%5895.37%20888.96%35894.10%50882.12%5995.37%20988.96%35994.10%50982.12%6095.37%21088.96%36094.10%51082.12%6195.37%21188.96%36194.10%51182.12%6295.37%21288.96%3629
17、4.10%51282.12%6395.37%21387.85%36394.10%51382.12%6495.37%21487.85%36494.10%51482.12%6595.37%21587.85%36594.10%51582.12%6695.37%21687.85%36694.10%51682.12%6795.37%21787.85%36794.10%51782.12%6895.37%21887.85%36894.10%51882.12%6995.37%21987.85%36994.10%51981.76%7095.37%22087.85%37094.10%52078.16%7195.3
18、7%22187.85%37194.10%52178.16%7295.37%22281.54%37294.10%52278.16%7395.37%22378.38%37394.10%52378.16%7495.37%22478.38%37494.10%52478.16%7595.37%22578.38%37592.89%52578.16%7695.37%22678.38%37692.89%52678.16%7795.37%22778.38%37792.89%52778.16%7895.37%22878.38%37892.89%52878.16%7995.37%22978.38%37992.89%
19、52978.16%8095.37%23078.38%38092.89%53078.16%8195.37%23178.38%38192.89%53178.16%8295.37%23278.38%38292.89%53278.16%8395.37%23378.38%38392.89%53378.16%8495.37%23478.38%38492.89%53478.16%8595.37%23578.38%38592.89%53578.16%8695.37%23678.38%38692.89%53678.16%8795.37%23778.38%38792.89%53778.12%8895.37%238
20、78.38%38892.89%53878.01%8995.37%23978.38%38992.89%53978.01%9095.37%24078.38%39092.89%54078.01%9195.37%24178.38%39192.89%54178.01%9295.37%24278.38%39292.89%54278.01%9395.37%24393.67%39392.89%54378.01%9495.37%24496.33%39492.89%54478.01%9595.37%24596.33%39592.89%54578.01%9695.37%24696.33%39692.89%54678
21、.01%9795.37%24796.33%39792.89%54778.01%9895.37%24896.33%39892.89%54878.01%9983.47%24996.33%39992.89%54978.01%10083.47%25096.33%40092.89%55078.01%10183.47%25196.33%40192.89%55178.01%10283.47%25296.33%40292.89%55278.01%10383.47%25396.33%40392.89%55378.01%10482.98%25496.33%40492.89%55478.01%10582.24%25
22、596.33%40592.89%55578.01%10682.24%25696.33%40671.92%55678.01%10782.24%25796.33%40766.80%55778.01%10882.24%25896.33%40866.80%55878.01%10982.24%25996.33%40966.80%55978.01%11084.46%26096.33%41066.80%56078.01%11192.30%26196.33%41166.80%56178.01%11292.30%26296.33%41266.80%56278.01%11392.30%26396.33%41366
23、.80%56378.01%11492.30%26496.33%41466.80%56478.01%11592.30%26596.33%41566.80%56578.01%11692.30%26696.33%41666.80%56678.01%11792.30%26796.33%41766.80%56778.01%11892.30%26896.33%41866.80%56878.01%11992.30%26996.33%41966.80%56978.01%12092.30%27096.33%42066.80%57078.01%12192.30%27196.33%42166.80%57178.01
24、%12292.30%27296.33%42266.80%57278.01%12392.30%27396.33%42390.80%57373.72%12492.30%27496.33%42490.80%57477.75%12592.30%27596.33%42590.80%57577.75%12692.30%27696.33%42690.80%57677.75%12792.30%27796.33%42789.33%57777.75%12892.30%27896.33%42887.53%57877.75%12992.30%27996.33%42987.53%57977.75%13092.30%28
25、096.33%43087.53%58077.75%13192.30%28196.33%43187.53%58177.75%13292.30%28296.33%43287.53%58277.75%13392.30%28396.33%43387.53%58377.75%13492.30%28496.33%43487.53%58477.75%13592.30%28596.33%43587.53%58577.75%13692.30%28696.33%43687.53%58677.75%13792.30%28796.33%43787.53%58777.75%13892.30%28896.33%43887
26、.53%58877.75%13992.30%28996.33%43987.53%58977.75%14092.30%29096.33%44087.53%59077.75%14192.30%29196.33%44187.53%59177.75%14292.30%29296.33%44287.53%59277.75%14392.30%29396.33%44387.53%59377.75%14492.30%29496.33%44487.53%59477.75%14592.30%29596.33%44587.53%59577.75%14692.30%29696.33%44687.53%59677.75
27、%14792.21%29796.33%44787.53%59745.35%14892.02%29896.33%44887.53%14992.02%29996.33%44987.40%15092.02%30096.33%45086.88%通过上述计算求得利用率为：通过计算解得，在原材料只有一种规格2100cm1650cm的情况下，用单一下料两个方向排料优选的方法需要原材料597块，原材料的利用率为87.22%.5.3 两种原材料规格下的二维下料算法由第一问所建模型可以求出当料板为一块板材时的最有效下料策略，并求出所需的最小料板张数。现在，原材料有两种规格，问题主要体现在两种规模的原材料各用多少才
28、可以取到最优解。对此，我们可以利用第一问所建模型，通过多次限制一类料板的数量，将此类料板先切割完毕，然后通过切割另一类料板，生产余下的还未生产的成品。求出所需总共用的料板数，然后将这多次切割所得出的总料板数进行比较，取得最少的切割料板数，即为最优下料策略。所以建立数学模型如下：设为第1块板的数量，现分别令=i（i=1,2,3），利用第一问所建模型，求出在第一块料板的数量为的情况下可以生产的各种产品的产量为 (j=1,2,3)，（指在消耗第一块料板的数量为=i时，所生产的第j种产品的数量）则需要第二块料板生产的产品为所需生产的产品的总量（j=1,2,3）（指所需生产的第j种商品的总量）减去以生产
29、的各种产品的生产量，即xij=xj-，利用第一问所建模型，求出生产xij所需的第二块板的数量ki，则在第一块板的数量为的情况下，所需的总共板数位=+ki。取i=1,2,3直到只利用第一块板即可生产出所有的产品为止。则取m=min()(i=1,2,3)为最优解。同时若有多个值可以取得最小值，则通过判断利用率来判断哪个方式为最优解。即六、模型结果的分析在有一种规格2100cm1650cm原材料的情况下，需要规格为2100cm1650cm的原材料597块，原材料的利用率为87.22%。在有两种规格2100cm1650cm和2000cm1500cm原材料的情况下，需要规格为2100cm1650cm的原
30、材料594块，需要规格为2000cm1500cm的原材料3块，总共597块，原材料的利用率为87.28%。有结果看，两次实际使用的板材总数量一致，这与两块板形状基本相同有着密切关系，但第二次的利用率要高，这是因为总数一致，但第二块板面积要小。这应该是在本算法条件下得出的最优下料策略。七、模型的评价与补充7.1 模型的评价显然，本文采用启发式算法，对玻璃板材的最优下料策略进行分析计算的方法是基本成功的。事实上，对于一般的二维下料（板材下料）问题，均可以采用该方法进行下料排解。求出最少原材料的张数。7.1.1模型的优点简单易行，速度快且能够融合各种限制条件和具体目标，因此在实际生产排样中有着更广泛
31、的应用。7.1.2模型的缺点 只是一种近似求解，划分区域过程过于单一，没有考虑其他划分方式更适合一些矩形件的放置，从而减低板材数量，提高利用率八、模型的改进和推广优化下料，就是要提高原材料的利用率，降低生产成本，是国内外非常活跃的研究课题。板材玻璃的下料问题就属于这一类常见的二维下料问题，二位下料问题就是如何将矩形原材料切割成所需的零件，使所需要的原材料最少，利用率最高，其中钢板，木板等的剪切下料也属于此类下料问题。因此本模型可以推广到很多很多生产领域。参考文献1 钱颂迪.运筹学第三版. 北京:清华大学出版社2005.62 杨启凡.数学建模.北京：高等教育出版社 2005.63 朱道元.数学建
32、模案例精选.北京：科学技术出版社 2003.34001036x(2009)05-001204 吕俊丰，马岩，喻虎德 人造板一刀切数控下锯优化的编程模型研究 木材加工机械 2009年第5期：1215 2006-045附录：1.1 问题一的主程序源代码clc,clear;L1=2100;W1=1650;L2=2000;W2=1500;paper=0;SIZE=L1,W1;V=;P=;S=0;z=1;Q=0;A=865 857 98 ; 857 715 98 ; 804 746 196; 857 675 28 ; 857 665 28 ; 804 663 224; 804 661 308; 804
33、639 84 ; 804 631 56 ; 804 563 224; 804 536 196; 804 535 392; 804 551 392; 865 446 98 ; 762 446 196; 715 446 98 ; 680 446 224; 675 446 28 ; 667 446 28 ; 655 446 84 ; 647 446 56 ; 667 426 308; 580 446 224; 552 446 196; 551 446 392; 527 426 392;while sum(A(:,3)=0 while isempty(SIZE) = 0 if zsum(A(:,3)0
34、) z=1; SIZE(1,:)=; end if isempty(SIZE) = 1 break; end if sum(A(:,3)=0 break; end b=paixu(A,z); x=xingzhuang(SIZE(1,1),SIZE(1,2),b); if x=0 P=P,x; S=S+b(1)*b(2); for i=1:length(A) if A(i,1)=b(1)&A(i,2)=b(2) A(i,3)=A(i,3)-1; z=1; break; end end SIZE1=pailie(b,SIZE(1,:),x); SIZE(1,:)=; SIZE=SIZE;SIZE1
35、; else z=z+1; end end Q=Q+sum(P0); paper=paper+1; SIZE=L1,W1; V=V,S/(L1*W1); P=; S=0;endVpaper1.2 问题二的主程序源代码clc,clear;L1=2100;W1=1650;L2=2000;W2=1500;paper=0;SIZE=L2,W2;U=1;P=;V=;S=0;z=1;Q=0;A=865 857 98 ; 857 715 98 ; 804 746 196; 857 675 28 ; 857 665 28 ; 804 663 224; 804 661 308; 804 639 84 ; 804
36、 631 56 ; 804 563 224; 804 536 196; 804 535 392; 804 551 392; 865 446 98 ; 762 446 196; 715 446 98 ; 680 446 224; 675 446 28 ; 667 446 28 ; 655 446 84 ; 647 446 56 ; 667 426 308; 580 446 224; 552 446 196; 551 446 392; 527 426 392;while sum(A(:,3)=0 while isempty(SIZE) = 0 if zsum(A(:,3)0) z=1; SIZE(1,:)=; end if isempty(SIZE) = 1 break; end if sum(A(:,3)=0 break; end b=paixu(A,z); x=xingzhuang(SIZE(1,1),SIZE(1,2),b); if x=0 P=P,x; S=S+b(1)*b(2); for i=1:length(A) if A(i,1)=b(1)&A(i,2)=b(2) A(i,3)=A(i,3)-1; z=1; break; end end SIZE1=pailie(b,SIZE(1,:),x); SIZE(1,:)=; SIZE=SIZE;SIZE1;