板材下料問題

1、板材玻璃的下料問題摘要“下料問題（cutting stock problem）”就是指在給定板材寬度和長度的情況下，如何將具有一定種類和數(shù)量的矩形件排放到板材上，使所需的板材數(shù)量最少的問題，該問題廣泛存在于工業(yè)生產(chǎn)中。本文運用優(yōu)化理論，建立了矩形件優(yōu)化排樣數(shù)學(xué)模型，并提出了基于啟發(fā)式算法的一刀切約束條件下二維板材下料算法。關(guān)鍵詞 下料 二維下料問題 優(yōu)化 啟發(fā)式算法 矩形件排樣 一刀切 一、 問題的重述在大型建筑工程中，需要大量使用玻璃材料，如門窗等。在作材料預(yù)算時，需要求出原材料的張數(shù)。已知板材玻璃原材料和下料后的成品均為矩形。由于玻璃材料的特點，切割玻璃時，刀具只能走直線，且中間不能拐彎或

2、者停頓，即每切一刀均將玻璃板一分為二。切割次序和方法的不同、各種規(guī)格搭配（即下料策略）不同，材料的消耗將不同。工程實際需要解決如下問題，在給定一組材料規(guī)格尺寸后：（1） 在原材料只有一種規(guī)格的情況下（例如長為2100cm，寬為1650），給出最優(yōu)下料策略，此時所需要材料張數(shù)最小。（2） 在原材料為兩種規(guī)格的情況下（例如2100cm*1650cm和2000cm1500cm），給出最優(yōu)下料策略，使所需材料的張數(shù)最小，且利用率（實際使用總面積與原材料總面積之比）盡量高。（3） 下表是一些成品料及所需塊數(shù)（長寬塊數(shù)）分別以一種原材料2100cm1650cm及兩種原材料規(guī)格2100cm1650cm,20

3、00cm1500cm為例，分別給出（1）和（2）的算法及數(shù)字結(jié)果，并給出兩種情況下的利用率。二、問題的分析本問題屬于二維下料問題，該問題已被證明為是NP完全問題。由于任何NP完全問題都不能用任何已知的多項式算法求解，所以我們建立一個排樣的算法模型。由題目要求該算法首先要滿足生產(chǎn)工藝，即要滿足“一刀切”，即從板材的一端，沿直線方向切割到另一端。其次下料方案應(yīng)該使原材料的利用率大，從而降低生產(chǎn)成本，提高經(jīng)濟效益。再次應(yīng)該使用最少的下料方式，可以節(jié)省在生產(chǎn)過程因轉(zhuǎn)換下料方式而產(chǎn)生的時間和費用的浪費，提高生產(chǎn)效率。三、模型的假設(shè)（一） 切割玻璃時，刀具只能走直線，且中間不能拐彎或者停頓（二） 矩形件允

4、許任意擺放（三） 要求加工矩形件無順序（四） 切割矩形件時長和寬要與原材料的長和寬平行（五） 不考慮切割時的產(chǎn)生的損耗（六） 矩形件不能重疊，不超過原材料的大小四、符號的說明符號表示意義規(guī)格為2100cm1650cm的原材料的長規(guī)格為2100cm1650cm的原材料的寬規(guī)格為2000cm1500cm的原材料的長規(guī)格為2000cm1500cm的原材料的寬矩形件的長，i=1，2，26矩形件的寬，i=1，2，26矩形件的數(shù)量，i=1，2，26所需原材料的塊數(shù)有兩種規(guī)格原材料是，所需規(guī)格為2100cm1650cm原材料的塊數(shù)有兩種規(guī)格原材料是，所需規(guī)格為2000cm1500cm原材料的塊數(shù)只有一種原材

5、料的利用率有兩種原材料的利用率表示第一塊板材的使用數(shù)量指在消耗第一塊料板的數(shù)量為=i時，所生產(chǎn)的第j種產(chǎn)品的數(shù)量指所需生產(chǎn)的第j種商品的總量ki所需的第二塊板的數(shù)量所需要的第i塊板的總數(shù)量五、模型的建立與求解5.1 綜述從理論上看，該類問題屬于具有最高計算復(fù)雜性的優(yōu)化計算問題即NP完全問題。對于這類問題，以目前已成熟的計算理論和算法，或者根本無法求解，或者求解的計算量是爆炸性的。本文從現(xiàn)有算法中，總過比較分析，找到一種基于優(yōu)化排列的啟發(fā)式算法。通過實際排列和比對，可以達到較高的原材料利用率，符合實際生產(chǎn)過程的要求。5.2 一種原材料規(guī)格下的二維下料算法 本問題屬于NP完全問題，有現(xiàn)有理論知NP

