高培旺

(閩江學院，福建 福州 350121)

第一階段單純形法的一種分段定價策略

高培旺

(閩江學院，福建 福州 350121)

提出第一階段單純形法的一種分段定價策略，而在此策略下可產生兩種單純形算法變式.根據(jù)Cheng的判斷準則將所有非基變量分成四段，其中一段由最優(yōu)基本解中的非基變量構成，在迭代過程中對另外三段非基變量依其保持非基的可能性程度先后交替定價.第一種算法從迭代開始就根據(jù)Cheng的兩個判斷準則對四段非基變量不斷調整，這雖極大節(jié)省了定價計算的工作量，但兩個判斷準則的計算需要耗費大量時間，導致該算法計算效率很低.第二種算法對第一種算法作了改進，當目標當前值超過最優(yōu)值的2/3時，開始對非基變量分段，然后只根據(jù)Cheng的一個較簡單的判斷準則對定價后的非基變量進行調整.對來自NETLIB和MIPLIB的27個典型算例的初步試驗結果表明，改進的算法不僅比經(jīng)典單純形算法所用的總迭代次數(shù)要少，在所有算例上所搜尋的非基列數(shù)也少，所耗費的計算時間更少，其計算性能高效而穩(wěn)定.

線性規(guī)劃；單純形法；定價準則；分段定價；計算效率

考慮如下形式的線性規(guī)劃問題：

(LP) maxf=cx

s.t.Ax=b，

x≥0,

這里，A=(A1,A2,…,An)∈Rm×n(m

求解(LP)的單純形算法首先需要一個初始可行基來啟動.通過構造輔助的第一階段問題，應用第一階段單純形算法可尋求初始可行基，而這一工作幾乎占到整個單純形法計算工作量的一半[1-2].相比第二階段單純形法，第一階段單純形算法能產生更多的信息，諸如目標最優(yōu)值既定、人工變量都在初始基中、必須旋轉出去等.如何利用這些已知信息，進一步提高第一階段單純形算法的計算效率，則是一個值得研究的課題.

一般地，定價分為完全定價和部分定價，完全定價需要計算所有非基變量的簡約價值系數(shù)，計算代價是昂貴的.部分定價只考察非基變量的一部分，然后從中選擇一個合適的候選變量入基.經(jīng)典的Dantzig準則[6]、最陡邊算法[7]和一些原始—對偶樞軸準則[8-9]等都屬于完全定價策略，而部分定價策略包括分段定價、動態(tài)定價[3]以及嵌套定價或多重定價[4-5].顯然，部分定價策略減少了對非基變量考察的計算工作量，但由于考察不全面，有可能漏掉對最佳入基變量的選擇，從而增加迭代的次數(shù).可見，部分定價策略的設計是非常靈活的，也是很講究的，關系到計算性能的優(yōu)劣.

Cheng[10]發(fā)現(xiàn)在單純形算法中滿足某些準則的一個非基變量就會成為最優(yōu)基本解中的非基變量，第一階段單純形法已知最優(yōu)值的信息可以用于執(zhí)行其中的判斷準則.據(jù)此，提出了第一階段單純形法的一種分段定價策略，在此策略下產生兩種單純形算法變式，即首先根據(jù)Cheng的判斷準則將所有非基變量分成四段，其中一段由最優(yōu)基本解中的非基變量構成，再在迭代過程中對另外三段非基變量依其保持非基的可能性程度先后交替定價，并將定價后的非基變量進行相應調整.第一種算法從迭代開始就根據(jù)Cheng的兩個判斷準則對四段非基變量不斷調整，這樣用于定價的非基變量數(shù)隨著迭代進程越來越少.與經(jīng)典單純形算法相比，它極大節(jié)省了定價計算的工作量，其所搜尋的非基列數(shù)之比僅為0.25，但兩個判斷準則的計算需要耗費大量時間，導致該算法計算效率很低.第二種算法對第一種算法作了改進，考慮到目標當前值隨著迭代進程趨近最優(yōu)值，越來越多的非基變量將保留在最優(yōu)基中，因此，該算法選擇從目標最優(yōu)值的2/3處開始對非基變量分段，然后只根據(jù)Cheng的一個較簡單的判斷準則對定價后的非基變量進行調整，以減少判斷調整的計算工作量，最后通過MATLAB編程在計算機上對來自NETLIB和MIPLIB的27個典型算例實現(xiàn)數(shù)值試驗.結果表明改進的算法比經(jīng)典單純形算法所用的總迭代次數(shù)還少，其比為0.97，在所有算例上都比經(jīng)典單純形算法所搜尋的非基列數(shù)要少，總搜尋非基列數(shù)之比為0.65.它在所有算例上耗費的計算時間都比經(jīng)典單純形算法少，其計算性能高效而穩(wěn)定.

1 第一階段單純形算法的分段定價原理

為了更好地闡釋第一階段單純形算法的分段定價原理，有必要重復一下Cheng的判斷準則及部分證明過程.

1)B-1Aj≥0.

則xj保持為最優(yōu)基本解的一個非基變量.

從而有

