求解線性雙層規(guī)劃的割平面算法

1、求解線性雙層規(guī)劃的割平面算法趙茂先”，高自友 - . - .摘 要:利用線性雙層規(guī)劃的全局最優(yōu)解可在愚勺束域的極點上達到這一性質(zhì)，通過對問題可行解 集合的結(jié)構(gòu)進行探討，引進一種割平面技術(shù)，提出了一個求解線性雙層規(guī)劃的全局收斂算法，并通 過一個算例說明了算法的求解過程.中圖分類號0221.1文獻標(biāo)識碼:AA Cutting Plane Algorithm for Solving Linear Bilevel ProgramsZHAO Mao-xian1 *3 , GAO Zi-you1(1. School of Traffic and Tranq)ort, Beijing Jiaotong Un

2、iversity, Beijing 100044 ,China,2. Department of 可 phed Mathematics, Shandong University of Science and Technology, Tai an 271019 , China)Abstract Based on the result that a global optimal solution to linear bilevel programming occurs at an extreme point of its constraint region , we discuss the stm

3、ctural feature of its feasible region and pro2 pose a global convergent algorithm vzhich make use of cutting plane technique Finally , a simple exam2 pie is given to illustrate the application of the algorithm.Key words :linear bilevel program, global optimal solution, extreme point, cutting plane收稿

