切割板材問題

1、板材切割問題摘要把較大的矩形板材切割成若干個不同規(guī)格大小的矩形板材零件的問題，在工程技 術和工業(yè)生產中有著重要和廣泛的應用。一個好的切割方案首先應該使板材的利用率最大，從而減少損失，降低成本，提 高經濟效益。其次要求所采用的不同的切割方式盡可能少。因為在生產中轉換切割方式 需要費用和時間，既提高成本，又降低效率。此外，每種零件有各自的交貨時間，每天 零件的數(shù)量又受到企業(yè)生產能力的限制。因此在生產能力容許的條件下，以最少數(shù)量的 板材，盡可能按時完成需求任務，同時切割方式數(shù)也盡量地小第一階段：分析板材切割方案，此題中我們給出了橫向和縱向分割兩種方案；第二階段：編制程序（MATLAB,求得板材切割后

2、所得規(guī)格型號的最大數(shù)量以及剩 余板材的長和寬；第三階段：根據(jù)我們給定的最優(yōu)方案的假設利用回溯技術依次處理每塊余材料，統(tǒng) 計所得數(shù)據(jù)；問題解答如下：規(guī)格型號所需原板材數(shù)（塊）總計（塊）利用率1124287.5%26319435260關鍵詞：利用率橫向切割縱向切割MATLAB 回溯技術一問題重述某裝飾公司在裝飾工程施工過程中，需從長、寬分別為x,y的矩形原料板材上切割出長、寬分別為x，W i 1,2,川,k共k種規(guī)格不同的矩形裝飾板，每種裝飾板所需數(shù)量 分別為m,n2,川,氐 塊。由于工藝條件的限制，板材每次切割時都是沿直線裁成兩塊。請給出相應的切割方案及切割的算法，使購買的原料板材的數(shù)量盡可能少

3、。用你所設計的算法，對下列數(shù)據(jù)給出具體的切割方案，計算需要購買多少原料板材， 并計算板材的利用率。 原料板規(guī)格：長3m,寬2m 裝飾板規(guī)格：規(guī)格型號長（m寬（m需要數(shù)量（塊）12.050.406021.650.357031.351.304041.200.506550.850.207560.350.20130二基本假設1、對最優(yōu)分割方案的基本假設：以分割后所得規(guī)定型號的裝飾板材數(shù)最大，當幾種分 割方案所得型號的裝飾板材數(shù)相同時，以余材料塊數(shù)最少為最優(yōu)分割方案；2、對分割順序的假設：選擇以長的長度為標準，從大到小的順序進行分割;三模型變量與變量說明矩形原板材的長和寬;ni,匕,川,nka,b,a1

4、,b1,a2,b2m nt種不同矩形裝飾板所需數(shù)量xi,yi i 1,2,川,k切割所得的k種不同規(guī)格的矩形裝飾板的長和寬剩余材料的長和寬長和寬的最終切割次數(shù)對應規(guī)格型號板材最終切割數(shù)量四模型分析裝飾公司在裝飾工程施工中要將長和寬分別為 x、y的矩形原料板材上切割出長、寬 分別為Xi，yi i 1,2，川,k共k種規(guī)格不同的矩形裝飾板，且每種裝飾板所需數(shù)量分別 為m,n2,|沁塊。切割方案：首先，一塊原料板材分割單一規(guī)格型號的裝飾板的可能分割方案。分割方案有兩種,一是橫向切割，另一種是縱向切割。（程序見附錄一）。橫向切割方式有以下兩種：9縱向切割方式有以下兩種:（方貳三）對女矩形縱向助割,（方

5、式四）時大期形縱向切割,小妙形縱問放腎程序解釋:一個大矩陣按照上面橫向和縱向進行分割，做了一次分割以后，又對剩下的部分做 進一步的分割，分割方式仍為以上方式，直到將大矩陣分割完畢或剩余的部分不能進行 分割為止，分割操作才結束。程序執(zhí)行完后即可得到一塊原材料對特定規(guī)格型號的最終 切割數(shù)量及剩余材料長，寬及塊數(shù)。由程序所得結果結合最優(yōu)方案原則選擇切割方式，并記錄所得規(guī)格型號的數(shù)量和余 材料及對應的數(shù)量。以同樣的分割方式考慮對余材料的處理。對原板材及分割后所得余料的分割的順序 是以所給規(guī)格型號的長為標準，從大到小的順序依次進行分割。記錄所得對應規(guī)格型號 的裝飾板材的數(shù)量。五模型的建立與求解通過問題二

