Global Optimization Algorithms For Generalized Linear Fractional Programming Problem And Applications

Nowadays,many practical problems in various fields such as financial management,wireless networks,data envelopment analysis,engineering design,investment portfolio,system reliability analysis,and so on,all of them can be represented as generalized linear fractional programming problems.In this dissertation,we present global optimization algorithms for several types of generalized linear fractional programming problems according to their own characteristics.The main contents are as follows.1.A brief description of the three models of several types of generalized linear fractional programming problems studied in this paper and their current state of research,and finally the main work of this paper is given.2.The problem of minimax linear fractional programming of a network system model in signal is studied.Firstly,the original problem is transformed into an equivalent problem by introducing new variables.Second,a linear relaxation planning problem for the equivalent problem is constructed using linearization techniques.Then,the initial outer space rectangle is divided and a series of linear relaxation planning problems are solved in turn,and the outer space branch-and-bound algorithm is proposed.The algorithm eventually converges to the global optimal solution of the original problem.The final experimental results prove the feasibility of the algorithm.3.A global optimization algorithm is proposed for the sum of linear fractional problems in multipleview geometric modeling.Firstly,a linear relaxation programming problem is constructed to compute a lower bound on the global minimum of the original problem by using the equivalence transformation and single fractional function.Second,an outer space acceleration technique is designed to improve the speed of the algorithm by removing the entire outer space rectangle or the entire examined part of the outer space rectangle,which does not contain the global optimal solution of the equivalence problem.In addition,the complexity analysis of the outer space rectangle branch delimitation algorithm is used to estimate its maximum number of iterations.Finally,the global convergence of the algorithm is proved,and the numerical computation results are reported and analyzed to prove that the algorithm is effective.4.Consider the generalized linear fractional multiplicative problem in the system reliability analysis model.Firstly,the original problem is transformed into an equivalence problem by introducing new variables and equivalence changes.Secondly,two-stage linear approximation and bilinear relaxation are used to construct linear relaxation of the objective function and constraint function,respectively.The image space region reduction technique is constructed to improve the convergence speed of the algorithm.Combining the linear relaxation planning problem and the image space region reduction technique,an image space branchreduction-bound algorithm is constructed to prove its global convergence and the worst-case maximum number of iterations is estimated by analyzing the complexity.The numerical results show that the algorithm has high computational efficiency.