數(shù)學(xué)建模論文—薄膜切割問(wèn)題[應(yīng)用知識(shí)]

1、科院10組： 蔡光達(dá) 王良澤南 熊佩玉薄膜切割問(wèn)題摘要本文討論的是薄膜的合理切割問(wèn)題，屬于優(yōu)化問(wèn)題中的組合問(wèn)題。該問(wèn)題的關(guān)鍵在于如何合理地安排薄膜切割的模式，使得材料利用率達(dá)到最大且原材料使用最少。因此我們建立了線(xiàn)性?xún)?yōu)化模型，用LINGO和MATLAB軟件求解，得出在訂單所需薄膜件數(shù)的限定下，最合理的切割方式。對(duì)于問(wèn)題一，我們先求出10種規(guī)格的小卷的切割模式，由于符合條件切割模式有1000多種，所以隨機(jī)選取了一件大卷的利用率大于99%的16種模式（具體模式見(jiàn)表2）作為切割方式的基本模式。然后，我們以切割大卷的總件數(shù)最小為目標(biāo)函數(shù)，建立模型，運(yùn)用MATLAB軟件求解，共運(yùn)用了9種切割模式（具體模

2、式見(jiàn)表3），切割大卷的總卷數(shù)為265件，材料利用率為99.80%。對(duì)于問(wèn)題二，該問(wèn)題在問(wèn)題一的基礎(chǔ)上加入了時(shí)間限制，我們把時(shí)間限制轉(zhuǎn)化為對(duì)大卷數(shù)目的約束，即在切割的168件大卷中第3、7、9號(hào)訂單的小卷件數(shù)必須全部切割完成。最后建立線(xiàn)性?xún)?yōu)化模型，求解得出前7天內(nèi)運(yùn)用第1、5、6、9共4種模式切割，然后改變切割模式，用第3、4、8、9、10、15共6種模式切割（具體模式見(jiàn)表4），切割大卷的總卷數(shù)為265件，完成整個(gè)切割任務(wù)單用時(shí)12天,材料利用率為99.63%。關(guān)鍵詞：線(xiàn)性?xún)?yōu)化模型 利用率 切割模式1. 問(wèn)題重述1.1問(wèn)題背景直接從薄膜廠(chǎng)制膜車(chē)間生產(chǎn)出來(lái)的的薄膜，在薄膜行業(yè)稱(chēng)為半成品，簡(jiǎn)稱(chēng)大卷或

3、母卷，寬度一般為8100mm，厚度有若干種規(guī)格（如19微米、21微米等），長(zhǎng)度則根據(jù)厚度不同而有所不同。薄膜廠(chǎng)銷(xiāo)售部門(mén)首先接到客戶(hù)訂單或直接提貨單，客戶(hù)訂單或提貨單中有所需要的薄膜類(lèi)型（如BOPP膜、消光膜、CPP膜、珠光膜等），薄膜厚度(如19微米，21微米等)、薄膜寬度（如330mm，620mm等，）、件數(shù)；其次銷(xiāo)售部門(mén)根據(jù)當(dāng)前市場(chǎng)行情同客戶(hù)商談價(jià)格，談好價(jià)格后，客戶(hù)會(huì)發(fā)過(guò)來(lái)一個(gè)清單；然后銷(xiāo)售部會(huì)根據(jù)情況把相同薄膜類(lèi)型、相同厚度的需求合在一起，進(jìn)行組合優(yōu)化，形成一個(gè)切割任務(wù)單；最后在切割車(chē)間通過(guò)機(jī)器將大卷切割成客戶(hù)需要的規(guī)格（切割好后送達(dá)客戶(hù)的薄膜稱(chēng)為小卷，假設(shè)一般小卷的最小寬度為330m

