5月1日數(shù)學建模華中賽甄選

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

2、賽隊員 (簽名)：隊員 1：隊員 2：隊員 3：武漢工業(yè)與應用數(shù)學學會第八屆華中地區(qū)大學生數(shù)學建模邀請賽組委會第八屆華中地區(qū)大學生數(shù)學建模邀請賽編 號 專 用 頁1 / 18doc 格式 可編輯精品 word.選擇的題號： A參賽的編號：（以下內(nèi)容參賽隊伍不需要填寫）競賽評閱編號：鋼構件的排料問題摘 要本文針對三種不同的約束條件下的板料布局切割問題，根據(jù)底部填充原則，即采用優(yōu)化后的 BL 算法模型來求解問題。問題一，只考慮板料在以寬度為基準的條件下，針對矩形零件以寬度在下為原則來布局。首先，根據(jù) 矩形零件特征，依據(jù)其長度長短寬度大小的順序提取，其次，將排好的零件依次擺置在板料寬度中，并每 一次

3、加以判斷剩余寬度并根據(jù)與數(shù)組中元素對應的寬度比較進行撤出和撤入選擇，最后不斷撤出撤入對板 料填充，最終得到優(yōu)化算法后的板料擺放格局。問題二，考慮不規(guī)則的零件擺放，采用最小包絡矩形的方式將不規(guī)則零件規(guī)則化，且既有零件的寬度 為底擺置也有零件的長度為底擺置。首先，進行單個不規(guī)則零件的最小包絡矩形化，采用問題一中的方式2 / 18doc 格式 可編輯精品 word.對最小矩形進行擺放，由于最小包絡矩形誤差大，無法在一板料下擺放，否定此種做法，其次，采用不規(guī)則零件各自兩兩拼接再進行最小包絡矩形化，并對問題一中的算法進一步優(yōu)化，運用 0-1 整數(shù)規(guī)劃的方式對零件的長寬組合和與板料寬度差值分別篩選并運用底

4、部填充和剩余寬度最小原則擺放，進行簡單人工干 預，最終得到進一步優(yōu)化算法的板料擺放格局。問題三，在問題二的優(yōu)化算法后，考慮變化為規(guī)定零件在兩板料擺放。首先，在問題二中的長寬組合 和與板料寬差值方式基礎上采用底部填充，剩余寬度最小以及高度差最小原則對在單個板料先進行擺放， 其次，在對板料寬已填充滿的那部分矩形組合上的階梯狀矩形按利用率最大的原則重復組合擺放，進行簡 單的人工干預，最終得到推廣的優(yōu)化算法的板料擺放格局。為了提高對模型求解準確性和明了性，本文采用 Matlab 算法對擺放布局一步一步動態(tài)擺放規(guī)定矩形。本文的優(yōu)點在于運用以簡單的算法并采用不斷優(yōu)化的方式，針對零件的多樣性和復雜性優(yōu)化擺放

5、格 局，不同的問題求解不同之處僅僅是其所規(guī)定的零件規(guī)格不同。關鍵詞： BL算法矩形件優(yōu)化排樣底部填充1 問題重述1.1 背景在鋼構件制造產(chǎn)品的生產(chǎn)過程中，依照產(chǎn)品零件尺寸從板料中截取大小適當?shù)牧慵^程稱之為排料， 也稱之為下料。排料是鋼構件制造的第一道工序。在這道工序中，不同的排料方案具有不同的材料利用 率，而原材料的利用率直接影響產(chǎn)品的成本。對于一個年消耗大量鋼材的生產(chǎn)單位，若能夠提高原料利用 率的 1%，那么其節(jié)約的鋼材成本是可觀的。因此，降低廢料率提高原材料利用率是鋼構件生產(chǎn)企業(yè)追求的 目標。根據(jù)實際情況，板材排料又可分為兩種：一是規(guī)則形狀的零件排料，一是不規(guī)則形狀的零件排料。規(guī)則形狀零

