切割板材问题

1、板材切割问题摘要把较大的矩形板材切割成若干个不同规格大小的矩形板材零件的问题，在工程技 术和工业生产中有着重要和广泛的应用。一个好的切割方案首先应该使板材的利用率最大，从而减少损失，降低成本，提 高经济效益。其次要求所采用的不同的切割方式尽可能少。因为在生产中转换切割方式 需要费用和时间，既提高成本，又降低效率。此外，每种零件有各自的交货时间，每天 零件的数量又受到企业生产能力的限制。因此在生产能力容许的条件下，以最少数量的 板材，尽可能按时完成需求任务，同时切割方式数也尽量地小.第一阶段：分析板材切割方案，此题中我们给出了横向和纵向分割两种方案；第二阶段：编制程序（MATLAB,求得板材切割

2、后所得规格型号的最大数量以及剩 余板材的长和宽；第三阶段：根据我们给定的最优方案的假设利用回溯技术依次处理每块余材料，统 计所得数据；问题解答如下：规格型号所需原板材数（块）总计（块）利用率1124287.5%26319435260关键词：利用率横向切割纵向切割MATLAB 回溯技术一问题重述某装饰公司在装饰工程施工过程中，需从长、宽分别为x, y的矩形原料板材上切割出长、宽分别为x，yi i 1,2,|,k共k种规格不同的矩形装饰板，每种装饰板所需数量 分别为ni,n2,|,nk块。由于工艺条件的限制，板材每次切割时都是沿直线裁成两块。请给出相应的切割方案及切割的算法，使购买的原料板材的数量

3、尽可能少。用你所设计的算法，对下列数据给出具体的切割方案，计算需要购买多少原料板材， 并计算板材的利用率。原料板规格：长3m,宽2ml装饰板规格：规格型号长（m宽（m需要数量（块）12.050.406021.650.357031.351.304041.200.506550.850.207560.350.20130二基本假设1、对最优分割方案的基本假设：以分割后所得规定型号的装饰板材数最大，当几种分 割方案所得型号的装饰板材数相同时，以余材料块数最少为最优分割方案；2、对分割顺序的假设：选择以长的长度为标准，从大到小的顺序进行分割;三模型变量与变量说明x , y矩形原板材的长和宽；为，弘i 1,

4、2,|,k切割所得的k种不同规格的矩形装饰板的长和宽ni,n2, |,nka,b,a1,b1,a2,b2 m ntk种不同矩形装饰板所需数量剩余材料的长和宽长和宽的最终切割次数对应规格型号板材最终切割数量四模型分析装饰公司在装饰工程施工中要将长和宽分别为 x、y的矩形原料板材上切割出长、宽 分别为为, i 1,2,|,k共k种规格不同的矩形装饰板，且每种装饰板所需数量分别为 ni,n2,|“，nk 块。切割方案：首先，一块原料板材分割单一规格型号的装饰板的可能分割方案。分割方案有两种,一是横向切割，另一种是纵向切割。（程序见附录一）。横向切割方式有以下两种：9纵向切割方式有以下两种:（方式三）

5、时大矩形纵向切割.小并形织向放胃（方式四）过大矩格纵向切割,小拉形横向放瑞程序解释：一个大矩阵按照上面横向和纵向进行分割，做了一次分割以后，又对剩下的部分做 进一步的分割，分割方式仍为以上方式，直到将大矩阵分割完毕或剩余的部分不能进行 分割为止，分割操作才结束。程序执行完后即可得到一块原材料对特定规格型号的最终 切割数量及剩余材料长，宽及块数。由程序所得结果结合最优方案原则选择切割方式，并记录所得规格型号的数量和余 材料及对应的数量。以同样的分割方式考虑对余材料的处理。对原板材及分割后所得余料的分割的顺序 是以所给规格型号的长为标准，从大到小的顺序依次进行分割。记录所得对应规格型号 的装饰板材

6、的数量。五模型的建立与求解通过问题二建立具体的模型：将一块原材料（3m*2m按两种切割方式所切割得到对应规格型号的最多切割数量和余 材料及块数，并由基本假设得出最佳切割方式；见表格一下面对余材料处理，处理过后记录还差数量并由表格一得出下一规格型号还需要多 少原板材。见表格二最终所得处理结果：共需要42块板材，各型号所需板材数及利用率如下：规格型号所需原板材数（块）总计（块）利用率1124287.5%26319435260（利用率公式：所需板材数面积总和/总共所用板材数*100%）六模型评价与推广然而，如果该问题在所需规格型号较多时，所需记录的数据量较多，易混杂。该模 型的优点在于能很好的处理材

