呂一兵

(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

線性二層規(guī)劃擴(kuò)展KT方法研究

呂一兵

(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

為了更好地解決上層帶有任意線性約束的線性二層規(guī)劃問(wèn)題，Shi Chenggen提出了能夠求解更廣泛線性二層規(guī)劃問(wèn)題的擴(kuò)展KT方法。具體介紹了求解線性二層規(guī)劃的原KT方法以及擴(kuò)展KT方法，同時(shí)給出了一個(gè)用擴(kuò)展KT方法和用原KT方法可以得到不同最優(yōu)解的算例。算例結(jié)果表明，對(duì)有些線性二層規(guī)劃問(wèn)題，擴(kuò)展KT方法能夠得到與原KT方法不同的最優(yōu)解。提出了2種KT方法的等價(jià)性條件。算例結(jié)果證實(shí)了上述等價(jià)性條件的正確性。

線性二層規(guī)劃;KT方法;等價(jià)性

二層規(guī)劃是二層決策問(wèn)題的數(shù)學(xué)模型，它是一種具有二層遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問(wèn)題。在二層規(guī)劃模型中, 上層問(wèn)題和下層問(wèn)題都有各自的目標(biāo)函數(shù)和約束條件。上層問(wèn)題的目標(biāo)函數(shù)和約束條件不僅與上層決策變量有關(guān)，而且還依賴于下層問(wèn)題的最優(yōu)解，而下層問(wèn)題的最優(yōu)解又受到上層決策變量的影響。人們?cè)谏鲜兰o(jì)70年代開(kāi)始對(duì)二層規(guī)劃進(jìn)行研究以來(lái)，無(wú)論在理論方面還是在算法研究方面都取得了很大的成績(jī)，然而二層規(guī)劃問(wèn)題是NP-難問(wèn)題[1]，因此對(duì)二層規(guī)劃的研究大多數(shù)還局限于線性二層規(guī)劃。即便如此，Shi Chenggen指出[2]，人們一致認(rèn)可的線性二層規(guī)劃最優(yōu)解定義在處理上層帶有任意線性約束形式的線性二層規(guī)劃問(wèn)題時(shí)還存在缺陷。為了解決存在的缺陷，Shi Chenggen給出了線性二層規(guī)劃最優(yōu)解的新定義，并且在新定義的基礎(chǔ)上Shi Chenggen給出了求解線性二層規(guī)劃的擴(kuò)展KT方法[3]。同時(shí)Shi Chenggen指出擴(kuò)展的KT方法相比原來(lái)的KT方法能夠解決更為廣泛的線性二層規(guī)劃問(wèn)題。

雖然Shi Chenggen提出的求解線性二層規(guī)劃的擴(kuò)展KT方法能夠解決原KT方法的不足，但是并不是能夠解決比原KT方法更廣泛的線性二層規(guī)劃問(wèn)題。事實(shí)上，對(duì)于某些線性二層規(guī)劃問(wèn)題，用擴(kuò)展KT方法所得到最優(yōu)解有可能與用原KT方法得到的最優(yōu)解不相同，出現(xiàn)這種情況就比較容易造成實(shí)際應(yīng)用的混亂。因此研究2種求解線性二層規(guī)劃的KT方法之間的關(guān)系就顯得十分必要。為此，筆者具體介紹了求解線性二層規(guī)劃的原KT方法以及擴(kuò)展KT方法，同時(shí)給出了一個(gè)用擴(kuò)展KT方法和用原KT方法可以得到不同最優(yōu)解的算例，并提出了求解線性二層規(guī)劃的2種KT方法之間的等價(jià)性條件。

1 問(wèn)題的提出

假設(shè)：x∈X?Rn;y∈Y?Rm分別是上、下層決策變量,F、f:Rn×Rm→R1分別是上、下層目標(biāo)函數(shù)。線性二層規(guī)劃的一般數(shù)學(xué)模型[4]如下：

(1)

式中，c1,c2∈Rn；d1,d2∈Rm；b1∈Rp；b2∈Rq；A1∈Rp×n；A2∈Rq×n；B1∈Rp×m；B2∈Rq×m。

相應(yīng)線性二層規(guī)劃(1),Bard給出了如下定義[4]:

定義1(a)線性二層規(guī)劃的約束域：

S={(x，y) :x∈X，y∈Y，A1x+B1y≤b1，A2x+B2y≤b2}

(b)對(duì)于x∈X，下層問(wèn)題的可行域：

S(x) ={y∈Y:A2x+B2y≤b2}

(c)S在上層決策空間的投影:

S(X) = {x∈X:?y∈Y，A1x+B1y≤b1，A2x+B2y≤b2}

(d)對(duì)于x∈S(X)，下層問(wèn)題的合理反應(yīng)集：

P(x) ={y∈Y:y∈argmin[f(x,y):y∈S(x)]}

(e)線性二層規(guī)劃的誘導(dǎo)域:

IR={(x，y):(x，y)∈S，y∈P(x)}

為了保證(1)存在最優(yōu)解，Bard給出如下假設(shè)[4]。

假設(shè)1(a)S為非空緊集； (b)對(duì)于x∈S(X)，下層問(wèn)題的合理反應(yīng)集P(x)≠Φ；(c)P(x)為一一映射。 定義1以及假設(shè)1是線性二層規(guī)劃數(shù)學(xué)模型的基礎(chǔ)，它們對(duì)線性二層規(guī)劃問(wèn)題算法的形成起到了關(guān)鍵性作用，同時(shí)也是線性二層規(guī)劃最優(yōu)性條件的理論基礎(chǔ)。然而，Shi Chenggen舉例指出[2]，即使線性二層規(guī)劃在定義1下滿足上述3條假設(shè)，也可能不存在最優(yōu)解，因?yàn)榧词?條假設(shè)得到滿足，也無(wú)法保證線性二層規(guī)劃的誘導(dǎo)域非空。這正是定義1的缺陷之所在。為了解決該缺陷，對(duì)線性二層規(guī)劃的一般數(shù)學(xué)模型(1)，Shi Chenggen給出了如下關(guān)于線性二層規(guī)劃最優(yōu)解的新定義[2]。

