第八屆華中地區(qū)大學生數學建模邀請賽

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

2、 君隊員三：王 江 武漢工業(yè)與應用數學學會第八屆華中地區(qū)大學生數學建模邀請賽組委會第八屆華中地區(qū)大學生數學建模邀請賽編 號 專 用 頁選擇的題號： 題A 參賽的編號： 105141519第八屆華中地區(qū)大學生數學建模邀請賽題目： 鋼構件的排料問題【摘 要】隨著鋼結構產品的廣泛應用,提高原材料板材的利用效率是鋼結構企業(yè)迫切需要解決的問題，計算機輔助排樣優(yōu)化的目的在于提供高質,以便節(jié)約原材料,降低產品成本、提高企業(yè)經濟效益和社會效益。增強企業(yè)競爭力。 本文在理論和實踐中的主要研究工作如下: （1）針對二維規(guī)則鋼結構排樣，采用構造性的遞歸結構，每完成一個排樣基本單元排樣后，假定將板材切建立二維矩形件排

3、樣問題的幾何模型，之后采用啟發(fā)式算法進行求解割，完成零件的下料，并形成新的更小的板材。對新的更小的板材遞歸進行排樣，直到完成所有零件的排樣。為避免陷入局部最優(yōu)解，為算法設置了回溯機制。 （2）針對二維不規(guī)則鋼構件(異形件)排樣,在綜合利用計算幾何、計算機圖形學、優(yōu)化組合的知識的基礎上,采用最小包絡法建立模型，并用啟發(fā)式算法和動態(tài)規(guī)劃法求解。 （3）針對問題一,二,三的分析，總結出了模型的優(yōu)點和不足之處。知道了啟發(fā)式算法只能求出可行解而不能確定最優(yōu)解。 關鍵詞：排料；遞歸算法；最小包絡法；啟發(fā)式算法1目錄第八屆華中地區(qū)大學生數學建模邀請賽 承 諾 書1第八屆華中地區(qū)大學生數學建模邀請賽 編 號

4、專 用 頁2第八屆華中地區(qū)大學生數學建模邀請賽31.問題的重述42.分析問題52.1問題一52.2問題二62.3問題三63.模型假設64.符號說明65.模型的建立75.1問題一75.1.1模型的建立75.1.2模型的求解95.2問題二105.2.1 排料預處理105.2.2 建立數學模型135.2.3模型的求解145.3問題三145.3.1建立模型145.3.2模型求解：166.評價176.1 模型的優(yōu)點176.2 模型的缺點171.問題的重述在鋼構件制造產品的生產過程中，依照產品零件尺寸從板料中截取大小適當的零件過程稱之為排料，也稱之為下料。排料是鋼構件制造的第一道工序。在這道工序中，不同的

5、排料方案具有不同的材料利用率，而原材料的利用率直接影響產品的成本。對于一個年消耗大量鋼材的生產單位，若能夠提高原料利用率的1%，那么其節(jié)約的鋼材成本是可觀的。因此，降低廢料率提高原材料利用率是鋼構件生產企業(yè)追求的目標。根據實際情況，板材排料又可分為兩種：一是規(guī)則形狀的零件排料，一是不規(guī)則形狀的零件排料。規(guī)則形狀零件是指矩形零件。其描述一般只需用矩形的長和寬。規(guī)則形狀零件的排料問題的實質是研究如何組合零件擺放問題，使得在整個原料上擺放大量的不同長和寬的零件產生的廢料最少、整料和余料的利用率最高。排放時，其零件間的搭接關系的處理相對容易，只需考慮長、寬兩個因素（含預留的損耗量）。不規(guī)則零件在這里是

6、指多邊形零件（一般的意義是指由直線、圓、弧、孔等的組合形），相對矩形零件排料而言，不規(guī)則零件的直接排料要復雜得多。另外由于切割工藝的要求，切割只能實行“一刀切”的工藝（在整料或余料中，從一邊的某點到另外一邊某點的連線一次切割，但可以在切割下來的板料中再次切割）。板材的利用率就是所有零件面積之和與在一刀切工藝后繼續(xù)切割的那部分板材面積的比值。問題1: 對1張板料和若干規(guī)則形狀零件（板料和零件參數見附件1），如何在板料中擺放零件使其板料的利用率最高。問題2: 對1張板料和若干不規(guī)則形狀零件（板料和零件參數見附件2），如何在板料中擺放零件使其板料的利用率最高。問題3: 對2張板料和若干規(guī)則形狀零件（

