不適定線性二層規(guī)劃問題的一種新的激勵模型

賈世會， 王興趣

(1.武漢科技大學(xué)理學(xué)院， 武漢 430081； 2.冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室， 武漢 430081)

二層規(guī)劃問題是一種具有遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問題，由上、下兩層優(yōu)化問題構(gòu)成，上層和下層問題都有自己的目標(biāo)函數(shù)和約束條件，上層問題的目標(biāo)函數(shù)和約束條件不僅與上層決策變量相關(guān)，而且還依賴于下層問題的最優(yōu)解，而下層問題的最優(yōu)解又受上層決策的影響.不管是上層問題還是下層問題，目的都是達(dá)到各自最優(yōu)，但又同時受到對方?jīng)Q策的影響.迄今為止，二層規(guī)劃問題已經(jīng)在交通規(guī)劃、電力市場、生態(tài)環(huán)境、工程設(shè)計(jì)等[1-8]眾多應(yīng)用領(lǐng)域發(fā)揮著極其重要的作用.然而，作為一類NP-hard[9]問題，即使是一個線性二層規(guī)劃問題[10-11]一般也是很難求解的.本文考慮以下的線性二層規(guī)劃問題[12]：

s.t.A1x≤b1，

(1)

y∈ψ(x)，

其中，ψ(x)是下層問題反饋解的集合，

s.t.A2x+B2y≤b2，

(2)

這里，x，c1∈Rn，y，d1，d2∈Rm，A1∈Rp×n，b1∈RP，A2∈Rq×n，B2∈Rq×m，b2∈Rq．

設(shè)X={x∈Rn|A1x≤b1，x≥0}和Y(x)={y∈Rm|B2y≤b2-A2x，y≥0}.

若ψ(x)不唯一，即下層問題對于上層決策變量的每個(或某些)取值可能有多個對應(yīng)方案.那么上層決策者很難預(yù)測下層決策者會在ψ(x)反饋哪一個方案給自己，從而使得上層決策者很難確定自己的最終決策.通常稱此類問題為不適定性二層規(guī)劃問題(簡稱為IBPP).

對于不適定性二層規(guī)劃問題，這里存在兩種極端情況，第一種情況假設(shè)下層決策者完全與上層決策者合作，即會反饋一個對上層決策者而言最優(yōu)的解，此種情況稱作樂觀模型[4，13-14]，具體形式如下：

(3)

相反，第二種情況假設(shè)下層決策者完全不與上層決策者合作，即反饋一個最差的結(jié)果給上層，此時稱作：悲觀模型[15-19]，具體形式如下：

(4)

由于合作與競爭在現(xiàn)實(shí)生活中是共依共存的，樂觀和悲觀的解決方案可能都不是解決實(shí)際問題的最佳選擇.1995年，對于Stackelberg問題中的樂觀和悲觀模型，Aboussoror和Loridan[20]首先提出了協(xié)調(diào)解的概念；隨后，Mallozzi和Morgan[21]給出了上層決策者掌握了下層決策者部分信后的協(xié)調(diào)解構(gòu)造；繼而，引入合作指標(biāo)λ來描述下層決策者的合作程度.2002年，Cao和Leung[22]提出了不適定線性二層規(guī)劃問題的部分合作模型：

(5)

在這個模型里，λ是一個參數(shù)，它使得模型變得更加難以求解.

本文提出了問題(1)的一個協(xié)調(diào)模型，引入利潤分配比例β，此時，β是一個變量，而不是參數(shù).同時，根據(jù)約束條件，構(gòu)造兩個精確罰函數(shù)，將原模型進(jìn)行等價(jià)轉(zhuǎn)換.數(shù)值結(jié)果驗(yàn)證了該方法的可行性.最后，將此方法與文獻(xiàn)[22]的部分合作模型進(jìn)行比較，結(jié)果顯示，雖然兩種方法中下層決策者的收入是相同的，但本文方法得到的上層決策者的利潤要優(yōu)于Cao和Leung[22].

1 協(xié)調(diào)問題，激勵模型

為了建立理論結(jié)果，首先給出如下主要假設(shè).

假設(shè)：

(A1) 對于任意的x∈X，Y(x)≠?，存在著一個緊子集W?Rm使得對所有的x∈X，Y(x)?W.

(A2) 集合X是一個有界多面體.

取β為上層決策者最終利潤分配比例，基于激勵的原則，上層決策者將自身利潤(1-β)的份額給予下層決策者以激勵下層決策者與自己合作，于是可得如下協(xié)調(diào)模型：

s.t.x∈X，

y∈ψ(x)，

(6)

0≤α≤β≤1，

(7)

(8)

由對偶性理論，問題(2)的對偶問題如下：

(9)

s.t.x∈X，

A2x+B2y≤b2，

(10)

0≤α≤β≤1，

y≥0，z≥0．

