一維下料優(yōu)化模型的應(yīng)用及經(jīng)濟(jì)性分析

1、一維下料優(yōu)化模型的應(yīng)用及經(jīng)濟(jì)性分析陳 越中核華興建設(shè)有限公司遼寧紅沿河項目部摘要： “下料問題”是把相同形狀的一些原材料分割加工成若干個不同規(guī)格大小的零件的問題，此類問題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和廣泛的意義。本文首先以材料最省為原則建立下料模型，并結(jié)合 lingo編制出下料軟件， 可生成供使用的待加工零件最優(yōu)組合的報表。最后淺析此模型及軟件投入使用后的經(jīng)濟(jì)效益并進(jìn)一步拓展討論了多維下料問題的解決。關(guān)鍵詞：線性規(guī)劃下料問題組合 零件加工引言成本控制是企業(yè)賴以生存和發(fā)展的基礎(chǔ)，而相關(guān)數(shù)據(jù)表明， 原材料成本占總生產(chǎn)成本的百分比可以高達(dá)45%60%，因此最大限度地節(jié)約材料，提高材料的利用率，是實

2、際生產(chǎn)中的一個指導(dǎo)原則，能給企業(yè)帶來巨大的經(jīng)濟(jì)效益。一維下料優(yōu)化問題是討論從一種規(guī)格的材料中，分切出各種不同長度的坯料，以使材料的利用率最高。 下料方案的優(yōu)劣直接影響原材料的利用率，進(jìn)而影響原材料成本。這類優(yōu)化問題在型材、棒材、管材、金屬結(jié)構(gòu)材料、建筑材料，甚至布料下料中廣泛存在。 目前，國內(nèi)外關(guān)于這方面的研究十分活躍，并涌現(xiàn)出了不少近似算法，如 gilmore與gomory用線性規(guī)劃建立的一刀切問題的數(shù)學(xué)模型【1,2】以及sarker提出的動態(tài)規(guī)劃方法【3】等。本文通過改進(jìn)目前常用的兩種求解方法( 常規(guī)整數(shù)線性規(guī)劃方法和遺傳算法)，結(jié)合 lingo9.0 線性規(guī)劃軟件，編制出一種貼合核電站鋼

3、筋下料實際情況且易于操作的下料軟件， 并對其進(jìn)行算例對比， 提出一種更為合理經(jīng)濟(jì)的下料方案，基本杜絕了原料浪費現(xiàn)象。正文1 背景目前，紅沿河核電站引進(jìn)的鋼筋原材料有光圓鋼筋hpb235 級（下文統(tǒng)稱 i級鋼） 、帶肋鋼筋 hrb335 級（下文統(tǒng)稱 ii 級鋼） 、hrb400 級（下文統(tǒng)稱 iii 級鋼） ，表 1 對各型號的鋼筋不同直徑及原料長度做了統(tǒng)計。表 1 鋼筋原料直徑與長度統(tǒng)計表鋼筋型號直徑（ mm）原料長度（ mm）i 級鋼6 12000 8 12000 10 12000 12 12000 14 12000 16 12000 20 12000ii 級鋼12 1200014 120

4、0016 1200018 1200020 1200022 1200025 12000iii 級鋼12 1200014 1200016 1200020 1200025 1200032 1200040 12000實際上，鋼筋車間操作人員收到待加工的鋼筋料單，會將料單上同種規(guī)格和直徑的鋼筋進(jìn)行簡單組合后使用原材料切割，這種簡單組合造成了大量的余料甚至廢料。如何找出一種最優(yōu)的組合方式使得耗材最少以提高材料利用率，本文將采用一種啟發(fā)式多級序列線性優(yōu)化模型并求解出最優(yōu)方案。2 問題分析一維下料問題是組合優(yōu)化中的一個經(jīng)典問題，如果要得到理論上的嚴(yán)格全局最優(yōu)下料方案。 就要求所有可行下料方式都進(jìn)入線性規(guī)劃模型

