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

?

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

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

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

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

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

(1)

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

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

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

1模型及定義

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

(1)

其中， M(x)為如下線性多目標(biāo)規(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)的可行域。若點(diǎn)(x,y)∈S1,則稱(x,y)為問題(1)的可行解。

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

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

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

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

s.t.Ax+By≤b

問題(1)可轉(zhuǎn)化為：

(3)

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

(4)

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

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

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

(5)

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

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

2主要結(jié)果

(6)

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

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

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

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

有以下定理成立。

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

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

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

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

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

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

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

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

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

即：

3算法設(shè)計(jì)

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

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

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

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

(7)

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

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

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

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

4數(shù)值試驗(yàn)

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

(8)

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

上述算例中下層問題的對(duì)偶問題為：

則：

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

其頂點(diǎn)為:

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

表1　不同頂點(diǎn)所對(duì)應(yīng)的最優(yōu)解

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

5結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

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

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

[6]王廣民,萬(wàn)仲平,王先甲. 二(雙)層規(guī)劃綜述 [J].數(shù)學(xué)進(jìn)展,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]呂一兵,萬(wàn)仲平. 線性半向量二層規(guī)劃問題的全局優(yōu)化方法 [J].運(yùn)籌學(xué)學(xué)報(bào),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.

[編輯]張濤

[文獻(xiàn)標(biāo)志碼]A

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

[中圖分類號(hào)]O224

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

[基金項(xiàng)目]國(guó)家自然科學(xué)基金項(xiàng)目(11201039)。

[收稿日期]2015-10-15

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