7、板料和零件參數見附件3），如何在板料中擺放零件使其板料的利用率最高。2.分析問題2.1問題一：需要建立二維矩形件排樣問題的幾何模型，之后采用啟發(fā)式算法進行求解。算法采用構造性的遞歸結構，每完成一個排樣基本單元排樣后，假定將板材切割，完成零件的下料，并形成新的更小的板材。對新的更小的板材遞歸進行排樣，直到完成所有零件的排樣。為避免陷入局部最優(yōu)解，為算法設置了回溯機制，當后面的零件無法完成排樣時，算法返回修改之前的排樣，再嘗試完成后續(xù)零件的排樣。當所有零件完成排樣后，算法終止，記錄各個零件的位置坐標，得出排樣結果。2.2問題二： 根據問題一的求解，本文對不規(guī)則的零件先進行規(guī)則化處理，如：最小包絡矩

8、形法，通過對零件外輪廓多邊形進行操作，分別求得與多邊形平行或重合的最小包絡矩形，找出其中的最小者即為零件最小包絡矩形。為得到最小包絡矩形，通過聚合矩形法，將不規(guī)則的零件，進行旋轉，由文獻研究可的，當兩個零件的邊界相差180度時，能夠產生最小包絡矩形。最終問題歸結為規(guī)則的零件排料問題。2.3問題三： 通過對一二兩個問題的研究，本文對問題三作如問題的處理方式。問題三中，原材料數量增加了一倍，但原理與問題一類似，運用啟發(fā)式算法求解問題。3.模型假設（1） 每個零件與板塊原件的厚度都是一樣的。（2） 在滿足尺寸約束的條件下，每一塊矩形原件上都可以排放不同的零件，每個不同零件都可以在不同的原件上擺放。（

9、3） 各個原件完成排樣后，再根據各個原件上余料的情況進行多原件之間的零件的相互調整，減少余料提高排樣利用。（4） 假設零件可旋轉二維矩形件排樣。4.符號說明L：原件的長度；W：原件的寬；：第j類零件；：第i類零件的長度；：第i類零件的寬；：第i類零件的數量；：第i個原件排布的第j類零件的數量；：第i個原件；：第i張原件的長；：第i個原件的寬；：第k個j類零件；：的坐標；：第k 個j類零件在第i個原件上的坐標；：條料i的單位寬度；:條料i的面積；：第i個零件的條料數；：第i個零件最大條數；G（i，x）:最大面積值；：從k階段到n階段的最大收益；S:初始狀態(tài)；：狀態(tài)所確定的第n階段的允許決策集合；

10、：第n階段的最優(yōu)解；：第n階段的最優(yōu)值；5.模型的建立5.1問題一5.1.1模型的建立 在二維矩形件排樣問題中，假設一次排樣中使用了1張矩形原件，1張原件的長為，寬為。待排樣矩形零件種類數為9，第(=1，2，9)類零件的長度為，寬度，數量為。排樣完成后，原件上排布的類零件的數為；第k個j類零件在原件上的位置由零件左下角點在原件上的坐標(，）及零件的長寬確定。同一類型的不同類零件坐標位置不同。零件的各邊與原件的對應邊保持平行。根據排樣實際需要，在滿足約束條件的前提下，零件可以旋轉90度，交換零件的長寬后再排到原件上。那么，為了最大化排樣的利用率，目標函數為： (1) 排樣各約束條件表示如下:(2

11、) + +(3) 切片不能超過原件的邊緣： + +(4) 所有零件全部排完: 通過上述數學模型可知，二維矩形件排樣問題屬于帶復雜約束條件的單目標優(yōu)化問題。問題的難點是怎樣合理協(xié)調各工件之間及零件與原件之間的位置關系，使得排樣布局在滿足約束條件的前提下，具有較高的材料利用率。 這里先建立二維矩形件排樣的模型。在某個原件上進行排樣時，我們用矩形表示該原件，以左下角點為原點建立笛卡爾直角標系；水平方向向右為X軸正方向向上為Y軸正向。坐標系中的矩形表示排放在該原件上的不同的切片，各形的邊必須跟水平方向的x軸平行或者跟豎直方向的Y軸平行，各個零件相對的位置可以由零件左下角點在坐標系中的坐標、零件的寬wi

12、dth、零件的高height一確定。在滿足約束的前提下，零件可以在原件上旋轉90度得到新的布局。幾何模型中代表各個零件的矩形必須滿足以下約束條件：(1)矩形之間不能有重疊的區(qū)域；(2)矩形不能超出原件的邊緣；(3)矩形滿足“一刀切”工藝約束；如圖21所示為排樣結果滿足“一刀切”約束與不滿足“一刀切”約束的比較。yyxx a)滿足“一刀切”約束 b)不滿足“一刀切”約束圖2-1 “一刀切”約束示例5.1.2模型的求解1.啟發(fā)式算法1）排樣定位方法，每排放一個零件組時，該切片組怎樣定位在原件上。 2）切片排樣次序，確定零件組排放的先后順序。 在算法計算時先假設該任務具有100利用率的最優(yōu)解，用零件

