求二層線性規(guī)劃最優(yōu)解的極點(diǎn)方法*

趙禮陽1， 霍永亮2

(1.重慶師范大學(xué) 數(shù)學(xué)學(xué)院,重慶 401331;2.重慶文理學(xué)院 數(shù)學(xué)與財(cái)經(jīng)學(xué)院,重慶 402160)

摘要：根據(jù)二層線性規(guī)劃的最優(yōu)解一定可以在約束集的極點(diǎn)找到這一理論，給出了求解二層線性規(guī)劃的極點(diǎn)方法，通過上層目標(biāo)函數(shù)值的排序，避免了盲目驗(yàn)證極點(diǎn)這一缺陷，最后通過算例描述了算法求解過程，并驗(yàn)證了算法的有效性.

關(guān)鍵詞：二層線性規(guī)劃；約束條件；全局最優(yōu)解；極點(diǎn)

doi:10.16055/j.issn.1672-058X.2015.0011.021

收稿日期：2015-04-14；修回日期：2015-05-20.

基金項(xiàng)目：*重慶高校創(chuàng)新團(tuán)隊(duì)建設(shè)計(jì)劃項(xiàng)目(KJ301321).

作者簡介：趙禮陽(1990-)，男，重慶大足人，碩士研究生，從事最優(yōu)化理論研究.

中圖分類號(hào)：O221.5文獻(xiàn)標(biāo)志碼：A

0引言

考慮如下二層線性規(guī)劃問題(LBP)：

s.t.Ax+Bx≤b

(1)

二層線性規(guī)劃問題是二層規(guī)劃問題中最簡單的一種類型，在二層線性規(guī)劃問題中，其目標(biāo)函數(shù)和約束條件都是線性存在的[1,2].對(duì)于二層規(guī)劃，由于下層目標(biāo)函數(shù)要以上層決策變量作為參數(shù)，上層又要以下層最優(yōu)解反饋?zhàn)鳛闂l件達(dá)到上層的最優(yōu)，使得二層規(guī)劃比一般的數(shù)學(xué)規(guī)劃為更為復(fù)雜[3].

Candler[4]和Townsley[5]在研究上層為無約束，且下層有唯一解的二層線性規(guī)劃時(shí)得到一個(gè)有趣的性質(zhì)：假設(shè)二層線性規(guī)劃的最優(yōu)解個(gè)數(shù)為有限個(gè)，那么在約束集的極點(diǎn)(頂點(diǎn))處，至少存在一個(gè)極點(diǎn)是該問題的最優(yōu)解.之后，Bard在約束集有界的前提下，證明了這是二層線性規(guī)劃的一個(gè)共性[6].

此處根據(jù)二層線性規(guī)劃的全局最優(yōu)解一定可以在約束域極點(diǎn)找到的理論，首先求出約束域的所有極點(diǎn)，根據(jù)極點(diǎn)處上層目標(biāo)函數(shù)的值由小到大進(jìn)行極點(diǎn)排序，然后按照這個(gè)順序進(jìn)行最優(yōu)解檢驗(yàn)，最終確定問題的全局最優(yōu)，此處最后通過算例驗(yàn)證了算法的有效性.

1基本理論

定義1IR={(x,y):(x,y)∈S,y∈P(x)}為式(1)的可歸納域(可行集).

為了保證式(1)有解，假設(shè)S為非空有界閉集；并且對(duì)于任意給定的上層決策變量，下層都只有唯一最優(yōu)解反饋給上層.

定義2稱(x*,y*)為問題(LBP)的全局最優(yōu)解，簡稱最優(yōu)解.如果存在(x*,y*)∈IR，使得對(duì)任意的(x,y)∈IR，都有F(x*,y*)≤F(x,y)成立[7].

定義3如果(x0,y0)是S的任意一個(gè)極點(diǎn)(頂點(diǎn))，則對(duì)于S中相異于(x0,y0)的任意兩點(diǎn)(x1,y1),(x2,y2)∈S，以及任意的實(shí)數(shù)λ>0，λ∈(0,1)，下面等式(2)不成立.

(2)

定理1如果(x0,y0)是式(1)的唯一最優(yōu)解，則(x0,y0)必是式(1)約束集的極點(diǎn).

證明反證法.假設(shè)(x0,y0)是式(1)的唯一最優(yōu)解，但(x0,y0)不是式(1)約束集的頂點(diǎn)，則由定義3可得，存在(x1,y1),(x2,y2)∈S，且(x1,y1)≠(x0,y0)，(x2,y2)≠(x0,y0)，存在一正數(shù)λ∈(0,1)，等式(3)成立：

(3)

于是有λx1+(1-λ)x2=x0，λy1+(1-λ)y2=y0，那么(λx1+(1-λ)x2,λy1+(1-λ)y2)也是式(1)的最優(yōu)解，顯然成立等式(4)：

