鋼構件的排料問題

1、第八屆華中地區(qū)大學生數(shù)學建模邀請賽承 諾 書我們仔細閱讀了第八屆華中地區(qū)大學生數(shù)學建模邀請賽的競賽細則。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們的參賽報名號為： 105141501 參賽隊員 (簽名) ：隊員1： 隊員2： 隊

2、員3： 武漢工業(yè)與應用數(shù)學學會第八屆華中地區(qū)大學生數(shù)學建模邀請賽組委會第八屆華中地區(qū)大學生數(shù)學建模邀請賽編 號 專 用 頁選擇的題號： A題 參賽的編號： 105141501 （以下內容參賽隊伍不需要填寫） 競賽評閱編號： 第八屆華中地區(qū)大學生數(shù)學建模邀請賽題目： 鋼構件的排料問題 摘 要排樣問題普遍存在于工業(yè)生產的許多領域，一個好的排樣方案可以有效提高原材料利用率，降低生產成本，直接給企業(yè)帶來經濟效益。由此本文根據(jù)單板規(guī)則零件、單板不規(guī)則零件和雙板規(guī)則零件的特點提出了基于矩形包絡算法與啟發(fā)式排樣算法的一種優(yōu)化排樣布局的數(shù)學模型。針對問題一，本文首先制定了一套含有定序規(guī)則、定位規(guī)則、排放規(guī)則的

3、排樣布局規(guī)則，使得在給定的矩形板材上，盡可能多地排放所需的矩形件，然后根據(jù)這一規(guī)則提出的啟發(fā)式排樣算法，得出了零件的擺放方式，并且求出其板材的利用率為：=94.6%，較好地解決了在滿足“一刀切”等約束條件下的數(shù)控下料二維矩形件優(yōu)化排樣問題。針對問題二，本文運用最小矩形包絡算法，將不規(guī)則圖形轉化為規(guī)則圖形。一方面，本文將不規(guī)則的凹邊形轉化為其凸包，然后直接將所有的凸圖形進行矩形包絡；另一方面，先對不規(guī)則圖形進行聚合，然后對聚合后的圖像進行矩形包絡。比較兩種情況下，包絡矩形產生的廢料大小，得出廢料較少的最優(yōu)包絡矩形，最后運用啟發(fā)式排樣優(yōu)化模型對其進行排樣，求出其板材的利用率為99.23%，較好的解

4、決了不規(guī)則零件排樣問題。針對問題三， 本文改動問題一中模型的相關參數(shù)，將單板規(guī)則零件下料的排料優(yōu)化模型轉化為雙板規(guī)則零件下料的排料優(yōu)化模型，最后求出矩形零件的擺放方式，求出其板材的利用率為96.413%，較好的解決了雙板規(guī)則圖形的排樣問題。最后由于板材剩余面積較大，本文進行了探究實驗，增加零件的數(shù)量，最后得出兩塊板材的平均利用率為97.5%。實踐證明，增大板材尺寸，有利于提高材料利用率。因此，在生產中如果實際情況允許，盡量將多個任務合并在一起排樣，從而增加零件總數(shù)，使下料利用率達到理想水平，同時提高生產效率。關鍵詞：排樣布局規(guī)則；啟發(fā)式排樣算法；最小矩形包絡；零件排樣一、 問題重述在鋼構件制造

5、產品的生產過程中，依照產品零件尺寸從板料中截取大小適當?shù)牧慵^程稱之為排料，也稱之為下料。排料是鋼構件制造的第一道工序。在這道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影響產品的成本。對于一個年消耗大量鋼材的生產單位，若能夠提高原料利用率的1%，那么其節(jié)約的鋼材成本是可觀的。因此，降低廢料率提高原材料利用率是鋼構件生產企業(yè)追求的目標。根據(jù)實際情況，板材排料又可分為兩種：一是規(guī)則形狀的零件排料，一是不規(guī)則形狀的零件排料。規(guī)則形狀零件是指矩形零件。其描述一般只需用矩形的長和寬。規(guī)則形狀零件的排料問題的實質是研究如何組合零件擺放問題，使得在整個原料上擺放大量的不同長和寬的零件產

