線性規(guī)劃問(wèn)題的相關(guān)算法研究

曾國(guó)斌

（海口經(jīng)濟(jì)學(xué)院，海南海口571127）

線性規(guī)劃問(wèn)題的相關(guān)算法研究

曾國(guó)斌

（海口經(jīng)濟(jì)學(xué)院，海南海口571127）

本文主要是針對(duì)線性規(guī)劃問(wèn)題的相關(guān)算法進(jìn)行了綜述和原理的講解，分別闡述了線性規(guī)劃發(fā)展的歷程和線性規(guī)劃算法的主要數(shù)學(xué)模型，詳細(xì)研究了線性規(guī)劃的主要算法分為單純形法和內(nèi)點(diǎn)法的主要原理和算法，并為后續(xù)研究提供了一個(gè)借鑒方向.

線性規(guī)劃；內(nèi)點(diǎn)法；單純形法

1 線性規(guī)劃的發(fā)展歷程

線性規(guī)劃起源于蘇聯(lián)數(shù)學(xué)家L.V.Kantorovich，他與1939年在其代表性著作《Mathematical Methods in the Organization and Planning of Production》中發(fā)表了關(guān)于線性規(guī)劃的思想，但是由于當(dāng)時(shí)的條件限制使得這一思想并沒(méi)有在數(shù)學(xué)領(lǐng)域產(chǎn)生轟動(dòng)效應(yīng).[1]直到美國(guó)人G.B.Dantzig在1947年成功研究出解決線性規(guī)劃問(wèn)題的通用算法后，線性規(guī)劃開(kāi)始被人們所廣泛接受.[1]實(shí)際上，線性規(guī)劃問(wèn)題的相關(guān)算法V.Klee和G.J.minth在1972年首次提出了單純形法的迭代次數(shù)符合指數(shù)運(yùn)算才開(kāi)始研究的.

2 數(shù)學(xué)模型

線性規(guī)劃可以分為以下兩種模型，分別是標(biāo)準(zhǔn)型和非標(biāo)準(zhǔn)型.

2.1 標(biāo)準(zhǔn)型

線性規(guī)劃的模型的標(biāo)準(zhǔn)型為：max Z=x1C1+x2C2+x3C3+

x4C4+…+xnCn，約束條件為，非負(fù)的

與決策變量相對(duì)應(yīng)的價(jià)格系數(shù)設(shè)為cj，j=1,2,3,4…,n.技術(shù)系數(shù)設(shè)為aii，i=1,2,3…,m；j=1, 2,3…,n.右端項(xiàng)系數(shù)設(shè)為bi，i=1,2,3,4…,m.在線性規(guī)劃規(guī)劃模型的標(biāo)準(zhǔn)型中，約束條件是一組線性等式，利用向量和矩陣符號(hào)，線性規(guī)劃的標(biāo)準(zhǔn)模型還可以表示為：目標(biāo)函數(shù)maxZ=CX，約束條件.其中，C=(c1,c2,…cn)，A=，其中，X≥0是指X的各變量x1,x2,…xn≥0.而標(biāo)準(zhǔn)型線性規(guī)劃模型具有的特點(diǎn)有：第一，目標(biāo)函數(shù)是求最大值；第二，約束條件為線性方程組；第三，未知量都有非負(fù)限制.

2.2 非標(biāo)準(zhǔn)型

非標(biāo)準(zhǔn)性線性規(guī)劃模型可以通過(guò)三種形式轉(zhuǎn)化為標(biāo)準(zhǔn)型：

2.2.1 目標(biāo)函數(shù)是求最小minZ

設(shè)minZ=c1x1+c2x2+…+cnxn，可設(shè)Z'=-Z，則很簡(jiǎn)單的將最小值問(wèn)題轉(zhuǎn)化為求最大值問(wèn)題，即是將minZ轉(zhuǎn)化為求max-Z，且maxZ'=-c1x1-c2x2-…-cnxn.

2.2.2 約束條件為不等式

如果約束條件為不等式，則可增加一個(gè)或減少一個(gè)非負(fù)變量，是約束條件變?yōu)榈仁剑黾踊驕p去的這個(gè)條件稱為松弛變量.比如說(shuō)，ai1x1+ai2x2+…+ainxn≤bi加一個(gè)非負(fù)變量xn+1，使不等式變?yōu)榈仁剑篴i1x1+ai2x2+…+ainxn+xx+1=bi,如果約束為ai1x1+ai2x2+…+ainxn≥bi，使不等式變?yōu)榈仁剑篴i1x1+ai2x2+…+ainxn-xx+1=bi.

2.2.3 模型中的某些變量沒(méi)有非負(fù)限制

若某個(gè)變量xj可正可負(fù)，這是可設(shè)兩個(gè)非負(fù)變量x'j和x"j，令xj=x'j-x"j，這樣就可以滿足標(biāo)準(zhǔn)型的要求.

3 單純形法

單純形法，求解線性規(guī)劃問(wèn)題的通用方法.它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到.頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解.單純形法的計(jì)算步驟可以歸納為以下步驟[2]：

（1）找初始可行基，列出單純形表.

（3）若存在某個(gè)σk>0(m+1≤k≤n)，且其對(duì)應(yīng)的pk≤0，

則計(jì)算方可停止，此問(wèn)題無(wú)界.否則必須進(jìn)行步驟（4）

（5）換基迭代.以alk為主元素，用高斯消去法把xk所對(duì)應(yīng)的系數(shù)列向量，將原表中的XB列中的xl換成xk，可以得到一張新的計(jì)算表.

（6）重復(fù)步驟（2）-（5），直到計(jì)算終止.

