王　劍　胡鐵松　汪　琴

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

?

三步法求解下層最優(yōu)解不唯一的二層規(guī)劃

王劍胡鐵松汪琴

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

摘要：下層最優(yōu)解不唯一的二層規(guī)劃存在樂(lè)觀和悲觀情形，基于此提出樂(lè)觀和悲觀可行解的定義，并設(shè)計(jì)了求解樂(lè)觀和悲觀最優(yōu)解的三步法．而后分別用三步法和以往的兩步法求解了4個(gè)下層最優(yōu)解不唯一和1個(gè)下層最優(yōu)解唯一的算例，計(jì)算結(jié)果表明了三步法的有效性．

關(guān)鍵詞：二層規(guī)劃；樂(lè)觀最優(yōu)解；悲觀最優(yōu)解

二層規(guī)劃可行上層決策對(duì)應(yīng)的下層規(guī)劃問(wèn)題最優(yōu)解數(shù)目通常并非唯一，二層規(guī)劃的下層問(wèn)題具有唯一解是一類(lèi)特殊二層規(guī)劃問(wèn)題，只有當(dāng)對(duì)應(yīng)下層規(guī)劃為凸規(guī)劃且目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)時(shí)，其最優(yōu)解才唯一[1]．下層規(guī)劃最優(yōu)解不唯一的二層規(guī)劃的求解難點(diǎn)在于：對(duì)于一個(gè)可行的上層決策變量，其對(duì)應(yīng)下層最優(yōu)解的數(shù)目難以確定，目前尚缺乏一種解法可以求解出下層問(wèn)題的所有最優(yōu)解并將其反饋到上層規(guī)劃．因此，研究與探討下層最優(yōu)解不唯一的二層規(guī)劃問(wèn)題具有重要價(jià)值．

下層最優(yōu)解不唯一的二層規(guī)劃的最優(yōu)解尚無(wú)一個(gè)公認(rèn)的定義，Lucchetti R, Mignanego F等[2]提出了三個(gè)定義，其中第一條和第二條定義分別對(duì)應(yīng)Dempe[3]提到的樂(lè)觀和悲觀形式二層規(guī)劃的最優(yōu)解，也是較為通用的解定義，而第三條定義條件非常嚴(yán)苛，因而使用得極少．另外有一些學(xué)者，通過(guò)對(duì)原二層規(guī)劃問(wèn)題進(jìn)行處理，使得下層問(wèn)題最優(yōu)解唯一．Bialas和Karwan[4]提出在下層決策者配合上層決策者時(shí)，用f2+εf1來(lái)代替下層目標(biāo)函數(shù)f2，其中f1為上層目標(biāo)函數(shù)，ε為一個(gè)適當(dāng)小的正數(shù)；相應(yīng)地Ben-Ayed O[5]提出在下層決策者不配合上層決策者時(shí)，用f2-εf1來(lái)代替下層目標(biāo)函數(shù)f2．但兩者只是提出了一種思路，并沒(méi)有指出ε應(yīng)當(dāng)如何選取，并且即使在替換了下層目標(biāo)函數(shù)以后，也不能保證下層最優(yōu)解唯一．Dempe則提出了兩種正則化方法對(duì)原二層規(guī)劃進(jìn)行擾動(dòng)，第一種[6]是針對(duì)樂(lè)觀情形，在下層目標(biāo)函數(shù)為凸函數(shù)，且上層目標(biāo)函數(shù)正定的情況下，在下層目標(biāo)函數(shù)中添加αF，α為一個(gè)適當(dāng)小的正數(shù)，并用梯度法進(jìn)行求解；第二種[7]是在下層規(guī)劃為凸規(guī)劃時(shí)，在目標(biāo)函數(shù)中添加α‖x‖，并用聚束法進(jìn)行求解．相類(lèi)似地，P.Loridan和J.Morgan針對(duì)下層問(wèn)題嚴(yán)格擬凸與否，提出了兩種ε-正則法[8-9]，并討論了一定條件下解的存在問(wèn)題，也提出了幾個(gè)較為簡(jiǎn)單的算法．但不論是Dempe還是P.Loridan和J.Morgan提出的方法都存在兩個(gè)問(wèn)題：第一，對(duì)下層問(wèn)題有一定的要求，針對(duì)的是較為簡(jiǎn)單的二層規(guī)劃問(wèn)題，提出的方法難以解決一個(gè)一般的下層最優(yōu)解不唯一的二層規(guī)劃問(wèn)題；第二，改變了原二層規(guī)劃問(wèn)題，并不能保證最后求得的解滿(mǎn)足下層問(wèn)題的最優(yōu)性．

