木材最優(yōu)切割

1、精選優(yōu)質(zhì)文檔-傾情為你奉上五一數(shù)學建模競賽承 諾 書我們仔細閱讀了五一數(shù)學建模競賽的競賽規(guī)則。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與本隊以外的任何人（包括指導教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其它公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承擔由此引起的一切后果。我們授權(quán)五一數(shù)學建模競賽組委會，可將我們的論文以任何形式進行公開展示（包括進行網(wǎng)

2、上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表等）。參賽題號（從A/B/C中選擇一項填寫）： B 參賽隊號： 參賽組別（研究生、本科、專科、高中）： 所屬學校（學校全稱）： 參賽隊員： 隊員1姓名：XXX 隊員2姓名：XXX 隊員3姓名：XXX 聯(lián)系方式： Email： 聯(lián)系電話： 日期： 年 月 日（除本頁外不允許出現(xiàn)學校及個人信息）五 一 數(shù) 學 建 模 競 賽 題 目： 木料切割最優(yōu)化問題關(guān)鍵詞：矩形件下料 切割問題 guillotine摘 要：隨著社會的發(fā)展、人們對環(huán)境資源的重視，提高材料的利用率、獲得最大利潤就成了不可避免的問題，而解決這個問題的關(guān)鍵就是對產(chǎn)品的生產(chǎn)進行緊湊型的布

3、局。本文旨在解決家具廠木料的切割問題，由一維問題（或者說是1.5維問題）遞推到二維問題，通過尋找合適的切割方法（采用guillotine，貪心啟發(fā)式算法的多目標二維切割），使得我們從目標木板上切割出的所需產(chǎn)品的面積和最大或者利潤最大，后對方案進行優(yōu)化處理，最終得出最優(yōu)方案。問題一用guillotine方法切割可得一塊木板上P1最多能切割59個。問題二在問題一的基礎(chǔ)上，通過迭代的方法，分析得出前三甲利用率分別為99.64%，99.23%和99.03%的最佳方案。問題三又在問題二的基礎(chǔ)上，引入了生產(chǎn)任務(wù)作為限制因素，并結(jié)合貪心啟發(fā)式算法的多目標二維切割和問題使問題得到解決。問題四在問題三的基礎(chǔ)上，

4、又增添了兩個長寬不同的矩形件，用lingo找尋它的最下限后，用循環(huán)得出最大利用率為99.64%，這時候使用的木板數(shù)為359塊。問題五改變了問題四的目標函數(shù)，消除了生產(chǎn)任務(wù)對木塊切割的限制。在這種情形下，得到最優(yōu)方案是在一塊木板上切割59塊矩形件P1，從而得出最大利潤為元，木板的利用率為98.2979%。專心-專注-專業(yè)問題的提出優(yōu)化問題重述與分析本題可簡化為給你一塊已知長寬的矩形木板，和一些知道長寬的矩形產(chǎn)品的生產(chǎn)目標和利潤，要求你設(shè)計一個最優(yōu)切割方案，使木板的利用率最高。在本題中，限制因素可以為生產(chǎn)目標、木板的面積、切割一塊產(chǎn)品所得的利潤。當然，對于這種二維下料問題，還需要考慮零件長、寬兩個

5、方向上的限制。問題一可以看成一個1.5維的切割問題，通過貪心算法我們可以輕易地得出木板切割的近似解，隨后利用迭代的思路與方法，逐漸接近它的上限。問題二除了問題一所涉及的變量P1外增添了新的變量P3，求資源利用率最高的前三種方案。但問題一和問題二都只涉及一塊原材料木板。問題三引入了生產(chǎn)目標作為限制因素，并且要求每塊木板上的切割方案相同，目標還是達到最高的利用率。問題四在問題三的基礎(chǔ)上加入P2和P4，因為木板的切割方案相同，實際問題就轉(zhuǎn)化成了一塊木板上的切割方案。根據(jù)在每塊木板上切割同一種的產(chǎn)品，可得到一個需要原材料木板的最低數(shù)量，同時可以得出一個生產(chǎn)的優(yōu)先級，可以根據(jù)這個優(yōu)先級著重安排生產(chǎn)方案，

