一類半向量二層規(guī)劃問題樂觀最優(yōu)解的求解方法

王思, 呂一兵　(長江大學信息與數(shù)學學院,湖北 荊州 434023)

?

一類半向量二層規(guī)劃問題樂觀最優(yōu)解的求解方法

王思, 呂一兵(長江大學信息與數(shù)學學院,湖北 荊州 434023)

[摘要]研究了上層為分式規(guī)劃、下層為線性多目標規(guī)劃的一類半向量二層規(guī)劃問題樂觀最優(yōu)解的求解方法。利用對偶理論, 先將半向量二層規(guī)劃問題轉化為相應的單層優(yōu)化問題, 同時取下層問題的對偶間隙與上層目標函數(shù)分母的比值作為罰項, 構造了該類半向量二層規(guī)劃問題的罰問題, 最后基于罰問題的相關性質設計了一種求解算法。數(shù)值試驗表明, 所設計的算法是可行的。

[關鍵詞]半向量二層規(guī)劃；線性分式；罰函數(shù)；樂觀最優(yōu)解

二層規(guī)劃包含上下2層, 上層和下層都有各自的目標函數(shù)和約束條件, 其中上層是以下層決策變量為參數(shù), 而下層又受制于上層決策變量的復合優(yōu)化問題[1]。由于二層規(guī)劃能夠恰當?shù)拿枋鰧嶋H問題中存在的層次關系, 因此被廣泛的應用于非平衡經濟市場競爭、資源分配、交通網絡、環(huán)境保護以及工程設計[2～5]等問題，其相關理論也受到越來越多的國內外學者的關注[6，7]。二層規(guī)劃的數(shù)學模型可以表述為:

(1)

其中, x∈Rn；y∈Rm；F:Rn×Rm→R；H：Rn×Rm→Rk；h:Rn×Rm→Rr。

當上層是一個標量優(yōu)化問題, 下層是一個向量優(yōu)化問題時, 相應的二層規(guī)劃被稱為半向量二層規(guī)劃問題。Bonnel和Morgan[8]分析了下層為凸向量優(yōu)化時解的最優(yōu)性必要條件,并給出了求解這類問題的一種精確罰函數(shù)方法。 Zheng和Wan[9]設計了包含2個不同罰因子的精確罰函數(shù)方法來求解半向量二層規(guī)劃問題, 然而, 由于算法中包含2個罰參數(shù),求解時的計算量較大。任愛紅和王宇平[10]針對這類問題, 先將其轉化為單層優(yōu)化問題, 同時提出了轉化問題的偏靜態(tài)條件定義, 并在此基礎上構造了半向量二層規(guī)劃的精確罰問題。呂一兵和萬仲平[11]針對線性半向量二層規(guī)劃問題, 將其轉化為有限個線性規(guī)劃問題, 并得到了這類問題的全局最優(yōu)解。

受上述文獻的啟發(fā), 筆者將考慮上層為線性分式單目標, 下層為線性多目標的一類半向量二層規(guī)劃問題：首先, 利用對偶規(guī)劃理論, 給出下層問題的對偶間隙； 然后, 考慮對偶間隙與上層目標函數(shù)分母的比值作為罰項, 構造了這類半向量二層規(guī)劃問題的罰問題, 最后基于罰問題的相關性質設計了一種求解算法。

1模型及定義

考慮如下半向量二層規(guī)劃問題, 其具體數(shù)學模型表述如下：

(1)

其中， M(x)為如下線性多目標規(guī)劃問題：

(2)

的弱有效解集； x∈Rn；y∈Rm；a1,a2∈Rn；b1,b2∈Rm；C∈Rl×m；A∈Rp×n；B∈Rp×m；b∈Rp,X={x|x≥0}。

定義1集合S1={(x,y)|Ax+By≤b,y∈M(x)}表示問題(1)的可行域。若點(x,y)∈S1,則稱(x,y)為問題(1)的可行解。

定義2(x*,y*)∈S1為問題(1)的全局最優(yōu)解, 如果對于任意的(x,y)∈S1, 有F(x*,y*)≤F(x,y)。