5、的系數(shù)矩陣，從計算的復(fù)雜性理論上看， 這屬于 npc (np完全)難問題。因此，我們放棄常規(guī)的整數(shù)規(guī)劃解法， 而在以優(yōu)化選取下料方式的前提下，尋找建立下料方案的模型。 本文要求一個好的下料方案在生產(chǎn)能力允許的條件下要滿足兩個要求：首先，應(yīng)該使原材料的利用率最大， 即用最少數(shù)量的原材料； 其次要求所采用的不同下料方式盡可能少。這樣，我們可以考慮分層建模：第一階段，先僅考慮單一原材料的模型，以耗材最少為原則搜尋最優(yōu)的下料方式；第二階段解決具體問題時， 再進(jìn)一步考慮將多種原材料并行搜索。 改進(jìn)方案以滿足要求。 通過計算機(jī)編程計算得到我們所需要的最優(yōu)下料方案。由于原料的種類并不單一，有20 種之多，每

6、種原料待加工零件也未確定，導(dǎo)致計算量很大， 所以在建立優(yōu)化模型的基礎(chǔ)上， 我們需要找到比較合適的算法來解決這類實際問題。 作者力圖建立一種實用的模型， 并提出一種新的優(yōu)化思想方法啟發(fā)式多層次逐層優(yōu)化方法，并結(jié)合貪心算法解決此問題。3 模型的建立3.1 基本假設(shè)(1) 假設(shè)每個切割點處產(chǎn)生的損耗為5mm，且視為廢料不可忽略。(2) 假設(shè)車間加工成品速度能夠滿足交貨時間，即忽略交貨時間的限制。3.2 符號說明符號意義單位l原材料的長度mmin第i種零件的需求量個iw第i種零件的寬度 , 且iwwmmil第i種零件的長度，且iiwllmmia一種下料方式中，切割第i種零件的數(shù)量個p下料方式數(shù)種ic下

7、料方式i的使用次數(shù)次3.3 啟發(fā)式多級序列線性優(yōu)化模型該模型的基本思想是在每級求解時， 盡可能多的重復(fù)使用最優(yōu)的一種方法進(jìn)行下料，直到所涉及到的某種零件需求加工完；然后對剩余的零件重復(fù)上步的操作，直到所有剩余的零件數(shù)目均減小至零為止。原問題的最優(yōu)解就是各個序列優(yōu)化問題所求得的最優(yōu)下料方式的總和。給定m種長度的零件mlll，21，所需的數(shù)量分別為mbbb，21，已知原材料長度為l。設(shè)在最優(yōu)一種下料方式中，第i件零件的加工數(shù)量為ia ，由此建立如下模型：miballastlasiimiiimiii，210max11優(yōu)化參數(shù)變量：maaa，21均為非負(fù)整數(shù)，且不同長度的零件種類有限( 即該問題中要求

8、的變量個數(shù)有限) ，可用分枝定界法來求解。啟發(fā)式多級序列線性優(yōu)化計算方法將上述當(dāng)前最優(yōu)下料方式計算求解作為多級序列線性優(yōu)化計算的子程序， 在每級求解中重復(fù)調(diào)用。 完整的求解步驟如下：步驟1 將待加工零件中待切割的最長零件作為第一搜索順序，調(diào)用當(dāng)前最優(yōu)下料計算子程序，求解得到優(yōu)化值iila組成的miiila1，此時零件之間種類和數(shù)量的組合作為第一級下料方式。步驟2 計算此種下料方式的重復(fù)次數(shù)，即此種下料方式所需原材料l的根數(shù)d。其中mmabababd，2211min。步驟3 計算去掉d根后，余下的每種待切割的零件個數(shù)置為：iiidabb。步驟4 將ib 作為新一級優(yōu)化計算的給定值， 如果所有的i