6、件是指矩形零件。其描述一般只需用矩形的長和寬。規(guī)則形狀零件的排料問題的實質是研 究如何組合零件擺放問題，使得在整個原料上擺放大量的不同長和寬的零件產(chǎn)生的廢料最少、整料和余料 的利用率最高。排放時，其零件間的搭接關系的處理相對容易，只需考慮長、寬兩個因素（含預留的損耗 量）。不規(guī)則零件在這里是指多邊形零件（一般的意義是指由直線、圓、弧、孔等的組合形），相對矩形零 件排料而言，不規(guī)則零件的直接排料要復雜得多。另外由于切割工藝的要求，切割只能實行“一刀切”的工藝（在整料或余料中，從一邊的某點到另外一邊某點的連線一次切割，但可以在切割下來的板料中再次切割）。板材的利用率就是所有零件面積之和與在一刀切工

7、藝后繼續(xù)切割的那部分板材面積的比值。 (即所有零件的面積為 S1，在對板材進行多次一刀切工藝，不能再進行一刀切的板料的面積為 S2，利用率 =S1/S2)3 / 18doc 格式 可編輯精品 word.1.2 所需要解決的問題(1) 對 1 張板料和若干規(guī)則形狀零件（板料和零件參數(shù)見附件 利用率最高。(2) 對 1 張板料和若干不規(guī)則形狀零件（板料和零件參數(shù)見附件 的利用率最高。(3)對 2 張板料和若干規(guī)則形狀零件（板料和零件參數(shù)見附件 利用率最高。1），如何在板料中擺放零件使其板料的2），如何在板料中擺放零件使其板料3），如何在板料中擺放零件使其板料的2.問題分析在制造工業(yè)需要大量鋼構件制

8、造產(chǎn)品，工廠要生產(chǎn)產(chǎn)品零件，就要從板料中截取大小適當排料來生產(chǎn) 零件，在生產(chǎn)中其原材料的利用率與生產(chǎn)企業(yè)的成本是密切相關的，故生產(chǎn)企業(yè)的目的就是要提供高質量 的排料方案來節(jié)約材料，降低成本來提高經(jīng)濟效益與社會效益。故要解決的就是優(yōu)化板材的使用效率。另外由于切割工藝的要求，切割只能實行“一刀切”的工藝（在整料或余料中，從一邊的某點到另外 一邊某點的連線一次切割，但可以在切割下來的板料中再次切割）。如下圖所示：2.1 針對問題一的分析鑒于題目所定義的板材的利用率就是所有零件面積之和與在一刀切工藝后繼續(xù)切割的那部分板材面積 的比值。針對一張板料是固定的，故要考慮到讓規(guī)則的矩形零件盡量合理緊密的排列，

9、讓矩形零件盡量無間隙的排列在一起。故可以利用 BL 算法來進行排列，但是有缺陷 ,有些最優(yōu)排樣圖是無法得到的，故要對BL算法進行改進可以根據(jù)矩形的長度與寬度對矩形進行排序，在對其進行有規(guī)律的排序即可得出。2.2 針對問題二的分析由于題目所提供的是五邊形與六邊形，故在問題一的基礎之上，可以用矩形來包絡五邊形與六邊形， 可以設計算法來找到最小的矩形來包絡該五邊形與六邊形。后通過對其運算后在板料上是無法排列出來 的。故對之前的最小矩形包絡進行優(yōu)化，得出對五邊形與六邊形各自進行兩兩拼接，設計算法找到最小的 矩形來包絡拼接后的圖形。4 / 18doc 格式 可編輯精品 word.2.3 針對問題三的分析

10、由于題目提供了兩塊大小一致的板材，所提供的零件是規(guī)則的矩形，在此問題中比問題一板材增加了 一塊板，故在問題一的基礎上還應考慮到零件如何更加合理的分配到兩塊板材上，使得零件分布在兩塊板 材上的利用率比在一塊板材上分布的利用率更高，故這里要涉及到分配的問題，不同的分配方式會有不同的利用率結果?；趩栴}一要應用運籌學中的 0-1 規(guī)劃來考慮分配。3.模型假設1、鑒于附件中所提供的零件數(shù)據(jù)值較大，以及數(shù)據(jù)的差值接近整百值，假設將數(shù)據(jù)進行整數(shù)化對布 局影響不大。2、假設板料只有長寬尺寸上的差別，不考慮厚度的因素影響。3、假設一刀切工藝后只有其中一部分允許再次一刀切切割。4、假設一刀切工藝后形成的不能再一

