板材下料問(wèn)題

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

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

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

4、許任意擺放（三） 要求加工矩形件無(wú)順序（四） 切割矩形件時(shí)長(zhǎng)和寬要與原材料的長(zhǎng)和寬平行（五） 不考慮切割時(shí)的產(chǎn)生的損耗（六） 矩形件不能重疊，不超過(guò)原材料的大小四、符號(hào)的說(shuō)明符號(hào)表示意義規(guī)格為2100cm1650cm的原材料的長(zhǎng)規(guī)格為2100cm1650cm的原材料的寬規(guī)格為2000cm1500cm的原材料的長(zhǎng)規(guī)格為2000cm1500cm的原材料的寬矩形件的長(zhǎng)，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時(shí)，所生產(chǎn)的第j種產(chǎn)品的數(shù)量指所需生產(chǎn)的第j種商品的總量ki所需的第二塊板的數(shù)量所需要的第i塊板的總數(shù)量五、模型的建立與求解5.1 綜述從理論上看，該類問(wèn)題屬于具有最高計(jì)算復(fù)雜性的優(yōu)化計(jì)算問(wèn)題即NP完全問(wèn)題。對(duì)于這類問(wèn)題，以目前已成熟的計(jì)算理論和算法，或者根本無(wú)法求解，或者求解的計(jì)算量是爆炸性的。本文從現(xiàn)有算法中，總過(guò)比較分析，找到一種基于優(yōu)化排列的啟發(fā)式算法。通過(guò)實(shí)際排列和比對(duì)，可以達(dá)到較高的原材料利用率，符合實(shí)際生產(chǎn)過(guò)程的要求。5.2 一種原材料規(guī)格下的二維下料算法 本問(wèn)題屬于NP完全問(wèn)題，有現(xiàn)有理論知NP

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

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

8、材長(zhǎng)為L(zhǎng),寬為W，且LW，板材數(shù)量不記。第k種矩形件的長(zhǎng)為,寬為數(shù)量為面積為（1ik），所需要的板材總數(shù)為N，則優(yōu)化的目標(biāo)函數(shù)為，同時(shí)每張板材的利用率也要符合工業(yè)生產(chǎn)的要求。5.2.3模型的求解我們借助于計(jì)算機(jī)模擬排樣過(guò)程，求解出所需的最小張數(shù)，模擬過(guò)程如下：（一） 將所有的矩形件按從大到小排列并保存，從中找出一個(gè)未排的面積最大的矩形件，放在已知板材的左下角。（二） 確定排放方式：按照沿寬度方向排列橫排和縱排的原則。設(shè)置一下四個(gè)參數(shù)：A=mod(W, ) B=mod(W, )C=floor(W, ) D=floor(W, )分為一下四種情況：（1） C1，D1此時(shí)矩形件橫排縱排均可，接著看怎么

9、樣排剩余邊界距離小，如果BA，同時(shí)L則說(shuō)明沿著寬度方向縱排剩余邊界面積小于沿著寬度方向橫排，所以采用縱排，反之橫排。（2） C1，D1，L則采用縱排（3） C1，D1 L則采用橫排（4） C1，D1則無(wú)法排列區(qū)域1區(qū)域2已放排完上述矩形件后，板材被分為三大部分如圖 已放區(qū)域，未放區(qū)域1、未放區(qū)域2，這時(shí)區(qū)域1、區(qū)域2被看做新的板材。（三） 再次掃描矩形件，重復(fù)（一）（二），直至所有的矩形件被排列完成。輸出排樣結(jié)果。用上述方法對(duì)26種矩形件進(jìn)行排樣后，的下列數(shù)據(jù)：序號(hào)利用率序號(hào)利用率序號(hào)利用率序號(hào)利用率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%通過(guò)上述計(jì)算求得利用率為：通過(guò)計(jì)算解得，在原材料只有一種規(guī)格2100cm1650cm的情況下，用單一下料兩個(gè)方向排料優(yōu)選的方法需要原材料597塊，原材料的利用率為87.22%.5.3 兩種原材料規(guī)格下的二維下料算法由第一問(wèn)所建模型可以求出當(dāng)料板為一塊板材時(shí)的最有效下料策略，并求出所需的最小料板張數(shù)?，F(xiàn)在，原材料有兩種規(guī)格，問(wèn)題主要體現(xiàn)在兩種規(guī)模的原材料各用多少才

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

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

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

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

32、模案例精選.北京：科學(xué)技術(shù)出版社 2003.34001036x(2009)05-001204 呂俊豐，馬巖，喻虎德 人造板一刀切數(shù)控下鋸優(yōu)化的編程模型研究 木材加工機(jī)械 2009年第5期：1215 2006-045附錄：1.1 問(wèn)題一的主程序源代碼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) 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(