第一篇：國內(nèi)外非?；钴S的研究課題材料利用率的最大化一直是人們追求的目標(biāo)（最終版）

國內(nèi)外非?；钴S的研究課題材料利用率的最大化一直是人們追求的目標(biāo)。這類矩形件的排料屬典型的組合優(yōu)化問題 具有很高的計算復(fù)雜性。所謂有限制二維板材優(yōu)化下料 就是利用一定規(guī)格的板材 為指定尺寸 指定數(shù)量和指定紋理的零件下料 在滿足配套的和切割便利前提下 使板材的利用率最高。在各行各業(yè)的下料中，涉及大量的二維優(yōu)化下料問題，最優(yōu)二維下料所涉及的知識面非常廣泛，具體的方法種類繁多，應(yīng)用也極為普遍。傳統(tǒng)的下料工作都是人工依靠經(jīng)驗進行的，時間長并且效果不理想。由于生產(chǎn)實際的需要，人們迫切需要利用現(xiàn)代科技來解決這一問題。本文在分析國內(nèi)外下料問題研究現(xiàn)狀基礎(chǔ)上，引入 A 玩具企業(yè)關(guān)于布絨玩具布料二維裁剪的實例，要求使用布料皮數(shù)最少來實現(xiàn)公司的既定目標(biāo)，實現(xiàn)其利潤的最大值。本文以 lingo 軟件作為計算平臺和工具庫，計算具有實用價值的二維不規(guī)則零件優(yōu)化下料系統(tǒng)。該系統(tǒng)具有良好的數(shù)據(jù)接口和友好的交互環(huán)境，用戶可以方便地輸入和調(diào)整參數(shù)該系統(tǒng)具有快速的響應(yīng)特性，可以在比較短的時間內(nèi)得到下料結(jié)果。關(guān)鍵詞：優(yōu)化，二維，下料 I 龍麒文：最優(yōu)二維下料 ABSTRACT Optimized packing has been a very active research topic at home and abroad tomaximize material utilization has been one goal.Such materials are of rectangulartypical combinatorial optimization problems with high computational complexity.The so-called two-dimensional sheet optimization of restricted feeding is the use ofcertain specifications sheet the specified size specify the quantity and texture of theparts under the specified materials and cutting in the supporting facilities to meet theprerequisite to make sheet usage.Under the compound in all walks of life involvinga large number of two-dimensional optimization of cutting stock problem the optimaltwo-dimensional cutting stock a wide range of knowledge involved the specificmethod of a wide range of applications are very common.Under the traditionalmanual work is expected to rely on experience and a long time and are not ideal.Since the actual production needs people urgently need to use modern technology tosolve this problem.This paper analyzes the domestic and international issues of material under thepresent situation based on the introduction of A toy business on the two-dimensionalcutting fabric toys instance requires the least number of fabric skin to achieve thecompanys stated objectives to achieve their maximum profit.This paper lingo software computing platforms and tools as libraries computinghas the practical value of the two-dimensional irregular parts optimized blanks.Thesystem has a good data interface and friendly interaction environment users caneasily input and adjust the parameters the system has fast response characteristicscan be obtained within a relatively short period of time under the expected results.KEY WORDS：Optimization two-dimensional cutting II 2010 屆數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)畢業(yè)論文 第1章 前 言1.1 下料問題概況1.1.1 下料問題的提出及意義 隨著全球資源的日益匱乏，人們對資源利用問題的研究愈來愈重視。最大限度地提高原材料利用率是生產(chǎn)中提高效益的一個重要手段。平面下料，一般是指把表示零件二維輪廓的多個相同或不同的幾何圖形，在原材料平面區(qū)域上找到一個合理布局，使得幾何圖形之間不出現(xiàn)重疊并且材料利用率幾何圖形的面積/原材料平面區(qū)域的面積最高。在理論上，下料問題涉及到計算幾何、運籌學(xué)、計算機圖形學(xué)、邏輯推理等多學(xué)科、多領(lǐng)域的知識，屬于復(fù)雜的組合最優(yōu)化問題，從數(shù)學(xué)計算復(fù)雜性理論的角度來看，優(yōu)化下料問題是屬于具有最高計算復(fù)雜性問題。但是，在很多企業(yè)，仍然是在沒有下料圖的情況下進行人工下料，下料技術(shù)人員僅僅憑借自己的經(jīng)驗自由地在材料上下料，一般排出來的并不是最優(yōu)的方案，并且材料浪費很多有些企業(yè)，即使有下料圖，但是一方面下料圖是人工繪制，費時費力，效率低下，另一方面也不能做到最優(yōu)化下料，材料利用率仍然不高。而且對規(guī)模較大的下料問題，不但手工下料不可能做到真正的優(yōu)化，即使采用計算機輔助下料也必須開發(fā)高效的算法才一能實現(xiàn)利用率相對較高的優(yōu)化料和切割。因此，企業(yè)必須尋求快速高效的下料方式，以提高在市場中的競爭能力。計算機和計算機輔助技術(shù)的應(yīng)用和發(fā)展，大大提高了工作效率和質(zhì)量，使得許多人工難以完成的工作成為可能。上世紀(jì)四十年代以來，人們便嘗試著提出各種理論，設(shè)計不同的計算方法來解決計算機輔助優(yōu)化下料問題。優(yōu)化下料問題實際上是一個十分困難的問題，從數(shù)學(xué)計算復(fù)雜性理論看，它屬于 NP 完全問題，也就是說在一般情況下，即使是使用很快的計算機，在人們可以接受的時間內(nèi)也不太可能求出這類問題的最優(yōu)解。另一方面，由于實際生產(chǎn)的需要，人們又迫切需要利用現(xiàn)代科技對這一問題給出一個能滿足生產(chǎn)需要的求解方法。這些方法應(yīng)該是能以較高的計算速度求出一個近似的解。所謂近似的解是指雖然不是最優(yōu)解，但接近最優(yōu)解，并且要比人工下料的效果好，能達(dá)到或超過人們所期

