| 摘要: |
| 针对线性比式和问题(P)提出一种新的分支定界算法,并进行数值验证.该算法把问题转换成等价问题,并利用线性松弛技术建立问题的松弛线性规划,从而将原始的非凸规划问题归结为一系列线性规划问题,通过可行域的连续细分以及求解一系列线性松弛规划,得出的算法收敛到问题(P)的全局最优解.数值算例结果表明算法是可行有效的. |
| 关键词: 线性比式和 全局优化 线性松弛 分支定界 ω分法 |
| DOI：10.13656/j.cnki.gxkx.20161121.011 |
| 投稿时间：2016-08-15 |
| 基金项目:国家自然科学基金项目(11171094)资助。 |
|
| A Branch and Bound Algorithm for the Sum of Linear Ratios Problem |
|
SHEN Peiping, LI Danhua
|
| (College of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan, 453007, China) |
| 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. |
| Key words: sum of linear ratios global optimization linear relaxation branch and bound ω division |
