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

针对一类线性分式规划问题,给出一个新的分支定界算法.算法的主要特点是在建立原问题等价的松弛线性规划问题时,利用对数函数和指数函数的单调性和凹凸性,提出了一个新的二级松弛规划来确定最优值的下界,这可以用于改善算法的收敛速度.通过对松弛线性规划问题可行域的细分以及一系列松弛线性规划问题的求解过程,从理论上证明了此算法能收敛到初始问题的全局最优解.并通过数值算例证明了算法的有效性.

Global optimization of a kind of linear fractional programming problems

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.