求解價格控制問題的旋轉(zhuǎn)算法＊

金照林 胡鐵松

（武漢長江工商學(xué)院1） 武漢 430065）

（武漢大學(xué)水資源與水電工程科學(xué)國家重點實驗室2） 武漢 430072）

0 引 言

對于價格控制問題，滕春賢等［1］研究了價格控制問題解集的基本性質(zhì)以及連通性．阮國楨等［2］在理論分析的基礎(chǔ)上提出了求解價格控制問題的單純形算法．周水生等［3］利用下層問題對偶間隙為零的原理提出了價格控制問題的罰函數(shù)方法．

文中在旋轉(zhuǎn)算法的基礎(chǔ)上，對其進行了改進，發(fā)揮了該算法原理簡潔、實際計算效率高且容易學(xué)習(xí)理解的優(yōu)點，用于求解價格控制問題．如稍加變通，該方法還可用來求解其他主從遞階決策問題，例如線性二層或多層規(guī)劃問題等，顯示了該算法在求解此類問題上的優(yōu)勢．

本文采用“由上至下”的方式，根據(jù)算法的特點，可以便利地構(gòu)造割平面約束，使用算例證實了該方法的有效性．

1 相關(guān)理論

價格控制問題假定上層決策者控制價格變量x，以優(yōu)化其收益函數(shù)aTx＋bTy．式中：y為n種產(chǎn)品的產(chǎn)量，下層決策者在上層決策者宣布價格策略以后，通過調(diào)整其產(chǎn)量y，以優(yōu)化其收益目標xTy．由上所述，價格控制問題的一般數(shù)學(xué)模型為

式中：x＝（x1，x2，…，xn）T為上層控制的決策變量；y＝（y，y，…，y）T為下層控制的決策變量；

12n上、下層的目標函數(shù)分別為f1（x，y），f2（x，y），a∈Rn，b∈Rn；A為m×n階矩陣；B為m×n階矩陣．

定義1 對于問題（1），集合S＝｛（x，y）｜Ax＋By≤r｝稱為它的容許集．S顯然是閉凸集，這里假設(shè)S是有界的．

定義2 S中的點（x，y）稱為問題（1）的可行點，若對于這個x，y恰好是下層問題的解．一切可行點的集合記作S1，S1稱為問題（1）的一層可行集，S稱為二層可行集．

由于容許集S為多面凸集，但可行集S1一般不是凸集，因此價格控制問題（1）一般是非凸規(guī)劃問題．下層問題的目標函數(shù)xTy為線性函數(shù)，但由于系數(shù)向量x是不斷變化的，這表明價格控制（式（1））也可以被歸為非線性二層規(guī)劃問題．

文獻［1］闡述了有關(guān)價格控制解的最優(yōu)性條件，本文直接引用了原作者的論述．

定理1 S中的點（x，y）為可行點（即（x，y）∈S1）的充要條件是：存在ω≥0，ω∈Rm，使得ωTB＝xT，ωT（Ax＋By－r）＝0．

推論1 S中的點（x，y）為可行點的充要條件是：存在ω≥0，（ω∈Rm），使得ωTB≥xT，ωT（Ax＋By－r）＝0．

推論2 （x＊，y＊）是式（1）的最優(yōu)解的充要條件是，存在ω≥0，（ω∈Rm），使得（x＊，y＊，ω＊）為下述式（2）的最優(yōu)解

推論2說明式（1）與式（2）是等價的，其中約束條件（3）與ω≥0稱為互補不等式，約束條件（5）為互補松弛條件．

2 使用旋轉(zhuǎn)算法求解價格控制問題

對價格控制問題以及線性二層規(guī)劃問題的求解，呂一兵提出了基于罰函數(shù)的修正Frank－Wolf方法［5］，但該算法通常僅能得到問題的局部最優(yōu)解．本文在張忠楨先生提出的旋轉(zhuǎn)算法的基礎(chǔ)上［6］，對其進行了改進，并應(yīng)用于解決線性主從遞階問題，顯示了其相比于以往傳統(tǒng)方法的優(yōu)勢．

2.1 算法的思想

使用旋轉(zhuǎn)算法求解價格控制問題大體有兩種思路，一是“由上至下”的方法，即先不考慮互補松弛條件而直接求得式（2）（典型的線性規(guī)劃問題）的最優(yōu)值，然后再“由上至下”逐頂點檢查是否滿足互補松弛條件，該方法毫無疑問可以找到問題的全局最優(yōu)解，但在求解大型問題時可能會導(dǎo)致計算量和存儲量較大．第二種思路是“由下至上”的方法，即從某一個初始點出發(fā)，在滿足所有約束條件的基礎(chǔ)上目標函數(shù)向更優(yōu)的方向迭代，例如罰函數(shù)法，該思路計算量較小，但容易最后獲得的解為局部最優(yōu)．

