鐵塔制造中角鋼優(yōu)化下料系統(tǒng)設(shè)計思想與算法探討

■程 默 ■江西省送變電建設(shè)公司，江西 南昌 330200

由于原材料的價格的不斷升高和日趨激烈的市場競爭，使得鐵塔制造企業(yè)必須要面對降低生產(chǎn)成本、提高生產(chǎn)效率等問題。工業(yè)領(lǐng)域中下料問題的應(yīng)用十分廣泛，在理論上鐵塔行業(yè)中的角鋼下料屬于NP完全問題中規(guī)模較大的，所以對其進(jìn)行求解的過程比較復(fù)雜?，F(xiàn)在仍然有許多企業(yè)采用手工計算的方式，這樣不但材料的利用率不高而且還浪費了時間，雖然有的運用了計算機(jī)輔助下料方法，但是功能和方法比較單一，沒有辦法與采購、庫存等各個部門實現(xiàn)數(shù)據(jù)的協(xié)同、共享工作，導(dǎo)致下料流程不合格。所以，探討鐵塔制造中角鋼優(yōu)化下料系統(tǒng)設(shè)計思想與算法具有重要的工程應(yīng)用價值和理論意義。

1 優(yōu)化下料算法

工業(yè)當(dāng)中，關(guān)于優(yōu)化下料的問題，在國外稱為CSP，包括材料的排樣問題、切割問題和裝箱問題。根據(jù)是否為空間尺寸下料問題可劃分為廣義下料問題和狹義下料問題。在工業(yè)領(lǐng)域當(dāng)中，下料問題存在的比較廣泛。對于下料問題的不斷深入的研究，可以得出目前主要的求解手段有兩大類:

1．1 最優(yōu)解法

數(shù)學(xué)模型中一維下料問題是一個對整數(shù)進(jìn)行規(guī)劃的問題，一般的下料優(yōu)化方法是通過將整數(shù)變量松弛后，看做是線性規(guī)劃，運用單純形方法進(jìn)行求解，然后將得到的結(jié)果圓整，但是這樣不能確保一定得到最優(yōu)解，并且進(jìn)行圓整后會導(dǎo)致零件生產(chǎn)過量或者生產(chǎn)不足，這就需要對其進(jìn)行再處理;也可以運用針對整數(shù)規(guī)劃求解的割平面和分支定界法進(jìn)行求解;與此之外還可以采用枚舉法，通過比較可行解空間內(nèi)所有點的目標(biāo)函數(shù)從而找出下料問題的最優(yōu)解;但是這些方法計算效率比較低，經(jīng)常因為解空間太大而對實際問題的處理束手無策，所以這些方法只能對小規(guī)模問題進(jìn)行優(yōu)化。

1．2 啟發(fā)式算法

優(yōu)化下料問題作為一個NPC難的問題，有復(fù)雜的計算程度，求解時間根據(jù)問題規(guī)模呈現(xiàn)指數(shù)級的增長，所以通常沒有多項式算法。由于存在復(fù)雜的實際情況，所以不能通過最優(yōu)算法來求得每個問題實例中的最優(yōu)解，因此啟發(fā)式算法的求解比較常用。針對最優(yōu)算法，可以用啟發(fā)式算法來這樣進(jìn)行定義:如果算法是基于經(jīng)驗或直觀構(gòu)造，那么在能夠接受的花費下為待解決優(yōu)化問題的每一個實例給出一個可行解，是無法事先預(yù)約這個可行解與最優(yōu)解存在的偏離程度的。通過啟發(fā)式算法尋找出最優(yōu)解的近似解，可以在可接受的花費的前提下得到一個滿意的問題解，使得生產(chǎn)實際中能夠應(yīng)用優(yōu)化下料技術(shù)，所以啟發(fā)式算法在現(xiàn)階段的研究較多，根據(jù)規(guī)則的不同，啟發(fā)式算法的構(gòu)成也不同。

2 設(shè)計優(yōu)化步驟

2．1 零件分組

對于下料的實際生產(chǎn)當(dāng)中，我們需要安排許多種類的零件，通過長度對零件進(jìn)行分組，對每組的四個零件優(yōu)化，這種方法所得到的最優(yōu)解只是每組內(nèi)的一部分的最優(yōu)解而不是得到整體的。我們可以運用這樣的分組原則:將截面規(guī)格相同的零件按照尺寸長多進(jìn)行從大到小的排列，取出兩個最小長度零件和最大長度零件，將取出的這四個零件合成一組，使得零件可以長短搭配。根據(jù)這種分組原則，不僅可以使安排所有這四種零件的概率得到提高，使原材料的消耗得到降低，還使下料的排列方式數(shù)量得到減少，并提高了優(yōu)化計算程序總體運行速度，使系統(tǒng)的穩(wěn)定性得到了加強(qiáng)。

