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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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