一種求解LP問題的兩階段基點迭代轉移方法

劉道建 ,黃天民,陳 勇

(1．西南交通大學 電氣工程學院，四川 成都 610031； 2. 湖南科技大學 數(shù)學與計算科學學院，湖南 湘潭 411201)

當今，盡管學術界將LP算法劃分成三大類型[1-4]：單純形類算法、橢球類算法和內點類算法，但它們具有一個共同特征，即均屬于迭代算法，根本區(qū)別在于迭代方式不同，這也導致了它們在搜索效率上的差異.單純形類算法的優(yōu)點在于迭代過程通過 “換基”實現(xiàn)，所以迭代運算均為線性的．缺點是在迭代過程中目標函數(shù)值的非嚴格單調性，當然，出現(xiàn)目標函數(shù)值的非嚴格單調性的內在因素在于退化基點的“一解多基”現(xiàn)象，這一缺陷可能導致迭代過程中的基循環(huán)問題．而橢球類算法與內點類算法卻恰好相反，它們的優(yōu)點是在迭代過程中目標函數(shù)值的嚴格單調性，缺點是主要的迭代運算是非線性的，每次迭代的計算量巨大．也正因為這一缺陷，雖然它們是多項式時間的，但實際使用效果并非十分理想，甚至搜索效率還不如單純形類算法.那么，是否存在迭代運算為線性的，而迭代過程的目標函數(shù)值嚴格單調的LP算法？回答是肯定的，攝動單純形法[1]就是這樣的LP算法.

所謂攝動單純形法，實為一種先將普通的LP問題轉化為無退化現(xiàn)象的LP問題，再利用單純形法求解的LP算法．從理論上看，攝動單純形法是一種理想的LP算法，它同時具備上述提到的兩個優(yōu)良特性.然而，在實踐中，因為攝動項的添加，相當于要解一個雙倍于原LP問題規(guī)模的新問題，導致迭代過程的計算量呈爆炸性增長．因此，這種算法的實用性大大降低了.

線性、幾何平面特性為線性規(guī)劃的兩大基本結構特性．橢圓類算法、內點類算法都是從非線性規(guī)劃中移植過來的，屬于非線性化方法．自然地，這些算法無法充分反映與利用好線性規(guī)劃的以上兩大結構特性.而傳統(tǒng)的單純形類算法(包括攝動單純形法)的運算平臺是單純形表，該平臺的線性特征十分明顯，但幾何平面特征明顯不足，這也導致了傳統(tǒng)單純形類算法的功能缺陷.

鑒于以上情況，本文欲實現(xiàn)的主要研究目標如下：1)利用線性規(guī)劃的結構特性，構建更能反映線性規(guī)劃線性、幾何平面這一兩面性結構特點的LP新解算模型；2)從分析退化基點的轉移機理入手，找到退化基點的轉移性缺陷，并制定有效的應對之策；3)在以上兩方面研究成果的基礎上，提出迭代運算為線性、目標函數(shù)值嚴格單調的LP迭代算法，這也是本文欲達成的最終之研究目標.

1 單純形基點的定向迭代轉移模型

首先，本文研究對象為如下一般形式的LP問題：

MaxZ=cX，

(1)

其中，A1∈Rl×n，A2∈R(m-l)×n，by∈Rl×1，bz∈R(m-l)×1,c∈R1×n，且by≥0，bz>0.

引理1LP問題(1)與下列LP問題(2)等價：

MaxW=cX+0X′+0Y1-mY2,

(2)

其中，E1∈Rn,E2∈Rm-l均是單位矩陣，m∈Rm-l，且m的所有元素都是無窮大正常數(shù)M.

定義1對于LP問題(1)，將如下數(shù)字矩陣稱之為它的初始基點定向轉移矩陣：

(3)

而且，將它的如下三個分塊：

(4)

分別稱為該基點定向轉移矩陣的基解塊(列)、轉移方向塊和強迫性價值塊(列)，又將方向塊的任意一列稱為該矩陣的轉移控制方向列，統(tǒng)稱為轉移控制矢量組(向量by,bz,m同上).

特別地，對于如下特殊的LP問題：

MaxZ=cX,

(5)

它的基點定向轉移矩陣為：

對于LP問題(1)的如下約束不等式組：

引理2約束不等式組(6)有解當且僅當如下LP問題有最優(yōu)解：

