求线性比式和问题全局解的新方法*

靳 利

（河南机电高等专科学校基础部，河南新乡 453000）

1 引言

考虑下面凸约束域上的线性比式和问题:

凸约束域上的线性比式和问题（P）在经济、财政等领域有着广泛的应用。此外凸约束域上的凹比凸比式和问题也可转化为问题（P）。［1］虽然问题（P）的目标函数中每一项都是伪单调的，但它们的和既不是拟凸又不是拟凹的，所以问题（P）可能存在多个不是全局最优的局部解，使得求解起来十分困难.目前，线性约束的线性比式和问题（P）已有一些有效算法，［2，3］而问题（P）的算法较少。最近，Benson［4］通过凹极小化给出问题（P）一分支定界算法。本文首先把问题（P）转化为等价问题（Q），然后利用界的放缩技术建立了问题（Q）的松弛凸规划（RCP），通过对（RCP）可行域的细分以及一系列（RCP）的求解过程，从理论上证明了算法的收敛性。最后，数值实验表明该方法是有效可行的。

2 等价问题和凸化技术

显然，若问题RCP（Hk）和Q（Hk）的最优值分别为 v（Hk）和 μ（Hk），则 v（Hk）≤μ（Hk）。

3 分支定界算法及收敛性

下面给出求解问题（P）的分支定界算法，通过求解一系列松弛凸规划RCP，逐步改进问题（Q）最优值的上界和下界，最终确定问题（Q）的全局最优解。假定在算法的第k次迭代中，Lk表示可能存在全局最优解的子长方体构成的集合，对于任意∈Lk，RCP（）的最优值记为 v（），令 vk=min{v（）:∈Lk}，则vk是问题（Q）最优值当前的一个下界。若RCP（）的最优解是问题（P）的可行解，则更新问题（P）最优值的上界μk，选定一子长方体Hk使得v（Hk）=vk，然后将Hk沿最长边平分成两部分，对每一部分求其相应的解，重复这一过程直到满足收敛条件为止。具体步骤如下:

步1 给定参数 ε ＞0，令 k=1，Lk={H}，Hk=H，vk=－∞。求解问题RCP（Hk），设其最优解和最优值分别为xk和v（Hk），令vk=v（Hk）;若xk是问题（P）的可行解，则令 μk= － h（xk）。若 μk－ vk≤ε，则算法停止，即xk是问题（P）的最优解，－μk是最优值;否则执行步2。

步2沿Hk的最长边方向将Hk平分为两部分（r=1，2）。对任意 r∈{1，2}，求解 RCP（），设其最优解和最优值分别为xkr和v（）;若v（）＞μk，则删除，否则;若是问题（P）的可行解，则令

定理2 假定问题（P）的全局最优解存在，则算法或者在有限步内求得问题（P）的全局最优解，或者算法产生的迭代序列xk的极限点必为问题（P）的全局最优解。

［5］中定理8.1.5。

利用Fortran95语言在Pentium（R）4微机上对下面问题进行数值计算。取ε=10－4。

算法经12次迭代，最大节点个数为4，运行时间几乎为0秒，得出最大值为4.8415，最优解为x*=（0.1，2.375），结果表明本文方法是有效可行的。

（责任编辑吕春红）

参考文献:

［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］申培萍.全局优化方法［M］.北京:科学出版社，2006.