4、m）。某薄膜廠(chǎng)接到如下訂貨（來(lái)自不同客戶(hù)的訂貨的匯總）1.2需要解決的問(wèn)題問(wèn)題1請(qǐng)你為該廠(chǎng)設(shè)計(jì)一個(gè)滿(mǎn)意的切割方案送交切割車(chē)間，該切割方案須指出切割大卷的總卷數(shù)、切割的方式數(shù)，材料的利用率等數(shù)據(jù)。問(wèn)題2若該廠(chǎng)的薄膜切割機(jī)每天最多只能處理24大卷的切割任務(wù)，3,7,9號(hào)訂單屬于加急訂單，必須在一周內(nèi)完成切割，然后發(fā)貨，問(wèn)該怎樣調(diào)整切割方案，在這種方案下完成整個(gè)切割任務(wù)單需要多少天。2. 模型假設(shè)假設(shè)1：切割過(guò)程中不會(huì)出現(xiàn)機(jī)器故障等其他非正常故障。假設(shè)2：假設(shè)大卷類(lèi)型、厚度與客戶(hù)訂單的類(lèi)型、厚度一致假設(shè)3：每種切割模式下的余料浪費(fèi)不能超過(guò)100mm假設(shè)4：忽略薄膜切割過(guò)程中大卷的損耗假設(shè)5：每次切割

5、都準(zhǔn)確無(wú)誤假設(shè)6：沒(méi)有額外追加訂單假設(shè)7：大卷總數(shù)足夠多3. 符號(hào)說(shuō)明符號(hào)符號(hào)說(shuō)明切割模式的總數(shù)第種切割模式第小卷的種類(lèi)小卷的總規(guī)格類(lèi)型按照第種切割方式所切割的大卷件數(shù)第種小卷的寬度第種切割方式得到寬度為的小卷件數(shù)第種小卷的需求量大卷的寬度切割大卷的總件數(shù)每天最多處理的大卷件數(shù)一周內(nèi)處理的大卷總數(shù)第個(gè)大卷種切割的第種小卷的件數(shù)T完成切割任務(wù)天數(shù)材料的利用率一張大卷能切出的小卷數(shù)量切得剩余材料的量最多能完全切割的大卷總數(shù)剩余沒(méi)有切的小卷數(shù)4. 問(wèn)題分析切割問(wèn)題是下料問(wèn)題的一個(gè)分支，而一維下料問(wèn)題是組合優(yōu)化中的一個(gè)經(jīng)典問(wèn)題，如果要得到理論上的嚴(yán)格全局最有下料方案。就要求所有可行下料方式都進(jìn)入線(xiàn)性規(guī)

6、劃模型的系數(shù)矩陣，從計(jì)算的復(fù)雜性理論上看，這屬于NPC（NP完全）難問(wèn)題。因此，我們放棄常規(guī)的整數(shù)規(guī)劃解法，而在以?xún)?yōu)化選取下料方式的前提下，尋找建立下料方案的模型。本文要求一個(gè)好的下料方案在生產(chǎn)能力允許的條件下要滿(mǎn)足兩個(gè)要求：首先，應(yīng)該使原材料的利用率最大，即用最少數(shù)量的原材料；其次要求所采取的不同下料方式盡可能少。本文主要分析的是怎樣切割薄膜使得所用原材料總數(shù)最少且材料利用率最大。訂單中要求的小卷規(guī)格都不能與大卷規(guī)格成整數(shù)倍，即大卷無(wú)論只切割哪一種規(guī)格，都不可能完全切完，一定會(huì)有剩余，這是對(duì)問(wèn)題的極端分析，可以更清晰的了解問(wèn)題和認(rèn)識(shí)問(wèn)題，從中理清思路，找出最好的解答策略。針對(duì)問(wèn)題一：對(duì)于薄膜

