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

曾國斌

（?？诮?jīng)濟學院，海南?？?71127）

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

曾國斌

（?？诮?jīng)濟學院，海南海口571127）

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

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

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

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

2 數(shù)學模型

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

2.1 標準型

線性規(guī)劃的模型的標準型為：max Z=x1C1+x2C2+x3C3+

x4C4+…+xnCn，約束條件為，非負的

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

2.2 非標準型

非標準性線性規(guī)劃模型可以通過三種形式轉化為標準型：

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

設minZ=c1x1+c2x2+…+cnxn，可設Z'=-Z，則很簡單的將最小值問題轉化為求最大值問題，即是將minZ轉化為求max-Z，且maxZ'=-c1x1-c2x2-…-cnxn.

2.2.2 約束條件為不等式

如果約束條件為不等式，則可增加一個或減少一個非負變量，是約束條件變?yōu)榈仁?，增加或減去的這個條件稱為松弛變量.比如說，ai1x1+ai2x2+…+ainxn≤bi加一個非負變量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 模型中的某些變量沒有非負限制

若某個變量xj可正可負，這是可設兩個非負變量x'j和x"j，令xj=x'j-x"j，這樣就可以滿足標準型的要求.

3 單純形法

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

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

（3）若存在某個σk>0(m+1≤k≤n)，且其對應的pk≤0，

則計算方可停止，此問題無界.否則必須進行步驟（4）

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

（6）重復步驟（2）-（5），直到計算終止.

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

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

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

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

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

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

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

4 內(nèi)點法

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

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

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

〔2〕薛靜芳.線性規(guī)劃的單純形算法研究及應用[D].大連海事大學,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