近年來(lái)有一類(lèi)解法，上下層都采用啟發(fā)式算法進(jìn)行求解，因?yàn)樵擃?lèi)算法使用了兩次啟發(fā)式算法，可以歸類(lèi)為兩步法，如基于遺傳算法的[10]，基于粒子群算法的[11]等．但用兩步法求解下層最優(yōu)解不唯一的二層規(guī)劃，下層規(guī)劃將隨機(jī)返回一個(gè)最優(yōu)解到上層，因而算法結(jié)果將不穩(wěn)定，無(wú)法保證求得樂(lè)觀最優(yōu)解或者悲觀最優(yōu)解．

本文從樂(lè)觀和悲觀二層規(guī)劃的定義出發(fā)，提出樂(lè)觀和悲觀可行解的定義，分析了這兩類(lèi)可行解的求解思路，而后設(shè)計(jì)了三步法求解下層最優(yōu)解不唯一的二層規(guī)劃的樂(lè)觀和悲觀最優(yōu)解．下文將按照如下順序展開(kāi)：第1部分描述二層規(guī)劃的相關(guān)數(shù)學(xué)定義及樂(lè)觀和悲觀最優(yōu)解，第2部分提出樂(lè)觀和悲觀可行解的定義和求解樂(lè)觀和悲觀最優(yōu)解的三步法，第3部分是算例及結(jié)果分析，第4部分是結(jié)論和未來(lái)工作．

1二層規(guī)劃的兩類(lèi)最優(yōu)解

考慮如下形式的二層規(guī)劃問(wèn)題(記為問(wèn)題1)：

(1)

其中x∈Rn1，y∈Rn2，F(xiàn)，f：Rn1×Rn2→R，G：Rn1×Rn2→Rm1，g：Rn1×Rn2→Rm2.

1)約束域：

上下層約束條件的交集稱(chēng)為約束域A，即：A={(x，y)|G(x，y)≤0，g(x，y)≤0}.

2)可行上層決策變量：

將滿(mǎn)足x∈A的上層決策變量x稱(chēng)為可行上層決策變量，所有的可行上層決策變量的集合用X表示，它表示約束域A在上層決策空間的投影，即：X={x|(x，y)∈A}.

3)反應(yīng)集：

當(dāng)二層規(guī)劃的可行上層決策變量x，對(duì)應(yīng)的下層問(wèn)題的最優(yōu)解并非唯一時(shí)，下層問(wèn)題返回的最優(yōu)解具有不確定性．此時(shí)，有兩種決策方式，相應(yīng)地有兩類(lèi)最優(yōu)解．

1.1樂(lè)觀最優(yōu)解

樂(lè)觀決策者認(rèn)為下層完全配合上層目標(biāo)，總是將對(duì)上層目標(biāo)最有利的最優(yōu)解返回給上層，這種情況下的二層規(guī)劃稱(chēng)為樂(lè)觀二層規(guī)劃，得到的最優(yōu)解即為樂(lè)觀最優(yōu)解．

樂(lè)觀二層規(guī)劃的數(shù)學(xué)表達(dá)[3]：

(2)

1.2悲觀最優(yōu)解