6、生的廢料最少、整料和余料的利用率最高。排放時，其零件間的搭接關系的處理相對容易，只需考慮長、寬兩個因素（含預留的損耗量）。不規(guī)則零件在這里是指多邊形零件（一般的意義是指由直線、圓、弧、孔等的組合形），相對矩形零件排料而言，不規(guī)則零件的直接排料要復雜得多。另外由于切割工藝的要求，切割只能實行“一刀切”的工藝（在整料或余料中，從一邊的某點到另外一邊某點的連線一次切割，但可以在切割下來的板料中再次切割）。板材的利用率就是所有零件面積之和與在一刀切工藝后繼續(xù)切割的那部分板材面積的比值。問題1: 對1張板料和若干規(guī)則形狀零件（板料和零件參數(shù)見附件1），如何在板料中擺放零件使其板料的利用率最高。問題2:

7、對1張板料和若干不規(guī)則形狀零件（板料和零件參數(shù)見附件2），如何在板料中擺放零件使其板料的利用率最高。問題3: 對2張板料和若干規(guī)則形狀零件（板料和零件參數(shù)見附件3），如何在板料中擺放零件使其板料的利用率最高。二、 問題分析2.1問題一的分析為了在給定長度和寬度的板材上，盡可能多地排放所需的矩形件，使得所需的板材盡可能的少，本文擬制訂一種矩形件排樣規(guī)則。由于在數(shù)控下料過程中要滿足“一刀切”的工藝要求，且為了操作簡單易行，速度快且能夠融合各種限制條件和具體目標，使得在整個原料上擺放大量的不同長和寬的零件產生的廢料最少、整料和余料的利用率最高，故本文擬采用啟發(fā)式算法排樣模型，擺放出不同大小的矩形零件

8、。2.2問題二的分析二維不規(guī)則多邊形零件的排料問題的復雜性主要是由多邊形的不規(guī)則幾何形狀和不同次序組合引起的。由于零件形狀不規(guī)則、排料過程中旋轉方向多樣、排列組合復雜、以及計算量非常大，所以本文準備將不規(guī)則形狀零件排料問題轉化為矩形排料問題。為了使不規(guī)則形狀較易于轉化為規(guī)則零件，本文欲將凹邊形現(xiàn)轉化其凸包，在進行求解。又由于當不規(guī)則形狀零件的面積和矩形面積相差很大時，會降低板材的利用率，浪費板材，故本文擬采用最小矩形包絡法，使得排料結果較優(yōu)，增加板材利用率。 2.3問題三的分析由于本文擬做的啟發(fā)式算法排樣優(yōu)化模型，簡單易行，速度快且能夠融合各種限制條件和具體目標等特點，因此在解決雙板規(guī)則零件的

9、優(yōu)化時，本文將改動相關的參數(shù)，也將采用該算法模型。三、 問題假設（1）假設切割板料刀片厚度忽略不計，不會對切割后板料面積產生影響。（2）假設在切割過程中，板料與零件均無磨損邊緣。（3）假設切割時造成板料在被切割中產生的的耗損，而導致原料總面積減少。（4）假設板材厚度與零件厚度一樣，兩者表面能夠無縫接觸。（5）假設板料不會因為外界環(huán)境高溫，受潮等產生形變。四、 符號說明：板材的長：板材的寬：板材的數(shù)量足以排下所有要排的矩形件數(shù)：第i種矩形件的個數(shù)：第i種矩形件的長度：第i種矩形件的寬度：第i種矩形件的面積，且：第類待排矩形件的個數(shù)：余料可利用面積：板材利用率五、 模型的建立與求解5.1 問題一的

10、建模與求解：單板規(guī)則零件下料的排料優(yōu)化模型根據(jù)如何擺放不同大小的矩形零件，使得在整個原料上擺放大量的不同長和寬的零件產生的廢料最少、整料和余料的利用率最高，發(fā)現(xiàn)其排樣算法主要有：背包算法、數(shù)學規(guī)劃法、啟發(fā)式算法、模擬退火和遺傳算法等。其中，遺傳算法、模擬退火算法在數(shù)控下料存在“一刀切”的工藝約束，較難應用，而一般的數(shù)學規(guī)劃法，在大規(guī)模排樣需求下，也因為計算量太大，計算時間太長無法滿足實際生產的需要，又由于本文針對的矩形件的數(shù)量、種類較多，不適合采用背包算法，而啟發(fā)式算法簡單易行，速度快且能夠融合各種限制條件和具體目標，故本文最后提出了如下的啟發(fā)式算法排樣模型。5.1.1 優(yōu)化排樣布局規(guī)則在矩形

