1、板材玻璃下料問題摘要排樣下料問題在很多工業(yè)領域中都有廣泛的應用，解決好排樣問題，可以提高材料的利用率。本文解決的是玻璃板材的最優(yōu)化下料策略，不同的下料策略形成不同的線性規(guī)劃模型。在充分理解題意的基礎上，以使用原材料張數最少為目標，采用逐級優(yōu)化的方法，進行下料方案的篩選。在第一題中，首先選用單一下料兩個方向排料優(yōu)選的下料策略，成品料的長在原材料的長和寬兩個方向上分別排列，求出最優(yōu)解；其次采用單一下料中成品料的長和寬在原材料的長、寬兩個方向套裁排料優(yōu)選，算出所需原材料的塊數和利用率；最后按照零件需求量，進行幾種零件配套優(yōu)選，用新易優(yōu)化板材切割軟件求出最優(yōu)的板材切割方法，列以原材料消耗總張數最少為目

2、標函數的數學模型，用LINGO軟件編程，求出最佳下料方案。按照原材料的利用率，篩選出最佳的下料方案為按照零件需求量，進行幾種零件的配套優(yōu)選下料方案，所求需要原材料的塊數為548，利用率為95.03%。第二題的求解以第一題相似，當有兩種規(guī)格的原材料時，在第一題的基礎上，用玻璃板材切割軟件排出兩種原材料的最佳切割方法，建立數學模型，用LINGO軟件編程，算出最佳的下料方案。求得需要規(guī)格為2100cm×1650cm的原材料532塊，需要規(guī)格為2000cm×1500cm的原材料16塊，共計548塊，利用率為95.40%。此模型可以推廣到更多板材排樣下料領域的應用，通過逐級優(yōu)化和組合

3、原理，確定各種切割方式，然后再進行線性規(guī)格問題的求解。關鍵詞：優(yōu)化排樣 板材下料 最優(yōu)化 線性規(guī)劃一·問題重述在大型建筑工程中，需要大量使用玻璃材料，如門窗等。在作材料預算時，需要求出原材料的張數。已知板材玻璃原材料和下料后的成品料均為矩形。由于玻璃材料特點，切割玻璃時，刀具只能走直線，且中間不能拐彎或停頓，即每切一刀均將玻璃板一分為二。切割次序和方法的不同、各種規(guī)格搭配（即下料策略）不同，材料的消耗將不同。工程實際需要解決如下問題，在給定一組材料規(guī)格尺寸后：（1）在原材料只有一種規(guī)格的情況下（例如長為2100cm,寬1650cm），給出最優(yōu)下料策略，時所需要材料張數最少。（2）在原

4、材料為兩種規(guī)格的情況下（例如2100cm×1650cm和2000cm×1500cm），給出最優(yōu)下料策略，使所需要材料張數最少，且利用率（實際使用總面積與原材料總面積之比）盡量高。（3）下表是一些成品料及所需塊數（長×寬×塊數），分別以一種原材料2100cm×1650cm及兩種原材料規(guī)格2100cm×1650cm、2000cm×1500cm為例，分別給出(1)和（2）的算法及數字結果，并給出兩種情況下的利用率。表1：成品料規(guī)格及所需塊數序號長×寬塊數序號長×寬塊數1865×857982857

5、15;715983804×7461964857×675285857×665286804×6632247804×6613088804×639849804×6315610804×56322411804×53619612804×53539213804×55139214865×4469815762×44619616715×4469817680×44622418675×4462819667×4462820655×4468421

6、647×4465622667×42630823580×44622424552×44619625551×44639226527×426392二·模型假設1、 假設不考慮在切割板材玻璃的過程中的損耗；2、 假設不考慮人為的損耗；3、 假設不考慮切割工藝的不同；4、 假設不考慮玻璃厚度的影響；5、 假設不考慮刀片的厚度；6、 假設切割玻璃的刀片可旋轉；7、 假設不考慮兩種原材料的優(yōu)先級及成本，只考慮原材料的利用率；三·符號說明符號表示意義規(guī)格為2100cm×1650cm的原材料的長規(guī)格為2100cm×