6、在滿足需求的條件下，使木料使用的數(shù)量達到最?。ㄟ@時不一定木板的利用率最大）。后在這個可行解的情形下，找尋最優(yōu)解。（然后又在不同切割方案下，找尋最佳的木板利用率。）問題五和問題四類似，在每塊木板切割方案一致時，可以轉(zhuǎn)化為一塊木板上的最大利潤問題。但是問題五放寬了每個產(chǎn)品的需求數(shù)量（即生產(chǎn)任務(wù)），在給定木板數(shù)100的情形下，目標函數(shù)變?yōu)樽畲蟮睦麧櫋l件假設(shè)1、 假設(shè)在木板上采用guillotine的切割方案2、 采用直線切割3、 合理的切割模式：通常建設(shè)一個合理的切割模式的余料不應(yīng)大于或者等于需要板材的最小尺寸。4、 假設(shè)每次切割都精準符號說明 符號說明原料木板的長、寬和數(shù)量第i個產(chǎn)品的長、寬、生

7、產(chǎn)任務(wù)和利潤第i個產(chǎn)品在一塊木板上切割后的數(shù)量從第i個條形木板上切割出長度為的成材數(shù)自定義的一個期望內(nèi)的木材的利用率，可以被人為的改動表示切割方案個數(shù)，即有k種切割方案表示在第i種切割方案下第j種規(guī)格板材所切割的數(shù)量表示第i種方案所用原料木板的數(shù)量模型建立與優(yōu)化1、問題一（1）算法分析分析第一題，其采用單一材料形式進行分割，我們通過guillotine切割方案進行初步求解，其采用“一刀切”的形式對問題進行求解，得出在一塊木板上P1切割的最大數(shù)為56，但是（相對誤差比較大）利用率比較低。后通過貪心算法再次對問題進行優(yōu)化求解，得出切割的最大數(shù)為60，接近于木板切割（裝載）的上限，針對于該問題，貪心

8、策略能得到較好的解，但它不適用于其他問題。圖例1：貪心算法圖例2：guillotine切割（2）模型建立建立一個1.5維的切割問題模型來求近似解（3）模型求解P1的數(shù)量木板利用率5998.29793%2、問題二（1）算法分析在第一題的基礎(chǔ)上，繼續(xù)貪心找到了每種產(chǎn)品的上限，通過guillotine切割進行迭代分析求出不同方案的木板利用率，經(jīng)過對比分析，選取了三種利用率最高的方案。（2）模型建立（3）切割P1和P3的全部方案方案編號P1的數(shù)量P3的數(shù)量木板利用率14450.996428400.9597312380.9850416330.9484520310.9737624260.937072825

9、0.9830832210.967093619 0.99231040140.95571144120.9810124870.9443135260.9903145600.9330（4）模型求解根據(jù)上面的方案，進行利用率的排序，易得三種最佳方案方案編號P1的數(shù)量P3的數(shù)量木板利用率14450.9964936190.9923135260.99033、問題三（1）算法分析可結(jié)合問題一，得出在一塊木板上分別切割P1和P3所能得到的最大數(shù)，再結(jié)合生產(chǎn)任務(wù)能得到滿足需求的最小木板數(shù)，該值為35。假設(shè)全部木板都用一種切割方式，并結(jié)合貪心啟發(fā)式算法的多目標二維切割和問題，建立了模型。后進行優(yōu)化改進，讓不同的木板有不