11、件優(yōu)化排樣中，待排矩形零件的排放順序、矩形件與矩形件之間的排放方式以及矩形件與板材之間的相對排放位置都是十分重要的。本排樣算法應用的相應規(guī)則如下：（1）定序規(guī)則通過比較待排矩形件的某一項或某幾項屬性(如長度、面積等)來建立定序規(guī)則，它對最終排樣結果有著重要的影響。本算法采用的是根據(jù)待排矩形件面積遞減的順序進行排樣，即先排面積大的矩形件。（2）定位規(guī)則確定被選待排矩形件在布局空間中的擺放位置。本算法采用的是占角策略，即將待排矩形件擺放在板材的某一角，采用的是先占左下角的定位規(guī)則。（3）排放規(guī)則矩形件在板材上有沿板材長度方向的橫排和豎排、沿板材寬度方向的橫排和豎排共4種方式。本算法優(yōu)先考慮沿寬度方

12、向的橫排和豎排的方式，如圖1。通過計算排后板材剩余邊界距離大小來決定橫排或豎排。 寬度方向橫排 寬度方向豎排圖1 工作排列示意圖5.1.2數(shù)控下料優(yōu)化約束條件（1）矩形件之間不能有相互重疊的區(qū)域；（2）矩形件不能排出板材之外；（3）已經排好的零件位置保持不變；（4）符合最左下原則，即第一個排放零件應放置在板材的左下角，其余零件則盡量放置在剩余區(qū)域的最左最低位置；（5）滿足數(shù)控裁板下料的“一刀切”的工藝要求?！耙坏肚小币部煞Q直線貫通問題，是指在矩形板材上切割的每一刀都平行于矩形板材的一組平行邊，端點從矩形板材的一組平行邊中的一條延伸到另一條，將矩形板材分為兩部分。簡單地說，“一刀切”約束條件下的

13、每一刀都會把當前正在鋸切的板材一刀兩段。如圖2a為“一刀切”模式，它可以按圖中所標記的切割順序進行“一刀切”加工；而圖2b為非“一刀切”模式，它無法用有“一刀切”工藝要求的設備進行加工。 a為一刀切模式 b為非一刀切模式圖2 鋸切模式示意圖5.1.3數(shù)控下料優(yōu)化過程矩形件排樣優(yōu)化是指在給定長度和寬度的一定數(shù)量的板材上，盡可能多地排放所需的矩形件，使得所需的板材盡可能的少。人造板數(shù)控下料優(yōu)化屬于矩形件排樣優(yōu)化問題，實際上是一個二維優(yōu)化布局問題，從數(shù)學計算的復雜理論性上說，該類問題屬于NP完全問題(Nondeterministic Polynomial )，即為非多項式確定問題，計算復雜性很高，只

14、能用有效的近似算法求解。以下是該問題的數(shù)學模型。設板材的長為L，寬為W，且L>W，板材的數(shù)量足以排下所有要排的k種矩形件。第i種矩形件的個數(shù)是，其長度為，寬度為，面積為，且 。于是所有要排的矩形件的總數(shù)是。并把這k種矩形件元素集合記為 ，稱 為排樣元素。設總共有N張板材，余料可利用面積為C，則優(yōu)化的目標函數(shù)是：即如何排料使板材利用率最大。5.1.4數(shù)控下料優(yōu)化過程的基本描述（1）排序與定序將所有待排矩形件按面積 由大到小進行排序并保存。采用按面積定序的規(guī)則，即在R中找到一個未用的且面積最大的排樣元素放在已知板材的左下角。（2）確定排放方式優(yōu)先考慮沿板材寬度方向的橫排和豎排。設下列四個判別

