金照林 胡鐵松

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

（武漢大學(xué)水資源與水電工程科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室2） 武漢 430072）

0 引 言

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

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

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

1 相關(guān)理論

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

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

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

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

定義2 S中的點(diǎn)（x，y）稱為問(wèn)題（1）的可行點(diǎn)，若對(duì)于這個(gè)x，y恰好是下層問(wèn)題的解．一切可行點(diǎn)的集合記作S1，S1稱為問(wèn)題（1）的一層可行集，S稱為二層可行集．

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

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

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

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

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

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

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

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

2.1 算法的思想

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

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

使用“由上至下”的方法，計(jì)算過(guò)程分為兩個(gè)階段：

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

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

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

令Q＝（x1－x0，x2－x0，…，xn－x0）為一個(gè)n階方陣，e＝（1，1，…，1）為一個(gè)n階行向量．由線性規(guī)劃基本理論知向量組Q線性無(wú)關(guān)，因此Q－1存在，并且由等式eQ－1（x－x0）＝1決定的超平面將通過(guò)每一個(gè)x0相鄰的極點(diǎn)x1，x2，…，xn，稱上述超平面為極點(diǎn)x0對(duì)應(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說(shuō)明由極點(diǎn)x0對(duì)應(yīng)的割平面在切割多面體的一部分ˉS后，余下的S＊是S的一個(gè)非空子集．且為非退化的多面體．

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

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

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

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

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

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

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

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

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

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

2.2 算法示例

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

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

求解過(guò)程為：

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

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

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

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

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

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

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

步驟2 增加割平面約束，逐步極點(diǎn)搜索．

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

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

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

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

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

［3］周水生，劉三陽(yáng)，劉紅英．價(jià)格控制問(wèn)題及其推廣形式的罰函數(shù)法［J］．系統(tǒng)工程學(xué)報(bào)，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é)報(bào)：交通科學(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é)報(bào)，2005，29（3）：65－67．

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