線性比式和分式規(guī)劃問題的分支定界算法*

申培萍,李丹華

(河南師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,河南新鄉(xiāng)　453007)

?

線性比式和分式規(guī)劃問題的分支定界算法*

申培萍,李丹華

(河南師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,河南新鄉(xiāng)453007)

(College of Mathematics and Information Science,Henan Normal University,Xinxiang,Henan,453007,China)

摘要:針對線性比式和問題(P)提出一種新的分支定界算法,并進行數(shù)值驗證.該算法把問題轉(zhuǎn)換成等價問題，并利用線性松弛技術(shù)建立問題的松弛線性規(guī)劃,從而將原始的非凸規(guī)劃問題歸結(jié)為一系列線性規(guī)劃問題，通過可行域的連續(xù)細(xì)分以及求解一系列線性松弛規(guī)劃,得出的算法收斂到問題(P)的全局最優(yōu)解.數(shù)值算例結(jié)果表明算法是可行有效的.

關(guān)鍵詞：線性比式和全局優(yōu)化線性松弛分支定界ω分法

0　引言

【研究意義】線性比式和優(yōu)化問題在運輸計劃,政府規(guī)劃及經(jīng)濟投資等領(lǐng)域有著重要的作用[1].考慮如下線性比式和問題:

1　預(yù)備知識

2　算法及其收斂性

令N={1,2,…,n},ρj=min{uj-ωj,ωj-lj},j∈N,q∈arg max{ρj|j∈N}.

這樣X就被分割成兩個子盒子X1=[l′,u]和X2=[l,u′],其中,

l′=(l1,…,lq -1,ωq,lq +1,…,ln),

u′=(u1,…,uq -1,ωq,uq +1,…,un).

求解問題Q(Xk)得最優(yōu)解和最優(yōu)值分別為yk和LB(Xk)=g(yk).令

由上述算法可知,在迭代過程中至少會產(chǎn)生一個嵌套的盒子序列,不妨仍記為{Xk},那么每個盒子的上下界及分割點ωk所產(chǎn)生的序列{lk},{ωk},{uk}滿足如下條件:

lk≤lk+1≤ωk+1≤uk+1≤uk,k=1,2,….

(1)

而由ρj及q的定義知,

?x∈D.

證明(i)若算法經(jīng)過k次迭代終止,結(jié)論顯然成立;否則,由算法可知,

(2)

(3)

則有

這與(3)式矛盾,故假設(shè)不成立.即有

即

那么對?x∈D,有

UBk-LB(Xk)≤,

所以,對任意x∈D,有

3　數(shù)值實驗

為驗證算法的可行性,在AMD A8 CPU(主頻 1.9 GHz)4 GB內(nèi)存的微機上用Matlab(2012b)進行數(shù)值計算.

例1[2]

s.t.2x1+x2+5x3≤10,

x1+6x2+3x3≤10,

5x1+9x2+2x3≤10,

9x1+7x2+3x3≤10,

x1,x2,x3≥0.

其中,a1(x)=4x1+3x2+3x3+50,a2(x)=3x1+

4x2+50,a3(x)=x1+2x2+5x3+50,a4(x)=x1+2x2+4x3+50,b1(x)=3x2+3x3+50,b2(x)=

4x1+4x2+5x3+50,b3(x)=x1+5x2+5x3+50,b4(x)=5x2+4x3+50.

例2[1]

s.t.6x1+3x2+3x3≤10,

10x1+3x2+8x3≤10,

x1,x2,x3≥0.

其中,a1(x)=3x1+4x2+50,a2(x)=3x1+5x2+

3x3+50,a3(x)=x1+2x2+4x3+50,a4(x)=4x1+3x2+3x3+50,b1(x)=3x1+5x2+4x3+50,b2(x)=5x1+5x2+4x3+50,b3(x)=5x2+4x3+50,b4(x)=3x2+3x3+50.

數(shù)據(jù)結(jié)果表明,本文算法是可行的.

4　結(jié)論

參考文獻(xiàn)：

[1]SHEN P P,WANG C F.Global optimization for sum of linear ratios problem with coefficients[J].Applied Mathematics and Computation,2006,176(1):219-229.

[2]JIAO H W,LIU S Y.A practicable branch and bound algorithm for sum of linear ratios problem[J].European Journal of Operational Research,2015,243(3):723-730.

[3]CARLSSON J G,SHI J M.A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension[J].Operations Research Letters,2013,41(4):381-389.

[4]張永紅,汪春峰.求線性比式和問題全局解的一個新方法[J].應(yīng)用數(shù)學(xué)學(xué)報,2012,35(1):42-48. ZHANG Y H,WANG C F.A new global algorithm for sum of linear ratios problem[J].Acta Mathematicae Applicatae Sinica,2012,35(1):42-48.

[5]WANG C F,SHEN P P.A global optimization algorith- m for linear fractional programming[J].Applied Mathematics and Computation,2008,204(1):281-287.

[6]KUNO T,MASAKI T.A practical but rigorous approa- ch to sum-of-ratios optimization in geometric applications[J].Computational Optimization and Applications,2013,54(1):93-109.

(責(zé)任編輯：尹闖)

A Branch and Bound Algorithm for the Sum of Linear Ratios Problem

SHEN Peiping,LI Danhua

Key words：sum of linear ratios,global optimization,linear relaxation,branch and bound,ω division

Abstract：In this paper,we presents a new branch and bound algorithm for globally solving the sum of linear ratios problem,which is verified by the numerical examples.The algorithm transform the problem to its equivalent problem,and establish a relaxational linear programming problem of by using a linear relaxation technique,thus the initial nonconvex programming problem is reduced to a sequence of linear programming problems.The proposed algorithm is convergent to the global minimum of (P) through the successive refinement of the feasible region and solutions of a series of relaxation linear programming,and finally numerical examples are given to illustrate the feasibility and effectiveness of the proposed algorithm.

收稿日期：2016-08-15

作者簡介：申培萍(1964-)，女，博士，教授，主要從事最優(yōu)化理論與應(yīng)用研究。

中圖分類號:O221.2

文獻(xiàn)標(biāo)識碼：A

文章編號：1005-9164(2016)05-0392-04

*國家自然科學(xué)基金項目(11171094)資助。

廣西科學(xué)Guangxi Sciences 2016,23(5):392～395

網(wǎng)絡(luò)優(yōu)先數(shù)字出版時間：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.011

網(wǎng)絡(luò)優(yōu)先數(shù)字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1546.022.html