线性分式和规划问题的分母输出空间分支定界算法

A Denominators' Outcome-space Branch and Bound Algorithm for Solving Linear Fractional Sum Programming Problems

提出了一种新的线性分式和规划问题的分母输出空间分支定界算法,并证明了算法的收敛性.在这个算法中,以目标函数中每个分式的分母作为变量构成输出空间,对这些变量的取值范围笛卡尔乘积构成的超矩形进行剖分,在决策变量远远大于分式的个数时可以大大地降低计算量,同时用线性规划松弛技术确定下界.数值实验表明所提出的算法可行有效.

A new branch and bound algorithm is proposed for solving linear tractional sum programming problems anti the convergence of the algorithm is proved. In this algorithm, the denominators of the fractions in the target function are as variables to construct outcome space. The super-rectangular which is the Cartesian product of the variables ranges is parti- tioned. When the number of the decision variables is far greater than the number of fractions, the computation can be reduced significantly. The linear programming relaxation technique is used to determine lower bounds in the proposed algorithm. Nu- merical experiments show that the proposed algorithm is feasible and effective.