則意味著變量xj與最優(yōu)基B*對應的簡約價值系數(shù)為正，因而是最優(yōu)基本解的一個非基變量.

在問題(LP1)中，改變xj的目標函數(shù)系數(shù)為cj，約束矩陣系數(shù)為Aj，就得到原來的第一階段問題.由于其它變量的系數(shù)沒有發(fā)生變化，因此xj對應最優(yōu)基B*的簡約價值系數(shù)仍然保持為正，即

于是，可將上述命題推廣，得到如下結果.

1)B-1Aj≥0.

則xj保持為最優(yōu)基本解的一個非基變量.

由于很多線性規(guī)劃的現(xiàn)實問題都是退化的，推論1的適用性更廣.除非特別聲明，后面所指的條件1)、2)就是推論1的.

根據(jù)上述分析，J4確定是最優(yōu)基本解中的非基變量指標集，在以后的迭代過程中不需要再定價；J2和J3中的非基變量成為最優(yōu)基本解中的非基變量的可能性較大，但隨著迭代進程趨近最優(yōu)解，J3中的非基變量更有可能保持非基狀態(tài)；J1中的非基變量成為最優(yōu)基本解中的非基變量的確定性程度無法判定，應首先定價.這里采用Dantzig的“最負簡約價值系數(shù)”準則來選擇入基列指標.具體過程如下：選擇指標集J1，每次迭代之后根據(jù)分段策略將J1中的非基變量調整到J2、J3和J4中.當J1為空時，選擇J2，若J2非空時對其非基變量定價一次，調整四個指標集，再返回J1對其非基變量定價.當J1和J2都為空時，繼續(xù)對J3中的非基變量定價1次，當其所有非基變量的簡約價值系數(shù)保持非負，當前基本可行解就是第一階段問題的一個最優(yōu)解；否則，調整指標集J1、J2、J3和J4后，返回J1重復上述過程.基于上述算法原理，第一階段單純形算法分段定價策略的計算步驟描述如下：

算法A

步驟2)置J=J1，如果J為空集，轉步驟3)；否則，轉步驟5)．

步驟3)置J=J2，如果J為空集，轉步驟4)；否則，轉步驟5)．

步驟8)調整指標集J1、J2、J3和J4，返回步驟2)．

為了檢驗算法A這種分段定價策略的計算性能，從線性規(guī)劃標準測試庫NETLIB[11]和混合整數(shù)規(guī)劃標準測試庫MIPLIB[12]中選取了27個典型算例進行初步測試(對混合整數(shù)規(guī)劃問題，只求解其相應的線性規(guī)劃松弛問題的解)，并與經(jīng)典單純形算法的完全定價策略進行比較.使用MATLAB V7.1語言對Dantzig的經(jīng)典單純形算法和算法A進行了編程，在Lenovo ThinkCenter M9201z計算機上執(zhí)行數(shù)值試驗，且數(shù)值試驗的環(huán)境是完全相同的．以求解線性規(guī)劃問題所需要的樞軸數(shù)(用Iters表示)、定價過程中所搜尋過的非基列總數(shù)(用Cols表示)作為主要計算指標，對27個算例第一階段問題求解.計算結果見表1.

表1 單純形算法與分段定價策略兩種算法求解第一階段問題的計算比較

注：在獲得最優(yōu)表后，對退化人工變量從基中旋出,沒有再給Cols計數(shù).

從表1可以看到，算法A在11個算例上比經(jīng)典單純形算法所用的迭代次數(shù)多，在27個算例上所用的總迭代次數(shù)之比為1.17，但算法A在所有算例上所搜尋的非基列數(shù)都比經(jīng)典單純形算法少得多，總搜尋列數(shù)之比僅為0.25，即使算法A在算例scsd1上所用迭代次數(shù)之比高達2.60，所搜尋的非基列數(shù)之比也只有0.52.可見，算法A的定價效率是非常高的.然而，算法A在大部分算例上所耗費的執(zhí)行時間比經(jīng)典單純形算法要多，尤其對規(guī)模較大的問題，如scagr25，lp41，mod010，其計算性能是非常差的，因而沒有在表中列出算法A的執(zhí)行時間.究其原因，迭代次數(shù)較多導致基矩陣求逆和基交換的計算量增加，而更重要的是算法A在每次迭代中對4個指標集的調整需要耗費大量時間，使得定價計算量的減少“得不償失”.為此，對算法A作了進一步改進.

2 進一步改進

算法B

步驟7)置J=J1，如果J為空集，轉步驟8)；否則，轉步驟10)．

步驟8)置J=J2，如果J為空集，轉步驟9)；否則，轉步驟10)．

步驟13)按照推論1的條件1)調整指標集J1、J2、J3和J4，返回步驟7)．

用MATLAB V7.1語言對算法B也進行了編程，并在Lenovo ThinkCenter M9201z計算機上求解表1中27個算例的第一階段問題(計算結果見表1).