7、切割問(wèn)題首先要確定采用哪些切割模式。所謂切割模式，是指按照訂單要求在原料大卷上安排切割的一種組合。例如，我們可以將8100mm的大卷切割成13件寬度為620mm的小卷，余料為40mm；或者將8100mm的大卷切割成寬度為820mm的小卷1件和寬度為1470mm、1250mm、920mm的各2件，余料為0。顯然，可行的切割模式很多。于是問(wèn)題轉(zhuǎn)化為在滿(mǎn)足客戶(hù)需要的條件下，按照哪幾種合理的模式進(jìn)行切割，每種模式切割多少件大卷最為節(jié)省。而由于需求的小卷規(guī)格為10種，所以枚舉法大的工作量較大，消耗時(shí)間，且不具有普遍性。我們?cè)O(shè)法把切割方式作為約束條件，放在規(guī)劃中一起解決。針對(duì)問(wèn)題二：該問(wèn)題在問(wèn)題一的基礎(chǔ)上

8、增加了限制條件，即薄膜切割機(jī)每天最多只能處理24大卷的切割任務(wù)；3,7,9號(hào)訂單必須在一周內(nèi)完成切割。對(duì)于這兩個(gè)限定其實(shí)我們可以和在一起討論，切割時(shí)間與切割大卷件數(shù)有一定的關(guān)系，我們將3,7,9號(hào)訂單分離出來(lái)考慮，并把對(duì)時(shí)間的限制轉(zhuǎn)化為對(duì)大卷件數(shù)的限制，即要求在切割的前168件小卷內(nèi)3、7、9號(hào)訂單中的三種規(guī)格的小卷必須完成切割。在這樣的基礎(chǔ)上，再考慮搭配最佳切割方式，建立的數(shù)學(xué)模型同問(wèn)題一完全一樣，只是增加了一個(gè)限制約束。最終運(yùn)用軟件求出這種方案下得最佳材料的利用率和切割大卷的總卷數(shù)。5. 數(shù)據(jù)分析4.1對(duì)數(shù)據(jù)的極端分析首先對(duì)數(shù)據(jù)進(jìn)行一系列簡(jiǎn)單的分析，主要是進(jìn)行一些極端的分析，對(duì)問(wèn)題總體有了

9、一個(gè)大致的了解。當(dāng)一張大卷只被切割成一種規(guī)格的小卷時(shí)，能切出的小卷數(shù)量x以及剩余材料的量y(其中超過(guò)330的都用紅色字體表示出來(lái))、在所需件數(shù)范圍內(nèi)最多能完全切割的大卷總數(shù)a以及剩余沒(méi)有切的小卷數(shù)b。表1：對(duì)數(shù)據(jù)的極端分析（規(guī)格單位：mm）訂單號(hào)規(guī)格件數(shù)133020624180814262045613403513820156972017349203188740396510005381006561250157660026171360263513005238147013957502749180018249004521022509431350311規(guī)格最大的是10號(hào)，規(guī)格最小的是1號(hào)；件數(shù)最多的是2

10、號(hào)，件數(shù)最少的是5號(hào)；x最大的是1號(hào)，x最小的是10號(hào)；y最大的是10號(hào)，y最小的是2號(hào)；a最大的是7號(hào)，a最小的是5號(hào)。4.2對(duì)選出的利用率高的切割方式數(shù)據(jù)分析一個(gè)大卷的不同切割方式有1000多種，為簡(jiǎn)化計(jì)算，我們對(duì)切割方式進(jìn)行了限制并隨機(jī)挑選出16種大卷利用率大于99%的方案作為本題求解的進(jìn)本模式。具體切割模式如下：表2：切割大卷的基本模式（小卷規(guī)格單位：mm）規(guī)格模式330620820920100012501360147018002250余料利用率100120202000100%2190000000103099.63%3011000100003099.63%420071000000100

11、%500100040014099.51%600100000408099.01%759100000005099.%38803250000000100%901000103102099.75%1001000301011099.88%1100050100010100%1230200040003099.63%1310001010301099.88%1410001000032099.75%1520012000022099.75%1621100001023099.63%6. 問(wèn)題一的解答6.1模型一的建立6.1.1確定目標(biāo)函數(shù)該模型的建立是為了解決薄膜的切割問(wèn)題，為了使切割方案合理，我們以大卷的最少使用件數(shù)