2．2 求全部下料方式

分組后可通過下面步驟求出下料方式:(1)零件的種類數(shù)不大于4時，可以直接進(jìn)行數(shù)學(xué)模型的計算，如果零件不少于1種時，根據(jù)前面的分組原則對零件進(jìn)行分組。(2)對截面規(guī)格相同的原材料的尺寸長度種類數(shù)進(jìn)行判斷，如果種類數(shù)是1時，可以直接求得所有下料方式，如果種類數(shù)比1大時，要先將對應(yīng)的1種原材料尺寸的所有下料方式求出，這時所求的4種零件只剩下3種零件了，依次進(jìn)行判斷，可以得到全部的下料方式，也就是4種零件所對應(yīng)1種原材料的尺寸長度的所有下料方式。(3)將每組零件對應(yīng)的原材料的所有下料方式相互混合在一起，就可以得到了每組零件對應(yīng)于所有原材料的各種下料方式，線性規(guī)劃方程組當(dāng)中的系數(shù)矩陣正是由這些下料方式組成。

2．3 關(guān)于整數(shù)線性規(guī)劃

求出下料方式以后就可以建立整數(shù)線性規(guī)劃的相關(guān)模型了，對于設(shè)計角鋼的優(yōu)化下料，決策變量要求只取出整數(shù)值，求出的解中不能夠出現(xiàn)小數(shù)或分?jǐn)?shù)，使所用原材料總根數(shù)最小等于目標(biāo)函數(shù)和以達(dá)到零件需要量為約束條件所進(jìn)行的數(shù)學(xué)規(guī)劃問題就是角鋼優(yōu)化下料問題?？杀硎緸?MAXZ=CX;Aχ≤b;χ≥0。

其中，C代表下料方式的最大可利用長度。

對與不等式約束條件極值問題，最普通的算法和一般求解的方法是單純形法，總體思路:先要引進(jìn)人工的變量，把數(shù)學(xué)整體模型轉(zhuǎn)變成標(biāo)準(zhǔn)的線性規(guī)劃方面的問題。通過已經(jīng)得到的等式相互約束條件將目標(biāo)函數(shù)當(dāng)中的某些自變量約去，使得非基變量變成零，求出一組基向量所對應(yīng)的基本可行解，通過這種基本可行解進(jìn)行考察，看使目標(biāo)函數(shù)達(dá)到最小值的是不是這一點。不是話，再去考察其他的基本可行解使得目標(biāo)函數(shù)達(dá)到最小值。

對于原始單純形法，每次進(jìn)行迭代都要將整個單純形表改寫，對于單純形表上的所有數(shù)據(jù)，都要參與到運算當(dāng)中，某些運算其實是不必要的，如果約束方程的變量個數(shù)n和個數(shù)m比較大時，對于計算機(jī)的計算量和儲存量要求都很大，會導(dǎo)致計算量和儲存量方面的浪費，對單純形法進(jìn)行改進(jìn)，將單純形法當(dāng)中需要的計算依次按格式排列，防止出現(xiàn)不必要的計算。

3 結(jié)束語

對于角鋼的優(yōu)化下料系統(tǒng)，整個系統(tǒng)的核心是優(yōu)化計算模塊，所以想要實現(xiàn)計算功就要有高性能的算法。我們要加大對下料系統(tǒng)的算法研究，以確保滿足當(dāng)前閾值的下料方式，兼顧加工難度、利用率以及整體計算時間。本篇文章將鐵塔廠角鋼優(yōu)化下料工作做為應(yīng)用的背景，不斷提高原材料利用率和下料車間工作效率，從生產(chǎn)管理和下料技術(shù)兩個的角度出發(fā)，探究了角鋼的優(yōu)化下料系統(tǒng)，優(yōu)化了下料工作的整體性，加大了市場競爭力和企業(yè)快速反應(yīng)能力。

［1］李瓊，金升平．一維優(yōu)化下料問題的模型與算法的綜合比較［J］．武漢交通科技大學(xué)學(xué)報，1998．

［2］華中平，張立．基于線性規(guī)劃的角鋼優(yōu)化下料算法研究．湖北工業(yè)大學(xué)學(xué)報，2005．

［3］王連杰．基于線性規(guī)劃的一維優(yōu)化下料系統(tǒng)研究與與開發(fā)．大連理工大學(xué)碩士論文，2005．