11、刀切的那部分允許其他非一刀切切割方式。4.符號說明符 定義號5.模型的建立與求解5.1 問題一的建模與求解5.1.1 問題分析通過對板材與零件尺寸大小的分析，尋找一種算法讓這些零件與板材更加契合故可以對這些零件根據(jù)其尺寸大小進行編號，故下述為改進后的 BL 算法。5.1.2 模型的建立與求解此模型基于 BL 算法來建立。(1)將板料按寬邊，底部填充原則設置初始最高輪廓線 T 為板材的最下面的邊，先根據(jù)已有數(shù)據(jù)進行篩選工5 / 18doc 格式 可編輯精品 word.作，按照長度從長到短，寬度從大到小原則進行排序，即先以長度優(yōu)先為準則，若長度一致的，再使用以寬度優(yōu)先排入為準則，以此類推對應地將其

12、編號： 1-16；形成一數(shù)組 。(2)先將 放在板料的左下角，寬度 w1 與原板料的寬度 wo貼合，長度與原板料的長度在最左側貼合，(3)：再排入 ，使 寬度在下，按照 (1)中所要求的原則，每當要排入一個零件 Pi(i=2， 3， 4 .).,就在最高輪 廓線 T 集中選取最低的一段水平線 ,如有數(shù)段 ,則選取最左邊的一段 ,測試該段線的寬度是否大于或等于要排零件的寬度 wi 。i:如果該段線的寬度大于要排入零件的寬度 wi ,則將該零件在此位置排放 ,并判斷排放后整體排樣高度的變化 ,如果排樣后高度增加了 (甚至超出了板材邊界 ),那么就從前面已排的零件中尋找寬度合適的零件 (零件寬度和該

13、段水平線的寬度均合適 ):a.如果沒有 ,則按照原排樣序列進行排 ,更新最高輪廓線后轉至第 (2)步;b.如有數(shù)個這樣滿足條件的零件 ,則先選取下標最小 Pmin 的一個 ,并判斷交換前后的整體排樣高度，然后 ,依次選取另外的幾個零件 ,進行相同的操作 :如果其中部分改變操作降低了整體排樣高度 H 0 ,則選取整體排樣高度最低的進行交換 ,并更新排樣序列和零件最高輪廓線 T,刪除對應的 Pi，其他已排樣的零件位置不變 ;如果改變都沒有降低整體排樣高度 ,則不改變排樣位置 ,按原序列進行排樣 .ii:如果該段線的寬度小于要排入零件的寬度 ,則從零件所在位置起向后搜索后面可以放下的零件a.如果有零

14、件的寬度恰好等于該段水平線的寬度 ,優(yōu)先排入此零件 ,并更新零件最高輪廓線提高至去除原定最低高度后的最低高度） ;b.如果沒有寬度相等的零件 ,則從該零件所在位置起向后搜索第一個可以放:L （更新即為下的零件 ,同時將這個零件調到待排零件的位置并排入 ;c.如果在這短線上沒有任意可以排放的零件 ,就將原來排的依次反順序撤出，并在依次撤出過程中后面 的零件中搜索寬度之和有無和為板材最下邊的寬度，如有就提前排入，若都沒出現(xiàn)情況就更新最低水平線T第二低的一段齊平 ,更新零件最高輪廓線 L.重復步驟 (2),直至將零件排入 ;重復上述過程 ,直至所有零件都排放完畢 .流程由下圖（ 1）所示：（圖 1）

15、圖一表示的是：先優(yōu)先選擇矩形件的長度排列，排列后可發(fā)現(xiàn)板料的底部還有 100 的間隙，而沒有矩形件的寬度是小于或者等于 100 的，故要將矩形件 2 退出，以此類推出下列的排料過程為圖（ 2）：6 / 18doc 格式 可編輯2S精品 word.圖（ 2）流程圖二中最后的一張圖就是矩形零件在板料上的擺放布局，由圖可知黑色那條線是第一次一刀切后，紅色的為第二次一刀切，最后所得到的板料就是不能再進行一刀切的部分，其面積為 S1。所有的零件面積之和為 S2.94.15%通過使用 MATLAB 編程可以得出最后可算出板料利用率 S15.1.3 模型的結果分析由上述可知板料的利用率為 94.15%，說明

