线性比式和分式规划问题的分支定界算法*

申培萍,李丹华

(河南师范大学数学与信息科学学院,河南新乡　453007)



线性比式和分式规划问题的分支定界算法*

申培萍,李丹华

(河南师范大学数学与信息科学学院,河南新乡453007)

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

摘要:针对线性比式和问题(P)提出一种新的分支定界算法,并进行数值验证.该算法把问题转换成等价问题，并利用线性松弛技术建立问题的松弛线性规划,从而将原始的非凸规划问题归结为一系列线性规划问题，通过可行域的连续细分以及求解一系列线性松弛规划,得出的算法收敛到问题(P)的全局最优解.数值算例结果表明算法是可行有效的.

关键词：线性比式和全局优化线性松弛分支定界ω分法

0　引言

【研究意义】线性比式和优化问题在运输计划,政府规划及经济投资等领域有着重要的作用[1].考虑如下线性比式和问题:

1　预备知识

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)得最优解和最优值分别为yk和LB(Xk)=g(yk).令

由上述算法可知,在迭代过程中至少会产生一个嵌套的盒子序列,不妨仍记为{Xk},那么每个盒子的上下界及分割点ωk所产生的序列{lk},{ωk},{uk}满足如下条件:

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

(1)

而由ρj及q的定义知,

∀x∈D.

证明(i)若算法经过k次迭代终止,结论显然成立;否则,由算法可知,

(2)

(3)

则有

这与(3)式矛盾,故假设不成立.即有

即

那么对∀x∈D,有

UBk-LB(Xk)≤,

所以,对任意x∈D,有

3　数值实验

为验证算法的可行性,在AMD A8 CPU(主频 1.9 GHz)4 GB内存的微机上用Matlab(2012b)进行数值计算.

例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.

数据结果表明,本文算法是可行的.

4　结论

参考文献：

[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].应用数学学报,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.

(责任编辑：尹闯)

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-)，女，博士，教授，主要从事最优化理论与应用研究。

中图分类号:O221.2

文献标识码：A

文章编号：1005-9164(2016)05-0392-04

*国家自然科学基金项目(11171094)资助。

广西科学Guangxi Sciences 2016,23(5):392～395

网络优先数字出版时间：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.011

网络优先数字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1546.022.html