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

劉道建　黃天民　陳勇

摘要：利用線性規劃的線性、幾何平面這一兩面性結構特點，定義了LP問題的一種特殊基點轉移矩陣及其轉移運算，并建立了單純形基點的定向迭代轉移模型，從而提出了一種求解LP問題的兩階段基點定向轉移搜索方法.另外，借助新提出的可行域局部ε正則化方法，將退化基點迭代轉移轉化為非退化基點迭代轉移，徹底消除了基點退化對極點轉移搜索過程的不利影響.

關鍵詞：線性規劃； 基點轉移矩陣；退化的；局部正則化；算法

中圖分類號：O221.1 文獻標識碼：A

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1基本思路與構想

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

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

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

對照分析新算法的運算平臺為基點轉移矩陣，相比單純形類算法的運算平臺——單純形表， 基點轉移矩陣這一新平臺的結構化程度更高，不僅線性特征明顯，而且幾何平面特征也十分突出，更能反映LP模型之結構特點.另外，單純形類算法之基點轉移，因“換基”中的基退化問題而極易發生基循環現象.而利用新算法求解LP問題時，因為使用了可行域局部 正則化方法處理基點退化轉移問題，求解過程中的基點轉移總在非退化情況下進行，所以，從根本上消除了基循環現象發生之可能.

4結論

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

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

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

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

4） 單純形法是利用換基的方式來實現基點迭代轉移的，轉移過程極易受退化現象的影響（即易發生基循環問題）.新算法的基點轉移，本質上，已經回歸到了傳統的點向式轉移方式，整個搜索過程始終在非退化的情形下完成，沒有出現基循環的可能.

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

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

參考文獻

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

[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 polynomialtime algorithm for linear programming[J]. Combinatorica， 1984， 4（5）：373-395.

[5]LI Wei. New variable of artificialfree algorithm for linear programming problem[J]. J of Math（PRC）， 2008， 28（9）： 243-248.

[6]顏紅彥，潘平奇. 線性規劃的無比值檢驗CrissCross算法[J]. 合肥工業大學學報：自然科學版，2009，32（12）：1949-1952.

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

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

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

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

4結論

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

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

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

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

4） 單純形法是利用換基的方式來實現基點迭代轉移的，轉移過程極易受退化現象的影響（即易發生基循環問題）.新算法的基點轉移，本質上，已經回歸到了傳統的點向式轉移方式，整個搜索過程始終在非退化的情形下完成，沒有出現基循環的可能.

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

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

參考文獻

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

[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 polynomialtime algorithm for linear programming[J]. Combinatorica， 1984， 4（5）：373-395.

[5]LI Wei. New variable of artificialfree algorithm for linear programming problem[J]. J of Math（PRC）， 2008， 28（9）： 243-248.

[6]顏紅彥，潘平奇. 線性規劃的無比值檢驗CrissCross算法[J]. 合肥工業大學學報：自然科學版，2009，32（12）：1949-1952.

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

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

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

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

4結論

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

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

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

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

4） 單純形法是利用換基的方式來實現基點迭代轉移的，轉移過程極易受退化現象的影響（即易發生基循環問題）.新算法的基點轉移，本質上，已經回歸到了傳統的點向式轉移方式，整個搜索過程始終在非退化的情形下完成，沒有出現基循環的可能.

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

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

參考文獻

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

[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 polynomialtime algorithm for linear programming[J]. Combinatorica， 1984， 4（5）：373-395.

[5]LI Wei. New variable of artificialfree algorithm for linear programming problem[J]. J of Math（PRC）， 2008， 28（9）： 243-248.

[6]顏紅彥，潘平奇. 線性規劃的無比值檢驗CrissCross算法[J]. 合肥工業大學學報：自然科學版，2009，32（12）：1949-1952.

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

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

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

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