使用旋轉(zhuǎn)算法求解價格控制問題時，以上兩種思路都是可行的．對于“由下至上”的方法，由于要維持互補條件，因此在旋轉(zhuǎn)運算樞軸元素只能在運算表的主對角線上的元素中選擇，而當主對角線上的元素為0時，則使用雙樞軸旋轉(zhuǎn)運算同樣可以維持互補松弛條件．限于篇幅的原因，本文僅介紹第一種方法即“由上至下”的方法．

使用“由上至下”的方法，計算過程分為兩個階段：

第一階段：先不考慮互補松弛條件（5），此時原問題是一個典型的線性規(guī)劃，使用旋轉(zhuǎn)算法可以很容易找到其最優(yōu)解．第二階段：逐極點測試是否符合互補條件，一旦找到即為問題的全局最優(yōu)解．

如何實現(xiàn)從上至下逐極點測試，文獻［7］提出的極點排序法和文獻［8］中的分支定界法存在的問題是計算量和存儲量較大，而趙貿(mào)先［9］提出使用相鄰的極點來構(gòu)造割平面的想法可以有效解決這一問題．

設(shè)多面體S＝｛x∈Rn｜Ax≤b｝（其中A＝（aij）∈Rm×n，b＝（b1，b2，…，bm）T∈Rm，m≥n），如S 是非退化的，x0是S的一個極點，則x0在S中有n個相鄰的極點，記為（x1，x2，…，xn）．

令Q＝（x1－x0，x2－x0，…，xn－x0）為一個n階方陣，e＝（1，1，…，1）為一個n階行向量．由線性規(guī)劃基本理論知向量組Q線性無關(guān)，因此Q－1存在，并且由等式eQ－1（x－x0）＝1決定的超平面將通過每一個x0相鄰的極點x1，x2，…，xn，稱上述超平面為極點x0對應(yīng)的割平面，相應(yīng)的割為eQ－1（x－x0）≥1．

記S＊＝｛x∈S：eQ－1（x－x0）≥1｝，ˉS＝｛x∈S：eQ－1（x－x0）＜1｝．下述定理2說明由極點x0對應(yīng)的割平面在切割多面體的一部分ˉS后，余下的S＊是S的一個非空子集．且為非退化的多面體．

定理2 設(shè)多面體S是非退化的，則S＊是非退化的，則S＊∪ˉS＝S，S＊∩ˉS＝?．

根據(jù)以上結(jié)論，首先用旋轉(zhuǎn)算法在第一階段不考慮互補松弛條件，求出式（1）的最優(yōu)解（x0，y0）為S上的一極點后，然后判斷是否滿足互補條件，如果滿足則問題已獲得全局最優(yōu)解；否則根據(jù)定理5，引進極點（x0，y0）對應(yīng)的一個割平面，使得S中被割去的部分S不含該價格控制問題的任何一個可行解，且保證余下的部分S＊也是一個非退化的多面體．重復(fù)上述過程．因為每進行一次割操作都將割去原約束域上的一個極點，而這種割操作不會增加約束域上的極點，并且S的極點有有限個，所以經(jīng)過有限步后一定能找到S上的一個極點為該價格控制問題的全局解．

以上方法在構(gòu)造割平面時需要使用矩陣求逆運算，而使用旋轉(zhuǎn)算法在表上運算時更為簡便，方法見表1．

表1 約束e為相鄰極點構(gòu)造的割平面

在表1中，如果ωrs＊和ωij＊為可行的樞軸元素，實際為以當前已入基的約束as和aj決定的極點的2個相鄰極點所對應(yīng)的基，最下行約束d為當前極點的相鄰極點組成的割平面．

利用上述思想，現(xiàn)將求解價格控制問題的算法步驟描述如下．

步驟0 令S0＝S，置k＝0，轉(zhuǎn)步驟1．

步驟2 對給定的xk，判斷是否滿足互補松弛條件，如滿足，則停止，（xk，yk）為價格控制問題的全局解；否則，轉(zhuǎn)步驟3．

步驟3 用旋轉(zhuǎn)算法找到點（xk，yk）在Sk中的所有相鄰極點，并按照表2的方法構(gòu)造相對應(yīng)的割平面約束d，轉(zhuǎn)步驟4．

步驟4 令Sk＋1＝｛（x，y）∈Sk∩d｝，轉(zhuǎn)步驟1．

2.2 算法示例

相關(guān)文獻在驗證其理論與算法的時候大都使用如下實例．在運算開始前，先將各約束條件編號為a1～a3，對于基本的可分離變量的約束條件編號為e11～e22．

為便于理解，在以下旋轉(zhuǎn)運算表中，單元格為灰色底紋表示該元素作為樞軸迭代后得到的解（x，y）∈S，單元格有邊框表示最終選定該元素為樞軸進行下次迭代．

求解過程為：

步驟0 形成上下層初始運算表．由式（2）在忽略互補松弛條件后，可得如下初始表2，其中標記h1，h2，u1，u2 ，u3分別為e21，e22，a1，a2，a3對應(yīng)的互補不等式．

表2 初始旋轉(zhuǎn)運算表

在運算表中，C表示上層問題的約束條件系數(shù)．當初始值對應(yīng)的目標函數(shù)值為0時，在偏差列DEV中，C行中的元素實際為上層問題的目標函數(shù)值．