7、1650cm的原材料的寬規(guī)格為2000cm×1500cm的原材料的長規(guī)格為2000cm×1500cm的原材料的寬成品零件的長，i=1，2，26成品零件的寬，i=1，2，26所需成品料的塊數，i=1，2，26所需原材料的塊數規(guī)格為2100cm×1650cm的原材料的面積規(guī)格為2000cm×1500cm的原材料的面積第i個成品料的在方向上能被排下的個數第i個成品料的在方向上能被排下的個數第i個成品料的在方向上能被排下的個數第i個成品料的在方向上能被排下的個數只有一種原材料的利用率有兩種原材料的利用率第i個成品料的面積組成切割矩陣的各個數值第j種切割方式下在L

8、方向套裁切割被排下的個數第j種切割方式下在L方向套裁切割被排下的個數第j種切割方式下長度方向的余料第j種切割方式下余料面積第j種切割方式使用的次數x第n種切割方法有兩種規(guī)格原材料是，所需規(guī)格為2100cm×1650cm原材料的塊數有兩種規(guī)格原材料是，所需規(guī)格為2000cm×1500cm原材料的塊數四·問題分析板材玻璃下料問題屬于線性規(guī)劃中的二維下料（板材下料），玻璃最優(yōu)化切割中，原材料有兩個方向（長和寬），在只有一種原材料的時候，令原材料的長為L，寬為W，零件的長為,寬為，i=1，2,，26。從操作方便的角度考慮，一張板材上不宜下過多的零件，但一般來說，參加套裁的

9、零件種類越多，材料的利用率越高，在實際玻璃切割中要兼顧這兩方面的情況，既要考慮操作的方便，又要考慮材料的利用率，一般我們討論零件種數最多為3種或4種的情況。而且由于玻璃材料特點，切割玻璃時，刀具只能走直線，且中間不能拐彎或停頓，即每切一刀均將玻璃板一分為二，是一種典型的Guillotine切割，國內外對Guillotine下料問題的研究非常活躍，已取得了不少的研究結論。對剪切下料一般的處理方法有：使用背包算法以保證能實現一刀切的剪切工藝；在一張板材上只排一種規(guī)格的零件的單一下料法或只排少數幾種的綜合套裁法。考慮到本題的實際情況，我們使用第二種方法。當然，在保證利用率不減的情況下，所下的零件數越

10、少越好。既然原材料有長和寬兩個方向，零件也有長和寬兩個方向，則每個零件的長可在原材料的長和寬方向上排列，寬也可在原材料的長和寬的方向上排列，這就夠成了二維下料方式的多樣性，當所需下料的零件種類較多時，下料方式也就相應的比較多，這又為二維下料增加了困難，為了克服這個困難，并考慮到采取組成最優(yōu)化方案的切割方式的材料利用率都不應太低，因此采取逐級優(yōu)化的方法，進行優(yōu)化切割方案的篩選。對于第一題中有一種原材料的時候，有以下三種切割方案：（1） 單一下料兩個方向排料優(yōu)選；（2） 單一下料在長、寬兩個方向套裁排料優(yōu)選；（3） 按照零件需求量，進行幾種成品料配套優(yōu)選，選出最佳下料方案。對于第二題中有兩種原材料

11、的時候，在只考慮原材料利用率的情況下，我們選用與第一題中只有一種原材料時的第三種切割方案，即按照零件需求量，進行幾種零件配套優(yōu)選，選出最佳下料方案。最后，根據所求的（1）題和（2）題中原材料的數量，算出每種切割方案的利用率，選出最佳切割方案。五·模型的建立與求解下料問題模型主要有密切相關的兩部分組成。第一部分為初始切割方式下的優(yōu)化選取模型，第二部分為下料方案的優(yōu)化模型。其中，后者是一種大型線性規(guī)劃模型。5.1問題一模型的建立與求解單一下料兩個方向排料優(yōu)選對于一張原材料上僅裁一種零件（即單一下料）的切割方式，每一種零件可以排出兩種單一切割方式。第一種，成品料的長在原材料長的方向上排列的

12、下料方式；第二種，成品料的長在原材料寬的方向上排列的下料方式。（1）、單一下料兩個方向排料優(yōu)選數學模型如下:，i=1，2，26；，i=1，2，26；，i=1，2，26；，i=1，2，26；如第一種零件在方向上能排=2，在方向上僅能排1次，因此能切下第一種零件的總數是2×1=2（個），如圖5.1。圖5.1另一方面，在方向上排1次，在方向上能排2次，所以整塊玻璃能容納下以一種零件的總數是1×2=2（個），如圖5.2。圖5.2兩個方向切割的零件數相等，可任選一種切割方式。若切割第二個零件，情況就有所不同了，在方向能排2次，在方向上也能排2次，因此能切下第二種零件的總數是2