可以看出，退化解是指基可行解里至少還存在著一個(gè)為0的分量.若按照□規(guī)則去代換變量時(shí)，若最小比值的個(gè)數(shù)不止一個(gè)，那么在下一次迭代中就會(huì)出現(xiàn)數(shù)值為0的基變量，此時(shí)就發(fā)生了退化現(xiàn)象.在此退化解上迭代，下一次換出的將是為0的基變量，而目標(biāo)函數(shù)值不會(huì)發(fā)生改變.迭代續(xù)下去，循環(huán)現(xiàn)象便會(huì)發(fā)生，永遠(yuǎn)達(dá)不到最優(yōu)解.若按最大檢驗(yàn)數(shù)法則選取進(jìn)基變景，非基變景的非負(fù)檢驗(yàn)數(shù)中最大值不止一個(gè)，又怎么選？為了解決上述這種情況，很多前輩都進(jìn)行過(guò)相關(guān)研究，Bland法則可以很好地解決這個(gè)問(wèn)題. Blank法則不走入：

（1）在所有檢驗(yàn)數(shù)大于0的非基變暈屮，若最大檢驗(yàn)數(shù)的存在不止一個(gè)吋，選取最小下標(biāo)的xk換進(jìn)基變量，即k=

（2）當(dāng)按照規(guī)則確定換入變量吋，若最小比值不止一個(gè)時(shí)，選取最小下標(biāo)的xl作為換出變量，即

如某番茄廠2010年種植了3種番茄3，分別是：石紅二號(hào)、石紅三號(hào)和新番九號(hào)，兩條不同規(guī)格的番茄醬生產(chǎn)線，番茄可種植土地為4000平方米，但是至于300平方米適合種植新番九號(hào).同時(shí)，由于生產(chǎn)需要，必須要求一號(hào)生產(chǎn)線產(chǎn)量達(dá)到5萬(wàn)噸，二號(hào)生產(chǎn)線達(dá)到10萬(wàn)噸，如何合理規(guī)劃3種番茄品種的種植面積才能使番茄醬產(chǎn)量在滿足訂單的前提下達(dá)到最大.因此建立以下模型：maxz-y1+y2.滿足約束條件：

x1+x2+x3≤4000.其中，石紅二號(hào)種植面積為x1，石紅三號(hào)種植面積為x2，新番九號(hào)種植面積為x3，y1為一號(hào)生產(chǎn)線產(chǎn)量，y2為2號(hào)生產(chǎn)線產(chǎn)量.在加上松弛變量之后可得到此線性規(guī)劃的標(biāo)準(zhǔn)形式：maxz-50.37x1+52.71x2+44.13x3，滿足約束條件：

x1+x2+x3+x6-4000.利用單純形法，經(jīng)過(guò)迭代運(yùn)算，最終得到的基本可行解為：

x1-200,x2-3500,x3-300,s1-0,s2--3400,s3-0,s1-29966, s5--27832,s6-0，這時(shí)z-207798，由于σj≤0，可知z-207798為最優(yōu)值.

4 內(nèi)點(diǎn)法

內(nèi)點(diǎn)法是一種求解線性規(guī)劃或非線性凸優(yōu)化問(wèn)題的算法.它是由John von Neumann發(fā)明的，他利用戈?duì)柕さ木€性齊次系統(tǒng)提出了這種新的求解線性規(guī)劃的方法.后被Narendra Karmarkar于1984年推廣應(yīng)用到線性規(guī)劃，即Karmarkar算法[4].其基本原理如下：minf(x)s.t.c(x)≥0，x∈Rn， c(x)∈Rm，與其對(duì)應(yīng)的對(duì)數(shù)型懲罰函數(shù)為是原始函數(shù)f(x)的梯度，且▽ci(x)是ci的梯度.除了原始變量x，還需要引入了拉格朗日乘子λ∈Rm：?m i=1 ci(x)λi=μ，這有時(shí)也被稱為為擾動(dòng)互補(bǔ)條件，類似于KKT條件中的互補(bǔ)松弛.為了找到使得懲罰函數(shù)梯度為0的(xμ,λμ)，可以得到以下這么一個(gè)關(guān)于梯度的等式：δ-ATλ=0，其中，A是限制條c(x)的雅克比矩陣，應(yīng)用牛頓法可以發(fā)現(xiàn)，這里μ是一個(gè)小的正參數(shù)，常被稱作“懲罰因子”.懲罰函數(shù)的梯度為其中，W是f (x)的黑塞矩陣，B是λ的對(duì)角矩陣.內(nèi)點(diǎn)法的研究熱點(diǎn)主要轉(zhuǎn)向于半定優(yōu)化、半定互補(bǔ)、非凸優(yōu)化及組合優(yōu)化問(wèn)題上.

在Karmarkar算法上深入研究并提出了各種修正內(nèi)點(diǎn)法方法：仿射尺度法，對(duì)數(shù)障礙函數(shù)法，路徑跟蹤法算法等.原仿射比例調(diào)節(jié)法是從原問(wèn)題出發(fā)，用一個(gè)仿射變換代替投影變換，把坐標(biāo)系從一個(gè)非負(fù)象限(不是單純形)映射到其本身.

〔1〕曾梅清,田大鋼.線性規(guī)劃問(wèn)題的算法綜述[J].科學(xué)技術(shù)與工程,2010,10(1):152-159.

〔2〕薛靜芳.線性規(guī)劃的單純形算法研究及應(yīng)用[D].大連海事大學(xué),2013.

〔3〕Vershik A.L.V.Kantorovich and linear programming.arXiv preprint arXiv:0707.0491.2007.

O221.2

A

1673-260X（2014）05-0001-02