注1在問題(1)中, 由于下層為多目標規(guī)劃問題, 因此, 對于給定的上層決策變量,下層問題的最優(yōu)解一般是不唯一的． 對于下層有不唯一最優(yōu)解的二層規(guī)劃問題, 其最優(yōu)解的定義一般采用樂觀最優(yōu)解或悲觀最優(yōu)解[12]。筆者考慮采用樂觀最優(yōu)解的定義。

在下面的研究中，假設如下條件成立：

(A1)約束域S={(x,y)|Ax+By≤b,x≥0,y≥0}以及集合X均為非空緊集。

s.t.Ax+By≤b

問題(1)可轉化為：

(3)

利用線性規(guī)劃的對偶理論, 得到問題(3)的下層對偶問題為：

(4)

其中， ?∈Rp(行向量)為對偶變量。

記W={?|-?B≤λTC, ?≥0}, 對偶間隙π(x,y,λ,?)=λTCy+?b-?Ax，關于問題(1)和問題(3)最優(yōu)解的關系, 有以下結果。

定理1假設條件(A1)成立,(x*,y*,λ*)為問題(3)的最優(yōu)解, 當且僅當存在?*∈W, 使得(x*,y*,λ*,?*)為如下問題：

(5)

的最優(yōu)解, 同時(x*,y*)為問題(1)的最優(yōu)解。

證明由對偶理論可知, 一定存在?*∈W, 使得?*為問題(5)的最優(yōu)解。對于固定的(x*,λ*)且滿足λTCy+?b-?Ax=0, 則y*為下層問題的最優(yōu)解, 故(x*,y*)也是問題(1)的最優(yōu)解。

2主要結果

(6)

其中,μ∈R+是罰參數(shù)；(x,y,λ,?)∈S×U。

關于問題(5)和問題(6)最優(yōu)解之間的關系, 有下面的結果。

引理1若(xμ,yμ,λμ,?μ)是問題(6)的最優(yōu)解, 并且它也是問題(5)的可行解, 則它也是問題(5)的最優(yōu)解。

對于給定的(λ，?)∈U及μ∈R+, 定義：

有以下定理成立。

定理2假設條件(A1)成立, 則問題：

的最優(yōu)解(λ*,?*)一定在其多面體的極點處取得。

證明首先證明φμ(λ,?)是凹函數(shù)。取集合U中任意2點(λ1,?1),(λ2,?2)，η∈(0,1), 則有：

φμ(η(λ1,?1)+(1-η)(λ2,?2))

=ηφμ(λ1,?1)+(1-η)φμ(λ2,?2)

故φμ(λ,?)為凹函數(shù)。又由于集合U為多面體, 則在多面體約束條件下的極小化凹函數(shù),其最優(yōu)解一定在U的極點處取得。

定理3假設條件(A1)成立, 則問題(6)的最優(yōu)解(x*,y*,λ*, ?*)∈SE×UE。

證明若(x*,y*)為問題(1)的最優(yōu)解, 則一定存在(λ*,?*)∈U, 使得：

又由于(xμ,yμ,λμ,?μ)是問題(6)的最優(yōu)解, 則有：

即：

3算法設計

根據上述性質, 筆者設計一種求解問題(6)的算法，算法描述如下：

步1選取初始值μ>0及δ>0。

步2利用線性規(guī)劃技術求得多面體U的所有頂點, 記為UE={u1,u2,…,ut}, 令i=1。

步3求解下面的問題P(λi,?i)：

(7)

求得最優(yōu)解為(xi,yi)。

注2該算法需要求出下層對偶問題可行域多面體U的全部頂點, 即UE, 這是算法實現(xiàn)的關鍵點之一, 求解多面體頂點方法可參考文獻[16]。

定理6上述算法所得到的解為問題(1)的最優(yōu)解。

證明由定理1以及引理1, 定理6顯然成立。

4數(shù)值試驗

為了說明上述算法的可行性, 考慮以下線性分式半向量二層規(guī)劃問題[14]：

(8)

圖1表示原問題(8)的約束域和可行域, 當上層固定一個決策變量x, 下層問題y的取值如虛線所示。

上述算例中下層問題的對偶問題為：

則：

U={(λ,?)∈R2+6|λ1+λ2=1,3?1-4?2-3?3-2?4+?5+4?6≤λ1+2λ2,λ≥0,?≥0}

其頂點為:

(λ2,?2)=(1,0,0,0,0,0,1,0)