定義2(a)線性二層規(guī)劃的約束域：

S={(x，y) :x∈X，y∈Y，A1x+B1y≤b1，A2x+B2y≤b2}

(b)S在上層決策空間的投影:

S(X)={x∈X:?y∈Y，A1x+B1y≤b1，A2x+B2y≤b2}

(c)對(duì)于x∈S(X)，下層問(wèn)題的可行域：

S(x)={y∈Y:(x,y)∈S}

(d)對(duì)于x∈S(X)，下層問(wèn)題的合理反應(yīng)集：

P(x) ={y∈Y:y∈argmin[f(x,y) :y∈S(x)]}

(e)線性二層規(guī)劃的誘導(dǎo)域:

IR={(x,y) :(x,y)∈S,y∈P(x)}

對(duì)于定義2, Shi Chenggen給出了下列定理[2]:

定理1如果S為非空緊集, 那么線性二層規(guī)劃(1)必存在最優(yōu)解。

1.1原KT方法

Bard給出的求解線性二層規(guī)劃(1)的KT方法[4]，即原KT方法的主要思想是以線性二層規(guī)劃下層問(wèn)題的KT最優(yōu)性條件代替下層問(wèn)題，將線性二層規(guī)劃問(wèn)題(1)轉(zhuǎn)化為帶有互補(bǔ)約束的單層規(guī)劃問(wèn)題。假設(shè)u∈Rq,v∈Rm分別是相應(yīng)于式(1)的第4個(gè)式子和y≥0的對(duì)偶變量，Bard給出了如下命題[4]。

命題1(x*,y*)是問(wèn)題(1)的最優(yōu)解的必要條件是存在行向量u*,v*,使得(x*,y*,u*,v*)是如下問(wèn)題的最優(yōu)解:

minF(x,y) =c1x+d1y

s.t.A1x+B1y≤b1

A2x+B2y≤b2

uB2-v= -d2

u(b2-A2x-B2y)+vy= 0

x≥0y≥0u≥0v≥0

(2)

式(2)是一類求解線性二層規(guī)劃算法的理論基礎(chǔ)[5]，然而Shi Chenggen給出的一個(gè)算例表明式(2)在求解上層帶有任意線性約束的線性二層規(guī)劃問(wèn)題時(shí)存在著無(wú)法找到問(wèn)題最優(yōu)解的缺陷[3]。為了解決這種缺陷，Shi Chenggen在定義2的基礎(chǔ)上，給出了求解線性二層規(guī)劃的擴(kuò)展KT方法。

1.2擴(kuò)展KT方法

擴(kuò)展KT方法的基本思想是在定義2的基礎(chǔ)上，以下層問(wèn)題的KT最優(yōu)性條件代替下層問(wèn)題，從而得到相應(yīng)的單層規(guī)劃。Shi Chenggen給出并證明了如下命題[3]:

命題2(x*,y*)是問(wèn)題(1)的最優(yōu)解的充要條件是存在行向量u*∈Rp,v*∈Rq,w*∈Rm,使得(x*,y*,u*,v*,w*)是如下問(wèn)題的最優(yōu)解:

minF(x,y) =c1x+d1y

s.t.A1x+B1y≤b1

A2x+B2y≤b2

uB1+vB2-w= -d2

u(b1-A1x-B1y)+v(b2-A2x-B2y)+wy= 0

x≥0y≥0u≥0v≥0w≥0