13、5;2=4（個），如圖5.3。圖5.3另一方面，在方向能排1次，在方向上也能排2次，因此能切下第二種零件的總數是1×2=2（個），如圖5.4。圖5.4綜上可以看出，圖5.3的切割方式比圖5.4的切割方式的利用率要高，所以單一下料也存在比較優(yōu)選的問題，稱作單一下料的初級優(yōu)化。同理，用Excle對26種材料做單一下料的初級優(yōu)化后，得到如下的數據：長寬面積成品料所需塊數每塊原料切割個數所需原材料塊數1865857741305982492857715612755984253804746599784196449485767557847528475857667571619284768046635

14、330522246387804661531444308652880463951375684614980463150732456610108045634526522246381180453643094419663312804535430140392666138045514430043926661486544638579098617157624463398521968251671544631889098813176804463032802249251867544630105028941966744629748228942065544629213084910216474462885625697226

15、6742628414230893523580446258680224925245524462461921969222555144624574639294426527426224502392944總計729表5.5通過上述計算求得利用率為：（2）、單一下料兩個方向排料優(yōu)選結果如下:通過計算解得，在原材料只有一種規(guī)格2100cm×1650cm的情況下，用單一下料兩個方向排料優(yōu)選的方法需要原材料729塊，原材料的利用率為72.70%。單一下料在長、寬兩個方向套裁排料優(yōu)選成品料在原材料和方向上套裁下料，和可以套裁。但這時應注意，在切割玻璃時，每切一刀將玻璃板一分為二。數學模型與單一下料兩個方

16、向排料選優(yōu)一樣，用Excle對26種材料做單一下料的在長、寬兩個方向套裁排料優(yōu)化后，得到如下的數據：長寬面積成品料所需塊數切割個數/塊原材料所需原材料塊數1865857741305982492857715612755984253804746599784196449485767557847528565857667571619285668046635330522246387804661531444308652880463951375684614980463150732456610108045634526522246381180453643094419672812804535430140392756

17、1380455144300439266614865446385790986171576244633985219692216715446318890989111768044630328022410231867544630105028103196674462974822810320655446292130841092164744628856256106226674262841423081031235804462586802241121245524462461921961118255514462457463921136265274262245023921233總計670表5.6通過上述計算求得利用率

18、為：單一下料在長、寬兩個方向套裁排料優(yōu)選結果如下：通過計算解得，在原材料只有一種規(guī)格2100cm×1650cm的情況下，用單一下料在長、寬兩個方向套裁排料優(yōu)選的方法需要原材料670塊，原材料的利用率為78.87%。按照零件需求量，進行幾種成品料配套優(yōu)選按照零件需求量，進行玻璃套裁下料方式的數學模型表示為：；(1)；（2）且，i=1,2,，m；k=m+1,m+2,2m；（3）k-m如果則；如果則；(4)；(5)；(6)；(7)；(8)且為整數；(9)上述9個方程組成了玻璃下料問題的數學模型。我們的目的是要求出滿足上述9個方程的各種切割方式的張數。通過“新易優(yōu)化板材切割”軟件，排出玻璃板

19、材的最優(yōu)切割方法，共有72種切割方案，每一種切割方案如附錄中表1.0所示。建立線性規(guī)劃方程組：求得的利用率為：按照零件需求量，進行幾種成品料配套優(yōu)選結果如下：通過用LINGO軟件，對上述27個線性方程進行編程求解，求得在原材料只有一種規(guī)格2100cm×1650cm的情況下，用按照零件需求量，進行幾種成品料配套優(yōu)選的方法需要原材料548塊，原材料的利用率為95.03%。所以，通過逐級優(yōu)化，篩選優(yōu)化切割方案比較得出，按照零件需求量，進行幾種成品料配套優(yōu)選的下料策略原材料的利用率最高，為95.03%，故應采取這種下料策略，所需要原材料張數最少，為548張。5.2問題二模型的建立與求解（1）