13、總面積除以原片的寬度，得到最短需要的原件長度。使用該長度的原件進行排樣計算，嘗試求得具有100利用率的最優(yōu)解，并將找到一個具有100利用率的排樣圖作為算法的終止條件。并且排樣圖滿足“一刀切”等約束存在一個能排放完所有零件的解，那么該排樣解中的余料面積和等于原片的面積減去所有零件的面積。我們將原片的面積減去所有零件的面積所得的值作為余料的面積閾值，將零件的面積和與原片面積的百分比作為利用率閾值。在排樣計算過程中，我們實時記錄當前排樣方案產生的余料面積，當余料面積和大于該原片余料面積閾值時，該排樣方案的排樣利用率低于利用率閾值，不可能在完成所有零件的排放，該排樣方案失敗，需要修改該排樣方案中前期排

14、放的零件，以獲得新的排樣方案，直到找出解為止。2.算法求解 用啟發(fā)式算法進行求解。算法采用構造性的遞歸結構，完成零件的下料，并形成新的更小的板材。對新的更小的板材遞歸進行排樣，直到完成所有零件的排樣，當所有零件完成排樣后算法終止，記錄各個零件的位置坐標，得出排樣結果。運用<極致下料>板材企業(yè)版V14.0求得結果如下：小結建立二維矩形件排樣問題的數學模型，明確了此類排樣問題的目標函數、排樣布局必須滿足的約束條件；為排樣優(yōu)化算法的設計提供了思路。設計了排樣過程及排樣結果的幾何模型，將排樣約束轉化為計算機可以識別的幾何模型。5.2問題二5.2.1 排料預處理1.最小包絡矩形的求取求取零件

15、的最小包絡矩形是排料算法的要求。所謂最絡矩形就是能夠包含零件的所有矩形中面積最小者。資料表明：只有當零件的包絡矩形與零件的外輪廓多邊形中的一條邊平行或重合時，此包絡矩形才有可能是最小包圍絡形。據此，我們得到了求零件最小包絡矩形的方法：對零件外輪廓多邊形進行操作，分別求得與多邊形平行或重合的最小包絡矩形，找出其中的最小者即為零件最小包絡矩形，如圖1所示，此后，在排料時還需恢復零件原形。350400250150200150 圖1 最小包絡矩形的求取2.聚合矩形的求取為了提高板材利用率，需要對零件進行一定程度的聚合然后求取聚合后零件的最小包絡矩形，稱之為聚合矩形。零件的聚合就是使零件相互接觸，但不重

16、疊，以達到包絡矩形的面積最小。在排料過程中由于零件可以任意方向旋轉，兩個零件的聚合問題就較為復雜，但根據文獻中的研究結果1，兩個相同的零件進行聚合，只有當兩個零件相差180。時，才能產生最小包絡矩形，因此，在零件聚合過程中，可以只考慮相差180。時的情況。圖2表示了零件聚合過程，其聚合過程如下：(1)求零件的最小包絡矩形，圖中虛線所示矩形即為零件的最小包絡矩形；(2)將原零件復制一個，翻轉180。，按其最小包絡矩形移到零件的左上角，如圖所示；(3)將原零件的總長度從左到右按一定精度等分，將復制件依次移動到每個位置后，依據碰撞算法心1分別與原零件碰撞，每次碰撞后，均求一次最小包絡矩形，記錄下該矩

17、形的面積。圖中實線所示的是其中一個位置上復制件與原零件進行碰撞的結果；(4) 將復制件沿原零件的上、下、左、右四個方向分別與原零件進行碰撞試驗，最后面積最小的矩形即為零件聚合體的最小包絡矩形，記下此時的位置和碰撞距離值。圖中所求得聚合矩形是將原零件經翻轉后從左邊靠近的結果。如果聚合后的聚合矩形的面積小于兩個零件的最小包容矩形面積之和，則聚合成功；反之則自動放棄聚合。對于聚合成功的零件圖形都可以提高其局部的材料利用率。36254.89945650聚合后的圖形如下： 362549945650（1）3625499456 （2）50圖2 零件的聚合3.不規(guī)則零件的排料過程 經過零件預處理求得了最小包絡