6、建立具體的模型：將一塊原材料（3m*2n）按兩種切割方式所切割得到對應規(guī)格型號的最多切割數(shù)量和余 材料及塊數(shù)，并由基本假設得出最佳切割方式；見表格一下面對余材料處理，處理過后記錄還差數(shù)量并由表格一得出下一規(guī)格型號還需要多 少原板材。見表格二最終所得處理結果：共需要42塊板材，各型號所需板材數(shù)及利用率如下:規(guī)格型號所需原板材數(shù)（塊）總計（塊）利用率1124287.5%26319435260（利用率公式：所需板材數(shù)面積總和/總共所用板材數(shù)*100%）六模型評價與推廣然而，如果該問題在所需規(guī)格型號較多時，所需記錄的數(shù)據(jù)量較多，易混雜。該模 型的優(yōu)點在于能很好的處理材料（原材料及余材料）的分割方式，采

7、用回溯法處理便于 理解。該模型除可用于裝飾板切割外可用于多種方面，比如鋼板、玻璃、印刷電路板、包裝紙七參考文獻1譚漢松 論文板材最優(yōu)切割算法的設計與實現(xiàn)J 2002年5月；2劉衛(wèi)國 MATLABS序設計與應用第二版M高等教育出版社2006年7 月;附錄:附錄%1 縱向切割x=input('請輸入x的值：);y=input('請輸入y的值：);x1=input(請輸入 x1 的值：' );y1=input(請輸入 y1 的值：' );%a,b,a1,b1,a2,b2為剩余材料的長和寬；%其中余材料 a1,b1 的塊數(shù)為 m，a2,b2的塊數(shù)為 n；%m n為長和寬

8、的最終切割次數(shù)；%t為該規(guī)格型號板材最終切割數(shù)量a2=0;b2=0;m=fix(x/x1); n=fix(y/y1);if m=0disp( 此種切割方法不可行' );end a=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=0 a2=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的值

9、：);x1=input(請輸入 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=0 a2=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、一規(guī)格型號的裝飾板的可能分割方案及最佳分割方案規(guī) 格 型 號切割 方式最多切割 數(shù)量余材料最佳 切割 方式需要數(shù)量需要原材 料數(shù)量1長（m寬（m塊數(shù)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.11橫向切割830.310.60.515縱向切割340.450.31V750.850.052橫向切割3330.110.450.216縱向切割850.250.21V1

11、30橫向切割833P 0.05 ”10.20.21附錄表格二:規(guī)格型號一處理完后，剩余材料為12塊長2 ( m寬0.95( m其余材料處理后的結果如下:規(guī)格型號切割 方式最多切割數(shù)量余材料需要數(shù)量還差 數(shù)量需要 原材料 數(shù)量2長(m寬(m塊 數(shù)縱向切割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規(guī)

12、格型號二處理完后，剩余材料為5塊長1.65 (m 寬0.2 (m、5塊長1.35 (m 寬0.35(m、i 塊長 2( m 寬 1.35( m、1 塊長 1.65 ( m 寬 1.65( m其余材料處理后的結果如下：規(guī)格 型號切割方式最多切割數(shù)量余材料需要 數(shù)量還差 數(shù)量還需要 原材料 數(shù)量長(m寬(m塊數(shù)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橫向切割0

13、0006縱向切割100.20.15106830.250.11200001000橫向切割120.350.16規(guī)格型號3處理完后，剩余原材料為19塊長1.35( m寬0.4( m、19塊長3(m寬0.65 (m其余材料處理后的結果如下：規(guī)格型號切割方式最多切割數(shù)量余材料需要 數(shù)量還差 數(shù)量還需要 原材料 數(shù)量長(m 寬(m塊數(shù)4縱向切割：381.20.1538642630.650.619橫向切割00005縱向切割0003939橫向切割00006縱向切割0000837橫向切割760.350.05190.650.05190.30.219規(guī)格型號4處理完后，剩余原材料為i塊長3(m寬0.3(m、i塊長0.6(m寬0.5(m、2塊長 o.8(m 寬 o.6( m、2 塊長 1.2(m 寬 o.i (m其余材料處理后的結果如下：規(guī)格型號切割方式最多切割數(shù)量余