MaxW=0X+0X′+0Y1-mY2，

(7)

其中，E1∈Rn，E2∈Rm-l均是單位矩陣，m∈m-l，且m的所有元素都是無窮大正常數(shù)M.

定義2對于線性不等式組(6)，將如下數(shù)字矩陣稱之為它的初始基點定向轉移矩陣：

(8)

而且，將它的如下三個分塊：

(9)

分別稱為該基點定向轉移矩陣的基解塊(列)、轉移方向塊和強迫性價值塊(列)，又將方向塊的任意一列稱為該矩陣的轉移控制方向列，統(tǒng)稱為轉移控制矢量組，其中，向量by，bz，m與引理1中所定義的完全一致.

1)它們的基解塊(列)表示單純形(超多面體)的一個頂點A0；

2)它們的方向塊之列向量代表過超多面體頂點A0的棱線方向.若以頂點A0為迭代點、這些棱線方向為迭代方向，則能夠實現(xiàn)頂點A0向其鄰近頂點的迭代轉移；

3)它們的強迫性價值系數(shù)塊(列)即代表頂點A0之優(yōu)化轉移的目標參考方向.

由此可見，借助基點定向轉移矩陣，完全將LP的求解問題與線性不等式組的定解問題轉化為同一類型的數(shù)學問題——矩陣優(yōu)化轉換問題.

為此，下面將針對基點定向轉移矩陣之優(yōu)化轉換問題，引進一種特殊的矩陣變換——負旋轉迭代運算．

定義3若基點定向轉移矩陣的一個初等列變換同時滿足如下條件：

1)它以基點定向轉移矩陣中的某轉移控制列的一個負元素為中心變換元素；

2)圍繞中心變換元素，先經(jīng)過矩陣列初等變換使中心變換元素變?yōu)?，在經(jīng)過若干次矩陣列初等變換后使中心變換元素所在行的其他元素均變?yōu)榱阍?強迫性價值列始終都不參與列初等變換)；

3)在列變換過程中，要保持基解列的所有分量元素非負.則稱這種特殊的矩陣初等變換為該基點定向轉移矩陣關于轉移控制列的一次負旋轉迭代轉換，同時把其中的中心變換元素稱為該負旋轉迭代變換的旋轉主元(簡稱旋轉元).

性質1如果基點定向轉移矩陣的基解列是非退化的，那么，通過該矩陣關于轉移控制組的任何一列元素(非負元素列除外)的負旋轉迭代轉移，一定可實現(xiàn)該基點向與之鄰近基點的一次基點轉移.

至此，通過構建單純形(包括LP問題的可行域、線性不等式組的解空間)的基點定向轉移矩陣，在單純形的基點與數(shù)字矩陣之間建立起了一種對應關系．在矩陣的各功能塊中，基解列代表基點，而其方向塊的各列代表基點的迭代轉移方向(即該超多面體頂點的極方向)，強迫性價值系數(shù)列代表該基點轉移的目標參考方向.本研究的目標之一在于，通過對基點定向轉移矩陣的負旋轉迭代(等價于基點的迭代轉移)，最終找到單純形的一個優(yōu)化極點.

實際上，依據(jù)上述性質1，僅解決了單純形非退化基點的轉移問題.要想利用基點定向轉移矩陣的負旋轉迭代運算來搜索單純形的優(yōu)化極點，還必須解決單純形退化基點的轉移問題.為此，引入下列定義及有關命題：

定義4若單純形基點定向轉移矩陣的基解列中所含零元素的個數(shù)大于決策變量數(shù)與剩余變量數(shù)之和，則稱該基點定向轉移矩陣對應的基點是退化的，將方向塊中非單位行對應的基解列的零元素稱為該基點的退化零元素，并稱單純形在該退化基點處具有局部非正則性.

定義5將“用無窮小量正參數(shù)ε替代退化基點的所有退化零元素”的操作稱為一次單純形局部小量正參數(shù)ε正則化；若單純形的極點都是非退化的，則稱該單純形具有正則性(也稱LP問題是正則的LP問題).

性質2只要小量正參數(shù)ε足夠小，可行域的局部小量正參數(shù)ε正則化就不會改變LP問題的最優(yōu)基.

