全局求解一类线性比式和问题的分支定界算法  

The Branch and Bound Algorithm for Global Solution for A-class Sum of Linear Ratios

作　　者：尹建菲 申培萍 王慧满 Yin Jianfei;Shen Peiping;Wang Huiman(School of Mathematics and Statistics,North China University of Water Resources and Electric Power,Zhengzhou 450046,China)

机构地区：[1]华北水利水电大学数学与统计学院,河南郑州450046

出　　处：《洛阳师范学院学报》2024年第5期1-5,共5页Journal of Luoyang Normal University

基　　金：国家自然科学基金项目(12071133)。

摘　　要：针对一类线性比式和规划问题(SLR)提出一种新的分支定界算法.首先通过Charnes-Cooper变换和引进新的变量将该问题转化为等价非线性规划问题(EP).其次在给定子盒子上对问题(EP)非凸约束的凹部分进行线性近似,得到一个凸二次规划问题(SOCR).然后用所提出的算法求问题(SLR)的全局最优解.最后从理论上证明了算法的收敛性和计算复杂度,数值实验表明该算法是可行有效的.A new branch and bound algorithm is proposed for a-class sum of linear ratios(SLR)programming problems.Firstly the problem(SLR)is transformed into an equivalent nonlinear programming problem(EP)by the Charnes-Cooper transformation and the introduction of new variables.Secondly,a convex quadratic programming problem(SOCR)is obtained by linearly approximating the concave part of the non-convex constraints of the problem(EP)on the given sub-rectangle.And then the global optimal solution of the problem(SLR)is obtained by using the proposed algorithm.Lastly,the convergence and computational complexity of the algorithm are proved theoretically.And numerical experiments show that the proposed algorithm is feasible and effective.

关 键 词：线性比式和 全局最优解 分支定界 计算复杂度 

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