望的材料利用率。下料系統(tǒng)的意義，可以歸納為:通過節(jié)約材料、減少下料工作量和化簡切割工藝，1 龍麒文：最優(yōu)二維下料最終達(dá)到降低產(chǎn)品成本的目的。1.節(jié)約材料，提高經(jīng)濟效益 人工下料受人的工作態(tài)度、能力等主觀因素所限制，很難給出材料利用率最高或者接近最高的下料方案。應(yīng)用計算機輔助優(yōu)化下料，可以充分發(fā)揮計算機強大的計算能力，經(jīng)過大量下料方案的比較，選出材料利用率最高或者接近最高的下料方案，以達(dá)到節(jié)約材料的目的。2.減少下料工作量，加快下料速度 人工下料時，為了得到一個較好的下料方案，往往需要長時間的反復(fù)工作。而計算機輔助下料，則可以在非常短的時間內(nèi)完成下料，并且得到高質(zhì)量的下料方案。3.化簡切割工藝，減少切割工作量 下料時經(jīng)常遇到這樣的情況，存在許多材料利用率接近的下料方案，稱其中材料利用率最高的下料方案為最優(yōu)下料方案。應(yīng)用計算機輔助下料，可以在大量的達(dá)到最優(yōu)或接近最優(yōu)的下料方案中，選擇切割工藝盡可能簡單的下料方案，減少切割工作量。在生產(chǎn)實踐中，下料問題廣泛出現(xiàn)并等待解決。下料的優(yōu)劣，直接與材料成本及經(jīng)濟效益有關(guān)，而傳統(tǒng)的手工下料效率低、勞動強度大，不僅耗費了企業(yè)技術(shù)人員大量的勞動，而且下料時間長、材料利用率低，降低了企業(yè)的生產(chǎn)效率和企業(yè)的市場反應(yīng)能力，增加了生產(chǎn)成本。在激烈的市場競爭中，企業(yè)必須降低生產(chǎn)成本、提高生產(chǎn)效率、增強對市場的反映和應(yīng)變能力，否則，將面臨淘汰的威脅。企業(yè)必須尋求快速高效的下料方式，以提高在市場中的競爭能力。所以，特別是在零件種類繁多，零件數(shù)目巨大，零件形狀復(fù)雜的情況下，由人工實現(xiàn)下料問題的難度很大，而利用計算機輔助下料可以通過計算機實現(xiàn)優(yōu)化下料工作，節(jié)約材料、減少下料工作量，提高下料效率，最終達(dá)到降低產(chǎn)品成本的目的，提高了企業(yè)的競爭力。對下料問題的研究已經(jīng)有很久的歷史，特別是在最近的三十年，這類問題已經(jīng)在操作研究和計算機科學(xué)兩方面都取得了廣泛的關(guān)注，原因是它有巨大的理論背景和廣泛的應(yīng)用領(lǐng)域。1.1.2 下料問題的分類及應(yīng)用 我們通常說的下料問題，指的就是平面下料問題，按照零件的維數(shù)可以劃分為：一維下料問題、二維下料問題和三維布局問題，其中二維下料問題是研究最廣也是最深入的因為研究的側(cè)重點和表現(xiàn)形式不同，廣義的說，下料問題又有很多名稱，如：下料問題、裝箱問題、背包問題、貨盤裝載、布局問題、最優(yōu)平衡、內(nèi)存分配等。隨著二維下料問題應(yīng)用范圍的越來越廣泛，對其的研究也逐漸加深，從開始的對矩形件的下料問題研究，到對不規(guī)則零件的下料.由于二維不規(guī)則零件下料問題有著有更廣泛 2 2010 屆數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)畢業(yè)論文的應(yīng)用領(lǐng)域，所以，也成為了目前下料問題研究的重點和難點。下料問題廣泛應(yīng)用于鉑金加工，服裝，印刷業(yè)中各種圖書的排版，航空航天工業(yè)，造船業(yè)，紡織業(yè)，玻璃加工業(yè)及交通運輸，電子工業(yè)中集成電路的排布及倉庫零件的存儲等。表 l 所示為材料下料問題較多的行業(yè)，這些行業(yè)構(gòu)成了下料的主要應(yīng)用領(lǐng)域： 表 1 構(gòu)成了下料的主要應(yīng)用領(lǐng)域 應(yīng)用分類 舉例 金件加工 工業(yè)用各種金件、廚房用具和各種家用電器用金件、打字機 電子元件用金件、電動機用硅鋼片、造船業(yè)金件 服裝行業(yè) 各種布料、皮革下料，如襯衫、西服、鞋襪、降落傘等。布 料皮革定級中的優(yōu)化下料等 紙業(yè)與玻璃頁 辦公用紙、財務(wù)用紙的裁制等，玻璃的裁制 木材制品 各種家具 印刷業(yè)排版 各種書刊、報紙排版、印刷電路板 集裝箱裝貨 將貨物組合優(yōu)化后裝入有限空間的集裝箱中 型材棒材下料 棒材、角鋼、工字鋼等各種型材下料，建筑業(yè)中鋼筋、鋁合 金下料 微電子工業(yè) 集成電路的排布 軍事國防 圖形目標(biāo)的搜索等優(yōu)化問題 航空航天 航天器倉布局1.2 二維下料問題1.2.1 二維下料問題的分類 二維排料問題大致分為兩類：第一類是矩形件下料問題，這類問題可以說是下料問題研究的熱點，在工業(yè)生產(chǎn)中常見的要求有兩類:一是材料數(shù)量無限，而要求的矩形件數(shù)量是固定的，要求耗用材料量最少二是材料數(shù)量有限要求排列出盡可能多的矩形，使廢料最少。第二類是不規(guī)則件的下料問題。這類問題是下料問題研究的難點，由于零件和材料均為任意形狀，切各自的大小均不同，使得每一次排料均得重新下料，因此，增加 3 龍麒文：最優(yōu)二維下料了問題的難度，所以下料問題的解法只是尋找一個較好的解決問題的方法，尋找近優(yōu)解而不是最優(yōu)解。1.2.2 二維下料問題現(xiàn)狀綜述 優(yōu)化下料技術(shù)的研究理論涉及到線性規(guī)劃、動態(tài)規(guī)劃、啟發(fā)式算法以及人工智能等多種學(xué)術(shù)研究前沿理論，國內(nèi)外許多學(xué)者對二維下料（下料）問題進行了大量的研究，取得了一定的成果。對于學(xué)術(shù)的深層發(fā)展和繁榮，具有一定的推動意義： Lindecrantz1 1964 首 次 提 出 基 于動 態(tài) 規(guī) 劃解 決矩 形 材等 切 割 問題 的算 法。Gilmore amp Gomory 2 3 1965，Beasley 4 1985都是采用的用動態(tài)規(guī)劃解決無約束二維截斷切割問題。Viswanathan amp Bagchi5 1993提出了一個從底向上的最佳優(yōu)先搜索算法，解決約束二維直角截斷切割問題。黃繼進 6 1994結(jié)合動態(tài)規(guī)劃和人工智能啟發(fā)式搜索的思想，通過修正 Haims 使用動

