求线性比式和问题全局解的一个新方法

A New Global Algorithm for Sum of Linear Ratios Problem

针对一般线性比式和问题的求解,给出—个新的分支定界算法.首先利用等价转换技巧和—个新的线性化技巧,建立等价问题的松弛线性化问题,将原始的非凸规划问题归结为一系列线性规划问题的求解;然后借助于这一系列松弛线性化问题的解确定出原问题的最优解.算法的收敛性理论上得以证明,数值算例表明算法是可行的.

This paper presents a new branch and bound algorithm for globally solving general sum of linear ratios problem. First, by using an equivalent transformation technique and a new linear relaxation technique, the equivalent problem can be reduced to a sequence of linear programming problems. The proposed algorithm will convergent to the global optimal solution by means of the subsequent solutions of the series of linear programming problems. Convergence of the algorithm is established and numerical results are given to show the feasibility.