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

A Branch and Bound Algorithm for the Sum of Linear Ratios Problem

作　　者：申培萍[1] 李丹华[1] SHEN Peiping;LI Danhua(College of Mathematics and Information Science,Henan Normal University , Xin xiang , Henan ,453007 , China)

机构地区：[1]河南师范大学数学与信息科学学院,河南新乡453007

出　　处：《广西科学》2016年第5期392-395,共4页Guangxi Sciences

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

摘　　要：针对线性比式和问题(P)提出一种新的分支定界算法,并进行数值验证.该算法把问题转换成等价问题,并利用线性松弛技术建立问题的松弛线性规划,从而将原始的非凸规划问题归结为一系列线性规划问题,通过可行域的连续细分以及求解一系列线性松弛规划,得出的算法收敛到问题(P)的全局最优解.数值算例结果表明算法是可行有效的.In this p a p e r,w e presents a n e w branch a n d b o u n d algorithm for globally solving thes u m of linear ratios p r o b l e m,w h i c h is verified b y the numerical examples.T h e algorithm transfo r m the p r o b l e m to its equivalent p r o b l e m,a n d establish a relaxational linear p r o g r a m m i n gp r o b l e m of b y using a linear relaxation technique?thus the initial n o n c o n v e x p r o g r a m m i n gp r o b l e m is reduced to a sequence of linear p r o g r a m m i n g problems.T h e proposed algorithm isconvergent to the global m i n i m u m of(P)t h r o u g h the successive refinement of the feasible regiona n d solutions of a series of relaxation linear p r o g r a m m i n g?a n d finally numerical e x a m p l e sare given to illustrate the feasibility a n d effectiveness of the proposed algorithm.

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

分 类 号：O221.2[理学—运筹学与控制论]