15、參數(shù)： 可分為三種情況對這四個參數(shù)進行判別：1）如果說明矩形件沿板材寬度方向橫排豎排均可放下；如果，說明沿板材寬度方向縱排工件后，板材剩余邊界距離小于橫排工件，則將零件沿板材寬度方向進行縱排，否則，將零件沿板材寬度方向進行橫排。2）如果則只能將矩形件沿板材寬度方向進行橫排。3）如果c<1，d>1，則板材不能排放任何工件。排完上述面積最大的矩形件后，板材被劃分為三個部分，即已排區(qū)域Ri、未排區(qū)域1和區(qū)域2，如圖3、圖4所示。這時區(qū)域1和區(qū)域2被看作新的待排板材。 圖3 橫切 圖4 縱切（3）再次掃描排樣元素集合R找出未排的面積最大的矩形件，按照最左最低原則在剩余區(qū)域重復上述（2）的方

16、法繼續(xù)排樣，同時考慮橫切和豎切，又會相應地產生新的未排區(qū)域，并判斷剩余區(qū)域是否排完；如果未排完，則繼續(xù)排樣；否則，更新矩形件信息，同時將剩余區(qū)域作為一定尺寸的板材重新布料，直到任何工件都不能填充為止，即當區(qū)域1和區(qū)域2的面積小于矩形件的最小面積時為止。（4）按照上述算法，利用MATLAB軟件輸出排樣結果。5.1.5 排樣算例及分析以問題所給的零件進行下料，應用上述優(yōu)化算法進行排樣。表1為生產所需下料的任務數(shù)據(jù)列表，人造板板料尺寸為2350×900mm，表中編號代表矩形件的不同種類。表1 9種排樣矩形件列表 (單位：mm)編號長寬數(shù)量面積135030021050002350200270

17、000350024021200004500210210500055003502175000630025027500072502002500008500400220000095002002100000應用上述算法對表1元素進行排樣，共需一張人造板材，排樣結果如下圖所示：圖5 表1排樣結果算法結果分析：通過計算，板材的利用率=94.6%，考慮到板材剩余廢料面積較小，即不可利用面積較小，使得板材的平均利用率與理論值較接近。實踐證明，參與排樣的矩形件種數(shù)、板材尺寸對材料的利用率影響很大。零件種數(shù)越多，材料利用率越高。另外，增大板材尺寸，也有利于提高材料利用率。模型結論本文提出的啟發(fā)式排樣算法較好地解決

18、了人造板“一刀切”數(shù)控下料的二維矩形件優(yōu)化排樣問題，應用在數(shù)控裁板下料中能夠獲得較高的板材利用率，可為家具制造企業(yè)節(jié)約成本，增加效益。其排樣思想對其他行業(yè)的排料問題也具有一定的指導意義。5.2單板不規(guī)則零件下料的排樣優(yōu)化模型二維不規(guī)則多邊形零件的排料問題的復雜性主要是由多邊形的不規(guī)則幾何形狀和不同次序組合引起的。由于零件形狀不規(guī)則、排料過程中旋轉方向多樣、排列組合復雜、以及計算量非常大，所以將不規(guī)則形狀零件排料問題轉化為矩形排料問題，可以有效的求解不規(guī)則形狀零件排料問題。但是當不規(guī)則形狀零件的面積和矩形面積相差很大時，會降低板材的利用率，浪費板材，故本文采用最小矩形包絡法，使得排料結果更優(yōu)，增

19、加板材利用率。 5.2.1排料樣品分析為了確保排料布局的合理性，滿足工藝上的一刀切要求，本文對于不規(guī)則多邊形即凸五邊形、凹六邊形（如圖6）采用組合規(guī)則和鄰接規(guī)則來合成矩形塊。即采用矩形包絡法將這些不規(guī)則形排料問題轉化成比較簡單、算法成熟的矩形件排料問題來實現(xiàn)。這樣做還可減少廢料碎片、降低算法復雜度、提高板材利用率。 圖6 待擺放的零件類型5.2.2最小包絡矩形的求取求取零件的最小包絡矩形是排料算法的要求。所謂最小包絡矩形就是能夠包含零件的所有矩形中面積最小者。因為只有當零件的包絡矩形與零件的外輪廓多邊形中的一條邊平行或重合時，此包絡矩形才有可能是最小包圍絡形。而最小包絡矩形的確定將會影響到板材