6、完全問題問題具有以下的性質(zhì)：(1)任何NP完全問題都不能用任何已知的多項式算法求解；(2)若任何一個NP完全問題具有多項式算法，則一切NP完全問題都有多項式算法?；谏鲜隼碚撏ㄟ^查閱資料知該問題是屬于離散優(yōu)化問題，歸為背包問題一類，背包算法的特點是算法簡單，但只是針對數(shù)量較多，種類較少的矩形件排樣，當(dāng)矩形件的尺寸差異較大時，并不適合采用該算法。所以我們采用啟發(fā)式算法。5. 21 優(yōu)化排樣 本文利用計算機模擬，采用優(yōu)化排樣的方法，對所有矩形件進行排樣，算出最少的原材料張數(shù)。在矩形件優(yōu)化排樣中，待排矩形件的排列先后順序、矩形件與矩形件之間的排放方式以及矩形件與板材之間的相對排放位置都是十分重要的。

7、本排樣算法應(yīng)用的相應(yīng)規(guī)則如下：（1）排列先后規(guī)則：通過比較待排矩形件的面積來建立定序規(guī)則，即根據(jù)待排矩形件的面積遞減的順序進行排樣，它對最終排樣結(jié)果有著重要的影響。（2）定位規(guī)則：確定被選待排矩形件在布局空間中的擺放位置。本算法采用的是占角策略，即將待排矩形件擺放在板材的某一角，采用的是先占左下腳的定位規(guī)則。（3）排布規(guī)則：矩形件在板材上有沿板材長度方向的橫排和豎排、沿板材寬度方向的橫排和豎排共4種方式，如圖。本算法采用沿寬度方向的橫排和豎排的方式。通過計算排后板材剩余邊界距離大小來決定橫排或豎排。 沿長度方向橫排 沿長度方向縱排 沿寬度方向橫排 沿寬度方向縱排問題一的數(shù)學(xué)模型 設(shè)板材長為L,

8、寬為W，且LW，板材數(shù)量不記。第k種矩形件的長為,寬為數(shù)量為面積為（1ik），所需要的板材總數(shù)為N，則優(yōu)化的目標(biāo)函數(shù)為，同時每張板材的利用率也要符合工業(yè)生產(chǎn)的要求。模型的求解我們借助于計算機模擬排樣過程，求解出所需的最小張數(shù)，模擬過程如下：（一） 將所有的矩形件按從大到小排列并保存，從中找出一個未排的面積最大的矩形件，放在已知板材的左下角。（二） 確定排放方式：按照沿寬度方向排列橫排和縱排的原則。設(shè)置一下四個參數(shù)：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則無法排列區(qū)域1區(qū)域2已放排完上述矩形件后，板材被分為三大部分如圖 已放區(qū)域，未放區(qū)域1、未放區(qū)域2，這時區(qū)域1、區(qū)域2被看做新的板材。（三） 再次掃描矩形件，重復(fù)（一）（二），直至所有的矩形件被排列完成。輸出排樣結(jié)果。用上述方法對26種矩形件進行排樣后，的下列數(shù)據(jù)：序號利用率序號利用率序號利用率序號利用率178.16%15192.02%30196.33%45186.88%278.16%15292.02%30296.3

10、3%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.16%16192.02

11、%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%2

12、078.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%3289

13、4.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.1

14、6%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%34594.10%

15、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%5495.37%204

16、88.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%36294.10%51282

17、.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.37%22187.85

18、%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%52978.16%8

19、095.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%23878.38%3889

20、2.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.01%9795.3

21、7%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%25596.33%405

22、92.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.80%56378.

23、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%12292.30%

24、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%28096.33%430

25、87.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.53%58877.

26、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%14792.21%

27、29796.33%44787.53%59745.35%14892.02%29896.33%44887.53%14992.02%29996.33%44987.40%15092.02%30096.33%45086.88%通過上述計算求得利用率為：通過計算解得，在原材料只有一種規(guī)格2100cm1650cm的情況下，用單一下料兩個方向排料優(yōu)選的方法需要原材料597塊，原材料的利用率為87.22%.5.3 兩種原材料規(guī)格下的二維下料算法由第一問所建模型可以求出當(dāng)料板為一塊板材時的最有效下料策略，并求出所需的最小料板張數(shù)?，F(xiàn)在，原材料有兩種規(guī)格，問題主要體現(xiàn)在兩種規(guī)模的原材料各用多少才可以取到最優(yōu)解。對此