性質3只要小量正參數(shù)ε足夠小，經(jīng)過局部小量正參數(shù)ε正則化的基點定向轉移矩陣，不論通過多少次負旋轉迭代運算，所得矩陣的ε零化矩陣(即，令其中的ε值為零而得到的矩陣)仍然為原LP問題的人工強迫性LP問題可行域基點的轉移矩陣.

實際上，之所以要對單純形進行局部小量正參數(shù)ε正則化處理，目的就是讓可行域退化的基點非退化化，將退化基點的轉移問題轉化為非退化極點的轉移問題，徹底消除基點退化對迭代搜索的不利影響.

基于以上非退化基點的定向轉移矩陣及其轉移性質、單純形局部ε正則化、以及基點與矩陣的上述對應關系，針對LP問題(1)，(5)或線性不等式組(6)的定解問題，構建如下單純形基點的定向迭代轉移模型：

上述點向式基點定向迭代轉移模型清楚地表達了單純形非退化可行基點之間的轉移過程及轉移機理．經(jīng)過一次負旋轉迭代運算，不僅將非退化頂點Ak轉移到與之相鄰的頂點Ak+1，而且，也將頂點Ak的轉移控制方向組dj(Ak)(j=1,2,…,n)轉換成頂點Ak+1的轉移控制方向組dj(Ak+1)(j=1,2,…,n)，為新基點Ak+1的轉移創(chuàng)造了與舊基點Ak轉移同樣的條件.要利用單純形極點轉移進行尋優(yōu)搜索，模型的這種屬性是必須具備的，也是最基本的條件.

依據(jù)基點定向轉移矩陣及其負旋轉迭代的定義，不難得到如下定理：

定理1對于LP問題(1)，設下列矩陣A0為它的基點定向轉移矩陣：

(11)

如果存在一組矩陣{Hs|s=1,2,…,k}>(其中，Hs為A0的第s次負旋轉迭代運算對應的初等變換矩陣)，且令：

2)若W≤0，但v≠0，則LP問題(1)的解集必為空集，即LP問題(1)無最優(yōu)解；

推論對于線性不等式組(6)，設下列矩陣A0為它的基點定向轉移矩陣：

(14)

如果存在一組矩陣{Hs|s=1,2,…,k}>(其中，Hs為A0的第s次負旋轉迭代運算對應的初等變換矩陣)，且令：

1)若W≤0，且v=0，則線性不等式組(6)的解集非空；

2)若W≤0，但v≠0，則線性不等式組(6)的解集必為空集．

2 兩階段基點迭代轉移算法

2.1 基本思路與構想

先利用單純形基點的定向迭代轉移模型，從線性不等式組(6)的初始基點定向轉移矩陣出發(fā)，通過負旋轉迭代運算，求得線性不等式組(6)的一個可行基點及其基點定向轉移矩陣，從而，利用這一矩陣，可以求得LP問題(1)的一個可行基點及其基點定向轉移矩陣(它的基解列、轉移控制列中不含人工變量值分量，而價值系數(shù)列中也不含強迫性無窮大正參數(shù)M)，再利用單純形基點的定向迭代轉移模型求解之，最終求得原LP問題的最優(yōu)解.新算法的整個尋優(yōu)過程可分為如下兩個階段：

1)定解階段：判斷原LP問題的可行域(即約束不等式組的解空間)是否非空？

2)尋優(yōu)階段：在可行域非空的情況下，利用單純形基點的定向迭代轉移模型求出原LP問題的最優(yōu)解.

2.2 所涉及的基本操作

為表述方便，不妨設當前需要操作的基點定向轉移矩陣如下：

1)構建擇優(yōu)函數(shù)

根據(jù)前面的最優(yōu)性判別定理，為確定極點的優(yōu)化轉移方向，可以構建如下?lián)駜?yōu)函數(shù)：

?(ζ)=c,ζ(ζ∈{aj|j=1,2,…,r}>)．

(17)

2)選擇迭代方向

根據(jù)上述擇優(yōu)函數(shù)(17)，按照如下公式確定當前極點的優(yōu)化轉移方向ap：

(18)

顯而易見，在aj(j=1,2,…,r)中，就是選擇使擇優(yōu)函數(shù)值最大的向量做為當前極點的優(yōu)化轉移方向.

3)選擇旋轉主元