P.Loridan和J.Morgan[12]提出在下層決策者不配合上層決策者時(shí)，上層決策者為了使得風(fēng)險(xiǎn)最小，認(rèn)為下層決策者總是選擇最不利于上層的最優(yōu)解，這種情形下的二層規(guī)劃稱(chēng)為悲觀二層規(guī)劃，得到的最優(yōu)解即為悲觀最優(yōu)解．

悲觀二層規(guī)劃的數(shù)學(xué)表達(dá)[3]：

(4)

2三步法求解樂(lè)觀和悲觀最優(yōu)解

2.1等價(jià)約束

對(duì)于任意一個(gè)固定的上層決策變量x，如果下層問(wèn)題存在最優(yōu)解，那么下層問(wèn)題一定存在唯一的最優(yōu)值f*，顯然，對(duì)于任意一個(gè)x′∈X有：{y|f(x′，y)=f*}={y|y∈ψ(x′)}．

2.2樂(lè)觀可行解

根據(jù)樂(lè)觀二層規(guī)劃的定義，對(duì)于一個(gè)x′∈X，當(dāng)y是如下問(wèn)題o的最優(yōu)解時(shí)，這個(gè)y才會(huì)被樂(lè)觀上層決策者接受，從而(x′，y)才是樂(lè)觀二層規(guī)劃的一個(gè)可行解，稱(chēng)為樂(lè)觀可行解．

(7)

由于ψ(x′)數(shù)目無(wú)法確定，也無(wú)法全部求出，故用f(x′，y)=f*代替y∈ψ(x′)可以得到問(wèn)題o的等價(jià)問(wèn)題3：

(8)

2.3悲觀可行解

同理，根據(jù)悲觀二層規(guī)劃的定義，對(duì)于一個(gè)x′∈X，當(dāng)y是如下問(wèn)題p的最優(yōu)解時(shí)，(x′，y)是悲觀二層規(guī)劃的一個(gè)可行解，稱(chēng)為悲觀可行解．

(9)

與樂(lè)觀可行解求解類(lèi)似，可以得到問(wèn)題p的等價(jià)問(wèn)題4：

(10)

2.4樂(lè)觀&悲觀可行解求解

根據(jù)上文的分析，可以通過(guò)如下3個(gè)步驟求解樂(lè)觀和悲觀可行解：第1步，確定一個(gè)滿(mǎn)足x′∈X的x′；第2步，求解x′對(duì)應(yīng)下層規(guī)劃問(wèn)題2的最優(yōu)值f*；第3步，求解x′對(duì)應(yīng)的問(wèn)題3(4)，得到最優(yōu)解y，最終得到一個(gè)樂(lè)觀(悲觀)可行解(x′，y)．

2.5三步法求解樂(lè)觀&悲觀最優(yōu)解

上文給出了求解單個(gè)樂(lè)觀(悲觀)可行解的方法，如果使上層決策變量在X內(nèi)變化，并求解對(duì)應(yīng)的樂(lè)觀(悲觀)可行解，最后比較這些樂(lè)觀(悲觀)可行解的適應(yīng)度(上層目標(biāo)函數(shù)值)大小，適應(yīng)度最小的樂(lè)觀(悲觀)可行解就是原二層規(guī)劃問(wèn)題的樂(lè)觀(悲觀)最優(yōu)解，具體過(guò)程如圖1所示．

圖1　三步法運(yùn)行過(guò)程　　　　圖2　兩步法迭代過(guò)程

2.6三步法和兩步法對(duì)比

新方法是一個(gè)求解策略，并不針對(duì)某一種特定的算法，為了使得算法適用性更廣，可以采用啟發(fā)式算法和新方法結(jié)合．新方法總共使用了3次啟發(fā)式算法，故而命名為三步法．為了方便對(duì)比，將兩步法的流程列入圖2，可以看出三步法和兩步法差別就在于是否有問(wèn)題3(4)的求解，且兩步法在下層問(wèn)題完成求解后直接返回了下層最優(yōu)解Y*，三步法返回的是下層最優(yōu)值f*，再經(jīng)過(guò)問(wèn)題3(4)的求解返回Y*．