態(tài)規(guī)劃法實現(xiàn)二維矩形優(yōu)化排料的算法，提出了帶預(yù)選搜索步深的二維一刀切矩形優(yōu)化排料算法，簡稱 GRSCO 排料算法。Tarnowski71994提出了解決二維 Guillotine 切割問題的多項式（二次）時間算法，將初始問題分解為三個子問題，其中兩個由多項式時間內(nèi)的動態(tài)規(guī)劃求解，還有一個子問題求解的時間為常量。1.2.3 二維下料問題的發(fā)展趨勢 目前排樣問題的主要研究熱點集中在二維排樣方面，主要包括矩形排樣和二維不規(guī)則排樣問題。矩形排樣方面，主要以研究動態(tài)規(guī)劃方法、矩形定位策略和排樣方案智能搜索為主。二維不規(guī)則排樣方面，由于形狀的復(fù)雜性，還必須考慮幾何形狀上的表示方法，以及幾何區(qū)域之間的重疊、靠接、包含等計算同時旋轉(zhuǎn)角度上的隨意性使得可行的排樣方案數(shù)量上為無窮大。因此當(dāng)前研究趨勢主要集中在以下幾個方面: l不規(guī)則形狀的表示和幾何計算:不規(guī)則形狀表示在早期的文獻中多采用矩形擬合方法，目前這種方法由于不夠精確已很少出現(xiàn)，而主要以點陣圖形表示法和多邊形表示法為主。其中點陣表示法圖形計算較為簡單，但是精度較低，時間復(fù)雜度較高。多邊形表示法目前已成為研究熱點，用于快速計算多邊形重疊判斷和靠接位置的臨界多邊形 NFP 則是多邊形法排樣的關(guān)鍵問題。2零件定位策略:從原來的“最左最下”原則，目前己發(fā)展到“最低水平線”、最高材料利用率、以及綜合評價等原則。3方案編碼和解碼:從最初的序號編碼，目前發(fā)展到主要包括序號和角度編碼，序號、角度和向限區(qū)間編碼，坐標(biāo)點和角度編碼，是否允許鏡像等因素也逐漸加入到 4 2010 屆數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)畢業(yè)論文了編碼當(dāng)中。方案的解碼負(fù)責(zé)將編碼還原為具體的排樣方案，必須和零件定位策略相結(jié)合，并在保證零件不重疊等約束條件下得到一個排樣方案。4智能搜索算法從最初的啟發(fā)式算法目前發(fā)展到大量采用智能算法例如模擬退火算法、禁忌搜索算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)以及蟻群算法等。1.3 論文背景及主要研究方向1.3.1 論文背景 XX 玩具實業(yè)有限公司是集設(shè)計、開發(fā)、生產(chǎn)、銷售為一體的中大型企業(yè)，真正具有自主品牌的毛絨玩具企業(yè)。XX 公司位于占地面積 10000平方米，環(huán)境優(yōu)雅，交通極為便利。公司現(xiàn)有衣車300 臺，裁床機 4 臺，打棉機 2 臺，沖棉機 3 臺，龍門過針機 2 臺，電腦繡花機 3 臺，及其它配套的設(shè)備。產(chǎn)品設(shè)計人員均為大專以上設(shè)計及相關(guān)專業(yè)畢業(yè)，具有極高的靈感及創(chuàng)意。曾在行業(yè)產(chǎn)品設(shè)計比賽中多次獲得殊榮。開發(fā)師們功底同樣深厚，都有至少 4 年以上的工作經(jīng)歷，技術(shù)嫻熟，深諳消費者的理念。公司擁有自己的玩具品牌，有 30 多個系列 1000 多個品種，涵蓋毛絨玩具、節(jié)日禮品、汽車用品、文具用品、手機玩具、床上用品、兒童玩具、聲控玩具、影控玩具、錄音玩具、音樂玩具、電動玩具、智能玩具等，產(chǎn)品不僅新穎美觀，而且大方實用。公司立足大陸，面向世界。除在國內(nèi)建立經(jīng)銷加盟的網(wǎng)絡(luò)外，還和眾多知名的公司建立良好的合作關(guān)系。在國外公司產(chǎn)品出口歐美、俄羅斯、日本、臺灣等國家和地區(qū)，公司的品牌產(chǎn)品已經(jīng)走向五湖四海。公司嚴(yán)格執(zhí)行 GB6675-2007、GB9832、GB5296.5 和歐洲 EN--71 的標(biāo)準(zhǔn)生產(chǎn)，參照“COC”社會責(zé)任運作，于 2009 年通過 ISO9001:2008 國際質(zhì)量體系認(rèn)證。公司秉承著以為消費者提供高質(zhì)、環(huán)保、安全、時尚的毛絨玩具的宗旨，引導(dǎo)國內(nèi)玩具市場的流行趨勢，致力于打造中國玩具毛絨玩具第一品牌1.3.2 論文主要研究內(nèi)容 毛絨玩具是絕大多數(shù)小孩子所喜愛的玩具，消費量很大，中國制造的毛絨玩具也很普遍。然而，大部分企業(yè)技術(shù)含量低，勞動強度大，資源浪費嚴(yán)重，經(jīng)濟效益低。顯而易見，只有開發(fā)出一種最優(yōu)化的利用原材料進行合理的下料，就能改變這種資源浪費。經(jīng)過多次試驗比較，我們終于成功開發(fā)了這項技術(shù)，并成立此玩具公司，進行 5 龍麒文：最優(yōu)二維下料科學(xué)高效利用原材料，合理下料。生產(chǎn)毛絨玩具的過程中，主要生產(chǎn)環(huán)節(jié)就集中于玩具的裁剪和縫紉問題上面，其中，關(guān)于裁剪方面的布料下料最大化利用則是企業(yè)利潤提升的關(guān)鍵，所以，在這，我們通過所學(xué)的專業(yè)知識，對二維下料的最大化利用作相關(guān)的探討和研究?，F(xiàn) XX 公司收得一份 10 萬毛絨玩具的訂單，因公司的生產(chǎn)線和生產(chǎn)原材料即布匹尺寸是固定的，制作毛絨玩具所必需的裁剪樣式也是由 5 種裁剪圖樣所構(gòu)成：圖樣【1】3 件、圖樣【2】3 件、圖樣【3】2 件、圖樣【4】1 件、圖樣【5】1 件。我們要實現(xiàn)公司的的利潤最大化利用，就必須通過最優(yōu)化處理，找到最合適的下料方法，使布匹的利用率達(dá)到最大化，以此，我們利用最優(yōu)二維下料來解決此事。1.4 解決問題的方法與思路 對于二維下料問題，下料方式要滿足零件長，寬方向上的套裁，所以遠(yuǎn)比一維下料復(fù)雜且數(shù)量大得多.因此，我們希望通過降維啟發(fā)式方法即通過形成“板條”而把二維下料問題降為一維下料的方法來解決.在此稱一維下料的原材料為“條材”，而二維下料的原材料為“板材”.板材與條材的區(qū)別在于:條材加工時只考慮長度而板材要同時考慮長、寬.如果把零件成組看待，板條就是這樣一種零件組:其在一個方向上的長度等于或近似于原材料的長或?qū)挿较虻拈L度然后在另

一個方向即原材料的寬或長方向進行裁剪.這樣，二維下料問題因“板條”的引人便降為一維下料問題。因此，要實現(xiàn)目標(biāo)，就要分兩步進行：第一步：尋求一張原始布皮所能裁剪出的圖樣的所有方案。第二步：綜合所有方案，運用數(shù)學(xué)知識，構(gòu)造目標(biāo)函數(shù)，得出最少布匹完成方案。6 2010 屆數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)畢業(yè)論文 第 2 章 數(shù)學(xué)模型的建立2.1 數(shù)學(xué)模型的選擇 零件的寬度決定板條的種類，當(dāng)種類確定后，則要在不超過寬或長度的前提下在原材料上進行板條的布局有若干種.而布局方式一旦確定，就只剩下每個板條內(nèi)部零件組的組合問題，這時就可利用一維中求解下料問題的啟發(fā)式多級序列線性優(yōu)化的方法來解決.其建模的具體過程類似于一維的分層建模思想，即先滿足原材料最少要求，再從中選出其中滿足時間要求的二維下料最優(yōu)方案.