16、用底部填充算法所得到的結果還是較優(yōu)的，說明底部填充算法還是有具有一定可行性的。因為該算法可以將板材的底部盡可能充分填充，故可讓板材的內(nèi)部盡量不出 現(xiàn)間隙?？沙浞痔岣甙宀膬?nèi)部使用率。5.2 問題二的建模與求解5.2.1 問題分析問題二是基于問題一的基礎之上，題目給出了兩類不規(guī)則圖形，為五邊形與六邊形（如圖 3，圖 4）首先會考慮將問題二轉化為問題一來處理，相對矩形零件排料而言，多邊形零件的直接排料要復雜得多。如何提高板材利用率 , 降低生產(chǎn)成本 ,從而帶來顯著的經(jīng)濟效益 ,是我們的研究重點。因此提出了一種簡單的 求取不規(guī)則零件的最小包絡矩形的方法，此方法通過假設將復雜多變的多邊形近似的看作在一個

17、面積和其最接近的矩陣（即為包絡的最小面積矩形）當中，再根據(jù)第一問中的改進后的 BL方法和底部填充原則將板料進行布局并排料。7 / 18doc 格式 可編輯精品 word.圖(3)圖（ 4）由于由于題目中所給出的零件一規(guī)格數(shù)據(jù)值較大，以及數(shù)據(jù)的差值接近整百值，故將零件一數(shù)據(jù)進行 調整，得到下表新的數(shù)據(jù)，如圖（ 5）對零件一改進后的數(shù)據(jù)0504103600圖（ 5）400400120005041036000400120004005.2.2 模型的建立建立最小包絡矩形具體步驟如下：(1) 先根據(jù)叉乘的判斷方法判斷多邊形的凹凸性，如果為凸變形就保持原來的形狀不變，如果為凹邊形 就將原多邊形凸化（具體凸

18、化方法見附錄）；(2) 通過比較得出多邊形的各個端點的距離間隔最遠的兩個點，記為 A， B；我們近似的看線 AB 為所求的矩形的對角線，(3) 由 A、 B 兩點與臨近的點組合可以得出 4 條邊；(4) 將這四條邊中的其中一條旋轉至 x 軸 ,讀出旋轉過后的各個端點的值，比較得到 、 、 、 ，則包絡矩形的面積為(5)：選下一條邊，重復步驟 (4)。(6)比較所得到的四個矩形的面積大小，選擇最小面積的矩形即為最小包絡矩陣。該算法的流程圖如下圖（ 6）所示：8 / 18doc 格式 可編輯精品 word.先用叉乘方法判斷多邊形的凹凸性凸多邊形將凹多邊形變?yōu)橥苟噙呅瓮ㄟ^比較得出多邊形各個端點距離最

19、遠的兩個點 A,B, 以線段AB 為所 求矩形 的對角 線，得到一個 矩形將所得到的矩形的一條邊旋轉至 x軸，得到包絡矩形的面積用 Matlab 編程比較得到最小的包絡矩形的面積得到最小的包絡矩形圖（ 6）通過以上辦法，我們先采用用最小包絡矩形包絡單個圖形形成一系列矩形，, ,同時大于， , 由于在矩形切割過程中根據(jù)底部填充原則必然出現(xiàn)的面積值，所以該模型無法使用，由于在用最小包絡矩形時與原來的多邊形之間產(chǎn)生的面積差過于大，我們通過將圖形的拼接使得產(chǎn)生的最小包絡矩形與拼接過后的多邊形的平均面積差比單個 多邊形的包絡小，優(yōu)于原來的包絡方式使得產(chǎn)生的剩余面積可以相對變大可供切割的靈活性相對就變大，

20、 我們采用了將五邊形和六邊形分別兩兩組合的方式產(chǎn)生最小包絡矩形，如圖（ 7）圖（ 8）所示圖(7)圖（ 8)圖中所示矩形拼接根據(jù)拼接理論，即在多邊形兩兩拼接后所形成的最小矩形必可以在以多邊形邊上的某一點為圓心旋轉一定角度 1800 后就可得到另一個拼接上的多邊形。圖（ 9）表格中我們以取計算出六邊形9 / 18doc 格式 可編輯0精品 word.各個邊的中點進行旋轉 180 形成的拼接六邊形的最小包絡矩形為例比較各個產(chǎn)生的面積Length700Width550Squart38500700800800650400500350400280000400000280000260000550 500