命題2是擴(kuò)展KT方法的理論基礎(chǔ)， 同時(shí)Shi Chenggen指出， 擴(kuò)展KT方法相比原KT方法能夠解決更為廣泛的線性二層規(guī)劃問(wèn)題[3]。

1.3反例

然而，對(duì)有些線性二層規(guī)劃問(wèn)題，利用擴(kuò)展KT方法與原KT方法可以得到不同的最優(yōu)解。這種情況可以通過(guò)下面的例子予以說(shuō)明。

例1考慮如下線性二層規(guī)劃問(wèn)題,其中x∈R1，y∈R1，X={x|x≥0}，Y={y|y≥0}。

(3)

首先用原KT方法， 即命題1去求解例1。

令：

g1(x,y)=x+y-3≥0g2(x,y) =12-2x-y≥0g3(x,y)=2x-y≥0

式(3)可以相應(yīng)的轉(zhuǎn)化為：

minF(x,y)=x-4y

s.t. 3x-2y≤4

-x-y≤-3

2x+y≤12

-2x+y≤0

-u1+u2+u3-v=-3

u1g1(x,y)+u2g2(x,y)+u3g3(x,y)+uy=0

x≥0y≥0u1≥0u2≥0u3≥0v≥0

(4)

可以分2種情況進(jìn)行討論：

minx-4y

s.t. 3x-2y≤4

-x-y=-3

2x+y≤12

-2x+y≤0

x≥0y≥0

利用單純形方法，可以得到最優(yōu)解為(x*,y*) = (1，2)。

minx-4y

s.t. 3x-2y≤4

-x-y=-3

2x+y≤12

-2x+y≤0

x≥0y=0

利用單純形算法，可知上述問(wèn)題不可行。

由上述2種情況可知用原KT方法求解例1，得到的最優(yōu)解為(x*，y*)=(1，2)。

其次用擴(kuò)展KT方法,即利用命題2求解例1。類似于文獻(xiàn)[3]的求解過(guò)程， 可以得到用擴(kuò)展KT方法求解例1的最優(yōu)解為(x*，y*)= (4,4)。

從上面的例子可以看到，對(duì)于例1，2種KT方法得到了2個(gè)不同的最優(yōu)解。這表明雖然擴(kuò)展KT方法可以解決原KT方法存在的不足[3]，但是對(duì)有的線性二層規(guī)劃問(wèn)題，擴(kuò)展KT方法可以得到與原KT方法不同的結(jié)果。出現(xiàn)這種情況顯然會(huì)造成實(shí)際應(yīng)用的混亂。因此，研究2種KT方法之間的關(guān)系就顯得十分必要。

2 擴(kuò)展KT方法和原KT方法之間的等價(jià)條件

由前所述，求解線性二層規(guī)劃的KT方法的基本思想是以下層問(wèn)題的KT最優(yōu)性條件代替下層問(wèn)題。導(dǎo)致2種KT方法對(duì)同一個(gè)線性二層規(guī)劃問(wèn)題得到不同最優(yōu)解的原因在于定義1與定義2有不同的下層問(wèn)題可行域定義。因此，要研究2種KT方法之間的關(guān)系，只需要研究2種定義(定義1與定義2)下的下層問(wèn)題之間的關(guān)系。

2.1等價(jià)性條件

下面指出當(dāng)線性二層規(guī)劃(1)滿足一定條件時(shí)，2種定義下的下層問(wèn)題是等價(jià)的。此時(shí)對(duì)該類線性二層規(guī)劃問(wèn)題，2種KT方法可以得到相同的最優(yōu)解。在給出結(jié)果之前,為方便起見(jiàn)先介紹2個(gè)有用的記號(hào)：

P1(x):定義1下線性二層規(guī)劃(1)的下層問(wèn)題的合理反應(yīng)集

P2(x):定義2下線性二層規(guī)劃(1)的下層問(wèn)題的合理反應(yīng)集

命題3假設(shè)對(duì)于x∈S(X),滿足(x,P1(x))∈S,那么線性二層規(guī)劃(1)的下層問(wèn)題在x∈S(X)的條件下與下列線性規(guī)劃問(wèn)題有相同的最優(yōu)解:

(5)

證明由P1(x)的定義可知，對(duì)x∈S(X)，P1(x)為下列線性規(guī)劃之最優(yōu)解：

(6)

由于(x,P1(x))∈S，則對(duì)于x∈S(X)，P1(x)同樣為式(5)的最優(yōu)解。