(4)

又因?yàn)?x0,y0)是式(1)的唯一最優(yōu)解，則

(5)

(6)

λ與(1-λ)分別乘入式(5)(6)，相加得

這就與F(x0,y0)=F(λx1+(1-λ)x2,λy1+(1-λ)y2)矛盾，故定理得證.

于是成立等式：

(7)

2算法描述

因?yàn)榫€性二層規(guī)劃的全局最優(yōu)解一定出現(xiàn)在該問題約束集的極點(diǎn)處，因此在約束集空間的極點(diǎn)上面就能搜索到問題的全局最優(yōu)解.基于這種思想，設(shè)計(jì)一種快速極點(diǎn)算法，具體步驟描述如下：

第1步:求出二層線性規(guī)劃約束集合S的所有極點(diǎn)(xi,yi),i=1,2,…,n，不妨假設(shè)對(duì)于任意(xp,yp)和(xq,yq)，滿足p

第2步:給定問題一個(gè)初始解(xi,yi)，i=1，i≤n，轉(zhuǎn)第3步；

第3步:把xi帶入下層目標(biāo)函數(shù)f(x,y)，求解f(xi,y)在約束集S中的最優(yōu)解yi+1，轉(zhuǎn)第4步；

第4步:比較yi+1和yi值，如果yi+1=yi，停止計(jì)算，輸出全局最優(yōu)解(xi,yi)；否則令i=i+1，轉(zhuǎn)第3步.

3數(shù)值實(shí)驗(yàn)

例1

s.t.y+2x≤12

2y-3x≥-4

y-2x≤0

很容易，能得到約束域S如圖1所示.

圖1　約束域

4小結(jié)

因?yàn)槎泳€性規(guī)劃問題反饋?zhàn)顑?yōu)解集的非凸性，給求解二層線性規(guī)劃問題帶來了一定困難，此處給出的求解二層規(guī)劃全局最優(yōu)解的方法，簡單易行，并且具有一定的應(yīng)用價(jià)值.針對(duì)極點(diǎn)的重新排序，相對(duì)隨機(jī)取初始迭代點(diǎn)，此方法能更快的找到全局最優(yōu)解，最后的算例驗(yàn)證了算法的有效性.

參考文獻(xiàn)：

[1] BENSION H P. On the Structure and Properities of a Linear Multilevel Programming Problem[J]. Journal of Operation Theory and Applications，1989(60):353-373

[2] BEREANU B. Stable Stochastic Linear Programs and Applications[J]. Mathematischen Operation for Schung and Statistik,1975,6(4):593-607

[3] BIALAS W F,KARWAN M H. Two-level Linear Programming[J]. Managenment Science,1984,30(8):1004-1020

[4] CANDLER W，Norton R. Mulilevel Programming and Development Policy[R]. Technical Report 258，World Bank Staff，Washington DC,1977

[5] CANDLER W， TOWNSLEY R. A Linear Two-level Programming Problem[J]. Computers and Operations Research,1982,9(1):59-76

[6] BARD,J F. An Investigation of the Linear Three Level Programming Problem[J]. IEEE Transaction System,Man and Cybernetics,1984,14(5):711-717

[7] BRACKEN J，MCGILL J T. Mathematical Programs with Optimization Problems in the Constraints[J]. Operation Research，1973,21(1):37-44

[8] 陶玉潔，張永，楊杰.二層線性規(guī)劃求頂點(diǎn)的算法[J].通化師范學(xué)院學(xué)報(bào)，2007，28(4):8-10

[9] 胡長英.雙層規(guī)劃理論及其在管理中的應(yīng)用[M].北京：知識(shí)產(chǎn)權(quán)出版社，2012

[10] 李宏衛(wèi)，王軍.三次型非線性包裝系統(tǒng)跌落沖擊響應(yīng)分析[J].包裝工程：工程版，2015(19)：18-22

The Method of Getting Extreme Point of the Optimal Solution toBilevel Linear Programming

ZHAO Li-yang1,HUO Yong-liang2

(1.School of Mathematical Sciences,Chongqing Normal University,Chongqing 401331,China; 2.School of

Mathematics and Finance,Chongqing University of Arts and Sciences,Chongqing 402160,China )

Abstract：According to the theory that the optimal solution to bilevel linear programming can be found on the extreme point of the constraint set,a method of getting extreme point of bilevel linear programming is presented. Through the top objective function sorting,this method avoids the shortcoming of verifing extreme point aimlessly. Finally,calculation example describles the perocess of algorithm for solving,and the effectiveness of the algorithm is verified.

Key words： bilevel linear programming; constraint condition; globle optimal solution; exeme point