12、為目標(biāo)函數(shù)函數(shù)建立模型。目標(biāo)函數(shù)：6.1.2確定約束條件從題目中分析可知，主要的約束條件有兩個(gè)，I切割出的小卷總寬度小于等于，且余料小于，即：II 最終切割得到的小卷件數(shù)必須達(dá)到訂貨件數(shù)，即：6.1.3綜上所述，得出目標(biāo)最優(yōu)化模型：6.2模型一的求解首先從第一張大卷開(kāi)始，將10種規(guī)格合理分配和安排，從而獲取1種最佳切割方式作為第1種切割方式，然后一直使用這種方法，直到某一種或幾種規(guī)格的小卷因?yàn)橐呀?jīng)完成或快完成目標(biāo)而使得方案無(wú)法進(jìn)行時(shí)，再根據(jù)實(shí)際情況，對(duì)剩下要完成的薄膜重新組合分配，再尋找出第2種切割方法，然后繼續(xù)以上的方法，得出第2種切割方案，以后方案依此類(lèi)推，直到獲得第種方案為止。算法思想：

13、切割剛開(kāi)始執(zhí)行時(shí)，處理答卷總數(shù)z=0,每經(jīng)過(guò)for語(yǔ)句每循環(huán)一次，z的值加1，最終輸出的z值就是切割大卷總數(shù)。再根據(jù)z值，求得材料利用率，切割方式可以根據(jù)最終程序輸出的每一種規(guī)格的薄膜在每一次切割答卷時(shí)產(chǎn)生的件數(shù)得出。模擬的流程如下所示:開(kāi)始將z賦值為0進(jìn)入第一種切割方式每切一次大卷z加1開(kāi)始該切割方式的實(shí)施后經(jīng)過(guò)s次循環(huán)后是否開(kāi)始下一切割方式以同樣的方法進(jìn)行是否完全結(jié)束切割否是結(jié)束方式是否能實(shí)施最終求得結(jié)果：表3：使用的薄膜切割方式方式330mm620mm820mm920mm1000mm1250mm1360mm1470mm1800mm2250mm余料大卷數(shù)301100010000303180

14、3250000000209010001031020381001000301011015110005010001044123020004000305413100010103010481410001000032051621100001023010求和717510265547150265切割大卷總件數(shù)： 材料利用率： 6.3模型一的結(jié)果分析我們選出了比較合適的方式在方案中加以利用，但是由于我們?yōu)榱颂岣卟牧侠寐剩懈顢?shù)量超出了訂單中要求的件數(shù)，大卷總數(shù)265可能比完全按照訂單切割的方案要多，但我們之所以多，不是多了切割出來(lái)的廢料，而是多了按照一定規(guī)格切割出的薄膜，因此不作為廢料進(jìn)行計(jì)算，算得的結(jié)果很

15、高99.80%接近100%。7. 問(wèn)題二的解答7.1模型二的建立7.1.1確定目標(biāo)函數(shù)問(wèn)題二要求出完成整個(gè)切割任務(wù)單需要的天數(shù)，因?yàn)樵搹S(chǎng)的薄膜切割機(jī)每天最多只能處理24大卷的切割任務(wù)，所以我們?nèi)砸允褂么缶淼淖钌偌?shù)為目標(biāo)函數(shù)。目標(biāo)函數(shù)： 所需天數(shù)： 7.1.2確定約束條件模型二的約束條件是在模型一的基礎(chǔ)上將對(duì)訂單號(hào)為3,7,9的小卷規(guī)格分離出來(lái)，對(duì)其加以限定約束，使其在一周之內(nèi)完成。我們將其時(shí)間限制轉(zhuǎn)化為對(duì)切割大卷件數(shù)的限制。分析可知，在切到第168個(gè)大卷之前必須完成對(duì)上述三個(gè)訂單的切割。即：7.1.3綜上所述，得出多目標(biāo)最優(yōu)化模型7.2模型二的求解模型二的求解，需要在模型一的基礎(chǔ)上，對(duì)于i=