Z2={(x，y，u)|x∈X，A2x+B2y≤b2，

于是，問題(10)轉(zhuǎn)化為：

(11)

(z，β)∈Z1，(x，y，u)∈Z2.

s.t.(z，β)∈Z1，

(12)

其中，k1，k2>0是懲罰參數(shù).令

表示問題(12)的目標(biāo)函數(shù).

假設(shè)k1，k2>0是固定的，(z，β)∈Z1，令

(13)

則有如下結(jié)論．

定理1若滿足假設(shè)(A1)和(A2)，則問題(12)在Z1×V(Z2)中至少有一個解，其中V(Z2)表示集合Z2的頂點(diǎn)集.

證明已知k1，k2>0，(z，β)∈Z1，函數(shù)θ(z，β)是凹的，那么，問題(13)有一個解(x，y，u)∈V(Z2).因?yàn)槎嗝骟wZ2是有界的，所以問題(13)可以重寫為：

其中，(xi，yi，ui)∈V(Z2)且|V(Z2)|表示集合Z2的頂點(diǎn)數(shù).

對于每一個(xi，yi，ui)∈V(Z2)，設(shè)

即

由目標(biāo)函數(shù)的凹性，得

(x*，y*，u*)表示問題(13)的解，相應(yīng)的，(z*，β*，x*，y*，u*)∈Z1×V(Z2)是問題(12)的一個解.

2 算法和主要結(jié)果

根據(jù)第2部分的結(jié)果，給出問題(6)～(8)的算法.

算法：

Step 0.選擇k1=k2>0，γ>1．

備注多面體的頂點(diǎn)數(shù)是有限的，其所有的頂點(diǎn)都可以用參考文獻(xiàn)[23-24]中的方法列出.

對于(xi，yi，ui)∈V(Z2)，可以將問題(12)轉(zhuǎn)化為一系列凹規(guī)劃問題P(xi，yi，ui)，具體如下：

(zi，βi)表示上式的解，那么可以得到

下面的結(jié)果表明Step1-Step2-Step1和Step1-Step3-Step1將在有限次迭代之后終止.

為了簡單起見，定義：

D2={(x，y，z，u，β)|(x，y，z，u，β)∈D1，

D3=

{(x，y，z，u，β)|(x，y，z，u，β)∈D1，π(x，y，z)=

D4={(x，y，z，u，β)|(x，y，z，u，β)∈D1，

D5={(x，y，z)|(x，y，z，u，β)∈D1，

π(x，y，z)>0}，

D6={(x，y，z，u，β)|(x，y，z，u，β)∈D1，

π(x，y，z)=0，

不失一般性，考慮如下三種情況.

于是有如下定理.

3 數(shù)值結(jié)果

s.t.y1+y2≤20+x1-x2，

y≥0．

s.t.y1+y2+y3+y4≤10-x1-x2，

-y1+y4≤0.8x1+0.8x2，

y2+y4≤4x2，

y≥0．

不失一般性，取k1=k2=10，γ=10以及α=0.7.數(shù)值運(yùn)算結(jié)果見表1，其中L和F分別表示上層決策者和下層決策者的利潤.這里，方法1表示本文激勵模型，Cao和Leung的部分合作模型用方法2來表示.

表1 激勵模型與部分合作模型結(jié)果對比

在例1中，(10，0)T是樂觀解，140是樂觀值.可以看出，本文方法的計(jì)算結(jié)果與文獻(xiàn)[22]的結(jié)果是相等的，而且，該結(jié)果也與樂觀模式的結(jié)果相同.

在例2中，(0，2)T是樂觀解，232是樂觀值.由表1可知，方法1和方法2中下層決策者有相同的收入，然而前者的上層決策者的利潤遠(yuǎn)遠(yuǎn)大于后者，產(chǎn)生這種情況的原因主要在于，在文獻(xiàn)[22]中，除了保證下層決策者的利益最大化外，上層決策者的回報(bào)還取決于下層決策者的部分合作程度λ，這種依賴關(guān)系在他們的局部合作模型中也有反映.該局部合作模型解決了λ值范圍的問題，即只有在給定參數(shù)λ的值之后，模型才能得到解決.這毫無疑問會改善和提高下層決策者在決策中的地位，甚至將會把模型固有的上下層遞階關(guān)系顛倒過來.

注意到，在本文激勵模型中，上層決策者的收益取決于利潤分配比例β，雖然它是一個變量，受到下層決策者的影響，但是模型目標(biāo)仍然是最大化上層決策者的利益，因此，與文獻(xiàn)[22]不同的是，上層決策者在決策過程中仍然扮演著主要的角色.

4 結(jié)論

本文提出了一個不適定線性二層規(guī)劃問題的激勵模型.這個模型可以激勵下層決策者心甘情愿與上層決策者合作，從而使上層決策者的利益最大化.數(shù)值結(jié)果表明，該方法是切實(shí)可行的，并且在保證下層決策者達(dá)到同樣的最優(yōu)利益的基礎(chǔ)上，本文模型中上層決策者的最終收益優(yōu)于基于合作度的部分合作模型的上層決策者收益.本文主要針對線性問題，在以后的研究中，將會將激勵措施用到非線性問題中，得到相應(yīng)的理論結(jié)果及具體算法.