求線性比式和問題全局解的新方法*

靳 利

（河南機電高等專科學(xué)?；A(chǔ)部，河南新鄉(xiāng) 453000）

1 引言

考慮下面凸約束域上的線性比式和問題:

凸約束域上的線性比式和問題（P）在經(jīng)濟、財政等領(lǐng)域有著廣泛的應(yīng)用。此外凸約束域上的凹比凸比式和問題也可轉(zhuǎn)化為問題（P）。［1］雖然問題（P）的目標函數(shù)中每一項都是偽單調(diào)的，但它們的和既不是擬凸又不是擬凹的，所以問題（P）可能存在多個不是全局最優(yōu)的局部解，使得求解起來十分困難.目前，線性約束的線性比式和問題（P）已有一些有效算法，［2，3］而問題（P）的算法較少。最近，Benson［4］通過凹極小化給出問題（P）一分支定界算法。本文首先把問題（P）轉(zhuǎn)化為等價問題（Q），然后利用界的放縮技術(shù)建立了問題（Q）的松弛凸規(guī)劃（RCP），通過對（RCP）可行域的細分以及一系列（RCP）的求解過程，從理論上證明了算法的收斂性。最后，數(shù)值實驗表明該方法是有效可行的。

2 等價問題和凸化技術(shù)

顯然，若問題RCP（Hk）和Q（Hk）的最優(yōu)值分別為 v（Hk）和 μ（Hk），則 v（Hk）≤μ（Hk）。

3 分支定界算法及收斂性

下面給出求解問題（P）的分支定界算法，通過求解一系列松弛凸規(guī)劃RCP，逐步改進問題（Q）最優(yōu)值的上界和下界，最終確定問題（Q）的全局最優(yōu)解。假定在算法的第k次迭代中，Lk表示可能存在全局最優(yōu)解的子長方體構(gòu)成的集合，對于任意∈Lk，RCP（）的最優(yōu)值記為 v（），令 vk=min{v（）:∈Lk}，則vk是問題（Q）最優(yōu)值當前的一個下界。若RCP（）的最優(yōu)解是問題（P）的可行解，則更新問題（P）最優(yōu)值的上界μk，選定一子長方體Hk使得v（Hk）=vk，然后將Hk沿最長邊平分成兩部分，對每一部分求其相應(yīng)的解，重復(fù)這一過程直到滿足收斂條件為止。具體步驟如下:

步1 給定參數(shù) ε ＞0，令 k=1，Lk={H}，Hk=H，vk=－∞。求解問題RCP（Hk），設(shè)其最優(yōu)解和最優(yōu)值分別為xk和v（Hk），令vk=v（Hk）;若xk是問題（P）的可行解，則令 μk= － h（xk）。若 μk－ vk≤ε，則算法停止，即xk是問題（P）的最優(yōu)解，－μk是最優(yōu)值;否則執(zhí)行步2。

步2沿Hk的最長邊方向?qū)k平分為兩部分（r=1，2）。對任意 r∈{1，2}，求解 RCP（），設(shè)其最優(yōu)解和最優(yōu)值分別為xkr和v（）;若v（）＞μk，則刪除，否則;若是問題（P）的可行解，則令

定理2 假定問題（P）的全局最優(yōu)解存在，則算法或者在有限步內(nèi)求得問題（P）的全局最優(yōu)解，或者算法產(chǎn)生的迭代序列xk的極限點必為問題（P）的全局最優(yōu)解。

［5］中定理8.1.5。

利用Fortran95語言在Pentium（R）4微機上對下面問題進行數(shù)值計算。取ε=10－4。

算法經(jīng)12次迭代，最大節(jié)點個數(shù)為4，運行時間幾乎為0秒，得出最大值為4.8415，最優(yōu)解為x*=（0.1，2.375），結(jié)果表明本文方法是有效可行的。

（責(zé)任編輯呂春紅）

參考文獻:

［1］Benson H P.Using concave envelopes to globally solve the nonlinear sum of ratios problem［J］.Journal of Global Optimization，2002，（22）:343－364.

［2］Kuno T.A revision of the trapezoidal branch－and－bound algorithm for linear sum of ratios problems［J］.Journal of Global Optimization，2005，（33）:215－234 .

［3］Benson H P.A simplicial branch and bound duality－bounds algorithm for the linear sum －of－ratios problem［J］.Eourpean Journal of Operational Research，2007，（182）:597 －611.

［4］Benson H P.Solving sum of ratios fractional programs via concave minimization［J］.Journal of Optimization Theory Application，2007，（135）:1－17.

［5］申培萍.全局優(yōu)化方法［M］.北京:科學(xué)出版社，2006.