另一方面,假設(shè)對(duì)于x∈S(X)，式(5)的最優(yōu)解為P2(x),顯然有(x，P2(x))∈S。現(xiàn)在要證明對(duì)于x∈S(X)，P2(x)同樣為式(6)的最優(yōu)解。不妨假設(shè)對(duì)于x∈S(X)，式(6)的最優(yōu)解為y*≠P2(x)。由上面的證明可知對(duì)于x∈S(X)，y*為式(5)的最優(yōu)解。這就與對(duì)于x∈S(X)，式(5)的最優(yōu)解為P2(x)相矛盾。矛盾表明對(duì)于x∈S(X)，P2(x)也為式(6)的最優(yōu)解。這樣就完成了命題的證明。

下面在命題3的基礎(chǔ)上給出2種KT方法之間的等價(jià)性關(guān)系。

定理2若線性二層規(guī)劃(1)滿足約束域S為非空緊集，且x∈S(X),(x，P1(x))∈S，那么對(duì)于線性二層規(guī)劃(1)，原KT方法與擴(kuò)展KT方法可以得到相同的最優(yōu)解。

證明 由命題3可知，對(duì)于x∈S(X),若(x，P1(x))∈S,那么線性二層規(guī)劃(1)的下層問(wèn)題與式(5)具有相同的最優(yōu)解。也就是說(shuō)線性二層規(guī)劃(1)等價(jià)于下列線性二層規(guī)劃:

再由命題1以及命題2可知定理的結(jié)論成立。證畢。

如果定理2的條件得不到滿足，那么就有可能導(dǎo)致對(duì)同一個(gè)線性二層規(guī)劃問(wèn)題2種KT方法可以得到不同的最優(yōu)解。如在例1中， 對(duì)于3≤x′≤4,P1(x′)=0。顯然(x′，P1(x′)?S，這也導(dǎo)致例1在2種KT方法下得到了不同的最優(yōu)解。而如果下層問(wèn)題的合理反應(yīng)集P1(x)滿足(x,P1(x))∈S，那么對(duì)該類線性二層規(guī)劃問(wèn)題用2種KT方法可以得到相同的最優(yōu)解。

2.2算例

例2考慮下列線性二層規(guī)劃問(wèn)題，其中x∈R1,y∈R1,X= {x|x≥0},Y={y|y≥0}。

(7)

對(duì)于問(wèn)題(7)，S(X) ={1≤x≤4},可以得到：

容易驗(yàn)證(x,P1(x))∈S，定理1的假設(shè)條件得到滿足。那么問(wèn)題(7)在2種KT方法下應(yīng)該有相同的最優(yōu)解。事實(shí)上類似于例1的求解過(guò)程2種KT方法可以得到相同的最優(yōu)解為(x*,y*) = (4，4)。

3 結(jié) 語(yǔ)

對(duì)Shi Chenggen提出的擴(kuò)展KT方法進(jìn)行了討論,舉出的一個(gè)反例表明擴(kuò)展的KT方法雖然可以解決原方法的不足,但是并不是能夠解決更廣泛的線性二層規(guī)劃問(wèn)題。在反例的基礎(chǔ)上,提出了2種KT方法的等價(jià)性條件,即對(duì)于x∈S(X),有(x，P1(x))∈S,那么線性二層規(guī)劃在2種KT方法下可以得到相同的最優(yōu)解。值得指出的是對(duì)于x∈S(X),如何判別(x，P1(x))∈S是個(gè)值得繼續(xù)研究的問(wèn)題。而如果能夠得到比較簡(jiǎn)單的判別方法，那么在(x，P1(x))∈S的前提下就可以盡量將下層約束問(wèn)題移到上層，以簡(jiǎn)化下層約束問(wèn)題。這樣對(duì)構(gòu)造求解線性二層規(guī)劃的有效算法(如分枝定界法) 是有意義的。

[1]Ben-Ayed O, Blair O.Computational diffculity of bilevel linear programming[J].Operations Research, 1990,38:556～560.

[2] Shi Chenggen, Zhang Guangquan, Lu Jie. On the definition of linear bilevel programming solutin[J]. Applied Mathematics and Compution, 2005,160:169～173.

[3] Shi Chenggen, Zhang Guangquan, Lu Jie. An extended Kuhn-Tucker approach for linear bilevel programming[J]. Applied Mathematics and Compution, 2005,162:51～63.

[4] Bard J F. Practical Bilevel Optimization: Algorithms and Application[M]. The Netherlands:Kluwer Academic Publisher, 1998.

[5] Hansen P, Jaumard B, Savard G. New branch-and-bound rules for linear bilevel programming[J]. SIAM Journal on Science and Statistical Computing, 1992,13:1194～1217.

[6]Liu X, Wang R, Wang Sh. An algorithm to solve linear bilevel programming[J]. Journal of Systems Science and Systems Engineering, 1995,4(2):158～167.

[7] Marcotte P, Savard G. A note on the Pareto optimality of solutions to the linear bilevel programming problem[J]. Computers and Opertiond Research, 1991,18:355～359.

[編輯] 洪云飛

O224

A

1673-1409(2010)01-N001-05