3算例及結(jié)果

為了驗(yàn)證新方法的有效性，下面分別用基于粒子群的兩步法和三步法對(duì)5個(gè)算例進(jìn)行求解．算例1，2，3節(jié)選自文獻(xiàn)，算例4，5為作者構(gòu)造算例；算例1，2，4，5下層最優(yōu)解不唯一，算例3下層最優(yōu)解唯一；算例4，5決策變量維數(shù)可變，計(jì)算時(shí)算例4包括1+2和2+3維，算例5包括2+2維和4+4維．為了方便對(duì)比，三步法和兩步法的問(wèn)題1和問(wèn)題2的的粒子數(shù)和迭代次數(shù)均相同．

算例1[3]：

圖3　算例1可行域　　　　圖4　算例1迭代過(guò)程

3種迭代都進(jìn)行了多次計(jì)算，樂(lè)觀和悲觀迭代過(guò)程不盡相同，但收斂結(jié)果一致，上圖只是選取了其中一次；兩步法的迭代過(guò)程不盡相同，迭代也不一樣，上圖也只是選取了其中一次(下文算例同)．樂(lè)觀過(guò)程收斂代數(shù)為51，收斂最優(yōu)解為(-1.62e-23，2.22e-24)，最優(yōu)值為0；悲觀過(guò)程收斂代數(shù)為176，收斂最優(yōu)解為(2.66e-04，1.003 11)，最優(yōu)值為1.000 091；兩步法收斂代數(shù)為146代，收斂最優(yōu)解為(4.02e-09，-1)，最優(yōu)值為1．三步法順利求解了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解，而兩步法也剛好求解出了悲觀最優(yōu)解，這是一個(gè)特例．

算例2[2]：

算例2反應(yīng)集為：ψ(x)={(y1，y2)|y1+y2=1，x+y1-y2≤1，0≤x≤2}，可行域如圖5所示，任意一個(gè)x對(duì)應(yīng)下層規(guī)劃有無(wú)窮多個(gè)最優(yōu)解．

樂(lè)觀最優(yōu)解為：(x*，y*)=(0，1)，對(duì)應(yīng)樂(lè)觀最優(yōu)值為1 000；悲觀最優(yōu)解為：(x*，y*)=(2，0)，對(duì)應(yīng)悲觀最優(yōu)值為200．三步法和兩步法的迭代過(guò)程如圖6所示．

圖5　例2可行域　　　　　　圖6　例2迭代過(guò)程

樂(lè)觀過(guò)程收斂代數(shù)為130，收斂最優(yōu)解為(-1.56e-03，1.001 06，-5.04e-04)，最優(yōu)值為1 000.870；悲觀過(guò)程收斂代數(shù)為126，收斂最優(yōu)解為(2.000 03，-2.94e-04，1.003 45)，最優(yōu)值為199.699 6；兩步法收斂代數(shù)為68代，收斂最優(yōu)解為(0.203 076 1，0.895 614 0，0.104 396)，最優(yōu)值為829.162 5．三步法分別求解了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

算例3[13]：

圖7　算例3迭代過(guò)程

樂(lè)觀過(guò)程收斂代數(shù)為200，收斂最優(yōu)解為(-1.11e-03，29.995 2，-10.000 1，9.997 54)，最優(yōu)值為-2.934e-03；悲觀過(guò)程收斂代數(shù)為198，收斂最優(yōu)解為(-1.18e-03，29.995 5，-10.000 1，9.997 66)，最優(yōu)值為-2.658e-03；兩步法收斂代數(shù)為149代，收斂最優(yōu)解為(-1.07e-03，29.995 2，-10.000 1，9.997 56)，最優(yōu)值為-3.038e-03．3種迭代過(guò)程大同小異，收斂的最優(yōu)解和最優(yōu)值都較為接近，3種迭代運(yùn)算應(yīng)該還有繼續(xù)收斂到更優(yōu)解的可能，但最優(yōu)解和最優(yōu)解的精度已經(jīng)很高．

