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

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

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

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

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

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

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

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

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

2．1 零件分組

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

2．2 求全部下料方式

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

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

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

其中，C代表下料方式的最大可利用長(zhǎng)度。

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

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

3 結(jié)束語(yǔ)

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

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

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

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