從表1可見，改進的算法B雖然比算法A大幅增加了定價所搜尋的非基列數(shù)，但卻減少了迭代的次數(shù)，即與經(jīng)典單純形算法所用的總迭代次數(shù)之比為0.97，且在23個算例上比經(jīng)典單純形算法所用的迭代次數(shù)要少或相同.由于在所有算例上都比經(jīng)典單純形算法所搜尋的非基列數(shù)要少，因而其計算時間也比經(jīng)典單純形算法耗費得少，其計算性能高效而穩(wěn)定.

3 結論

單純形算法的計算工作量主要取決于迭代的次數(shù)和所搜尋的非基列數(shù)，部分定價策略就是在每次迭代中設法減少對非基變量的定價.本算法把所有非基變量按照它們成為最優(yōu)解中的非基變量的確定性程度分成四段，然后按可能性從小到大的順序選擇一段非基變量進行定價，且每次迭代還要根據(jù)分段準則對四段非基變量實施動態(tài)調整.隨著迭代進程趨于最優(yōu)解，不需要定價的非基變量數(shù)越來越多，因而所提出的分段定價策略可大大節(jié)省對非基變量定價的計算工作量.

分段調整的過程也需要耗費計算時間，如果調整計算太復雜，調整時機不合適，就會造成“得不償失”的結果，算法A就驗證了這一點.有時“簡單的就是最好的”，大量數(shù)值試驗已經(jīng)驗證了經(jīng)典單純形算法的高效性,為此算法B改進了算法A的缺陷.考慮到單純形算法在目標值接近最優(yōu)值時迭代非常緩慢，此時大部分非基變量都保持非基不變．于是，根據(jù)經(jīng)驗選擇了一個適當?shù)姆侄螘r機，同時摒棄復雜的調整準則.初步計算結果表明，這種改進是有效的，尤其對較大規(guī)模的問題，其計算優(yōu)越性體現(xiàn)得更加明顯.

[1] 李煒.求線性規(guī)劃初始可行基的新方法[J].運籌與管理,2004,13(1):7-10.

[2] 高培旺.關于求線性規(guī)劃初始正則解的一個新方法的注記[J].徐州工程學院學報(自然科學版),2012,27(2):1-4.

[3] MAROS I.A general pricing scheme for the simplex method[J].Annals of Operations Research,2003,124(1):193-203.

[4] PAN P Q,LI W,CAO J.Partial pricing rule simplex method with deficient basis[J].Numerical Mathematics:A Journal of Chinese Universities,2006,15(1):23-30.

[5] PAN P Q.Efficient nested pricing in the simplex algorithm[J].Operations Research Letters,2008,36(3):309-313.

[6] 束金龍,聞人凱.線性規(guī)劃理論與模型應用[M].北京:科學出版社,2013.

[7] FORRESTJ J H,GOLDFARB D.Steepest-edge simplex algorithm for linear programming[J].Mathematical Programming,1992,57(3):341-374.

[8] CURET N D.A primal-dual simplex method for linear programs[J].Operations Research Letters,1993,13(4):233-237.

[9] CHEN H D,PARDALOS P M,SAUNDERS M A.The simplex algorithm with a new primal and dual pivot rule[J].Operations Research Letters,1994,16(3):121-127.

[10] CHENG M C.New criteria for the simplex algorithm[J].Mathematical Programming,1980,19(2):230-236.

[11] DONGARRA J,GOLUB G,GROSSEE,et al.Netlib and NA-Net:building a scientific computing community[J].IEEE Annals of the history of computing,2008,30(2):30-41.

[12] BIXBY R E,CERIA S,MCZEAL C M,et al.An updated mixed integer programming library:MIPLIB 3.0[J].Optima,1998,54(1):12-15.

(編輯 徐永銘)

A Sectional Pricing Strategy for the Phase-1 Simplex Method

GAO Peiwang

(Minjiang University, Fuzhou 350121, China)

The paper presents a sectional pricing strategy for the phase-1 simplex algorithm.Based on this,two variants are derived.Firstly,all nonbasic variables are partitioned into four sections,one of which includes the nonbasic variables in an optimal solution.In the iterative process,pricing is implemented alternatively in turns in other three sections according to the possibility of those variables remaining nonbasis.Variant 1 uses Cheng's two criteria to change the composition of components in four sections at the outset of the iteration.So it greatly decreases the amount of pricing computation,but spends much more time than the classical simplex algorithm.Variant 2 starts section when the objective value arrives at two third of the optimum value,and changes sections by only one of Cheng's criteria.A preliminary test is accomplished on a set of 27 standard instances from NETLIB and MIPLIB.The computational results show that variant 2 uses fewer iterations in total, probes fewer columns,and spend much less computational time than the classical simplex algorithm.Therefore, variant 2 is of the interest in computational performance.

linear programming; simplex method; pricing rule; sectional pricing; computational efficiency

2016-06-02

閩江學院人才引進基金資助課題(MJU2012001)；廣西自然科學基金項目(0728260)；國家星火計劃項目(2013GA690426)

高培旺(1964-)，男，教授，博士，碩士生導師，主要從事最優(yōu)化理論及其應用研究.

O221.1

A

1674-358X(2016)04-0021-06