一種求解LP問題的兩階段基點(diǎn)迭代轉(zhuǎn)移方法

劉道建　黃天民　陳勇

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

關(guān)鍵詞：線性規(guī)劃； 基點(diǎn)轉(zhuǎn)移矩陣；退化的；局部正則化；算法

中圖分類號(hào)：O221.1 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

1單純形基點(diǎn)的定向迭代轉(zhuǎn)移模型

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

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

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

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

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

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

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

2兩階段基點(diǎn)迭代轉(zhuǎn)移算法

2.1基本思路與構(gòu)想

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

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

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

對照分析新算法的運(yùn)算平臺(tái)為基點(diǎn)轉(zhuǎn)移矩陣，相比單純形類算法的運(yùn)算平臺(tái)——單純形表， 基點(diǎn)轉(zhuǎn)移矩陣這一新平臺(tái)的結(jié)構(gòu)化程度更高，不僅線性特征明顯，而且?guī)缀纹矫嫣卣饕彩滞怀?，更能反映LP模型之結(jié)構(gòu)特點(diǎn).另外，單純形類算法之基點(diǎn)轉(zhuǎn)移，因“換基”中的基退化問題而極易發(fā)生基循環(huán)現(xiàn)象.而利用新算法求解LP問題時(shí)，因?yàn)槭褂昧丝尚杏蚓植?正則化方法處理基點(diǎn)退化轉(zhuǎn)移問題，求解過程中的基點(diǎn)轉(zhuǎn)移總在非退化情況下進(jìn)行，所以，從根本上消除了基循環(huán)現(xiàn)象發(fā)生之可能.

4結(jié)論

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

2）新算法是以單純形之極點(diǎn)的極方向?yàn)榈较虻囊环N極點(diǎn)迭代算法，它采用擇優(yōu)函數(shù)確定迭代方向，并通過矩陣初等變換來實(shí)現(xiàn)極點(diǎn)的迭代轉(zhuǎn)移，

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

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

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

5）新算法的迭代運(yùn)算是線性的，且迭代過程中目標(biāo)函數(shù)值嚴(yán)格單調(diào)，但與攝動(dòng)單純形算法比較，它的計(jì)算量得到大大減少，所以，本研究基本達(dá)到了先期預(yù)設(shè)的研究目標(biāo).

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

參考文獻(xiàn)

[1]胡清淮，魏一鳴. 線性規(guī)劃及其應(yīng)用[M]. 北京：科學(xué)出版社，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]顏紅彥，潘平奇. 線性規(guī)劃的無比值檢驗(yàn)CrissCross算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，32（12）：1949-1952.

[7]刑金萍，樊彩霞. 改進(jìn)的哈奇揚(yáng)算法求解線性不等式組問題[J]. 科學(xué)技術(shù)與工程，2009，10（19）：5752-5754.

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

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

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

4結(jié)論

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

2）新算法是以單純形之極點(diǎn)的極方向?yàn)榈较虻囊环N極點(diǎn)迭代算法，它采用擇優(yōu)函數(shù)確定迭代方向，并通過矩陣初等變換來實(shí)現(xiàn)極點(diǎn)的迭代轉(zhuǎn)移，

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

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

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

5）新算法的迭代運(yùn)算是線性的，且迭代過程中目標(biāo)函數(shù)值嚴(yán)格單調(diào)，但與攝動(dòng)單純形算法比較，它的計(jì)算量得到大大減少，所以，本研究基本達(dá)到了先期預(yù)設(shè)的研究目標(biāo).

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

參考文獻(xiàn)

[1]胡清淮，魏一鳴. 線性規(guī)劃及其應(yīng)用[M]. 北京：科學(xué)出版社，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]顏紅彥，潘平奇. 線性規(guī)劃的無比值檢驗(yàn)CrissCross算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，32（12）：1949-1952.

[7]刑金萍，樊彩霞. 改進(jìn)的哈奇揚(yáng)算法求解線性不等式組問題[J]. 科學(xué)技術(shù)與工程，2009，10（19）：5752-5754.

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

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

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

4結(jié)論

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

2）新算法是以單純形之極點(diǎn)的極方向?yàn)榈较虻囊环N極點(diǎn)迭代算法，它采用擇優(yōu)函數(shù)確定迭代方向，并通過矩陣初等變換來實(shí)現(xiàn)極點(diǎn)的迭代轉(zhuǎn)移，

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

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

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

5）新算法的迭代運(yùn)算是線性的，且迭代過程中目標(biāo)函數(shù)值嚴(yán)格單調(diào)，但與攝動(dòng)單純形算法比較，它的計(jì)算量得到大大減少，所以，本研究基本達(dá)到了先期預(yù)設(shè)的研究目標(biāo).

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

參考文獻(xiàn)

[1]胡清淮，魏一鳴. 線性規(guī)劃及其應(yīng)用[M]. 北京：科學(xué)出版社，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]顏紅彥，潘平奇. 線性規(guī)劃的無比值檢驗(yàn)CrissCross算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，32（12）：1949-1952.

[7]刑金萍，樊彩霞. 改進(jìn)的哈奇揚(yáng)算法求解線性不等式組問題[J]. 科學(xué)技術(shù)與工程，2009，10（19）：5752-5754.

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

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

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