一類半向量二層規劃問題樂觀最優解的求解方法

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

?

一類半向量二層規劃問題樂觀最優解的求解方法

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

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

[關鍵詞]半向量二層規劃；線性分式；罰函數；樂觀最優解

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

(1)

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

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

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

1模型及定義

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

(1)

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

(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)的全局最優解, 如果對于任意的(x,y)∈S1, 有F(x*,y*)≤F(x,y)。

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

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

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

s.t.Ax+By≤b

問題(1)可轉化為：

(3)

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

(4)

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

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

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

(5)

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

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

2主要結果

(6)

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

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

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

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

有以下定理成立。

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

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

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

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

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

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

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

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

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

即：

3算法設計

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

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

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

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

(7)

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

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

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

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

4數值試驗

為了說明上述算法的可行性, 考慮以下線性分式半向量二層規劃問題[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　不同頂點所對應的最優解

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

5結語

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

[參考文獻]

[1]滕春賢,李智慧. 二層規劃的理論與應用[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]呂一兵,萬仲平,胡鐵松.水資源優化配置的雙層規劃模型系統工程理論與實踐[J].2009,29(6):115～120.

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

[6]王廣民,萬仲平,王先甲. 二(雙)層規劃綜述 [J].數學進展,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]任愛紅,王宇平. 求解半向量雙層規劃問題的精確罰函數法 [J].系統工程理論與研究,2014,34(4): 910～916.

[11]呂一兵,萬仲平. 線性半向量二層規劃問題的全局優化方法 [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-)，女，碩士生，現主要從事最優化理論與算法方面的研究工作。[通信作者]呂一兵(1979-)，男，博士，副教授，現主要從事最優化理論與算法方面的教學與研究工作；E-mail:lvyibing_2001@sohu.com。

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

[收稿日期]2015-10-15

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