20、的利用率。據(jù)此,本文得到了求零件最小包絡矩形的方法，其算法如下：(1)判斷不規(guī)則圖形的凹凸性首先，按逆時針對多邊形頂點進行編號。然后,將待判別的點前后相鄰點進行連接構成一個三角形S，則三角形的面積表示為：，如果，則i點為凸頂點，如果，則i點為凹頂點;如果 ,則i點與i-1與i+1三點共線。(2)求凹多邊形的凸包判斷出凹點以后將該凹點去掉，并將該點前后相鄰的點進行連接，重新進行頂點編號，繼續(xù)判斷，直至多邊形中不存在凹點。這樣就會將凹多邊形轉化為它的凸包，而凹多邊形和它凸包的最小包絡矩形是相同的。圖7、8表示凹多邊形和它的凸包有著相同的最小包絡矩形。 圖7 凹六邊形包絡 圖8 凹六邊形凸包的包絡(

21、3)最小包絡矩形的求解經過凹凸性判別后，得到一個凸多邊形。設該凸多邊形有n個頂點n-1條邊。首先計算出第i條邊與X坐標軸的夾角，然后以第i個頂點為中心，對多邊形進行旋轉，使第i條邊與X軸平行，則第i個包絡矩形的底邊與旋轉后的第i條邊重合。多邊形旋轉后更新了所有的頂點坐標，更新方式按下式進行，然后在所有的已更新坐標值的頂點中搜尋最大和最小的X值和Y值。計算包絡矩形的面積：同時記錄下矩形的長邊和短邊的尺寸，依次循環(huán)上述步驟直到n-1個包絡矩形全部求出，再逐個比較面積，最小的就是該多邊形的最小包絡矩形。但是這樣無法保證單個板件的包絡矩形有較為理想的利用率。因此我們提出了一種基于單件包絡矩形面積利用率

22、的處理方案。首先，設置一判定閥值ratio。然后，分別計算每個板件包絡矩形的板材利用率：判斷若ratio<ratio i,表明該板件的包絡矩形利用率較高，相反若ratio>ratio i則表明該板件包絡矩形的板材利用率較低,存在較大的空白區(qū)域。這就需要對已經求出的包絡矩形進行再處理。處理的方法是將面積小于包絡矩形i的其他包絡矩形按面積由大到小進行排列,依次填入第i個包絡矩形,以獲得較高的板材利用率。對零件外輪廓多邊形進行上述算法操作,分別求得與多邊形平行或重合的最小包絡矩形,找出其中的最小者即為零件最小包絡矩形,如下圖所示： 圖9 五邊形的最小包絡圖 圖10六邊形的最小包絡圖此后,

23、在排料時還需恢復零件原形。(4)聚合矩形的求取為了提高板材利用率,需要對零件進行一定程度的聚合,然后求取聚合后零件的最小包絡矩形,稱之為聚合矩形。零件的聚合就是使零件相互接觸,但不重疊,以達到包絡矩形的面積最小。在排料過程中,由于零件可以任意方向旋轉,兩個零件的聚合問題就顯得尤為復雜,兩個相同的零件進行聚合,只有當兩個零件相差180o時,才能產生最小包絡矩形,因此,在零件聚合過程中,可以只考慮相差180o時的情況。圖11、12表示了零件聚合結構,其聚合過程如下:1)求零件的最小包絡矩形;2)將原零件復制一個,翻轉180o,按其最小包絡矩形移到零件的左上角;3)將原零件的總長度從左到右按一定精度

24、等分,將復制件依次移動到每個位置后,每次移動后,均求一次最小包絡矩形,記錄下該矩形的面積。4)將復制件沿原零件的上、下、左、右四個方向分別與原零件進行組合試驗,最后面積最小的矩形即為零件聚合體的最小包絡矩形,記下此時的位置和碰撞距離值。如果聚合后的聚合矩形的面積小于兩個零件的最小包絡矩形面積之和,則聚合成功;反之則自動放棄聚合。對于聚合成功的零件圖形都可以提高其局部的材料利用率。聚合矩形算法結果：對于凹六邊形來說，本文利用上述算法進行聚合（組合），聚合后將凹邊形轉變?yōu)橥惯呅?，最后對其進行最小矩形包絡，如圖11所示，使得空白面積最小，利用率最高； 圖11 組合六邊形的包絡圖但對于五邊形來說，利用