算例4：

s.t.0≤xi≤4

yj≥0

算例4的反應(yīng)集為：

對(duì)于任意一個(gè)可行上層決策變量，下層最優(yōu)解均為無(wú)窮多個(gè)．樂(lè)觀最優(yōu)解為：

樂(lè)觀最優(yōu)值為0，悲觀最優(yōu)解為：

圖8　算例4迭代過(guò)程(左邊1+2維，右邊2+3維)

對(duì)于1+2維：樂(lè)觀過(guò)程收斂代數(shù)為105，收斂最優(yōu)解為(0，4.88e-04，4)，最優(yōu)值為2.387e-04；悲觀過(guò)程收斂代數(shù)為39，收斂最優(yōu)解為(2.001 68，1.998 83，3.08e-08)，最優(yōu)值為8.002 304；兩步法收斂代數(shù)為132代，收斂最優(yōu)解為(0.519 99，0，3.480 51)，最優(yōu)值為0.270 642 1．三步法分別求解了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

對(duì)于2+3維：樂(lè)觀過(guò)程收斂代數(shù)為48，收斂最優(yōu)解為(0，0，3.50e-03，0，3.996 97)，最優(yōu)值為2.366e-04；悲觀過(guò)程收斂代數(shù)為199，收斂最優(yōu)解為(1.362 97，1.310 36，1.327 18，2.63e-08，0)，最優(yōu)值為5.336 414；兩步法收斂代數(shù)為195代，收斂最優(yōu)解為(0.494 50，0.273 02，0，6.046 59e-02，3.172 52)，最優(yōu)值為0.322 986 4．3種迭代運(yùn)算應(yīng)該還有繼續(xù)收斂到更優(yōu)解的可能，但最優(yōu)解和最優(yōu)值的精度已經(jīng)很高，可以認(rèn)為三步法分別求解了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

算例5：

算例5的反應(yīng)集為：

圖9　算例5迭代過(guò)程(左邊是2+2維，右邊是4+4維)

對(duì)于2+2維：樂(lè)觀過(guò)程收斂代數(shù)為189，收斂最優(yōu)解為(1.05e-08，-3.20e-10，1.01e-08，-8.76e-10)，最優(yōu)值為2.125e-016；悲觀過(guò)程收斂代數(shù)為6，收斂最優(yōu)解為(1，-1，-11.056 0，11.056 0)，最優(yōu)值為246.471 4；兩步法收斂代數(shù)為132代，收斂最優(yōu)解為(0.421 2，1，0.435 6，1.570 8)，最優(yōu)值為3.835 109．三步法分別求解了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

對(duì)于4+4維：樂(lè)觀收斂代數(shù)為144代，收斂最優(yōu)解(3.31e-10，3.57e-10，1.20e-08，4.80e-12，4.19e-09，-3.39e-08，2.89e-09，-4.73e-09)，最優(yōu)值為1.342e-15；悲觀過(guò)程收斂代數(shù)為35，收斂最優(yōu)解為(1，-1，1，1-11.056 1，11.560 4，-11.056 1，-11.056 0)，最優(yōu)值為492.945 5；兩步法收斂代數(shù)為89代，收斂最優(yōu)解為(0.799 921 9，0.497 671 3，-0.978 888 6，1.000 000，-4.068 758，-5.762 273，-1.364 951，1.570 795)，最優(yōu)值為56.934 84．三步法分別求解了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂(lè)觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

4結(jié)論

上述5個(gè)不同類(lèi)型的算例的計(jì)算結(jié)果，不僅證明了三步法對(duì)于下層最優(yōu)解不唯一的二層規(guī)劃的適用性，也證明了對(duì)于下層最優(yōu)解唯一的二層規(guī)劃，三步法同樣能有效地求解出其最優(yōu)解，從而三步法對(duì)于二層規(guī)劃具有普遍適用性．

