线性分式和规划问题的全局优化算法

Global Optimization Algorithm for Sum of Linear Ratios Problem

提出一种求解线性分式和规划问题的分支定界算法.该算法首先利用等价转换技巧构造出原问题的等价问题,然后通过凹凸性包络技术建立等价问题中目标函数与约束函数的下逼近函数,得到其线性松弛规划,从而将原来的非凸规划问题转化为一系列线性规划问题,以确定原问题最优值的下界.从理论上证明了算法的收敛性,并用数值试验验证了算法的可行性和有效性.

In this paper,a branch and bound algorithm is proposed for globally solving sum of linear ratios problem. In our algorithm, an equivalence problem is derived by using equivalence transformation technique. A linear relaxation programming of the equivalence problem can be constructed by basing upon the convex envelopes and concave envelopes technique. Thereby, the initial problem can be converted to a sequence of linear programming problem, and determine the global optimum＇s lower bound. The conver-gence of the algorithm is proved, and numerical experiments show that the proposed algorithm is feasible and effective.