25、上述算法，本文得出了兩組矩形包絡圖，且他們的空白部分的面積相等，如圖12、13所示，由圖我們可以發(fā)現(xiàn)，當對包絡矩形恢復零件原形時，圖12所需要的切割次數(shù)較多，且不能實行一刀切，導致成本增加，所以本文采用第二種聚合方法。 圖12 組合五邊形的包絡圖（1） 圖13組合五邊形的包絡圖（2）模型結論:通過以上的兩種包絡發(fā)現(xiàn)，單一的對多邊形進行包絡圖形中，空白部分的面積的兩倍要比組合包絡圖形中空白部分的面積要大，所以說，對于本問題中所給的零件，本文采用聚合矩形包絡使得利用率更大。5.2.3不規(guī)則件排樣求解根據(jù)問題中所給的不規(guī)則零件，本文進行了上述的最小包絡矩形近似處理，將二維不規(guī)則圖形排樣轉化為規(guī)則的矩

26、形排樣，得到了下表的包絡矩形數(shù)據(jù)，以這些矩形零件進行下料，應用上述啟發(fā)式優(yōu)化算法進行排樣。表2為近似替代后生產所需下料的任務數(shù)據(jù)列表，人造板板料尺寸為2380×1630mm，表中編號代表包絡矩形件的不同種類。表2 兩種零件近似包絡矩形數(shù)據(jù)列表 (單位：mm)零件處理后編號長寬數(shù)量面積組合五邊形矩形包絡16163997245784組合六邊形矩形包絡26004007240000將上表的包絡矩形零件運用模型一中的矩形件排樣的算法，得到了二維不規(guī)則圖形的排樣。下圖給出了一般不規(guī)則構件排樣效果圖.圖14 不規(guī)則構件排樣效果圖算法結果分析：通過計算，得出材料利用率為：=99.23%，排樣效果比較

27、理想。構件的排樣系統(tǒng)分別分析了矩形構件和不規(guī)則構件排樣的特點,將最小矩形包絡算法與啟發(fā)式排樣算法相結合。實現(xiàn)了矩形構件和不規(guī)則構件的排樣優(yōu)化,取得了較為理想的排樣效果。5.3 問題三的建模與求解5.3.1雙板規(guī)則零件的排樣優(yōu)化模型由于本文給出的啟發(fā)式算法排樣優(yōu)化模型，簡單易行，速度快且能夠融合各種限制條件和具體目標，因此在解決雙板規(guī)則零件的優(yōu)化時，本問題也采用該算法模型，只是相關的參數(shù)不同。以問題所給的零件進行下料，應用啟發(fā)式優(yōu)化算法進行排樣。表3為生產所需下料的任務數(shù)據(jù)列表，人造板板料尺寸為4550×1630mm，表中編號代表矩形件的不同種類。表3 9種排樣矩形件列表 (單位：mm

28、)編號長寬數(shù)量面積135030041050002350200070000350024051200004500210610500055003506175000630025047500072502002500008500400220000095002004100000由于本問題所給的板材數(shù)量是2，而生產的零件所需要的板材數(shù)量一塊足以，根據(jù)本文模型的特點，剩余的可以利用的板材面積在分母中都減掉了，故只考慮一塊板材中的排樣情況，應用啟發(fā)式優(yōu)化排樣算法對表3元素進行排樣，排樣結果如下圖所示：圖15 表3排樣結果算法結果分析：通過計算，板材的利用率=96.412%，利用率較高，較好的解決了雙板規(guī)則圖形的排

29、樣問題。5.3.2 模型探究考慮到板材剩余面積較大，可再次使用，所以本文嘗試優(yōu)先考慮增加面積較大的零件數(shù)量的原則，看能否提高板材利用率；探究發(fā)現(xiàn)：增加零件總數(shù)，能夠使下料利用率達到理想水平，提高了生產效率，探究最終得到零件的總數(shù)如下表4所示：表4 9種排樣矩形件列表 (單位：mm)編號長寬數(shù)量面積135030014105000235020011700003500240151200004500210161050005500350161750006300250157500072502001550000850040018200000950020016100000根據(jù)上表的零件數(shù)目，運用啟發(fā)式優(yōu)化排樣

