一类线性分式规划问题的全局优化方法  

Global optimization of a kind of linear fractional programming problems

作　　者：陈艳霞[1] 高岳林[1,2] 马文路 

机构地区：[1]宁夏大学数学计算机学院,宁夏银川750021 [2]北方民族大学信息与系统科学研究所,宁夏银川750021

出　　处：《纺织高校基础科学学报》2014年第2期216-221,226,共7页Basic Sciences Journal of Textile Universities

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

摘　　要：针对一类线性分式规划问题,给出一个新的分支定界算法.算法的主要特点是在建立原问题等价的松弛线性规划问题时,利用对数函数和指数函数的单调性和凹凸性,提出了一个新的二级松弛规划来确定最优值的下界,这可以用于改善算法的收敛速度.通过对松弛线性规划问题可行域的细分以及一系列松弛线性规划问题的求解过程,从理论上证明了此算法能收敛到初始问题的全局最优解.并通过数值算例证明了算法的有效性.For a kind of linear fractional programming problems, a new branch and bound algorithm is proposed. The main features of this algorithm is that by utilizing the monotonicity and bump of the logarithmic function and the exponential function , a relaxation linear programming problem of equivalent problem of original problem is established, and a new second-relaxation linear programming is put for ward to determine the lower bound of the optimal value of the original problem. This can be used to improve the convergence rate of the algorithm. Through the successive refinement of the linear relaxation of the feasible region and the solutions of a series of relaxation linear programming problems, it shows that the proposed branch and bound algorithm is convergent to the global minimum from theory. And finally the numerical experiments are reported to show the feasibility of the proposed algorithm.

关 键 词：线性分式规划 分支定界方法 线性松弛技术 全局优化 

分 类 号：O211.1[理学—概率论与数理统计]