9、b 都已減小至零， 則優(yōu)化計算結(jié)束；否則轉(zhuǎn)至步驟l ，重新用當(dāng)前最優(yōu)下料方式計算子程序，求得新一級的下料方式和重復(fù)次數(shù)。步驟5 各級最優(yōu)下料方式及其重復(fù)次數(shù)的集合即為多級序列線性優(yōu)化的最終結(jié)果。一維問題算法流程圖4 模型求解在確定了模型和算法后， 作者使用 lingo9.0 線性規(guī)劃軟件編程求解出任意多種原材料加工零件的最優(yōu)組合方案，為使操作界面窗口化以及使用過程簡便易懂，作者將這段程序嵌套在java 的運行環(huán)境中。以紅沿河核電站hdy-9nef193料單作為一個算例進(jìn)行操作說明。 （所有操作均在安裝了java以及 lingo9.0 環(huán)境下進(jìn)行）第一步：輸入數(shù)據(jù)。在excel 表格中輸入料單的

10、基本信息，包括規(guī)格、下料長度、數(shù)量。圖 1 為 hdy-9nef193 料單數(shù)據(jù)截圖。圖 1 其中規(guī)格一列 316表示 iii 級鋼直徑 16mm 的鋼筋， 108表示 i 級鋼直徑 8mm的鋼筋，以此類推。第二步：處理數(shù)據(jù)打 開 紅 沿 河 下 料 優(yōu) 化軟 件 ， 出現(xiàn) 如 圖 2 窗 口， 在 光 標(biāo)處 依 次 輸入file ，run，parse ，reset ，exit。命令說明：file ： 當(dāng)前需要計算的料單， 為料單數(shù)據(jù)文件所在目錄。run：創(chuàng)建當(dāng)前料單的lingo 模型及相關(guān)元數(shù)據(jù)信息文件。parse ：分析 lingo 模型的優(yōu)化結(jié)果，生成report.txt 報表。rese

11、t ：清空當(dāng)前記憶的料單。exit：退出。圖 2 料單信息載入第三步：打開 report.txt 報表處理結(jié)果對 hdy-9nef193 料單處理生成的報表如圖3、4 （由于篇幅原因只隨即挑選兩種規(guī)格的鋼筋進(jìn)行示意）圖 3 三級鋼直徑 16 的結(jié)果報表圖 4 三級鋼直徑 32 的結(jié)果報表如圖 3第三行表示一根下料長度為2340mm的零件和兩根 4560mm的零件組合重復(fù) 5 次，每根原料剩余 525mm 料頭。第四行表示一根下料長度為8450mm的零件和一根 3350mm的零件組合重復(fù)59 次，每根原料剩余190mm料頭。依次類推。將圖 3 其轉(zhuǎn)換成清晰易懂的最優(yōu)組合表格如下：表 2 三級鋼直

12、徑 16 的最優(yōu)組合切割方案重復(fù)次數(shù)組合方式余料（mm）5 2340mm（1 根）4560mm（2 根）525 59 8450mm（1 根）3350mm（1 根）190 5 1170mm（1 根）8450mm（1 根）2340mm（1 根）25 7 1170mm（3 根）8450mm（1 根）20 12 4800mm（1 根）7000mm（1 根）190 2 4800mm（2 根）2340mm（1 根）45 7 2050mm（1 根）1170mm（1 根）8450mm（1 根）315 8 2000mm（1 根）4800mm（2 根）385 實際利用率 iii 級鋼直徑 16mm 的鋼筋為 94

13、.36%，iii 級鋼直徑 32mm 的鋼筋為 97.61%。使用該軟件時并不局限于一份料單中的待加工零件之間組合，對于交貨時間相近的幾份甚至幾十份亦可交叉組合，并且會因為組合方式增多效果更好。5 模型的評價及經(jīng)濟(jì)性分析從本文針對紅沿河項目抽取的料單的解決可看出，針對本問題將多目標(biāo)整數(shù)規(guī)劃模型分解為多層整數(shù)線性規(guī)劃模型和啟發(fā)式多層次逐層優(yōu)化方法是十分有效的。 且不用擔(dān)憂隨著問題規(guī)模的增加， 計算量和存儲空間的會產(chǎn)生組合爆炸，特別適用于優(yōu)化目標(biāo)和約束條件復(fù)雜的問題。它在大大降低計算復(fù)雜度的同時保持了很高的材料利用率和尚可接受的下料方式數(shù)。并且簡化后的模型與算法在計算結(jié)果穩(wěn)定性方面均已完美的結(jié)果證

