線性二層規劃擴展KT方法研究

呂一兵

(長江大學信息與數學學院，湖北 荊州 434023)

線性二層規劃擴展KT方法研究

呂一兵

(長江大學信息與數學學院，湖北 荊州 434023)

為了更好地解決上層帶有任意線性約束的線性二層規劃問題，Shi Chenggen提出了能夠求解更廣泛線性二層規劃問題的擴展KT方法。具體介紹了求解線性二層規劃的原KT方法以及擴展KT方法，同時給出了一個用擴展KT方法和用原KT方法可以得到不同最優解的算例。算例結果表明，對有些線性二層規劃問題，擴展KT方法能夠得到與原KT方法不同的最優解。提出了2種KT方法的等價性條件。算例結果證實了上述等價性條件的正確性。

線性二層規劃;KT方法;等價性

二層規劃是二層決策問題的數學模型，它是一種具有二層遞階結構的系統優化問題。在二層規劃模型中, 上層問題和下層問題都有各自的目標函數和約束條件。上層問題的目標函數和約束條件不僅與上層決策變量有關，而且還依賴于下層問題的最優解，而下層問題的最優解又受到上層決策變量的影響。人們在上世紀70年代開始對二層規劃進行研究以來，無論在理論方面還是在算法研究方面都取得了很大的成績，然而二層規劃問題是NP-難問題[1]，因此對二層規劃的研究大多數還局限于線性二層規劃。即便如此，Shi Chenggen指出[2]，人們一致認可的線性二層規劃最優解定義在處理上層帶有任意線性約束形式的線性二層規劃問題時還存在缺陷。為了解決存在的缺陷，Shi Chenggen給出了線性二層規劃最優解的新定義，并且在新定義的基礎上Shi Chenggen給出了求解線性二層規劃的擴展KT方法[3]。同時Shi Chenggen指出擴展的KT方法相比原來的KT方法能夠解決更為廣泛的線性二層規劃問題。

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

1 問題的提出

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

(1)

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

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

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

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

(b)對于x∈X，下層問題的可行域：

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

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

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

(d)對于x∈S(X)，下層問題的合理反應集：

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

(e)線性二層規劃的誘導域:

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

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

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

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

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)對于x∈S(X)，下層問題的可行域：

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

(d)對于x∈S(X)，下層問題的合理反應集：

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

(e)線性二層規劃的誘導域:

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

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

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

1.1原KT方法

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

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

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)是一類求解線性二層規劃算法的理論基礎[5]，然而Shi Chenggen給出的一個算例表明式(2)在求解上層帶有任意線性約束的線性二層規劃問題時存在著無法找到問題最優解的缺陷[3]。為了解決這種缺陷，Shi Chenggen在定義2的基礎上，給出了求解線性二層規劃的擴展KT方法。

1.2擴展KT方法

擴展KT方法的基本思想是在定義2的基礎上，以下層問題的KT最優性條件代替下層問題，從而得到相應的單層規劃。Shi Chenggen給出并證明了如下命題[3]:

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

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是擴展KT方法的理論基礎， 同時Shi Chenggen指出， 擴展KT方法相比原KT方法能夠解決更為廣泛的線性二層規劃問題[3]。

1.3反例

然而，對有些線性二層規劃問題，利用擴展KT方法與原KT方法可以得到不同的最優解。這種情況可以通過下面的例子予以說明。

例1考慮如下線性二層規劃問題,其中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)可以相應的轉化為：

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種情況進行討論：

minx-4y

s.t. 3x-2y≤4

-x-y=-3

2x+y≤12

-2x+y≤0

x≥0y≥0

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

minx-4y

s.t. 3x-2y≤4

-x-y=-3

2x+y≤12

-2x+y≤0

x≥0y=0

利用單純形算法，可知上述問題不可行。

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

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

從上面的例子可以看到，對于例1，2種KT方法得到了2個不同的最優解。這表明雖然擴展KT方法可以解決原KT方法存在的不足[3]，但是對有的線性二層規劃問題，擴展KT方法可以得到與原KT方法不同的結果。出現這種情況顯然會造成實際應用的混亂。因此，研究2種KT方法之間的關系就顯得十分必要。

2 擴展KT方法和原KT方法之間的等價條件

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

2.1等價性條件

下面指出當線性二層規劃(1)滿足一定條件時，2種定義下的下層問題是等價的。此時對該類線性二層規劃問題，2種KT方法可以得到相同的最優解。在給出結果之前,為方便起見先介紹2個有用的記號：

P1(x):定義1下線性二層規劃(1)的下層問題的合理反應集

P2(x):定義2下線性二層規劃(1)的下層問題的合理反應集

命題3假設對于x∈S(X),滿足(x,P1(x))∈S,那么線性二層規劃(1)的下層問題在x∈S(X)的條件下與下列線性規劃問題有相同的最優解:

(5)

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

(6)

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

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

下面在命題3的基礎上給出2種KT方法之間的等價性關系。

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

證明 由命題3可知，對于x∈S(X),若(x，P1(x))∈S,那么線性二層規劃(1)的下層問題與式(5)具有相同的最優解。也就是說線性二層規劃(1)等價于下列線性二層規劃:

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

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

2.2算例

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

(7)

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

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

3 結 語

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

[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