20、、有兩種原材料的最優(yōu)下料策略的數學模型：在有兩種原材料的情況下，采用與中按照零件需求量，進行幾種成品料配套優(yōu)選方法同樣的數學模型，只是在玻璃板材的切割方案中，增加一種原材料，用“新易優(yōu)化板材切割”軟件，排出兩種玻璃板材的最優(yōu)切割方法，建立線性規(guī)劃方程組，求出所需要原材料的最少張數，根據求得的張數，求出有兩種規(guī)格原材料的利用率。進行玻璃套裁下料方式的數學模型與中的9個方程相同，這里不再重復。通過“新易優(yōu)化板材切割”軟件排出玻璃板材的最優(yōu)切割方案，共有77種切割方案，其種72種為用規(guī)格為2100cm×1650cm的原材料， 5種為用規(guī)格為2000cm×1500cm的原材料。每一

21、種切割方案如附錄中表2.0所示。建立線性規(guī)劃方程組：求得的利用率為：（2）、有兩種原材料的最優(yōu)下料策略的結果如下：通過用LINGO軟件，對上述27個線性方程進行編程求解，求得在有兩種規(guī)格2100cm×1650cm和2000cm×1500cm原材料的情況下，用按照零件需求量，進行幾種成品料配套優(yōu)選的方法需要規(guī)格為2100cm×1650cm的原材料532塊，需要規(guī)格為2000cm×1500cm的原材料16塊，總共548塊，原材料的利用率為95.40%。雖然總共需要的塊數與只有一種原材料時相同，但規(guī)格為2000cm×1500cm的原材料面積比規(guī)格為2

22、100cm×1650cm的原材料小，所以原材料的利用率提高了。六·模型的結果分析本模型按照逐級優(yōu)化的方法，進行下料方案的篩選。當只有一種原材料時，單一下料兩個方向排料優(yōu)選的下料策略需要原材料729塊，原材料的利用率為72.70%；單一下料在長、寬兩個方向套裁排料優(yōu)選的方法需要原材料670塊，原材料的利用率為78.87%；按照零件需求量，進行幾種成品料配套優(yōu)選的方法需要原材料548塊，原材料的利用率為95.03%。故最優(yōu)下料策略是最后一種，需要規(guī)格為2100cm×1650cm的原材料548塊。在有兩種規(guī)格2100cm×1650cm和2000cm×

23、1500cm原材料的情況下，需要規(guī)格為2100cm×1650cm的原材料532塊，需要規(guī)格為2000cm×1500cm的原材料16塊，總共548塊，原材料的利用率為95.40%。不論是只有一種原材料，還是有兩種原材料，所求得的利用率基本都是目前最高的，是一種比較好的最優(yōu)下料策略。七·模型的評價與補充7.1 模型的評價顯然，本文主要采用逐級優(yōu)化的方法，對玻璃板材的最優(yōu)下料策略進行分析計算的方法是基本成功的。事實上，對于一般的二維下料（板材下料）問題，初始切割方式的確定是下料問題中至關重要的內容，如果確定了最優(yōu)的切割方式，就可以把下料問題化成一個線性規(guī)劃問題，也就是要

24、求自動生成線性規(guī)劃方程的系數矩陣，編程進行計算求解。模型的優(yōu)點通過逐級優(yōu)化的方法，在分析各種不同切割方式的情況下，對下料方案進行比較篩選，可以選出最優(yōu)的下料策略。模型的缺點本模型的最大缺點是計算量太大，按照排列組合原理，一次套裁3種零件的切割方式有8種，所以，3個零件的套裁組合方式共有：(種)同理，4種零件的套裁組合方式共有76種。所以，當所要剪切的零件數較多時，計算量太大。7.2 模型的補充如果考慮到其他Guillotine切割的方法，如用遺傳學算法。遺傳學算法有幾個優(yōu)點，建模簡單；計算量相對的小，可得到近似最優(yōu)的可行解；材料的利用率高。在實際應用時，可根據具體問題的特點，先用基因遺傳算法確

