線性規劃問題的相關算法研究

曾國斌

（海口經濟學院，海南海口571127）

線性規劃問題的相關算法研究

曾國斌

（海口經濟學院，海南海口571127）

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

線性規劃；內點法；單純形法

1 線性規劃的發展歷程

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

2 數學模型

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

2.1 標準型

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

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

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

2.2 非標準型

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

2.2.1 目標函數是求最小minZ

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

2.2.2 約束條件為不等式

如果約束條件為不等式，則可增加一個或減少一個非負變量，是約束條件變為等式，增加或減去的這個條件稱為松弛變量.比如說，ai1x1+ai2x2+…+ainxn≤bi加一個非負變量xn+1，使不等式變為等式：ai1x1+ai2x2+…+ainxn+xx+1=bi,如果約束為ai1x1+ai2x2+…+ainxn≥bi，使不等式變為等式：ai1x1+ai2x2+…+ainxn-xx+1=bi.

2.2.3 模型中的某些變量沒有非負限制

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

3 單純形法

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

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

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

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

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

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

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

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

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

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

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

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

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

4 內點法

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

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

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

〔2〕薛靜芳.線性規劃的單純形算法研究及應用[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