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

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

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

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

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

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

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

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

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

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

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

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

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 實(shí)際利用率 iii 級(jí)鋼直徑 16mm 的鋼筋為 94

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

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

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

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

17、方面的提供得到鋼筋車(chē)間友善的幫助，在此一并表示感謝。最后還要感謝好友朱宏偉、謝警校、胡文杰、王繹詠、李恩平等人的幫助，在設(shè)計(jì)過(guò)程中，和他們一起討論，共同分析，解決了很多技術(shù)上的問(wèn)題。參考文獻(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