25、定較有前途的若干下料方法，再自動借用常用模型及其算法，確定以這幾種方法為基礎最優(yōu)下料方案。去兩種模型之長，避其之短，可能會得到更好的結果。八·模型的改進和推廣優(yōu)化下料，提高材料的利用率，是國內外非常活躍的研究課題。而板材玻璃的下料問題是一類最常見的二維下料問題，就是把一定數量的大矩形板切割成所需要的各種規(guī)格大小和數量的小矩形，鋼板，木板等的剪切下料也屬于此類下料問題。因此，本模型可以推廣到鋼板，木板等的下料問題。參考文獻1 吳建國.數學建模案例精編.北京：中國水利水電出版社，20052 楊振東.基于數控的玻璃最優(yōu)化切割的研究D.山東：山東科技大學機械電子工程，20033 吳杰君.板材

26、下料優(yōu)化排樣系統(tǒng)研究與實現D.合肥：合肥工業(yè)大學機械電子工程，20044 袁忠良，王秀平.板材合理下料J.天津大學學報，1995，28(4).5 蔡正軍，龔堅，劉飛.板材優(yōu)化下料的數學模型的研究J.重慶大學學報（自然科學版），1996，19(2).6 王秋萍.數學建模講義J.西安理工大學，2009.附錄1、 根據成品料需求量，進行一種玻璃套裁下料的72種最優(yōu)切割方案如表1.0123456789101112131621123224225662272122869412101123114121213132214211521612217218221924120122212222222313224222

27、522262427222822912230223122322133634243512236213722382239221140224164212431244112452144621347111448134911135023511125225325445514561125722581259111116011612622263464265426667326816970271721111415161718192021222324252611123333422521622782191011121413314133152122162173211841119202213112231123212411325

28、2126122712281629113033313113232331134352361423731138339403411142311431344324546147483249150151252123153441544255156357358145916034616162211631326434165661736716853691070242711197221表1.02、求解一種玻璃套裁下料的LINGO程序min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25+

29、x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x46+x47+x48+x49+x50+x51+x52+x53+x54+x56+x57+x58+x59+x60+x61+x62+x63+x64+x65+x66+x67+x68+x69+x70+x71+x72;x20+x29+x35+x43+x51+x56+x58+x59+x60+x72>=98;x16+2*x27+x48+x51+x56+2*x57+x59>=98;2*x3+2*x7+x12+2*x13+2*x25+2*x2

30、7+2*x19+2*x25+2*x27+2*x28+2*x32+2*x34+2*x36+2*x39+2*x43+2*x46+x49+2*x50+2*x51+x55+2*x58+x59+x60+x68>=196;2*x3+3*x50+4*x55+3*x67>=28;x2+2*x13+2*x25+x32>=28;x10+2*x16+2*x20+2*x29+2*x38+2*x39+2*x45+x47+x49+2*x62+4*x65+x72>=224;x2+2*x4+2*x6+x10+2*x14+2*x21+2*x30+4*x34+2*x37+x39+2*x40+2*x42+x

31、46+x47+x49+2*x52+2*X56+2*x57+2*x61+2*x67>=308;4*x9+4*x11+2*x22+2*x24+x39+x59>=84;2*x10+2*x31+2*x35+2*x65>=56;x7+x11+2*x16+2*x22+x23+2*x29+2*x31+2*x62+x72>=224;2*x2+2*x4+2*x7+2*x11+3*x12+2*x18+4*x19+2*x20+2*x21+3*x23+2*x24+2*x30+x36+2*x37+2*x53>=196;2*x6+2*x7+x9+3*x10+x14+x19+2*x26+x44

32、+x45+3*x46+x47+3*x48+4*x54+x59+4*x63+2*x64>=392;6*x1+6*x5+6*x8+2*x9+2*x18+2*x23+4*x26+6*x33+2*x35+6*x41+2*x44+4*x45+4*x47+3*x49+2*x70>=392;x1+2*x4+2*x6+2*x15+2*x16+3*x17+x24+x33+x43+x52>=98;x1+3*x3+2*x4+2*x6+3*x13+2+x17+2*x20+2*x25+x29+2*x35+3*x38+3*x40+x41+3*x42+2*x51+x66+2*x72>=196;x12+x15+x17+x25+x27+x28+3*x32+x42+3*x43+2*x52+5*x68+x71>=98;3*x21+3*x22+6*x28+3*x31+2*x32+3*x37+6*x62+10*x69>=224;x14+x41+x50+3*x57+x62+7*x66>=28;3*x14+2*x27>=2