整數(shù)非線性規(guī)劃方法優(yōu)化下料問題論文

1、整數(shù)非線性規(guī)劃方法優(yōu)化下料問題摘要：本文探討了生產(chǎn)實際中一維下料的優(yōu)化問題，建立了下料問題的非線性整數(shù)規(guī)劃的數(shù) 學(xué)模型，并通過LINGO程序，獲得該優(yōu)化模型的解。本方法適用于較大規(guī)模的型材下料問 題，能夠提高原材料的利用率。關(guān)鍵詞：下料問題優(yōu)化整數(shù)非線性規(guī)劃LINGOAbstract: This paper presents the optimization of one dimensional cutting stock problem and establishs the integer nonlinear programming mathematical model,which is s

2、loved by LINGO program. The approach is suitable to the cutting stock problem of moderate size. The raw and processed materials use factor can improved largely through adopting this method.Key words: cutting stock problem, optimization ,integer nonlinear programming, LINGO作者簡介：孫曉雅（1972-）女，河北唐山人，講師，博

3、士研究生，主要研究方向：運籌學(xué)、CAD技術(shù)。生產(chǎn)中常會遇到通過切割、剪裁、沖壓等手段， 將原材料加工成所需大小這種工藝過程，稱為原料 下料問題。以往經(jīng)常采用的“單一下料法”或“簡 單套裁法”，由于對如何下料事先缺乏周密考慮， 所以會產(chǎn)生較多的邊角余料，材料利用率不高。對于較大規(guī)模的一維下料問題，材料的切割模 式和各種切割模式下材料的數(shù)量都需要得到整數(shù) 解，因此該問題可歸結(jié)為整數(shù)非線性規(guī)劃問題，而 整數(shù)非線性優(yōu)化求解是一個十分復(fù)雜的問題。LINDO和LINGO是LINDO系統(tǒng)公司開發(fā)的一套 專門用于求解最優(yōu)化問題的軟件包LINDO用于求 解線性規(guī)劃和二次規(guī)劃問題，LINGO除了具有 LINDO的

4、全部功能外，還可以用于求解非線性規(guī)劃 問題。LINDO和LINGO軟件的最大特色在于可以 允許優(yōu)化模型中的決策變量是整數(shù)，而且執(zhí)行速度 很快。LINDO和LINGO軟件在教學(xué)、科研和工業(yè)、 商業(yè)、服務(wù)業(yè)等領(lǐng)域得到了廣泛的應(yīng)用。本文將對一維下料問題進行系統(tǒng)分析，建立非 線性整數(shù)規(guī)劃的數(shù)學(xué)模型，并編制了通用的LINGO 程序，實現(xiàn)了較大規(guī)模一維下料問題的優(yōu)化求解。1問題的提出本文以客車廠生產(chǎn)某型號汽車零件的下料問 題為計算實例。所需原始數(shù)據(jù)表如表1：表i n卜料問題的原始需求數(shù)據(jù)零件號名稱材料規(guī)格(mm)下料尺 寸（mm）集亞曷 而女里407加強筋扁鐵4x4020020040*座托板扁鐵4x403

5、3200409墊鐵扁鐵4x40170400410加長板扁鐵4x40200200原材料扁鐵長為4000mm。生產(chǎn)部門如果采用的不同的切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化， 從而增加生產(chǎn)和管理成本，所以該生產(chǎn)部門規(guī)定采 用的不同切割模式不能超過4種。在這種條件下， 探討最優(yōu)的下料方式，使得用料最省。對于簡單的下料問題，切割模式可以通過來確 定，但對于本文中的下料問題由于原材料扁鐵的長 度遠大于加工后產(chǎn)品的尺寸，而且加工品種比較多 的情況，用枚舉法確定切割模式的工作量非常大。 因此這里采用整數(shù)非線性規(guī)劃方法來建立下料問 題的數(shù)學(xué)模型，該方法可以同時確定切割模式和切 割計劃。一個合理的切割模式的余了