4、日期:2004211217基金項目國冢自然科學(xué)基金資助項目(704710S8)，國冢杰出青年科學(xué)基金資助項目(70225005);北京市自然科學(xué)基金資助項目(9042006)作者簡介：檔茂先(1966 -4 .果.汀芥汀都人.山茶科技大學(xué)副教梧.博十牛.email:nothin任xl伽63 . com在許多系統(tǒng)優(yōu)化問題中，如生產(chǎn)計劃，資源分 配，政府調(diào)節(jié)和工程設(shè)計等大規(guī)模實際問題中，系緯 可能涉及到不止一個決策者，并且不同的決策者具 有各自的目標(biāo)函數(shù).傳統(tǒng)的單層數(shù)學(xué)規(guī)劃技術(shù)已經(jīng) 不能很好的解決這類問題，多層規(guī)劃正是為了研究 系統(tǒng)層次性而產(chǎn)生的，并正逐漸形成一個新的運多 學(xué)分支1 .多層規(guī)劃中最

5、簡單的形式是雙層規(guī)劃，主要是 分析兩個各具LI標(biāo)函數(shù)的決策者之間按非合作和有 序的方式進行的相互作用.上層首先給下層一定的 信息，下層基于這些信息依照自己的利益做出反應(yīng) 上層再根據(jù)下層的反應(yīng)做出符合全局利益的決策 一方的行為影響另一方的策略選擇和目標(biāo)的實現(xiàn) /n /-r -A- T7 人 S 5 口 + AJ g +V，二 3- Ah題的LI標(biāo)函數(shù)和約束條件都是線性的，但一般情況 下，它也是一個非凸優(yōu)化問題，并且已經(jīng)證明線性雙 層規(guī)劃是NP-Hard問題.到目前為止，人們已經(jīng)提出了一些求解線性雙 層規(guī)劃的算法，但比較成功的求解全局最優(yōu)解的算 法還很少.Candler和Tovznsley5提出了

6、第一個全 局收斂算法，該算法反復(fù)求解兩個線性規(guī)劃,可得到 待檢查問題約束域上極點的單減序列.Bialas和 Karwan6對約束域的極點進行搜索,提出了所謂的 “ K次最好算法,并證明算法收斂于問題的全局最優(yōu) 解Bard和Falk7利用下層問題的K-T條件，將問 題轉(zhuǎn)化為一個標(biāo)準(zhǔn)的數(shù)學(xué)規(guī)劃問題，為了繞開約束 條件中的互補松弛項，用分枝定界技術(shù)等價求解一 系列容易的問題而Bard和Moore8提出隱式滿 dalingam9利用罰函數(shù)思想，在上層目標(biāo)函數(shù)中舔 加下層問題的對偶間隙，將原問題分解成一系列線 性規(guī)劃去求解，從而獲得全局最優(yōu)解除以上兒類算 法外，一些研究者還提出了互補旋轉(zhuǎn)算法，消元算法

7、和利用反凸約束技術(shù)的優(yōu)化方法等.本文作者針對線性雙層規(guī)劃的全局最優(yōu)解可在 其約束域極點上找到這一特性，對問題可行解集合 的結(jié)構(gòu)進行探討，充分利用其結(jié)構(gòu)特征，引進割平而 技術(shù)在約束域的極點上進行搜索，給出了一個求解 線性雙層規(guī)劃的全局收斂算法提出的算法不但避 免了文獻6中使用的計算量和存儲量較大的極點 桃京注 而日有明了女獻父 由令古澎界注汁曾昌十 1模型與定義設(shè)上層決策向量x gel下層決策向量y Gm.LO-T7n = -H71 Jill 、 6/1 IT/rZ=l_(Pi) rmnF(x, y) = cf x + dfy.XSt. Xg,其中y的解為(P2)mjnf(X,y)=dJy.s.

8、 t. Ax + By d2 G Em,t eEp, A UEPfB GEPg 稱(Pi)和(P?)分別為 LE P的上層問題和下層問題.記LBP的約束域為S = ( (x , y) : Ax + By 0 , y 0), S在上層決策空間上的投影為T = x:(x,y) WS. 對每個固定的x GT,稱S(x) =y:(x,y)S)為 下厚間顧的可行御.俗合定義 1 稱 P(x)=y：y Eargmin ( f ( x , y) : y WS(x)為下層問題的合理反應(yīng)集，D = ( x , y) es : y EP (x)為LBP的可行解集合或誘導(dǎo)域.定義2如果存在(x3 ,y3) &D,對

9、任意的(x, y) CD 滿足 F(x3 , y3) F ( x , y)，則稱(x，, y3) 是LBP的全局最優(yōu)解，簡稱全局解或最優(yōu)解.合理反映集p ( x)定義了下層決策者對上層決 策的反應(yīng)，而誘導(dǎo)域D給出了上層決策者可以優(yōu)化 的空間由于LB P的上下層的約束都是線性約束，所 以約束域S是坦上的一個多面體一為保證LB P牧假設(shè)2 Hx et.T層問題在S(x)上有唯一 的昴優(yōu)解假設(shè)1要求LBP的約束域S是上的一個 非空緊集，即S是一個多胞形，從而LBP-定有全 局解；假設(shè)2確保LBP在誘導(dǎo)域D上能得到確定 的全局解.在這兩個基本假設(shè)條件下，下面給出 LBP的一些基本結(jié)論，具體證明見文獻1

10、.引理1 LBP的誘導(dǎo)域D等價于S的支撐超 平面構(gòu)成的分段線性等式束集合.引理2 D是閉連通的，且D的極點就是S牧 極點.引理3 LBP定有全局解，且可在S的極點2理論與算法當(dāng)卜層給京某個x WT后,下層的最佳反應(yīng)的 線性規(guī)劃問題為(P9 nunf(X,y) = dJy.s. t. By 冬 Ax , y X).問題(Px)的對偶問題為(D x) maxz ( u , x) = u (Ax - b).uS t. - uB du X).其中，u GEp.記U = ( u : - uB dT2 , u X),tjE表示u的極點組成的集合.設(shè)GS)是問題 LBP的一個可行解，即對給定的x GTJ是問