在當前極點的優(yōu)化轉移方向ap已被確定的情況下，依據(jù)前面負旋轉迭代變換定義要求，就必須按照如下公式在ap中確定迭代運算的旋轉主元aqp：

4)局部小量正參數(shù)ε正則化

假如當前極點出現(xiàn)退化的零元素，那么，在進行負旋轉迭代變換之前，先把極點中的退化零元素全部替代為無窮小量參數(shù)ε，再利用上述(18)和(19)規(guī)則確定旋轉主元，最后進行負旋轉迭代運算.當搜索過程出現(xiàn)如下情形之一時，即可終止局部小量正參數(shù)ε正則化：

(a)在新極點對應的可行基解中，非零分量均已非含ε的無窮小量；

(b)新極點的轉移控制矢量與目標向量的內積均小于或等于零(對目標函數(shù)極大化情形).

5)搜索終止條件

當?(ak)≤0(?ak∈{aj|j=1,2,…,r})時，最優(yōu)(或定解)搜索立即終止.

2.3 基本步驟

利用新算法求解LP問題(1)的基本步驟如下：

步驟1 根據(jù)所給LP問題，確定它的約束不等式組的基點定向轉移矩陣；

步驟2 判斷當前矩陣的基解列中是否存在退化的零元素？是，用ε取代所有退化零元素；否，則進入下一步；

步驟3 判定當前基點定向轉移矩陣是否符合定解終止條件？是，則進入下一步；否，則直接轉入步驟五；

步驟4 根據(jù)前面定解定理，判定該約束不等式組是否有解？是，則直接轉入步驟7；否，即可判定原LP問題無最優(yōu)解，算法終止；

步驟5 利用所構建的選擇函數(shù)，在當前基點的轉移控制矢量組中選取一個目標優(yōu)化方向矢；并進入下一步；

步驟6 利用負旋轉迭代運算，求出比當前基點的目標函數(shù)值更優(yōu)的基點的定向轉移矩陣，并轉入到步驟2.

(以上為定解階段)

步驟7 利用當前基點定向轉移矩陣，求出原LP問題的一個基點定向轉移矩陣(它的價值系數(shù)列中不含強迫性無窮大正參數(shù)M)，并進入下一步；

步驟8 判斷當前矩陣的基解列中是否存在退化的零元素？是，用ε取代所有退化零元素；否，則進入下一步；

步驟9 判定當前基點定向轉移矩陣是否符合定解終止條件？是，算法終止，并給出原LP問題的最優(yōu)解，或者，判定原LP問題只有無界解；否，則轉入下一步；

步驟10 利用所構建的選擇函數(shù)，在當前極點的轉移控制矢量組中選取一個目標優(yōu)化方向矢；并進入下一步；

步驟11 利用負旋轉迭代運算，找出比當前基點的目標函數(shù)值更優(yōu)的基點之定向轉移矩陣，并轉入到步驟8.

(以上為尋優(yōu)階段)

3 實例展示

實例

解：

→

→

→

(以上為定解階段，并由性質3可得如下第一個矩陣)

→

→

→

顯然，此矩陣已符合終止條件，則：

標注在上述矩陣中，“*”表示省略元素后剩下的空格；x1，x2為決策變量，x3，x4分別為第5，6個條件約束的剩余變量，而x5～x8分別為第1～4個條件約束的松弛變量，y1，y2分別為第5，6個條件約束的人工變量．

對照分析新算法的運算平臺為基點轉移矩陣，相比單純形類算法的運算平臺——單純形表, 基點轉移矩陣這一新平臺的結構化程度更高，不僅線性特征明顯，而且?guī)缀纹矫嫣卣饕彩滞怀?，更能反映LP模型之結構特點．另外，單純形類算法之基點轉移，因“換基”中的基退化問題而極易發(fā)生基循環(huán)現(xiàn)象．而利用新算法求解LP問題時，因為使用了可行域局部 -正則化方法處理基點退化轉移問題，求解過程中的基點轉移總在非退化情況下進行，所以，從根本上消除了基循環(huán)現(xiàn)象發(fā)生之可能．

4 結 論

1)在求解LP問題的過程中，由于新算法對退化極點采取了可行域局部小量正參數(shù)ε正則化處理，確保了整個尋優(yōu)過程均在非退化情形下完成，消除了退化問題對極點迭代轉移過程的不利影響，所以，新算法很好地解決了算法運行中的基循環(huán)問題．

