金照林 胡鐵松
(武漢長江工商學(xué)院1) 武漢 430065)
(武漢大學(xué)水資源與水電工程科學(xué)國家重點實驗室2) 武漢 430072)
對于價格控制問題,滕春賢等[1]研究了價格控制問題解集的基本性質(zhì)以及連通性.阮國楨等[2]在理論分析的基礎(chǔ)上提出了求解價格控制問題的單純形算法.周水生等[3]利用下層問題對偶間隙為零的原理提出了價格控制問題的罰函數(shù)方法.
文中在旋轉(zhuǎn)算法的基礎(chǔ)上,對其進行了改進,發(fā)揮了該算法原理簡潔、實際計算效率高且容易學(xué)習(xí)理解的優(yōu)點,用于求解價格控制問題.如稍加變通,該方法還可用來求解其他主從遞階決策問題,例如線性二層或多層規(guī)劃問題等,顯示了該算法在求解此類問題上的優(yōu)勢.
本文采用“由上至下”的方式,根據(jù)算法的特點,可以便利地構(gòu)造割平面約束,使用算例證實了該方法的有效性.
價格控制問題假定上層決策者控制價格變量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)為互補松弛條件.
對價格控制問題以及線性二層規(guī)劃問題的求解,呂一兵提出了基于罰函數(shù)的修正Frank-Wolf方法[5],但該算法通常僅能得到問題的局部最優(yōu)解.本文在張忠楨先生提出的旋轉(zhuǎn)算法的基礎(chǔ)上[6],對其進行了改進,并應(yīng)用于解決線性主從遞階問題,顯示了其相比于以往傳統(tǒng)方法的優(yōu)勢.
使用旋轉(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.
相關(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時,下層的反饋并不惟一,實際上該解為樂觀解.
使用旋轉(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.