下料問題.doc

關于一維下料問題的研究摘要： “下料問題”是把相同形狀的一些原材料分割加工成若干個不同規(guī)格大小的零件的問題此類問題在工程技術和工業(yè)生產中有著重要和廣泛的應用在生產實踐中通常要求解決用料最省、浪費最少等問題下料問題即是其一。屬最優(yōu)化研究范疇一維下料問題是生產實踐中常見的問題，優(yōu)化下料要求最大限度地節(jié)約原材料，提高原材料的利用率。本文介紹了兩種方法，其一提出分支定界算法優(yōu)化一維下料問題，并用MATLAB編寫程序，通過計算機來完成這一復雜的過程。另一種方法-lingo，針對單一原材料的一維下料問題, 建立了整數規(guī)劃模型, 然后將模型轉化為求解最優(yōu)下料方式問題; 利用lingo進行編程, 實現循環(huán)調用得到一維下料問題的局部最優(yōu)解。實際上本文就是給出了解決適當規(guī)模下料問題的求解方法該方法既可手工演算又可通過計算機求解。在實踐中可以借鑒使用Abstract： The “utting Stock Problem”is a problem of dividing raw materials in the same shape into several parts in different shapes This kind of problem has important and wide appliance in engineering and industry productionBeing living to give birth to in the practice requires use to anticipate to save most usually and Squanders at least and so on ，First of all Immediate future the cutting stock problem is ，The category optimization is researched the category 。For one thing, Onedimensional cutting stock problems can be encountered at the production stage of many areas，the optimization of cutting requests to save raw material at most and improve the use of raw materia1A branch and bound algorithm for solving onedimensional cutting stock problems can be completed by computerFor another, Aimed at raw material for a single one-dimensional cutting stock problem, This paper established integer programming model and then transformed into themodel under optimal feeding method for solving the problem;the use of lingo programming to achieve loop calls are one- dimensional cutting stock problem of the locally most optimal solution.Actually, Resolution means that the original is give out ，the proper scale issue may be resolved ，As yet the handwork performs mathematical calculations，But may solve a problem by means of the calculating machine ，Being living in the practice may draw lessons from the use關鍵詞：一維下料問題 分支定界算法 ILp函數 最優(yōu)化onedimensional cutting stock problems branch-andbound algorithm ILp function Optimization問題的提出研究背景下料問題”是把相同形狀的原材料分割加工成若干不同規(guī)格大小的零件的問題 ，根據原材料長度是否相等，一維優(yōu)化下料可以分為單一型材的優(yōu)化下料和多型材的優(yōu)化下料其中需求零件的寬度相等的情況稱為一維下料問題。一維下料問題是在已知原材料和顧客需求坯料的情況下優(yōu)化下料使原材料的使用率達到最大或廢料達到最小的問題。一個好的下料方案首先應該使原材料的利用率最大, 從而減少損失, 降低成本, 提高經濟效益。其次要求所采用的不同的下料方式盡可能少, 即希望用最少的下料方式來完成任務。因為在生產中轉換下料方式需要費用和時間, 既提高成本, 又降低效率。此外, 每種零件有各自的交貨時間, 每天下料的數量受到企業(yè)生產能力的限制。因此實用下料問題的目標是在生產能力容許的條件下, 以最少數量的原材料, 盡可能按時完成需求任務, 同時下料方式數也盡量地小。不同的下料方案需要的原材料數量不同，通過優(yōu)化下料方案減少原材料的數量，降低成本。常用的求解一維下料問題的方法有分支定界法、動態(tài)規(guī)劃法和整數規(guī)劃法等方法。對于大規(guī)模的一維下料問題,許多專家嘗試用遺傳算法來求解,并取得了較為滿意的結果。2003年李培勇分完全下料和不完全下料建立優(yōu)化模型，并使用混合遺傳算法求解。2004年王小東等提出了一種基于啟發(fā)式多級序列線性優(yōu)化思想的新算法，將下料優(yōu)化問題轉化為多級序列線性優(yōu)化問題求解。2004年張春玲等討論了解決一維下料問題的常用算法以及算法的適用情況。這些等等等等。下面我再具體介紹一下前人的解法。1.線性規(guī)劃。首先建立優(yōu)化線性模型，然后對模型進行求解?？梢杂梅种Фń绶ㄇ蠼狻?.遺傳算法。從應用的角度對遺傳算法做了認真的分析和研究，然后將其應用于一維下料問題的求解，提出了一種基于遺傳算法的求解方法。 3.遺傳模擬退火算法。針對遺傳算法存在“過早收斂”的現象及其良好的兼容性，考慮將模擬退火算法與遺傳算法相結合，用來求解一維下料問題。4.廣義粒子群優(yōu)化算法，結了合遺傳算法和模擬退火算法。該算法通過引入交叉算子、變異算子和模擬退火操作，增加粒子的多樣性，以求算法實現全局搜索能力和局部探索能力的平衡 5.順序啟發(fā)式算法。通過多種啟發(fā)式策略和優(yōu)化方法的應用 ,弱化了啟發(fā)式算法生成排樣方式時本身的貪婪性質。求解一維下料問題時 ,考慮多個優(yōu)化目標 ,排樣結果具有更廣泛的應用價值 ,可滿足各種生產環(huán)境的需求。該算法設計簡潔明了 ,易于理解。且計算時間可以被生產實踐所接受。6.非線性規(guī)劃。對于較大規(guī)模的一維下料問題，材料的切割模式和數量要得到整數解，用非線性規(guī)劃求解比較好。能實現一維下料的優(yōu)化，等到滿意結果，使用料最省，利潤最大。研究意義對于工業(yè)和建筑業(yè)的許多原材料，例如圓鋼、圓木、鋼筋、鐵板、薄鐵皮、塑料板以及紙張、布匹等。一般都存在下料或裁剪問題。特別是在一些比較復雜的情況下，不采用科學方法、不尋求最優(yōu)下料法，往往造成原材料的很大浪費 。所以在很多生產部門中，為了提高原材料利用率，降低生產成本，在給定長度的原材料上，要求消耗盡可能少的原材料數量 ，切割出不同數量和規(guī)格的零件。當零件數量較少時，可用人工方法解決，當零件數量較多時 ，用人工方法對原材料利用率不是很高，會造成資源大量浪費，導致生產成本上升。因此最大限度地節(jié)約原材料，提高原材料的利用率是生產中提高效益的一個重要手段。 在當今社會，隨著國民經濟的飛速發(fā)展，一維下料問題在建筑、電力、水利等領域獲得了越來越廣泛的應用。尋找一種最優(yōu)的下料方案，不僅可以節(jié)省原材料，降低生產成本，而且能夠為企業(yè)帶來直接的經濟效益，促進國民經濟的健康發(fā)展。因此，開展對一維下料問題的研究具有重要的理論意義和工程應用價值。一維下料問題是一個經典的組合優(yōu)化問題。怎樣找到一種較好的下料方案,成為節(jié)約原材料,降低成本,從而提高企業(yè)的經濟效益的重要問題之一。本文采用整數線性規(guī)劃方法來求最優(yōu)解。問題的陳述一個好的下料方案首先應該使原材料的利用率最大，從而減少損失 ，降低成本 ，提高經濟低效率此外，每種零件有各自的交貨時間，每天下料的數量受到企業(yè)生產能力的限制因此實用下料問題的目標是在生產能力容許的條件下，以最少數量的原材料，盡可能按時完成需求任務，同時下料方式數也盡量地小。 我們來做兩道例題來講解一下一維下料問題的解法。例一：線材合理下料問題：有一批原料鋼材(如鋼管、鋼筋、角鋼、鋼梁等)，每根長7.4m現需做100套鋼架，每套利用長2.9 m、2.1 m、1.5m的鋼材各一根問如何下料，才能使所用的原料最省?例二：鋼管下料問題：現有原料鋼管每根19米，客戶需求4米50根，6米20根，8米15根，現有如下問題需要解決：如何下料最節(jié)??？如何盡可能滿足廄客需求？問題的分析一維下料問題是生產實踐中常見的問題，優(yōu)化下料要求最大限度地節(jié)約原材料，提高原材料的利用率。對于優(yōu)化下料問題 ，屬于整數規(guī)劃問題 ，要想求出下料方案的最優(yōu)解，從計算復雜性理論分析， 該問題屬于NP難題 ，即無法在多項式時間內求解。 雖然整數規(guī)劃問題是 NP難題，但是線性問題卻是有有效算法的。所以可以考慮不先求解整數規(guī)劃問題而先來求解其相應的線性問題。本文主要是采用線性規(guī)劃來求解，建立數學模型，分析求最優(yōu)解。一維下料的數學模型早在 1939年就已由 Kantorovich提出由于這類模型屬于整數規(guī)劃。所以其求解十分復雜，其原因是可行的下料方式數目可能很大，從而造成要求解的整數規(guī)劃的維數很高我們必須知道：首先，一個好的下料方案應該使原材料的利用率最大，從而減少損失，降低成本，提高經濟效益其次，要求所采用的不同下料方式盡可能少，即希望用最少的下料方式來完成任務因為在生產中轉換下料方式需要費用和時間 ，既提高成本，又降低效率因此下料問題的目標是在生產能力容許的條件下，以最少數量的原材料 ，盡可能按時完成需求任務 ，同時下料方式數也盡量地少為順利解決下料問題 ，根據該問題的特點，我們先從最基本的單目標決策問題人手 ，以材料損耗最少為目標，通過不同的數學原理建立最優(yōu)化模型 ，得出最初的結果。然后逐步增加其約束條件最小的下料方式數 ，并根據該約束條件進一步完善 我們的最優(yōu)化模型 ，得到損耗最少，下料方式數又小的結果接下來檢驗在所得下料方式的排列中，是否存在可以滿足時間條件限制的排列方式若存在 ，則該結果即為最優(yōu)解；若不存在 ，則這個結果就不符合題意 ，必須重新構建多目標決策的最優(yōu)化模型，在新模型中以客戶時間需求為第一 目標 ，材料損耗最少，下料方式最少為第二 目標因此，在下料時就應該優(yōu)先生產那些有時間限制要求的零件 ，并且求出在需求的時間段內下料方式和損耗的最優(yōu)結果 ，緊接著再求 出剩余 板材下料方式和損耗的最優(yōu)結果 ，從而最終得出既滿足時間條件限制又滿足損耗少、下料方式數小的最優(yōu)結果。模型建立的準備分支定界法的介紹與基本思想分支定界算法是20世紀60年代初由Land，Doig和Dakin等人提出的，其算法不僅可用于求解純整數或混合整數線性規(guī)劃問題，也適用于幾乎任何組合優(yōu)化問題。它采用了分而治之的算法策略，在分析一個組合最優(yōu)化問題一切可行解的過程中，采取了必要的限制條件，設法排除可行域中大量非最優(yōu)解區(qū)域，從而能夠求解一些規(guī)模較大的問題。分枝定界法的思想是：先求解整數規(guī)劃相應的線性規(guī)劃問題，如果其最優(yōu)解不符合整數條件，則需要增加新的約束來縮小可行域，得到新的線性規(guī)劃問題再求鰓。這樣通過求解一系列線性規(guī)劃問題，最終得到問題的整數最優(yōu)解。求解整數線性規(guī)劃分支定界法MATLAB程序：function x，Y=ILp(f，G，h，Geq，heq，lb，ub，x，id，options)globa1 upper opt c x0 A b Aeq beq ID options；if nargjn10，options=optimset()；optionsDisplay=off;optionsLargeScale=0ff; endif nargjn9，id=ones(size(f)；endif nargjn8，x=；endif nargjn7 lisempty(ub)，ub=inf*ones(size(f)；endif nargjn6 lisempty(1b)，lb=zer0s(size(f)；endif nargjn 5，heq=；endif nargjn4，Geq=；endupper=inf；c=f；x0 = x；A =G；b= h；Aeq Geq；beq =heq；ID=id；ftemp=ILP(1b(：)，ub(：)；x=opt；Y=upper；function ftemp=ILP(vlb，,vub)globa1 upper opt c x0 A b Aeq beq ID options；x，ftemp，how=linprog(c，A，b，Aeq，beq，rib，rub，x0，options)；if how 000005 in 0rder to avoid errorreturn；end；if max(abs(x*IDround(x*ID)000005 in oId to avoid erroropt=x; upper=ftemp；retum ；elseopt=opt；x；return；end；end；notintx=find(abs(xround(x)=000005)；in 0rder toavoid errorint x=fix(x)；tempvlb=vlb；tempvub=rub；if rub(notintx(1，1)，1)：intx(notintx (1，1)，1)+1；tempvlb(notintx(1，1)，1)=intx(notintx (1，1)，1)+1ftemp=IntLP(tempvlb，vub)；end；if vlb(notintx(1，1)，1)C：0，0.1，0.2，0.3，0.8，0.9，1.1，1.4；A=1，2，0，1，0，1，0，0；0，0，2，2，1，1，3，0；3，1，2，0，3，1，0，4；b=100；100；100； =ILp(C，A，b，0，0，0，0，0，0，0，0，inf，inf，inf，inf，inf，inf，inf，inf)；=。例二按照客戶需要在一根原料鋼管上安排切割的一種組合。合理切割模式的余料應小于客戶需要鋼管的最小尺寸 合理切割模式如下：模式4米鋼管根數6米鋼管根數8米鋼管根數余料（米）14003231013201341203511116030370023為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)省？兩種標準1原料鋼管剩余總余量最少2所用原料鋼管總根數最少決策變量按第i種模式切割的原料鋼管根數（i=1，27）目標1（總余量）min=3x1+x2+3x3+3x4+x5+x6+3x7模式4米根數6米根數8米根數余料14003231013201341203511116030370023需求502015滿足需求的約束條件為最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27 按模式2切割12根,按模式5切割15根，余料27米 當余料沒有用處時，通常以總根數最少為目標 目標2（總根數）min=x1+x2+x3+x4+x5+x6+x7 s.t最優(yōu)解：x2=15, x5=5, x7=5, 其余為0；最優(yōu)值：25。按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米 與目標1的結果“共切割27根，余料27米” 相比: 雖余料增加8米，但減少了2根 當余料沒有用處時，通常以總根數最少為目標 在模型窗口中輸入如下代碼：min=x1+x2+x3+x4+x5+x6+x7 4*x1+3*x2+2*x3+x4+x550x2+2*x4+x5+x6+x720x3+x5+2*x715都是第二種下料方式 125根原鋼，第四種下料方式 50根原鋼，共用 175根原鋼小結下料問題的求解，答案比較活泛盡管在所需原材料總塊數上答案一致，但在施工方案上卻可以大相徑庭通常，在求解小規(guī)模問題時利用手工演算，可以找到全部解，而利用Lindo、Microsoft Office Excel等只可找到部分解，而通常實際問題只需找到一個解即可結束語 經過幾個月的學習，我終于完成了關于一維下料問題的研究這一畢業(yè)設計。剛開始時，我對下料問題并不是太了解，后來經過不斷的學習和總結，現在已經變得很清晰了。本文介紹了簡單的一維下料問題，我通過不斷地查閱資料和書籍，同時在呂老師的耐心指導下，現在已經知道解決一維下料問題有很多種方法