一類線性多乘積規(guī)劃的分支定界算法

趙營(yíng)峰,尹景本

（河南科技學(xué)院,河南新鄉(xiāng)453003）

一類線性多乘積規(guī)劃的分支定界算法

趙營(yíng)峰,尹景本

（河南科技學(xué)院,河南新鄉(xiāng)453003）

針對(duì)廣泛應(yīng)用于金融及經(jīng)濟(jì)等實(shí)際問題中的一類線性多乘積規(guī)劃問題,提出一種分段線性化全局優(yōu)化算法.首先將問題轉(zhuǎn)化為等價(jià)問題,然后利用分段線性化技術(shù)得到問題目標(biāo)函數(shù)和約束函數(shù)的線性下界,構(gòu)造出等價(jià)問題的松弛線性規(guī)劃,并從理論上證明了算法的收斂性.數(shù)值試驗(yàn)表明算法是有效可行的.

多乘積規(guī)劃；分支定界；松弛線性規(guī)劃

多乘積規(guī)劃廣泛應(yīng)用于產(chǎn)品計(jì)劃、任務(wù)管理、化學(xué)工程設(shè)計(jì)、交通運(yùn)輸和商業(yè)等很多領(lǐng)域[1-4].本文針對(duì)一類特殊的線性多乘積規(guī)劃問題提出了一種新的分枝定界算法,該算法在理論上具有重要意義,很多數(shù)學(xué)規(guī)劃是其特殊情形或者可以轉(zhuǎn)化為多乘積規(guī)劃[5-9].針對(duì)多乘積規(guī)劃問題,首先利用恒等變形,建立了原問題的等價(jià)問題,然后對(duì)等價(jià)問題進(jìn)行松弛得到松弛線性規(guī)劃,通過對(duì)松弛線性規(guī)劃的可行域的細(xì)分以及一系列線性規(guī)劃的求解,不斷更新上下界,并從理論上證明了算法收斂到原問題的全局最優(yōu)解.

1 松弛線性規(guī)劃

考慮如下線性多乘積規(guī)劃問題

根據(jù)x2i在區(qū)間[li,ui]上的幾何性質(zhì)可知

且

因而令

可得到問題（P）在Sk上的松弛線性規(guī)劃

2 分支定界算法

下面給出分支定界算法,通過求解一系列松弛線性規(guī)RLP（Sk）,逐步改進(jìn)原問題（P）的最優(yōu)值的上界和下界,最終確定（P）的全局最優(yōu)解：

步驟1.給定收斂參數(shù)ε＞0,可行點(diǎn)集F=Φ,置迭代次數(shù)k=1,上界uk=∞,活動(dòng)節(jié)點(diǎn),求Lk={Sk}解松弛線性規(guī)劃RLP（Sk）,設(shè)其最優(yōu)解和最優(yōu)值分別為xk*和vk=φ（xk*）,令下界lk=vk,若xk*是原問題（P）的可行解,則令uk=f（xk*）,若uk-lk≤ε,算法停止,且xk*和vk=φ（xk*）就是原問題的全局最優(yōu)解和最優(yōu)值,否則執(zhí)行步驟2.

步驟2.沿著垂直于Sk的最長(zhǎng)邊方向平均分割Sk為兩部分設(shè)為S1k、S2k,然后分別求解RLP（Stk）,t=1,2.假設(shè)求得的最優(yōu)解和最優(yōu)值分別為xkt*和vk=φ（xkt*）,如果xkt*對(duì)原問題（P）可行,則令F=F∪{x（Stk）}, uk=min{uk,f（xkt*）}.

定理2若問題（P）的全局最優(yōu)解存在,則算法或在有限步內(nèi)求得問題（P）的全局最優(yōu)解,或產(chǎn)生收斂到問題全局最優(yōu)解的迭代序列{yk}.

證明：若算法在有限步內(nèi)終止,則根據(jù)算法知算法終止時(shí)uk-lk=f（xk*）-φ（xk*）ε.設(shè)v為問題的全局最優(yōu)值,因?yàn)閤k*是問題的一個(gè)可行解,所以