28、，我們可以利用第一問所建模型，通過多次限制一類料板的數(shù)量，將此類料板先切割完畢，然后通過切割另一類料板，生產(chǎn)余下的還未生產(chǎn)的成品。求出所需總共用的料板數(shù)，然后將這多次切割所得出的總料板數(shù)進行比較，取得最少的切割料板數(shù)，即為最優(yōu)下料策略。所以建立數(shù)學(xué)模型如下：設(shè)為第1塊板的數(shù)量，現(xiàn)分別令=i（i=1,2,3），利用第一問所建模型，求出在第一塊料板的數(shù)量為的情況下可以生產(chǎn)的各種產(chǎn)品的產(chǎn)量為 (j=1,2,3)，（指在消耗第一塊料板的數(shù)量為=i時，所生產(chǎn)的第j種產(chǎn)品的數(shù)量）則需要第二塊料板生產(chǎn)的產(chǎn)品為所需生產(chǎn)的產(chǎn)品的總量（j=1,2,3）（指所需生產(chǎn)的第j種商品的總量）減去以生產(chǎn)的各種產(chǎn)品的生產(chǎn)量，

29、即xij=xj-，利用第一問所建模型，求出生產(chǎn)xij所需的第二塊板的數(shù)量ki，則在第一塊板的數(shù)量為的情況下，所需的總共板數(shù)位=+ki。取i=1,2,3直到只利用第一塊板即可生產(chǎn)出所有的產(chǎn)品為止。則取m=min()(i=1,2,3)為最優(yōu)解。同時若有多個值可以取得最小值，則通過判斷利用率來判斷哪個方式為最優(yōu)解。即六、模型結(jié)果的分析在有一種規(guī)格2100cm1650cm原材料的情況下，需要規(guī)格為2100cm1650cm的原材料597塊，原材料的利用率為87.22%。在有兩種規(guī)格2100cm1650cm和2000cm1500cm原材料的情況下，需要規(guī)格為2100cm1650cm的原材料594塊，需要規(guī)

30、格為2000cm1500cm的原材料3塊，總共597塊，原材料的利用率為87.28%。有結(jié)果看，兩次實際使用的板材總數(shù)量一致，這與兩塊板形狀基本相同有著密切關(guān)系，但第二次的利用率要高，這是因為總數(shù)一致，但第二塊板面積要小。這應(yīng)該是在本算法條件下得出的最優(yōu)下料策略。七、模型的評價與補充7.1 模型的評價顯然，本文采用啟發(fā)式算法，對玻璃板材的最優(yōu)下料策略進行分析計算的方法是基本成功的。事實上，對于一般的二維下料（板材下料）問題，均可以采用該方法進行下料排解。求出最少原材料的張數(shù)。模型的優(yōu)點簡單易行，速度快且能夠融合各種限制條件和具體目標(biāo)，因此在實際生產(chǎn)排樣中有著更廣泛的應(yīng)用。模型的缺點 只是一種近

31、似求解，劃分區(qū)域過程過于單一，沒有考慮其他劃分方式更適合一些矩形件的放置，從而減低板材數(shù)量，提高利用率八、模型的改進和推廣優(yōu)化下料，就是要提高原材料的利用率，降低生產(chǎn)成本，是國內(nèi)外非常活躍的研究課題。板材玻璃的下料問題就屬于這一類常見的二維下料問題，二位下料問題就是如何將矩形原材料切割成所需的零件，使所需要的原材料最少，利用率最高，其中鋼板，木板等的剪切下料也屬于此類下料問題。因此本模型可以推廣到很多很多生產(chǎn)領(lǐng)域。參考文獻1 錢頌迪.運籌學(xué)第三版. 北京:清華大學(xué)出版社2005.62 楊啟凡.數(shù)學(xué)建模.北京：高等教育出版社 2005.63 朱道元.數(shù)學(xué)建模案例精選.北京：科學(xué)技術(shù)出版社 200

32、3.34001036x(2009)05-001204 呂俊豐，馬巖，喻虎德 人造板一刀切數(shù)控下鋸優(yōu)化的編程模型研究 木材加工機械 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 639 84 ; 804 631 56

33、; 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