11、題 (以的最優(yōu)解.將W代入問題(D。，由線性規(guī)劃對 偶理論，問題(DQ一定有最優(yōu)解,且可在UE中找 削浴二U“E旦/ z的一舄件組S(日=(x,y) e s : d? y - uAx += Q),由定義1和線性規(guī)劃對偶理論得如下結(jié)論.定理1在假設(shè)1和假設(shè)2條件下，S ( u)是非 空緊凸集，且S(u)是S的一個界面;(11) S(頁D證明(1)因為(WS) CD v s ,且滿足djy - uAx + ub = 0,所以GS) 6 ，即S非空.又因為S是 由非空緊凸集S和線性緊約束d?y - uAx + ub =0 的交構(gòu)成，所以S(Q是非空緊集.下證S(Q是S 的一個界面,即要證S (密是S

12、的弱擬凸子集.任取(X、v1)或x2 . v2) WS .0 Au( Ax 1- b) , dJy2 u ( Ax 2- b) (2) 由于0 1 1,根據(jù)式(1)和式立得djy1 - uAx1 + ub = d?y2 - uAx2 + ub = 0 所以 (x】，)，(#,) GS(U),即證得S(u)是S的弱擬凸子集，從而S(u)是S 的一個面.證明(ii)任取(x ,y) 6，由S(u)定義得 (x, y) GS , d?y = u ( Ax - b).假設(shè)(x, y) | D ,由 定義1 ,存在9滿足(私9)W D ,& - A2,且djy d?y.因為-uB 0, 所以d?y =

13、u ( Ax - b) u (- By) = - ( uB) g d2 磯 矛盾.從而(x, y) WD ,即證得S ( u) V D.根據(jù)定理1的結(jié)果和證明過程,顯然下列推論 成立.推論1 S (仍的極點也是S的極點.定理1和推論1對LBP的任意一個可行解都 成立.如果(W,/)是S的一個極點，且(W，7)WD, 上述結(jié)論也成立，即至少存在一個從極點(元歹)引 出的S的一個面S，滿足S是LBP誘導(dǎo)域 D的一個子集.如果對(W) GD,問題(D?的最優(yōu) 解不唯一，即在XJE中有多個(DQ的最優(yōu)解，則從 極點任，分引出的的面就不唯一由于線性規(guī)劃的 最優(yōu)極點只有有限個，所以在不唯一情況下，從極點

14、GS)引出的面只能有有限個,且最多不超過n +定理2設(shè)任,亍)是約束域S的一個極點， S(xJ)是從(妃是引出的任意一個S的面，若是, y) | D,則 n(x, y)與nt(S(x,y),有(x,y) | D.證明 假設(shè)(x,y) WD,由定理1,存在u eUE 和 S(7) , S(7)是 S 的一個面，且(x,y) es() V D 一因為S是一個多胞形，且(x , y) Gnt ( S ( x , y), 所以在S中通過(x,y)的面只有一個，從而S(x,T Uut% D. T Hff 9 , If1J . IS(xJ),所以CD,這與條件矛盾，從而定理 2得證.總結(jié)以上結(jié)論，對任意一

15、個S上的極點丘萬)， 有且僅有以下3種情形之一成立：從極點(W7)引出的任意一個S的面都是 LBP誘導(dǎo)域D的一個子集，此時任萬)ED;，：；、II 燈4 占，= PI 山 l tVi757rh *一旦D的一個子集,另一部分的任意一個面上的任意內(nèi) 點都不是LBP的可行點，此時也有(x, y)D;(ill)從極點(W&)引出的任意一個面上的任意 內(nèi)點都不是LBP的可行點，此時(W，n I D.wll 1T7 ”S. t. X 3), 其中y的解為 rmnf = y. s t. - x - 2yyn+m)線性無關(guān)，因此 Q-1 存在，并且由等式 eQ-(x,y) - (x,y) =1 決定的超平面將

16、通過每一個(x,y)相鄰的極點 (x1, y1) , ( X3, y2) , , ( xn + m, yn+m)_ 稱上述超平 面為極點(x , y)對應(yīng)的割平面，相應(yīng)的割為eQ】(x , y) - (x, y) 1.記 S1 = (x , y) 6 : eQ - (x , y) - (x, y)引， S=(x, y) WS ： eQ -】(x, y) - (x, y) 1), 其中,e = (l,l, ,1)為一個n+ m維行向量，置k =k + 1,轉(zhuǎn) Step 1.3算例用上述給出的算法對例1進行求解.，, j I riii 1 I . 1 r-jI . I . . 函數(shù)F = - y進

17、行極小化，解相應(yīng)的線性規(guī)劃問題 得最優(yōu)極點F (6,14),即有(x , y) = (6,14).然后 執(zhí)行算法第2步，得(x,y) | D.根據(jù)算法第3步,求得極點求出并求得F的相鄰極點為E(10,13)和G(0,10).4 - 6|q = Li .L1 2/11 . 3/ 1 iQ =，L - 1/22 - 2/ 111構(gòu)造極點F對應(yīng)的割平面約束為3x + 10y包00.余下的約束域S1為A、B、C、D、E和G構(gòu)成的多 胞形，見圖2所示.Fig 2 Constraint region S1在求得新的束域S】后，在S1上對上層目標(biāo)函數(shù)F=y進行極小化，得最優(yōu)極點E(10,13), (x】，y

18、】)| D,繼續(xù)構(gòu)造第2個割平面約束一因為在 S】中極點E的相鄰極點為點D (14,8)和G(0,10)，從而對應(yīng)的方陣410Q-53-3/ 62 5/ 31并求得 Q- = 5/ 62-2/ 3U構(gòu)造極點E對應(yīng)的割平面約束為x + 7y寸0.經(jīng)第 2次割操作后,余下的約束域S?為A、B、C、D和G 組成的多胞形，見圖3所示.在求得的S?上對上層目標(biāo)函數(shù)F = - y進行 極小化，得最優(yōu)極點為G(O.IO),即有(x)= (0,10).經(jīng)檢驗(X3 , y3) | D,繼續(xù)進行第3次割操 作,得極點G對應(yīng)的割平面約束為3x + 14yW 70 .余下的約束域S為極點A、B、C和D構(gòu)成St 多胞

19、形，見圖4所示.在S上繼續(xù)對F = - y進行 極小化，得最優(yōu)極點D(14,8),即W ( x3, y3) = (14, 8),且經(jīng)算法第2步后有(x3, y3) WD,所W ( x3 , y3) = (14.8)是例1的最優(yōu)解.圖3約束域S2Fig 3 Constraint region S2圖4約束域SFig 4 Constraint region S34結(jié)語本文誦對對線忤雙孱規(guī)劃諉導(dǎo)域結(jié)構(gòu)和約束域 極點有關(guān)特征的研究，利用線性雙層規(guī)劃的全局解 可以在其約束域極點上達到這一性質(zhì)，引進割平百 技術(shù)，給出了一種求解方法.所提方法的主要計算集 中在求解線性規(guī)劃問題上，由于用計算機求解較大 規(guī)模的

20、線性規(guī)劃程序已經(jīng)成熟，所以該方法具有廣 泛的實際意義.算例結(jié)果進一步表明了方法的可行 性和有效性.所給方法的另一計算是在每次割操作 前，要計算出當(dāng)前極點對應(yīng)的所有相鄰極點，這方而 的求解技術(shù)也較成熟.但要求線性雙層規(guī)劃的約束 域s是非退化的，這樣保證每次迭代都能割掉當(dāng)前 約束域的一部分.如果約束域s是退化的,就可能 就不能保證所提方法能繼續(xù)迭代下去.對退化情況， 應(yīng)進行適當(dāng)?shù)奶幚?，這應(yīng)是進一步所做的工作.參考文獻：Bard J F. Practical Bilevel Qjtiimzation: Algonthms and ApplicationsM Boston: Kluwer Academ

21、ic Publishers, 1998.J eroslow R G Tlie Fblyiio nual Hierarchy and A Model for Co npetitive Analysis J . Mat hematical Pro 2 gramimng , 1985 , 32 :146 - 164.Ben-Ayed O, Blar C E. Computational Difficulties of Bilevel Linear Programming J . O perations Research 1990,38:556 560.Bard J F So me Propertie

22、s of the Bilevel Programnunj p roblemJ . Journal of O p tiimzatio n Theory and &)phcal tions,1991 ,68 :371 - 378.Candler W, Townsely R. A Linear Two-Level Program? nnng Problem J . Cbm puters axid Operations Reseaech, 1982, 9:59 - 76.Bialas W F, Karwan M H. Two-Level Linear Program? ixnngJ . Mana ge

23、ment Saence, 1984 , 30 1004 - 1020.Bard J F, Falk J E An Explicit Solution to the Multi-Lev2 el Programming Problem J . Com puters and Operations Research, 1982 , 9 77 - 100.Bard J F, Moore J T. A Branch and Bound Algontlim for the Bilevel Programming Problem J . SIAM Journal of Scientific and Statistical Con