14、明，此模型用于任意料單均可得到最高的利用率。毋庸置疑，該模型投入使用后會給企業(yè)節(jié)省大筆原材料，其間直接帶來的經(jīng)濟(jì)效益不可勝數(shù)。 但生產(chǎn)車間需加派人手， 設(shè)置專人負(fù)責(zé)使用該軟件生成組合料方案，并且在裝車時也增加了難度。但這部分支出遠(yuǎn)不及節(jié)約成本帶來的效益，因此具有可行性。6 模型的擴(kuò)展不僅僅是一維下料亟需優(yōu)化， 工業(yè)生產(chǎn)中也存在許多二維乃至三維下料浪費的現(xiàn)象。對于二維下料問題，下料方式要滿足零件長，寬方向上的套裁，所以遠(yuǎn)比一維下料復(fù)雜且數(shù)量大得多。 因此，我們希望通過降維啟發(fā)式方法即通過形成“板條”而把二維下料問題降為一維下料的方法來解決。在此稱一維下料的原材料為“條材”，而二維下料的原材料為“

15、板材”。板材與條材的區(qū)別在于：條材加工時只考慮長度而板材要同時考慮長、寬。如果能把零件成組看待， 板條就是這樣一種零件組：其在一個方向上的長度等于或近似于原材料的長( 或?qū)?)方向的長度；然后在另一個方向即原材料的寬( 或長) 方向進(jìn)行裁剪 這樣，二維下料問題因“板條”的引入便降為一維下料問題。零件的寬度決定板條的種類，當(dāng)種類確定后，則要在不超過寬( 或長) 度的前提下在原材料上進(jìn)行板條的布局( 有若干種)。而布局方式一旦確定，就只剩下每個板條內(nèi)部零件組的組合問題，這時就可利用一維中求解下料問題的啟發(fā)式多級序列線性優(yōu)化的方法來解決。其建模的具體過程類似于一維的分層建模思想。由于篇幅原因，此處不

16、做深入討論。致謝本文的撰寫是在紅沿河項目部核島一隊岳雷先隊長的循循善誘和悉心指導(dǎo)下完成的。對于這次論文的順利完成， 首先要感謝岳隊在論文撰寫期間的悉心指導(dǎo)，關(guān)心和幫助。 另外，賈春榮書記和技術(shù)隊長陳湘也對論文的相關(guān)內(nèi)容給予了很大的幫助和指導(dǎo)，對這期間所遇到的困難及應(yīng)注意的問題也給予了關(guān)心和建議。岳隊和陳隊嚴(yán)謹(jǐn)、務(wù)實和忘我的工作作風(fēng)，以及熱情和藹、平易近人的待人作風(fēng)，給我留下了深刻的印象，并深深的影響著我，使我受益匪淺，在此謹(jǐn)致以最誠摯的謝意。軟件編程的完成要特別感謝我大學(xué)期間的建模隊友潘嘉程。在模型的設(shè)計和制作及論文的完成等方面都得到潘嘉程的指導(dǎo)，在此表示真摯的感謝。同時，在紅沿河有關(guān)鋼筋數(shù)據(jù)

17、方面的提供得到鋼筋車間友善的幫助，在此一并表示感謝。最后還要感謝好友朱宏偉、謝警校、胡文杰、王繹詠、李恩平等人的幫助，在設(shè)計過程中，和他們一起討論，共同分析，解決了很多技術(shù)上的問題。參考文獻(xiàn)1 gilmore.p.c,gomory r e.a linear programming approach to the cutting stock problem (part i)j.oper res,1961,9:849-859. 2 gilmore.p.c,gomory r e.a linear programming approach to the cutting stock problem (part ii)j.oper res,1963,11:863-887. 3 sarker.b.r, an optimu