木材最優(yōu)切割

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

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

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

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

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

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

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

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

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

10、同的切割方案，使得木板的利用率達(dá)最大。（2）模型建立 （3）模型求解木板S1的數(shù)量P1的數(shù)量P3的數(shù)量木板利用率備注344540.9964每塊木板切割方案相同219360.9923116520.9903合計(jì)數(shù)量：_47_7741623木板總利用率:_0.99479_木板總利用率=所有產(chǎn)品的總面積所有木板的總面積問題四（1） 算法分析問題四采用了guillotine二維切割方法，通過貪心等啟發(fā)式算法獲取最優(yōu)解的近似解。同時(shí)由于該問題屬于NP問題，無法采用多項(xiàng)式方法求解，故只能采用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每塊木板切割方案相同合計(jì)數(shù)量：_359_774215316231614木板總利用率:_0.9964_木板總利用率=所有產(chǎn)品的總面積所有木板的總面積問題五（1）算法分析根據(jù)第四題所得分割方案，建立數(shù)學(xué)模型進(jìn)行求解。（2）模型建立（3）模型求解木板S1的數(shù)量P1的數(shù)量P2的數(shù)量P3的數(shù)量P4的數(shù)量利潤（元）木板利用率備注100590001174.10.每塊木板切割方案相同木板S1合計(jì)數(shù)量100總利潤:木板總利用率:_0._木板總利用率=所有產(chǎn)品的總面積所有木板的總

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