6、不應(yīng)該大于或等 于需要的產(chǎn)品的最小尺寸，即座托板33mm，所以 合理的切割模式的余量不能大于32mm。2建立數(shù)學(xué)模型決策變量：由于不同切割模式不能超過4種，用七（非負整數(shù)）表示按照第i種模式（i = 1,2,3,4）切割的原料扁鐵的根數(shù)。用尸，尸，尸，尸表示使用 1i 2i 3i 4i第i中切割模式下每根原料扁鐵生產(chǎn)零件407氣 408*、409*、410*的數(shù)量。決策目標：使用原料扁鐵總根數(shù)最少。min x + x + x + x（1）1234約束條件：r x + r x + r x + r x 20011 1 12 213 3 14 4r x + r x + r x + r x 20021

7、 122 223 3 24 4r x + r x + r x + r x 40031 132 233 3 34 4 .。八八 TOC o 1-5 h z r x + r x + r x + r x 200、 41 142 243 3 44 4(2)3968 200r + 33r + 170r + 200r 40003968 200r + 33r +1 70r + 200r 40003968 200r12 + 33 產(chǎn) +170月 + 200產(chǎn) 4000132333433968 200 33虹 + 170r4 + 200r44 x x x。以減少運行時間，縮小可行接 1234的搜索范圍。本實例實

8、現(xiàn)過程如下：MODEL:Title扁鋼下料-最小化扁鋼根數(shù)的LINGO模型；SETS:NEEDS/1.4/:LENGTH,NUM;CUTS/1.4/:X;PATTERNS(NEEDS,CUTS):R;ENDSETSDATA:LENGTH=220 33 170 62;NUM=200 200 400 190;CAPACITY=4000;ENDDATAmin=SUM(CUTS(I): X(I);!目標函數(shù)；FOR(NEEDS(I): SUM(CUTS(J):X(J)*R(I,J) ) NUM(I);!滿足需求約束；FOR(CUTS(J): SUM(NEEDS(I): LENGTH(I)*R(I,J)

9、 CAPACITY-MIN(NEEDS(I):LENGT H(I) );!合理切割模式約束；FOR(CUTS(I)|I#LT# SIZE(CUTS):X(I)X(I+1);!人為增加約束；FOR(CUTS(J): GIN(X(J);FOR(PATTERNS(I,J): GIN(R(I,J);END3.3優(yōu)化模型的解通過程序計算得到該算例的求解報告。如圖2 所示。通過2386次迭代計算解得最少需要原料扁 鋼33根。Local optimal solution found.Objective value:33.00000Extended solver steps:145Total solver i

10、terations: 2386圖2目標函數(shù)最優(yōu)值33根原料扁鋼采用四種切割模式中，每種切割 模式需要扁鋼的根數(shù)，每種切割模式下每根原料扁 鐵生產(chǎn)零件407*、408*、409*、410*的數(shù)量，在LINGO 求解報告中給出，詳見圖3。VariableValueReduced CostX( 1)12.000001.000000X( 2)9.0000001.000000X( 3)8.0000001.000000X( 4)4.0000001.000000R( 1, 1)1.0000000.000000R( 1, 2)9.0000000.000000R( 1, 3)13.000000.000000R(

11、 1, 4)1.0000000.000000R( 2, 1)1.0000000.000000R( 2, 2)4.0000000.000000R( 2, 3)14.000000.000000R( 2, 4)11.000000.000000R( 3, 1)19.000000.000000R( 3, 2)11.000000.000000R( 3, 3)1.0000000.000000R( 3, 4)17.000000.000000R( 4, 1)8.0000000.000000R( 4, 2)0.0000000.000000R( 4, 3)8.0000000.000000R( 4, 4)8.0000000.000000圖3關(guān)于決策變量的求解報告通過上述數(shù)據(jù)可以求出該原料的利用率為98.77%，可見，按本方法進行套裁下料能極大地提 高了原材料的利用率，節(jié)約生產(chǎn)成本。4結(jié)論原料下料問題是與工廠生產(chǎn)實際密切相關(guān)的 一個問題。本文所闡述整數(shù)非線性規(guī)劃數(shù)學(xué)模型的 建模及LINGO程序的求解方法，具有