21、275000圖（ 9）由于用標準方法求得的最小包絡矩陣與圖中將五邊形延長形成對角線的方法形成的誤差遠小于 總面積而言，故在此題中我們用延長對角線的方法來近似看做最小包絡矩形。我們對第一問中所依據(jù)的算法進行優(yōu)化，類似與第一問的算法，其具體算法類似于問題一中的算法如 下：第一步：設置初始最高輪廓線 L 為板材的最下面的邊，先根據(jù)已有數(shù)據(jù)進行篩選工作，按照長度長短，寬度大小原則進行排序，并對應地將其編號： 1-14；形成一數(shù)組 。第二步：將 (i=1,2 自的值，儲蓄于數(shù)組i14sum( j ) ti ( pi L (i) (1i1 .1別根據(jù) i 的不同性以及它們的長寬 L,W 以多種方式組合并且

22、求出并它們的各中pi )W (i )第三步：將最高輪廓線 T 的長度 L0 與數(shù)組 sum 中各個值進行比較，其中的最小值 min(sum(j)-b)所對應的 Pi 以及對應的長寬相加形式，如果最高輪廓線的寬度 L 大于得出的最小值 ,則在各個的出的差值中搜索后面可以放下的零件a.如果差值恰好等于該段水平線的寬度 ,優(yōu)先排入求得該差值對應的零件組合方法的此組零件 組 P 中對應的元素，并更新數(shù)組 sum 以及零件最高輪廓線 L;:,刪去在數(shù)b.如果無 a 中的情況 ,則得出從所有差值中與水平線 L 寬度絕對值最小的那個差值對應的 Pi 以及對應的長寬相加形式 ,同時將相對應 Pi 以及其對應的

23、長寬方式調到待排零件的位置并排入 ;刪除排入后在數(shù)組 P 中的 Pi, 更新數(shù)組 sum 以及零件最高輪廓線 L;如果最高輪廓線的寬度小于得出的最小值，更新零件最高輪廓線 L;重復第二，第三步， ,直至將零件排入 ;重復上述過程 ,直至所有零件都排放完畢 .通過 MATLAB來求解在上述步驟（ 4）中的最小包絡矩形的求解，可以得到兩個五邊形拼接后得到的最小面積為 S5min 580 430 249400兩個六邊形拼接后得到的最小面積為 S6min 650 400 260000最后可得到最小的包絡矩形在板料上的擺放方式為圖 (10 )10 / 18doc 格式 可編輯q 1 t i ( p i

24、L m ( i ) (1 p i )W m ( i )精品 word.圖 ( 10)最后所得到的板料就是不能再進行一刀切的部分，其面積為 S1。所有的零件面積之和為 S2.計算可得利用率 87.23%5.2.3 模型的分析由上述得出的利用率為 87.23%可知，利用率比問題一中的利用率小，造成此結果的原因是：對五邊形與六邊形進行兩兩各自拼接后，再找到最小面積的矩形來包絡拼接后的多邊形，在此期間會產(chǎn)生一定的廢 料，由于拼接后所得到的最小包絡矩形，在板料中進行排料時會產(chǎn)生較多的廢料，故要對問題一中的模型 進行改造，對最小包絡矩形的長與寬的擺放可以多種進行組合。此模型可將板料的底部充分填充。故可以

25、得到一個較優(yōu)的結果。5.3 問題三的建模與求解5.3.1 問題分析在此問題中板材增加了一塊板，故在問題一的基礎上還應考慮到零件如何更加合理的分配到兩塊板材 上，采用合理的分配方式使得零件分布在兩塊板材上的利用率比在一塊板材上分布的利用率更高，故這里 要涉及到分配的問題，不同的分配方式會有不同的利用率結果。5.3.2 問題的建模與求解建模的具體算法步驟如下：1、此類問題中的核心方法：以底部填充原則法對板料的寬度 i 31的先進行填充，若 i 1 ，L0 ,用問題二的方法對底部能被完全填充其中 ti , pi 只能取 0 或 1， ti 表示是否選擇第 i 種零件， pi=1 表示選了第 i 種零

26、件后用它的長去填充， pi =0 表示選了第 i 種零件后用它的寬去填充 ,若出現(xiàn)多組數(shù)據(jù)都能被完全填充，則按照其組合形成的高度差i k i0I H ( i )H 最小 i k 先放置的原則對板料進行左邊高右邊低的階梯狀放置，同時在長寬數(shù)組 L， W 中刪去已填充的元素值，將刪除過后的數(shù)組形成一新的長寬數(shù)組 ，更新零件最高輪廓線 L;重復循環(huán)步驟直至11 / 18doc 格式 可編輯精品 word.無法在進行填充為止，形成一新的長寬數(shù)組 ；2、再將長寬各自的新形成的數(shù)組運用底部填充原則組合成的值與原板料寬度差最小的先填充 ,若出現(xiàn)多組差值都一樣的，則按照其組合形成的高度差 H 最小先放置的原則

27、對板料進行左邊高右邊低的階梯狀放置重復步驟 2，直至將一塊板料填充完全，更新零件最高輪廓線 L;3、題中要求可選擇性填充兩塊板料，先按第 2 步方式填滿其中一塊板料，填充完整的因其不會對利用率產(chǎn)生影響故放置在一塊板料上不動，在形成階梯狀的未被填充完整的另外一部分按照利用率最大的原則將階梯狀的整體 “臺階 ”在兩塊板上進行挪動，重復挪動 梯 ”，分別求所得利用率，直至使求得階梯狀在兩塊板料中適當?shù)姆植?，使所求利用率最高?1)通過 MATLAB畫圖可得到若只在一個板料上排料，可得下圖 11 的排料方案：圖(11)(2)以下為在兩塊板料上，對矩形在兩塊板料上的合理分布得到的排料方案，鑒于矩形在板料

28、上是基于以板料的寬先擺滿的原則，若能把板料的寬上擺滿后，再進行擺放的過程中，要 以從左到右以高度優(yōu)先為準則，依次呈階梯狀排樣方案可得到以下幾種不同的排樣方案：方案一的排料方案如下圖 11， 12：12 / 18doc 格式 可編輯精品 word.圖(12)圖(13)方案二的排料方案如下圖 14.15圖(14)圖（ 15）最后可以得到若只在一張板材上進行排料可得到利用率為 92.21%方案一得到的利用率為 97.99%方案二得到的利用率為 98.60%5.3.3 模型的分析13 / 18doc 格式 可編輯精品 word.由模型的求解過程可以得到板材的最優(yōu)的利用率為 98.60% ，建立此模型的

29、思想為：先在一塊板料上對所有零件進行排料，可得到一個擺放的方案?？捎梢粔K板料上的擺放可以優(yōu)化得出，因為在一塊板料上每 一次的段線上都有可能出現(xiàn) , 因此得到的排料方案是呈多樣性的，故通過多次組合嘗試可得出一個較優(yōu)的排 料方案。使得利用率較高。6 模型的優(yōu)缺點與改進6.1 模型的優(yōu)缺點優(yōu)點：(1)BL 算法在實際的開發(fā)與研究過程中能較為廣泛的運用 ,其策略思想較易理解 ,實現(xiàn)較為簡單 ,適用范圍廣。(2)問題二中對問題一中的底部填充對矩形的限制變小，可對矩形的長度與寬度進行自由地組合，使得 模型的應用范圍更加廣泛。(3)底部填充法則可以讓零件分布在板材的下部，使得矩形零件較緊密地排列。(4)該算

30、法能很好的滿足貫通要求。缺點：對于矩形排樣的零件個數(shù)只能為有限個。只適用與矩形零件的一刀切問題，不規(guī)則零件通過最小包絡矩形的方法對板 材的浪費可能造成損失會變大，使利用率變化幅度強烈。底部填充的算法還是帶有主觀性的，在編程中具有局限性。6.2 模型的改進(1)在求解問題二時是通過最小包絡矩形對其中兩個相同規(guī)格的多邊形即為五邊形、 六邊形包絡，其對板料的浪費率還是較高，要更好的提高利用率，要求我們用更優(yōu)化的拼接方式，五邊形和六邊形的拼接， 形成一個臨界多邊形，不同的臨界多邊形決定了不同的擺放方式，例如：我們用三個五邊形拼接，示例如圖 (16)所示拼接而形成一臨界六邊形。14 / 18doc 格式

31、 可編輯精品 word.圖(16 )以此類推可以得到：利用 4 個或 5 個五邊形進行拼接，其拼接的可能性是多種方式的，上述的建模過程沒有進行對多種拼接進行討論，故該模型不夠完善，故可按此方向對模型進行改進。（2）對問題三中附件中出現(xiàn)的數(shù)據(jù) 零件二（ 0 個）零件二的規(guī)格03503500圖（ 17）002002003503500002002000我們將其中的 0 個視為零件二不限個數(shù)，我們采用問題三中方式，并制定規(guī)定的分配標準，目標為： 生產(chǎn)完附件三中所要求的其余零件能擺放零件二的最大個數(shù)。這個可以視為模型改進的一個方向(3)在求解問題二時是通過最小矩形包絡，由于其對板料的浪費率較高， 還可用

32、臨界多變形整體逼近來求解問題。(4)在對矩形選取的過程中， MATLAB只能對矩形的長度進行篩選，只能在一維的條件下進行選取。6.3 模型的推廣改進后的 BL 算法不僅僅可以使用在剛構建排料中使用，還可以應用在以下領域：服裝制造業(yè)生產(chǎn)過程的布匹材料的分割過程塑料制品中塑料板材、型材的分割家具制造業(yè)木質家具膠合板的分割15 / 18doc 格式 可編輯精品 word.7 參考文獻1 姜啟源等 .數(shù)學模型 M. 北京：高等教育出版社， 2003.2 葉曉光 .綱結構排樣優(yōu)化問題研究 D. 浙江 .浙江大學， 2008.5:21-293 劉月明 .二維不規(guī)則零件排樣算法及系統(tǒng)的研究 D.廣東 .華南

33、理工大學， 2012.11： 15-194 盧齊飛 .二維不規(guī)則圖形下料排樣優(yōu)化算法研究 D.廣東 .廣東工業(yè)大學， 2013.6： 10-175 王正東等 .數(shù)學軟件與數(shù)學實驗第二版 M. 北京：科學出版社， 2010.86 井振毅等 .MATLAB實用寶典 M. 北京 . 中國鐵道出版社， 2008.127 張軍等 .一刀切下料的數(shù)學模型 N.吉林 .延邊大學， 2001.38 郭瑞峰 .基于病毒進化遺傳算法的二維不規(guī)則圖形排樣 D. 廣東 .廣東工業(yè)大學， 2014.058.附錄BL算法的具體步驟如下：對于一個給定的排樣序列 Pj(j=l,2,n),規(guī)定橫放為正 ,豎放為負 .(l)將零

34、件 P1 放在板材的左下角 ,若 P1 為負值 ,則將其旋轉 90 度后再排放 ,并求出排放后所占板材的最大高度 ;(2)將零件 Pi(i=l,2,n)置于板材右邊最大高度處后 ,交替向下左移動尸 i,首先盡可能地向下移動 ,然后再盡可能地向左移動 ,直至無法再向下向左移動為止 (即接觸到其它零件或板材邊界 ),并求出此時的最大高度 .重復上述過程 ,直至所有零件排放完畢 ,最后所得到的最大高度即為所需板材的高度根據(jù)參考文獻（二維不規(guī)則圖形下料排樣優(yōu)化算法研究 _盧齊飛）對二維不規(guī)則零件的凹凸性判斷：用叉積法:繞多邊形的周長計算相鄰邊向量的叉乘 ,如各叉積均同號 ,則為凸多邊形 ;如果有正有負 ,則為凹多邊形。凸化方法：用上面所述方式對所要求的零件每個點進行凹凸性判斷，如果出現(xiàn)凹點，就將凹點附近的兩個 點相連代替原來的多邊形%此程序目的是填充滿長度或寬度為 n 的板料忽略其高度是否變化和寬度長度的組合排列，以填充三種零件為例進行填充function s=baifang(l1,n1,l2,n2,l3,n3,n)%l