求解價格控制問題的旋轉算法＊

金照林 胡鐵松

（武漢長江工商學院1） 武漢 430065）

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

0 引 言

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

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

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

1 相關理論

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

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

12n上、下層的目標函數分別為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顯然是閉凸集，這里假設S是有界的．

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

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

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

定理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）的最優解的充要條件是，存在ω≥0，（ω∈Rm），使得（x＊，y＊，ω＊）為下述式（2）的最優解

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

2 使用旋轉算法求解價格控制問題

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

2.1 算法的思想

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

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

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

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

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

設多面體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階行向量．由線性規劃基本理論知向量組Q線性無關，因此Q－1存在，并且由等式eQ－1（x－x0）＝1決定的超平面將通過每一個x0相鄰的極點x1，x2，…，xn，稱上述超平面為極點x0對應的割平面，相應的割為eQ－1（x－x0）≥1．

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

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

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

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

表1 約束e為相鄰極點構造的割平面

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

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

步驟0 令S0＝S，置k＝0，轉步驟1．

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

步驟3 用旋轉算法找到點（xk，yk）在Sk中的所有相鄰極點，并按照表2的方法構造相對應的割平面約束d，轉步驟4．

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

2.2 算法示例

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

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

求解過程為：

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

表2 初始旋轉運算表

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

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

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

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

表3 旋轉運算表（求線性規劃問題最優值）

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

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

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

表4 旋轉運算表（求線性規劃問題最優值）

表5 旋轉運算表（求線性規劃問題最優值）

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

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

表6 算例結果對比

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

3 結束語

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

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

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

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

［3］周水生，劉三陽，劉紅英．價格控制問題及其推廣形式的罰函數法［J］．系統工程學報，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］呂一兵．一種求解線性二層規劃的修正Frank－Wolf方法［J］．武漢理工大學學報：交通科學與工程版，2005，29（6）：993－996．

［6］張忠楨．凸規劃－投資組合與網絡優化的旋轉算法［M］．武漢：武漢大學出版社，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］趙貿先，高自友．求解線性雙層規劃的割平面算法［J］．北京交通大學學報，2005，29（3）：65－67．

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