18、矩形、聚合矩形和多個的包絡矩形，這樣就把不規(guī)則零件的排放問題轉化為預后的矩形區(qū)域在板材上的自動排放問題。這里采用矩、啟發(fā)式技術與動態(tài)規(guī)劃法相結合方法解決不規(guī)則零件問題，不規(guī)則零件排料的過程是： (1)利用矩形法，分別求取兩個相同零件的聚合矩形，兩個零件的最小包容矩形面積之和相比較，若大于，保合結果；若小于，求其最小包絡矩形，將其轉化為矩形件； (2)將相同或近似零件的聚合矩形或最小包絡矩形組成“條料”； (3)決定使用所形成的候選條料直接填充板材，還是通垂直方向上劃分板材，用兩個子區(qū)域代替原來的矩形； (4)在當前的子區(qū)域上排放這些稱作條料的成組零件，過程中應用動態(tài)規(guī)劃分塊實時補充的方法解決“

19、子區(qū)中條料的填充問題。該方法的規(guī)則是：每次只排放矩形塊；長邊尺寸大的矩形塊具有優(yōu)先排放權；材圖形長邊按x方向放置，排放的零件按照最左、最下則放人；排放過程中按照板材的可用區(qū)域尺寸和待形塊的尺寸和數量來動態(tài)地劃分排放區(qū)域；每排放零件。已劃分的區(qū)域大都會產生一定的空白區(qū)域，對于區(qū)域仍按照上述規(guī)則用待排矩形塊進行補充，這一過程進行下去。直到排放完所有零件。其排料流程見圖3所示：開始應用排料過程解是否滿意？產生子區(qū)間產生最優(yōu)定位條件獲取板材輸入與初始化否是結束是否有余料？否板材是否排滿？空白區(qū)是否可利用？是是否否是圖3 自動排料系統(tǒng)流程圖5.2.2 建立數學模型 在將不規(guī)則零件轉化為條料后，就要研究條

20、料排料過程。既已知：=條料i的單位寬度；=條料的面積,需解決的問題是：確定出可排放條料的數量，使得各個候選條料的寬度之和不能超過當前矩形板材區(qū)域的寬度形，而且板材的利用面積最大。根據優(yōu)化理論，可以建立的排料的數學模型如下：，其狀態(tài)轉移方程為：排料數學模型的允許決策集合為：bi為由零件i所組成的條料的最大數目bi。 因而可寫出矩形排料模型動態(tài)規(guī)劃的遞推關系式為：其中，G(i，x)是從r個候選條料中選擇前I各條料在寬度為的子區(qū)域上排放獲得最大面積值。函數G(i，x)被初始化為零，即對于任意x，有G(0，x)=0。5.2.3模型的求解 采用動態(tài)規(guī)劃法。運用這種方法大大的減少了計算量，而且隨著階段數增

21、加，減少程度更為顯著。動態(tài)規(guī)劃法有逆序解法和順序解法兩種。卻已知初始狀態(tài)，因此采用逆推法。動態(tài)規(guī)劃中。k階段與k+1階段的遞推關系式可寫為：,K=n,n-1,，1 設已知初始狀態(tài)為s，第k階段的初始狀態(tài)位。最優(yōu)值函數表示從k階段到n階段所得到的最大收益。從第n階段開始，則有： ,其中是由狀態(tài)所確定的第n階段的允許決策集合。借此一維極值問題，就得到最優(yōu)解和最優(yōu)值。且若只有一個決策時，則就已被更改寫成。在第，n-l階段，有，其中 ，一維極值問題，得到最優(yōu)解和最優(yōu)值。如此類推，直到第一階段，由于初始狀態(tài)s1已知，故x1=x1(s1)和是確定的，從而也可以確定，照上述遞推過程相反的順序推算下去，就可逐步確定出每階段的決策及效益。5.3問題三5.3.1建立模型同問題一構思類似，如大化排樣的利用率，在二維矩形件排樣問題中，假設一次排樣中使用了2張矩形原片，第i(i=1，2)張原片的長為，寬為。待排樣矩形切片種類數為9，第j(j=1，29)類零件的長度為，寬度為，數量為。排樣完成后，原片上排布的類零件的數量為。第k個j類零件在原片上的位置由切片左下角點在原片上的坐標（）及零件的長寬確定。同一類型的不同切片坐標位置不同。切片的各邊與原件的對應邊保持平行。根據排樣實際需要，在滿足