表1　不同頂點所對應的最優(yōu)解

圖1　原問題(8)的約束域和可行域

5結語

研究了一類線性分式半向量二層規(guī)劃問題樂觀最優(yōu)解的求解方法, 利用對偶理論,將其轉化為單層優(yōu)化問題, 同時取下層問題的對偶間隙與上層目標函數(shù)分母的比值作為罰項, 構造了線性分式半向量二層規(guī)劃的罰問題, 基于罰問題的相關性質設計了一種求解算法。數(shù)值結果表明, 所設計的算法是可行的。值得說明的是, 由于分式半向量二層規(guī)劃是個比較復雜的問題, 筆者只討論了上層為線性分式的情況, 進一步將針對上層為非線性分式討論其最優(yōu)解的取值情況。

[參考文獻]

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

[2]GaoZiyou,SunHuijun,ZhangHaozhi.Agloballyconvergentalgorithmfortransportationcontinuousnetworkdesignproblem[J].OptimizationandEngineering,2007,8(3): 241～257.

[3]ErhanErkut,FatmaGzara.Solvingthehazmattransportnetworkdesignproblem[J].ComputersOperationsResearch,2007,35: 2234～2247.

[4]呂一兵,萬仲平,胡鐵松.水資源優(yōu)化配置的雙層規(guī)劃模型系統(tǒng)工程理論與實踐[J].2009,29(6):115～120.

[5]劉娟娟,范炳全,祝炳發(fā). 雙層規(guī)劃在城市交通污染控制中的一個應用[J]. 管理工程學報,2005(4):87～90.

[6]王廣民,萬仲平,王先甲. 二(雙)層規(guī)劃綜述 [J].數(shù)學進展,2007,36: 513～529.

[7]ColsonB,MarcotteP,SavardG.Anoverviewofbileveloptimization[J].AnnalsofoperationsResearchannals,2007,153(1): 235～256.

[8]BonnelH,MorganJ.Semivectorialbileveloptimizationproblem:Penaltyapproach[J].JournalofOptimizationTheoryandApplications,2006,31(3): 365～382.

[9]ZhengY,WanZ.Asolutionmethodforsemivectorialbilevelprogrammingproblemviapenaltymethod[J].JournalofAppliedMathematicsandComputing, 2011,37: 207～219.

[10]任愛紅,王宇平. 求解半向量雙層規(guī)劃問題的精確罰函數(shù)法 [J].系統(tǒng)工程理論與研究,2014,34(4): 910～916.

[11]呂一兵,萬仲平. 線性半向量二層規(guī)劃問題的全局優(yōu)化方法 [J].運籌學學報,2015,19(2): 29～36.

[12]DempeS.Foundationsofbilevelprogramming[M].London:KluwerAcademicPublishers,2002.

[13]LvY,WanZ.Asolutionmethodfortheoptimisticlinearsemiveetorialbileveloptimizationproblem[J].JournalofInequalitiesandApplications,2014: 164.

[14]PedroCerbuna.Apenaltymethodforsolvingbilevellinearfractional/linearprogrammingproblems[J].Asia-PacificJournalofOperationalResearch,2004,207～224.

[15]BazaraaMS,SheraliHD，ShettyCM.NonlinearProgramming:TheoryandAlgorithms[M].2nded.NewYork:JohnWileyandSons,1993.

[16]MatheissRH,RubinDS.Asurveyandcomparisonofmethodsforfindingallverticesofconvexpolyhedralsets[J].MathernaticsofOperations,1980,5(2): 167～185.

[編輯]張濤

[文獻標志碼]A

[文章編號]1673-1409(2016)01-0001-06

[中圖分類號]O224

[作者簡介]王思(1990-)，女，碩士生，現(xiàn)主要從事最優(yōu)化理論與算法方面的研究工作。[通信作者]呂一兵(1979-)，男，博士，副教授，現(xiàn)主要從事最優(yōu)化理論與算法方面的教學與研究工作；E-mail:lvyibing_2001@sohu.com。

[基金項目]國家自然科學基金項目(11201039)。

[收稿日期]2015-10-15

[引著格式]王思, 呂一兵.一類半向量二層規(guī)劃問題樂觀最優(yōu)解的求解方法[J].長江大學學報(自科版)，2016,13(1)：1～6.