16、3,7,9這種特殊情況分開(kāi)進(jìn)行考慮，由于受一周時(shí)間的限制，我們決定重新設(shè)定一個(gè)類(lèi)似于z的新的變量w，它的取值范圍是1,7d,這樣處理，會(huì)出現(xiàn)兩個(gè)關(guān)于大卷數(shù)量的值：z，w。我們將選取其中較大的值進(jìn)行下一步計(jì)算，計(jì)算完成切割任務(wù)天數(shù)T是將z和w中較大值與24的比值取整后加1得出結(jié)果。結(jié)果如下表所示表4：?jiǎn)栴}二的薄膜切割模式模式330mm620mm820mm920mm1000mm1250mm1360mm1470mm1800mm2250mm余料/mm大卷數(shù)/件100120202000463011000100003040420071000000302190000000103078032500001003

17、9010001031020151001000301011051520012000022012600100000408041500100040014066求和2316615374674230265由于1,3,9號(hào)是加急訂單，為了在規(guī)定時(shí)間內(nèi)完成，我們應(yīng)該以以下四種切割方式為優(yōu)先方式，模式330mm620mm820mm920mm1000mm1250mm1360mm1470mm1800mm2250mm余料/mm大卷數(shù)/件10012020200046901000103102015600100000408041500100040014066表5：優(yōu)先切割模式7.3模型二的結(jié)果分析由上表可知，七天內(nèi)實(shí)際完

18、成1,3,9號(hào)訂單件數(shù)分別為156，264，194件，此結(jié)果滿(mǎn)足題意要求，大卷總數(shù)是265，材料利用率為：接近1，說(shuō)明此方案是可行的。完成整個(gè)切割任務(wù)單的天數(shù)為天。8. 模型的評(píng)價(jià)、改進(jìn)和推廣8.1模型評(píng)價(jià)模型優(yōu)點(diǎn)：（1）從切割一開(kāi)始就進(jìn)行最優(yōu)化方案，尋找最優(yōu)解，方法快捷簡(jiǎn)便且容易理解，容易被人接受。（2）對(duì)于實(shí)際生活中的各種類(lèi)似情況都可以通用，實(shí)用性強(qiáng)。（3）模型二在針對(duì)類(lèi)似問(wèn)題時(shí)，只需修改w的范圍和i的取值即可投入使用。模型缺點(diǎn)：該模型對(duì)切割模式較少的下料問(wèn)題比較適用，但對(duì)于一些問(wèn)題更復(fù)雜的情況就不易算出或求解不出。另外該題工作量也稍微有一點(diǎn)大，且多生產(chǎn)了一些規(guī)格的薄膜。8.2模型改進(jìn)8.

19、2.1改進(jìn)為了提高材料利用率造成的損失按訂單要求切割件數(shù)與實(shí)際切割件數(shù)的比較訂單12345678910要求2064561563185315726313918294實(shí)際 2354641583205315826413918294比較發(fā)現(xiàn)訂單號(hào)為1,2,3,4,6,7的實(shí)際切割件數(shù)超出了訂單切割件數(shù)，這是我們?yōu)榱吮ＷC材料利用率較高而造成的結(jié)果，下面分析它的利與弊，若以后訂單中仍會(huì)用到，則可以獲取利潤(rùn)，若以后訂單中很少用到，則會(huì)有損失。對(duì)這種情況，我們考慮對(duì)于那些訂貨率很高的規(guī)格的薄膜，允許超出了訂單中的件數(shù)，對(duì)訂貨率較低的規(guī)格的薄膜，我們不允許超出訂單中的件數(shù)。最終可以獲取更高的利潤(rùn)。對(duì)于問(wèn)題2出現(xiàn)