7、料（原材料及余材料）的分割方式，采用回溯法处理便于 理解。该模型除可用于装饰板切割外可用于多种方面，比如钢板、玻璃、印刷电路板、包装纸七参考文献1谭汉松 论文板材最优切割算法的设计与实现J 2002年5月；2刘卫国 MATLA程序设计与应用第二版M高等教育出版社2006年7月;附录:附录%1 纵向切割x=input（'请输入x的值：）；y=input（'请输入y的值：）；x1=input（请输入x1 的值：）;y1=input（请输入y1 的值：）;%a,b,a1,b1,a2,b2为剩余材料的长和宽；%其中余材料a1,b1 的块数为m， a2,b2 的块数为 n；%m n为长和

8、宽的最终切割次数；%t为该规格型号板材最终切割数量a2=0;b2=0;m=fix（x/x1）; n=fix（y/y1）;if m=0disp（ 此种切割方法不可行）;enda=x-m*x1;b=y;a1=x1;b1=y-n*y1;disp（a1,b1,m）;t=n*m;n=fix（b/x1）;m=fix（a/y1）;if n=0&m=0a2=a-m*y1;b2=x1;b=b-n*x1;t=t+n*m;disp（t,a,b,a2,b2,n）;elsedisp（t,a,b）;end%2 横向切割x=input（'请输入x的值：）；y=input（'请输入y的值：）；x1=i

9、nput（请输入x1 的值：）;y1=input（请输入y1 的值：）;a2=0;b2=0;n=fix(y/x1);if n=0disp('此种方法不可行);endm=fix(x/y1);a=y-n*x1;b=x;a1=x1;b1=x-m*y1;disp(a1,b1,n);t=n*m;n=fix(b/x1);m=fix(a/y1);if n=0&m=0a2=a-m*y1;b2=x;a=y1;b=b-n*x1;t=t+n*m;disp(t,a2,b2,a,b,m);elsedisp(t,a,b);end附录表格一:一块原料板材分割单一规格型号的装饰板的可能分割方案及最佳分割方案规

10、 格 型 号切割 力式最多切割 数量余材料最佳 切割 力式需要数量需要原材 料数量1长（m）宽(m块数6012纵向切割520.951V横向切割00002纵向切割81.350.351701.650.211.650.31横向切割91.650.21V1.350.3513纵向切割21.350.724020.31横向切割21.350.41V30.6514纵向切割90.80.61V651.2P 0.1 11横向切割830.310.60.515纵向切割340.450.31V750.850.052横向切割3330.110.450.216纵向切割850.250.21V130横向切割8330.0510.20.21

11、附录表格二:规格型号一处理完后，剩余材料为 12块长2 (mj)宽0.95 ( m)其余材料处理后的结果如下:规格 型号切割 方式最多切割数量余材料rru攵 数量还差 数量rru攵 原材料 数量2长（nm宽(nm块 数纵向切割241.650.25127046620.3512横向切割00003纵向切割00004040横向切割00004纵向切割00006565横向切割00005纵向切割120.80.251275510.850.0512120.350.1120.850.1512横向切割00006纵向切割240.350.05241301060.250.112横向切割0000规格型号二处理完后，剩余材料

12、为5块长1.65 (m)宽0.2 (m)、5块长1.35 (m)宽0.35(mj)、1 块长 2(m) 宽 1.35 (m、1 块长 1.65 (mj)宽 1.65 (mj)其余材料处理后的结果如下：规格型号切割方式最多切割数量余材料需要 数量还差 数量还需要 原材料 数量长(mm宽(nm块数193纵向切割10.50.05140381.350.651横向切割11.350.7111.350.3514纵向切割11.20.21656400.70.151横向切割00005纵向切割50.80.25513950.850.15550.50.35510.850.15110.50.351横向切割00006纵向切

13、割100.20.15106830.250.11200001000横向切割120.350.16规格型号3处理完后，剩余原材料为19块长1.35 (m宽0.4 (m、19块长3 (mj)宽0.65 (m)其余材料处理后的结果如下：规格型号切割方式最多切割 数量余材料需要 数量还差 数量还需要 原材料 数量长(mm宽(nm块数4纵向切割1381.20.1538642630.650.619横向切割00005纵向切割1°0003939横向切割00006纵向切割0000837横向切割760.350.05190.650.05190.30.219规格型号4处理完后，剩余原材料为1块长3 (m)宽0.3(mj)、1块长0.6 (m)宽0.5(mj)、2块长 0.8 (mi)宽 0.6 (m、2 块长 1.2 (mj)宽 0.1 (mj)其余材料处理后的结果如下:规格型号切割方式最多切割数 量余材