求二層線性規劃最優解的極點方法

求二層線性規劃最優解的極點方法*

趙禮陽1， 霍永亮2

(1.重慶師范大學 數學學院,重慶 401331;2.重慶文理學院 數學與財經學院,重慶 402160)

摘要：根據二層線性規劃的最優解一定可以在約束集的極點找到這一理論，給出了求解二層線性規劃的極點方法，通過上層目標函數值的排序，避免了盲目驗證極點這一缺陷，最后通過算例描述了算法求解過程，并驗證了算法的有效性.

關鍵詞：二層線性規劃；約束條件；全局最優解；極點

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

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

基金項目：*重慶高校創新團隊建設計劃項目(KJ301321).

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

中圖分類號：O221.5文獻標志碼：A

0引言

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

s.t.Ax+Bx≤b

(1)

二層線性規劃問題是二層規劃問題中最簡單的一種類型，在二層線性規劃問題中，其目標函數和約束條件都是線性存在的[1,2].對于二層規劃，由于下層目標函數要以上層決策變量作為參數，上層又要以下層最優解反饋作為條件達到上層的最優，使得二層規劃比一般的數學規劃為更為復雜[3].

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

此處根據二層線性規劃的全局最優解一定可以在約束域極點找到的理論，首先求出約束域的所有極點，根據極點處上層目標函數的值由小到大進行極點排序，然后按照這個順序進行最優解檢驗，最終確定問題的全局最優，此處最后通過算例驗證了算法的有效性.

1基本理論

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

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

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

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

(2)

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

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

(3)

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

(4)

又因為(x0,y0)是式(1)的唯一最優解，則

(5)

(6)

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

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

于是成立等式：

(7)

2算法描述

因為線性二層規劃的全局最優解一定出現在該問題約束集的極點處，因此在約束集空間的極點上面就能搜索到問題的全局最優解.基于這種思想，設計一種快速極點算法，具體步驟描述如下：

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

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

第3步:把xi帶入下層目標函數f(x,y)，求解f(xi,y)在約束集S中的最優解yi+1，轉第4步；

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

3數值實驗

例1

s.t.y+2x≤12

2y-3x≥-4

y-2x≤0

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

圖1　約束域

4小結

因為二層線性規劃問題反饋最優解集的非凸性，給求解二層線性規劃問題帶來了一定困難，此處給出的求解二層規劃全局最優解的方法，簡單易行，并且具有一定的應用價值.針對極點的重新排序，相對隨機取初始迭代點，此方法能更快的找到全局最優解，最后的算例驗證了算法的有效性.

參考文獻：

[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] 陶玉潔，張永，楊杰.二層線性規劃求頂點的算法[J].通化師范學院學報，2007，28(4):8-10

[9] 胡長英.雙層規劃理論及其在管理中的應用[M].北京：知識產權出版社，2012

[10] 李宏衛，王軍.三次型非線性包裝系統跌落沖擊響應分析[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