從上表可以看出，由于約束條件a3偏差小于0，因此該不等式為違反不等式，需要進行迭代使其進入容許集S，由表1可知，欲使同行偏差非負，可以選?。╡22，a3）為下次迭代的樞軸元素．

步驟1 進入約束域后，暫不考慮互補條件，使用旋轉(zhuǎn)算法求解線性規(guī)劃問題．

由于上步旋轉(zhuǎn)運算后中所有偏差非負，說明迭代已進入容許集，為求得線性規(guī)劃問題最優(yōu)值，需要將C行所有的約束條件系數(shù)變?yōu)榉秦摂?shù)，因此可以依次以（a2，a3）、（h2，x2）、（a3，u1）和（a1，e22）為樞軸元素，得到表3．

表3 旋轉(zhuǎn)運算表（求線性規(guī)劃問題最優(yōu)值）

步驟2 增加割平面約束，逐步極點搜索．

由表3可見，由于約束條件h1和e21必須有一個入基，因此該極點不符合互補條件．可構(gòu)造切割面e1，并使用旋轉(zhuǎn)算法求解新的線性規(guī)劃問題的最優(yōu)解，得表4．

由表4可見，由于h1，e21和u1，a1均在基外，因此需要根據(jù)相鄰極點構(gòu)造新的割平面約束e2，列在表4的最末行中，并使用旋轉(zhuǎn)算法求解新的線性規(guī)劃問題的最優(yōu)解，得表5．

表4 旋轉(zhuǎn)運算表（求線性規(guī)劃問題最優(yōu)值）

表5 旋轉(zhuǎn)運算表（求線性規(guī)劃問題最優(yōu)值）

表5整理后，測試后發(fā)現(xiàn)已滿足所有互補條件，可刪除所有割平面約束，計算終止．

因此，該價格控制問題的全局最優(yōu)解為x1＝5／3，x2＝5／3，y1＝4／3，y2＝4／3，上下層目標函數(shù)值分別為F＊＝5，f＊＝40／9．以下是相關(guān)文獻的計算結(jié)果．

表6 算例結(jié)果對比

由表6可見，計算結(jié)果優(yōu)于文獻［2－3］，與文獻［10］相同，但計算過程更為簡便．注意到該解并不是容許集的極點，同時在x1＝5／3，x2＝5／3時，下層的反饋并不惟一，實際上該解為樂觀解．

3 結(jié)束語

使用旋轉(zhuǎn)算法來求解價格控制問題，并使用了更為簡便的增加割平面約束的方法計算全局最優(yōu)解．如將該算法稍加變通，還可以求解包括線性多層規(guī)劃以及一主多從（或有共享變量的）的二層規(guī)劃（將另文說明），顯示了該方法在解決主從遞階問題上的優(yōu)勢．

對于一多面體，當出現(xiàn)退化的基本可行解時，它必然位于多于n個（線性無關(guān)）超平面的交集上，此時相應(yīng)極點的相鄰極點的會出現(xiàn)多于n個的情況，而如何搜索出這所有的極點，本文采用的是遍歷的方式，即遍歷所有的基組合，而尋找出當前極點對應(yīng)的相鄰極點，這樣會使運算量大增，這需要對退化情況下凸規(guī)劃理論進行更深入地研究．

［1］滕春賢，李智慧，李 磊．價格控制問題解集的基本性質(zhì)和連通性［J］．系統(tǒng)工程理論與實踐，1997（2）：45－49．

［2］阮國楨，楊豐梅，汪壽陽．線性二級價格控制問題的單純形方法［J］．系統(tǒng)工程理論與實踐，1997，16（12）：38－43．

［3］周水生，劉三陽，劉紅英．價格控制問題及其推廣形式的罰函數(shù)法［J］．系統(tǒng)工程學(xué)報，1999，14（2）：156－159．

［4］LORIDAN P，MORGAN J．Weak via strong stackelberg problem：new results［J］．Journal of Global Optimization，1996（8）：263－287．

［5］呂一兵．一種求解線性二層規(guī)劃的修正Frank－Wolf方法［J］．武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，2005，29（6）：993－996．

［6］張忠楨．凸規(guī)劃－投資組合與網(wǎng)絡(luò)優(yōu)化的旋轉(zhuǎn)算法［M］．武漢：武漢大學(xué)出版社，2004．

［7］BIALAS W F．KARWAN M H．Two－level linear programming［J］．Management Science，1984（30）：1004－1020．

［8］BARD J F．MOORE J T．A branch and bound algorithm for the bilevel programming problem［J］．SIAM Journal of Scientific and Statistical Computing，1990，18：35－42．

［9］趙貿(mào)先，高自友．求解線性雙層規(guī)劃的割平面算法［J］．北京交通大學(xué)學(xué)報，2005，29（3）：65－67．

［10］劉志勇，滕春賢，陳東彥．關(guān)于二層價格控制決策問題的探討［J］．統(tǒng)計與決策，2007，248（20）：37－42．