30、模型，最終得到排樣結果如下圖所示：圖16 板料1的排樣示意圖圖17 板料2的排樣示意圖探究結果：通過計算，本文得出第一快板材的利用率為98.2%，第二塊板材的利用率為：96.8%，最后得出兩塊板的平均利用率為97.5%。故本文推出增大板材尺寸，有利于提高材料利用率。因此，在生產中如果實際情況允許，盡量將多個任務合并在一起排樣，從而增加零件總數(shù)，使下料利用率達到理想水平，同時提高生產效率。六、 模型評價與應用6.1模型優(yōu)點（1）本文提出的啟發(fā)式排樣算法較好地解決了人造板“一刀切”數(shù)控下料的二維矩形件優(yōu)化排樣問題，應用在數(shù)控板材下料中能夠獲得較高的板材利用率，可為板材制造企業(yè)節(jié)約成本，增加效益。其

31、排樣思想可以廣泛的應用在金屬制品業(yè)、木材制品業(yè)、家具制造業(yè)等其他行業(yè)中，對于工業(yè)生產具有重要的經濟價值。（2）本文在解決問題二的二維不規(guī)則零件的自動排料問題時，設計了凸包和合成多邊形的圖形學算法，將矩形法、啟發(fā)式算法相結合來解決二維不規(guī)則零件的排料。模型特色在于它深入研究了不同切割方式的特點，找出了若干優(yōu)化準則，運用這些準則找到很好的切割方案，大大提高了計算效率，克服了傳統(tǒng)排料計算時間長、編碼過于復雜的缺點，顯著提高了材料利用率和生產效率，提高了運算速度。從而提高生產利用率，具有很高的實用性和有效性。而且可以將之擴大應用于多個板料的下料問題。6.2不足之處本文在解決問題二中凹六邊形下料時，雖然

32、擺放零件使其板料的利用率較高，但在凹處不符合一刀切的工藝要求，而且啟發(fā)式算法缺乏統(tǒng)一、完整的理論體系，求出的解只是問題的近似最優(yōu)解，與最優(yōu)解有一定差距。對于這個問題，還有待繼續(xù)研究。6.3 模型的應用及推廣目前，中小家具制造企業(yè)板材排料基本上采用手工試算或憑經驗，板材利用率不高，工作效率低。特別是在大批量生產時，手工試算排料幾乎不可能。所以在優(yōu)化下料時結合數(shù)控操作，可以大大提高生產率，增加經濟效益。在工程實踐中，優(yōu)化排樣的應用范圍非常廣泛：服裝制造時的面料分割；家具制造中的人造板分割；機械制造業(yè)的金屬型材、板材、管材的分割；建筑行業(yè)玻璃、裝飾材料的分割等。七、 參考文獻1 劉嘉敏，張勝男，黃有

33、群等，二維不規(guī)則形狀自動排料算法的研究與實現(xiàn)N，計算機輔助設計與圖形學學報，2007-7-12(7)。2 彭文利，陳淑茹，張定華等，優(yōu)化排料算法的研究現(xiàn)狀與趨勢J，模具工業(yè)，2006，32（8）：16-17。3 王華昌, 陶獻偉, 李志剛等，一種矩形件優(yōu)化排樣綜合算法，華中科技大學學報(自然科學版), 2003,31(6): 9-12。4 張英杰，二維不規(guī)則零件自動排料的優(yōu)化算法J，機械設計與研究，2009（10）：70-80。 5 賈志欣，排樣問題的研究現(xiàn)狀與趨勢，計算機輔助設計與圖形學學報, 2004, 16(7): 890-897。6 崔耀東，矩形毛坯下料排樣的一種優(yōu)化算法J，機械工程師

34、, 2003,(4): 32-34。7 計華，一種基于四叉樹結構的排料算法J, Computer Engineering，2003，9。8 陶獻偉，王華昌, 李志剛等，基于填充算法的矩形件排樣求解J，中國機械工程, 2003, 14(13):1104-1108。 9 李滿江，孟祥旭，王志強等，矩形件和任意多邊形排樣問題的算法及應用J，貴州工業(yè)大學學報（自然科學版），2002,(31):126-130。10 曾鳳華，剩余矩形匹配算法在矩形件排樣中的應用J，機電工程技術，2006,(35):64-65。八、 附錄clear;x=180473,180523,180884,180835,180473,180473;y=-741,-741,-462,-342,-342,-741;X=180884,180934,180934,180582,180523Y=-462,-462,-861,-861,-741Q=180473,180473,180582;W=-741,-861,-861;R=180835,180934,180934;T=-342,-342,-462;plot(x,y,X,Y,'b',Q,W,'b',