因此

命題成立.

如果算法產(chǎn)生一個(gè)無限迭代序列{yki},由于原問題的可行域是緊的,可設(shè)y*是它的一個(gè)聚點(diǎn),則存在子序{yk}列收斂到y(tǒng)*.由算法知uk是單調(diào)遞減有界序列,lk是單調(diào)遞增有界序列,所以

不妨設(shè)序列{yki}對(duì)應(yīng)的序列對(duì)原問題是可行的.

由于

所以

而舉行的二分法是窮舉的且f（x）和φ（x）都是連續(xù)函數(shù),因而

即

故y*是原問題的全局最優(yōu)解.

3 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證本文算法的可行性及有效性,采用Matlab編寫程序,其中的線性規(guī)劃采用單純形方法求解,計(jì)算如下例題

經(jīng)上機(jī)測(cè)試,算法僅經(jīng)1次迭代即達(dá)到問題的全局最優(yōu)解（2.0,8.0）.數(shù)值實(shí)驗(yàn)說明本算法是高效可行的.

4 小結(jié)

本文針對(duì)一類多乘積線性規(guī)劃問題,提出了一種新的分支定界收算法,數(shù)值實(shí)驗(yàn)表明算法高效可行.

[1]Konno H,Yajima Y,Matsui T.Parametric simplex algorithms for solving a special class of nonconvexminimization problems[J]. JournalofGlobalOptimization,1991,1（1）：65-81.

[2]Benson H P,BogerGM.Outcome-space cutting-planealgorithm for linearmulti-plicative programming[J].JournalofOptimization Theory and Applications,2000,104（2）：301-322.

[3]CploantoniCS,Manes R P,Whinston A.Programming,profit rates and pricing decisions[J].The Accounting Review,1969,44（3）：467-481.

[4]Ellero A.The optimal levelsolutionsmethod[J].Journalof Information&Optimization Sciences,1996,17（2）：355-372.

[5]Konno H,Watanabe H.Bond portfolio optimization problems and their application to index tracking：a partial optimization approach[J].Journalof theOperations Research Society of Japan,1996,39（3）：285-306.

[6]Kuno T.A finite branch-and-bound algorithm for linear multiplicative programming[J].Computational Optimization and Application,2001,20（2）：119-135.

[7]Kuno T.Globally determining a minimun-aera rectangle enclosing the projection of a higer dinmensional[J].Operations Research Letters,1993,13（5）：295-303.

[8]Jiao H W,Guo Y R,Shen P P.Global optimization of generalized linear fractional programming with nonlinear constraints[J]. Applied Mathematicsand Computation,2006,183（2）：717-728.

[9]Ryoo H S,SahinidisNV.GlobalOptimization ofmultiplicative programs[J].JournalofGlobalOptimization,2003,26（4）：387-418.

（責(zé)任編輯：盧奇）

A global Optim ization Algorithm for a class of linear multip licative programm ing

Zhao Yingfeng,Yin jingben
（Henan InstituteofScienceand Technology,Xinxiang453003,China）

In this paper a piecewise linearization global Optimization Algorithm is proposed for the linear multiplicative programming,which has a lot of important applications in various areas such as financial optimization and economy plan．Firstly,the original program is transformed into the equivalent problems．Second,utilizing piecewise linearization technique,linear underestimates of the objective and constraint functions,linear relaxation programming for linearmultiplicative programming is established over a rectangle,and the proposed global optimization algorithm is proposed that can converge to the globally optimal solution．And finally the numerical experiments are given to illustrate that the proposed algorithm is effective and feasible．

multiplicative programming；branch and bound；linear relaxation programming

O221.1

A

1008-7516（2013）03-0086-04

10．3969/j．issn．1008-7516．2013．03．018

2013-04-23

河南省高等學(xué)校青年骨干教師資助計(jì)劃（2010GGJS-140）；河南省教育廳自然科學(xué)研究項(xiàng)目（2010B110010）

趙營(yíng)峰（1982-）,男,河南輝縣人,講師．主要從事最優(yōu)化理論與算法研究．