20、了加急訂單，若能夠使用我們改進(jìn)后的方案，還有多余的薄膜可以利用，能夠更快的完成加急訂單的任務(wù)，提高可信度。8.2.2改進(jìn)只對(duì)單一個(gè)體的考慮而忽視了整體在求最優(yōu)解時(shí)，太過(guò)直接，應(yīng)該將眼光放長(zhǎng)遠(yuǎn)對(duì)整體考慮，考慮到各種最優(yōu)方案在整體模型中的不同階段的合理分配，再進(jìn)行一次優(yōu)化，建立出一個(gè)對(duì)于整體最有利的模型，并加以推廣運(yùn)用到各行各業(yè)中的類(lèi)似項(xiàng)目。在求最優(yōu)解時(shí)，太過(guò)直接，應(yīng)該將眼光放長(zhǎng)遠(yuǎn)對(duì)整體考慮，考慮到各種最優(yōu)方案在模型中的不同階段的合理分配，再進(jìn)行一次優(yōu)化，建立出一個(gè)對(duì)于整體最有利的模型，并加以推廣運(yùn)用到各行各業(yè)中的類(lèi)似項(xiàng)目。8.3模型推廣我們建立的模型具有普遍意義，模型的建立不僅易于多數(shù)人的理解，

21、而且可以應(yīng)用到實(shí)際生活中的很多問(wèn)題。如制造業(yè)中各種板材、線(xiàn)材、型材、管材零件的切割下料，服裝行業(yè)的剪裁問(wèn)題等等。參考文獻(xiàn)1劉勇彪.等界面長(zhǎng)條類(lèi)材料下料方案的最優(yōu)化設(shè)計(jì)J.機(jī)械設(shè)計(jì)與制造，1994,5. 2閔仲求.合理下料的實(shí)用數(shù)學(xué)模型及其計(jì)算機(jī)軟件的研究J.系統(tǒng)工程理論與實(shí)踐，1982,4.3劉道海，方毅，黃樟燦.一種求解組合優(yōu)化問(wèn)題的演化算法J.武漢大學(xué)學(xué)報(bào)（理學(xué)版），2002,48.4王小東，李剛，歐宗瑛。一維下料的一種新算法J.大連理工大學(xué)學(xué)報(bào)，2004,44.附錄附錄一：附件：訂貨單匯總薄膜類(lèi)型相同、厚度相同。訂單號(hào)規(guī)格（寬度，單位：mm）件數(shù)133020626204563820156

22、492031851000536125015771360263814701399180018210225094附錄二：?jiǎn)栴}一的求解問(wèn)題一的LINGO程序（方案選擇）：model:sets: fangs/1.20/:x;xingh/1.10/:jian,kuan;links(fangs,xingh):mjian;endsetsmin=sum(fangs:x);for(xingh(j):sum(fangs(i):mjian(i,j)*x(i)>jian(j);for(fangs(i):length-min(xingh(j):kuan(j)+1<sum(xingh(j):mjian(i,j

23、)*kuan(j);for(fangs(i):sum(xingh(j):mjian(i,j)*kuan(j)<8100);for(xingh(j):sum(fangs(i):x(i)>sum(xingh(j):jian(j)*kuan(j)/8100);for(fangs:gin(x);for(links:gin(mjian);data:jian=206,456,156,318,53,157,263,139,182,94;kuan=330,620,820,920,1000,1250,1360,1470,1800,2250;enddatadata: !ole('C:Docum

24、ents and SettingsAdministrator桌面jieguo.xls',moshi)=mjian;!ole('C:Documents and SettingsAdministrator桌面jieguo.xls',juanshu)=x;enddataend問(wèn)題一的MATLAB程序（結(jié)果求解）：clc,clearz=1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ;z=z'a=-001202020019000000100011000100002007100000001000400100100000405910000000032500000001000103100100030101000501