10、同的切割方案，使得木板的利用率達最大。（2）模型建立 （3）模型求解木板S1的數(shù)量P1的數(shù)量P3的數(shù)量木板利用率備注344540.9964每塊木板切割方案相同219360.9923116520.9903合計數(shù)量：_47_7741623木板總利用率:_0.99479_木板總利用率=所有產(chǎn)品的總面積所有木板的總面積問題四（1） 算法分析問題四采用了guillotine二維切割方法，通過貪心等啟發(fā)式算法獲取最優(yōu)解的近似解。同時由于該問題屬于NP問題，無法采用多項式方法求解，故只能采用guillotine方法得到部分解。（2） 切割方案P1P2P3P4利用率25.000011.00003.00009.

11、00000.947318.000013.00006.00009.00000.952425.00006.00009.00009.00000.921834.0000012.00009.00000.95439.00003.000029.00009.00000.978714.00006.000020.00009.00000.965819.00003.000021.00009.00000.980124.0000022.00009.00000.994329.00003.000013.00009.00000.981434.0000012.00009.00000.954330.000002.000027.00

12、000.961028.000004.000027.00000.969026.000006.000027.00000.977024.000008.000027.00000.985020.0000010.000027.00000.959718.0000012.000027.00000.967716.0000014.000027.00000.97574.00006.000016.000027.00000.996412.0000018.000027.00000.99178.0000020.000027.00000.96644.0000024.000027.00000.982412.00005.0000

13、3.000037.00000.986712.00009.00006.000024.00000.966112.00008.000012.000018.00000.966912.00005.000015.000021.00000.985912.00007.000018.000012.00000.967712.00006.000021.000011.00000.984212.00005.000027.00005.00000.985012.00005.000030.000000.969216.0000028.00007.00000.953916.000014.0000014.00000.902816.

14、0000018.000021.00000.965016.00008.00002.000027.00000.966916.00006.00004.000028.00000.964016.00005.00006.000028.00000.975416.000008.000033.00000.945016.00004.000010.000024.00000.965916.00002.000012.000025.00000.963016.00002.000014.000023.00000.973316.0000016.000024.00000.970316.0000018.000021.00000.9

15、650（3）模型建立 （4）模型求解木板S1的數(shù)量P1的數(shù)量P2的數(shù)量P3的數(shù)量P4的數(shù)量木板利用率備注3594 616270.9964每塊木板切割方案相同合計數(shù)量：_359_774215316231614木板總利用率:_0.9964_木板總利用率=所有產(chǎn)品的總面積所有木板的總面積問題五（1）算法分析根據(jù)第四題所得分割方案，建立數(shù)學模型進行求解。（2）模型建立（3）模型求解木板S1的數(shù)量P1的數(shù)量P2的數(shù)量P3的數(shù)量P4的數(shù)量利潤（元）木板利用率備注100590001174.10.每塊木板切割方案相同木板S1合計數(shù)量100總利潤:木板總利用率:_0._木板總利用率=所有產(chǎn)品的總面積所有木板的總

16、面積進一步討論 結(jié)果表示，分析與檢驗 誤差分析 上述問題求得的只是近似解，可能還有優(yōu)化的空間，目前還沒有發(fā)現(xiàn)此類解決NP問題一勞永逸的算法方案。結(jié)語（模型評價，特點 優(yōu)缺點 改進方法 推廣）該數(shù)學模型只能得到解的下限，不能直接得出解的結(jié)果，一方面是因為該模型選擇用面積近似求解而沒有考慮到所裝載物體的形狀，另一方面是因為無法很好的將木板的長寬與變量聯(lián)系在一起（約束條件的缺少），因此只能求出可行解的上限或者下限，不能求出精確解。除此之外，上述貪心策略求解切割方案的移植性較差，只能用于解決一些問題，但對于某些問題能得到更好的結(jié)果，例如問題一，采用guillotine只能求出裝載p1數(shù)為56，而采用貪心策略則能求出裝載p1數(shù)為59，更大得接近此問題的上限裝載量60。對于已存在的切割方案的優(yōu)化求解，可以采用一些智能算法對問題的解空間進行檢索，進一步獲取較多的切割方案。這種方法也是尋求最優(yōu)的全局最優(yōu)解的另一種方式。參考文獻1 向文欣