張 濤

楊世明 (長江大學地球物理與石油資源學院，湖北 荊州 434023)

一種求解線性二層規(guī)劃的罰函數(shù)方法

楊世明 (長江大學地球物理與石油資源學院，湖北 荊州 434023)

利用下層問題的最優(yōu)性條件代替下層問題，同時取互補條件為上層目標函數(shù)的罰項，將線性二層規(guī)劃轉(zhuǎn)化為相應的單層規(guī)劃。分析表明，該罰函數(shù)為精確罰函數(shù)。最后，設計了線性二層規(guī)劃的罰函數(shù)算法,并用數(shù)值試驗驗證了算法的可行性。

線性二層規(guī)劃； K-T條件；罰函數(shù)

二層規(guī)劃是一種具有遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問題，在二層規(guī)劃模型中,上、下層問題都有自己的目標函數(shù)和約束條件。上層問題的目標函數(shù)不僅與上層決策變量有關(guān)，而且還依賴于下層問題的最優(yōu)解，而下層問題的最優(yōu)解又受上層決策變量的影響[1]。二層規(guī)劃是NP難問題[2]，因此對二層規(guī)劃的研究大多數(shù)集中于線性二層規(guī)劃-上、下層目標函數(shù)以及約束條件均為線性函數(shù)，在求解線性二層規(guī)劃的方法中，一類重要的轉(zhuǎn)化思想是以下層問題的K-T條件代替下層問題，然后求解相應的帶互補約束條件的數(shù)學規(guī)劃問題。下面，筆者依然采用以下層問題的K-T條件代替下層問題的轉(zhuǎn)化思想，將線性二層規(guī)劃轉(zhuǎn)化為帶互補條件的數(shù)學規(guī)劃問題，并取互補條件為上層目標函數(shù)的罰項，構(gòu)造線性二層規(guī)劃的罰方法，通過理論分析，得到所設計的罰函數(shù)為精確罰函數(shù)。

1 基本概念

假設C1,x∈Rm,C2,b,y∈Rn2,a∈Rm,A1∈Rm×n1,A2∈Rm×n2，則線性二層規(guī)劃可以寫為：

s.t.A1x+A2y≤a

(1)

對于問題(1)，以下層問題的K-T條件代替下層問題有：

s.t.A1x+A2y+w=a

uTw+vTy=0

x、y、u、v、w≥0

(2)

式中，w∈Rm為松弛變量；u∈Rm,v∈Rn2為對偶變量。

基于上述轉(zhuǎn)化思想，文獻[3-4]分別設計了求解線性二層規(guī)劃的分枝定界方法[3]，平衡點方法[4]等，然而目前依然沒有求解線性二層規(guī)劃的有效方法。

對于問題(2)，筆者將互補條件作為上層目標函數(shù)的罰項構(gòu)造如下罰問題：

(3)

2 算法設計

假設如下條件滿足：

(H)線性二層規(guī)劃問題(1)的可行域S={(x,y)|A1x+A2y≤a,x,y≥0}為非空緊集。

事實上，如果條件(H)成立，則線性二層規(guī)劃問題(1)必存在最優(yōu)解[5]。

證明假設(x*,y*,w*)為線性二層規(guī)劃問題(1)的最優(yōu)解，則存在(u*,v*)滿足：

(u*)Tw*+(v*)Ty*=0

即：

定理2假設條件(H)成立，且(xk,yk,uk,vk,wk)為問題(3)的解序列，則存在k*∈R+，使得對所有的k≥k*，有(xk,yk,wk)為線性二層規(guī)劃問題(1)的最優(yōu)解。

證明令k*=k1，由定理1知定理2顯然成立。

由定理2,可以設計如下求解線性二層規(guī)劃的罰函數(shù)算法：

步1 選擇kgt;0以及步長xgt; 0。

步2 求解罰問題(3), 得到最優(yōu)解(xk,yk,uk,vk,wk)。

由定理2知，所構(gòu)造的罰函數(shù)為精確罰函數(shù)，則上述算法必在有限步內(nèi)完成計算。

3 數(shù)值試驗

s.t.-x-2y≤-10

x-2y≤6

2x-y≤21

x+2y≤38

-x+2y≤-18

s.t.-y1+y2+y3≤1

2x1-y2+2y2-0.5y3≤1

2x2+2y1-y2-0.5y3≤1用Matlab相關(guān)程序?qū)λ憷?和算例2分別求解其相應的罰問題，數(shù)值結(jié)果如表1所示。由表1知,當罰因子k=50時,計算1次可得到最優(yōu)解,這與定理2相符合,同時也表明了筆者設計算法的可行性。

表1 數(shù)值試驗結(jié)果

4 結(jié) 語

構(gòu)造了線性二層規(guī)劃的精確罰函數(shù)，并設計了線性二層規(guī)劃的罰函數(shù)算法。數(shù)值結(jié)果表明所構(gòu)造的算法對線性二層規(guī)劃是可行的，另外，所設計的算法只能保證得到線性二層規(guī)劃的局部最優(yōu)解，如何得到全局最優(yōu)解值得繼續(xù)研究。

[1]藤春賢，李智慧.二層規(guī)劃理論與應用[M].北京：科學出版社，2002.

[2]Ben-Ayed O,Blair O.Compitationd difficulty of bilevel linear programming [J].Operations Rosearch, 1990, 38:556-560.

[3]Bard J F.Partical Bilevel optimization Algorithm and Applications [M].Kluwer Academic publishers, 1998.

[4]Campelo M, Scheimberg S.A stndy of local solutions of linear bilevel programming [J].Journal of optimization theory and application, 2005,125(1):63-84.

[5]Shi C.On the definition of linear bilevel programming solution [J].Applied Mathmatics and computation，2005,160:169-176.

[6]Anandalingam G, White D J.A solution method for the linear static stackelberg problem using penalty functions[J].IEEE Transaction on Automatic control， 1990， 35(10) : 1170-1173.

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2012.01.001

O224

A

1673-1409(2012)01-N001-02