2)新算法是以單純形之極點的極方向為迭代方向的一種極點迭代算法，它采用擇優(yōu)函數(shù)確定迭代方向，并通過矩陣初等變換來實現(xiàn)極點的迭代轉移，

操作簡便快捷，便于程序化處理，避免了諸如橢圓法與內點法中繁雜的迭代運算，搜索效率顯著提高．

3)基點定向轉移矩陣作為新的LP問題算法平臺，與傳統(tǒng)的單純形表比，它的結構化程度高，且充分反映了線性規(guī)劃的幾何平面特性，為解決LP的解算問題找到了一種新的數(shù)學工具．

4) 單純形法是利用換基的方式來實現(xiàn)基點迭代轉移的，轉移過程極易受退化現(xiàn)象的影響(即易發(fā)生基循環(huán)問題)．新算法的基點轉移，本質上，已經(jīng)回歸到了傳統(tǒng)的點向式轉移方式，整個搜索過程始終在非退化的情形下完成，沒有出現(xiàn)基循環(huán)的可能．

5)新算法的迭代運算是線性的，且迭代過程中目標函數(shù)值嚴格單調，但與攝動單純形算法比較，它的計算量得到大大減少，所以，本研究基本達到了先期預設的研究目標．

6)對求解退化的LP問題，新算法繼承了攝動單純形算法的優(yōu)點(即始終保持迭代中目標函數(shù)值的嚴格單調性)，也克服了因攝動項的添加，使計算量猛然增加的缺陷．不過，與單純形算法類似，新算法也存在變量爆炸性難題，這也是在今后研究中需要重點突破與解決的問題．

[1] 胡清淮，魏一鳴. 線性規(guī)劃及其應用[M]. 北京：科學出版社，2004. 20-46．

HU Qing-huai, WEI Yi-ming. Linear programming and its application[M]. Beijing：Science Press, 2004. 20-46 ．(In Chinese)

[2] DANTZIG G B. Linear programming extensions [M]. Princeton: Princeton University Press, 1963. 79-87．

[3] KHACHIYAN L G. A polynomial algorithm for linear programming [J].Soviet Mathematics Doklady, 1979, 20(3)：191-194．

[4] KARMARKAR N K. A new polynomial-time algorithm for linear programming[J]. Combinatorica, 1984, 4(5):373-395．

[5] LI Wei. New variable of artificial-free algorithm for linear programming problem[J]. J of Math(PRC), 2008, 28(9): 243-248．

[6] 顏紅彥，潘平奇. 線性規(guī)劃的無比值檢驗Criss-Cross算法[J]. 合肥工業(yè)大學學報:自然科學版，2009，32(12)：1949-1952．

YAN Hong-yan, PAN Ping-qi. Ratio-test-free criss-cross algorithm for linear programming[J]. Journal of Hefei University of Technology: Natural Science, 2009，32(12)：1949-1952.(In Chinese)

[7] 刑金萍，樊彩霞. 改進的哈奇揚算法求解線性不等式組問題[J]. 科學技術與工程，2009，10(19)：5752-5754．

XING Jin-ping, FANG Cai-xia. Improved khachiyan algorithm for systems of linear inequalities[J]. Science Technology and Engineering, 2009,10(19)：5752-5754.(In Chinese)

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

ZENG Mei-qing, TIAN Da-gang. The review to the algorithm of linear programming problems[J]. Science Technology and Engineering, 2010，10(1)：152-159.(In Chinese)

[9] 孫中波，段復建.不等式約束優(yōu)化的非單調可行信賴域-SQP算法[J].應用數(shù)學學報，2011，34(4)：655-670．

SUN Zhong-bo, DUAN Fu-jian. A feasible trust region SQP method with non-monotone line search for inequality constrained optimization[J]. Acta Mathematicae Applicatae Sinica , 2011, 34(4)：655-670.(In Chinese)

[10] 劉道建, 黃天民. 一種線性不等式組的矩陣變換定解方法[J]. 上海交通大學學報:自然科學版，2012，46(10)：1701-1706．

LIU Dao-jian, HUANG Tian-min. A matrix column-transform solution-decision method for the system of linear Inequalities[J]. Journal of Shanghai Jiaotong University : Natural Science, 2012, 46(10)：1701-1706.(In Chinese)