由于三步法中多次進(jìn)行了單層求解運(yùn)算，運(yùn)算時(shí)間相對(duì)較長(zhǎng)．未來(lái)將致力于解決三步法的運(yùn)算時(shí)間問(wèn)題，并且將三步法運(yùn)用于實(shí)際二層規(guī)劃當(dāng)中．

參考文獻(xiàn)：

[1]運(yùn)籌學(xué)教學(xué)編寫(xiě)組．運(yùn)籌學(xué)[M]．北京：清華大學(xué)出版社，2005：143．

[2]Lucchetti R， Mignanego F， Pieri G. Existence Theorems of Equilibrium Points in Stackelberg[J]． Optimization, 1987, 18(6)：857-866．

[3]Dempe S. Foundations of Bilevel Programming[M]． Springer Science & Business Media, 2002．

[4]Bialas W F, Karwan M H. Two-level Linear Programming[J]． Management Science, 1984, 30(8)：1004-1020．

[5]Ben-Ayed O. Bilevel Linear Programming[J]． Computers & Operations Research, 1993, 20(5)：485-501．

[6]Dempe S, Schmidt H. On an Algorithm Solving Two-level Program Ming Problems with Nonunique Lower Level Solutions[J]． Computational Optimization and Applications, 1996, 6(3)：227-249．

[7]Dempe S. A bundle Algorithm Applied to Bilevel Programming Problems with Non-unique Lower Level Solutions[J]． Computational Optimization and Applications, 2000, 15(2)：145-166．

[8]Loridan P, Morgan J. ε-regularized Two-level Optimization Problems：Approximation and Existence Results[M]//Optimization. Springer Berlin Heidelberg, 1989：99-113．

[9]Loridan P, Morgan J. On Strict ε-solutions for a Two-level Optimization Problem[C]//Papers of the 19th Annual Meeting/Vortr?ge der 19. Jahrestagung. Springer Berlin Heidelberg, 1992：165-172．

[10] Sinha A, Malo P, Deb K. Test Problem Construction for Single-objective Bilevel Optimization[J]． Evolutionary Computation, 2014, 22(3)：439-477．

[11] Gao Y, Zhang G, Lu J, et al. Particle Swarm Optimization for Bi-level Pricing Problems in Supply Chains[J]． Journal of Global Optimization, 2011, 51(2)：245-254．

[12] Loridan P, Morgan J. Approximate Solutions for Two-level Optimization Problems[M]． Birkh?user Basel, 1988．

[13] Aiyoshi E, Shimizu K. A Solution Method for the Static Constrained Stackelberg Problem Via Penalty Method[J]． Automatic Control, IEEE Transactions on, 1984, 29(12)：1111-1114．

[責(zé)任編輯王康平]

收稿日期：2015-11-05

基金項(xiàng)目：國(guó)家自然科學(xué)基金(51479142,51339004)，湖北省水利重點(diǎn)科研項(xiàng)目(HBSLKL201304)，湖北水利科研項(xiàng)目(HBSLKY201401)

通信作者：胡鐵松(1964-)，男，教授，主要研究方向?yàn)檫\(yùn)籌學(xué)．E-mail：tshu@whu.edu.cn

DOI：10.13393/j.cnki.issn.1672-948X.2016.02.023

中圖分類(lèi)號(hào)：O224

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672-948X(2016)02-0102-06

Three-step Method for Solving Bilevel Programming with Non-unique Lower Level Optimal Solutions

Wang JianHu TiesongWang Qin

(State Key Laboratory of Water Resources & Hydropower Engineering Science, Wuhan Univ., Wuhan 430072, China)

AbstractBased on optimistic and pessimistic bilevel programming with non-unique lower level optimal solutions, the definitions of optimistic and pessimistic feasible solution is proposed, three-step method for solving bilevel programming with non-unique lower level optimal solutions is also proposed. Finally, the proposed three-step method and two-step method proposed before have been applied to 5 benchmark problems. The numerical results demonstrate the feasibility and effectiveness of three-step method.

Keywordsbilevel programming;optimistic optimal solution;pessimistic optimal solution