Research And Application Of Several Kinds Of Complex Bilevel Programming Problems

The bilevel programming problem(BLPP) is a nonconvex optimization problem with a hierarchical structure. On one hand, the bilevel programming problem in which the parameters are precise has been well studied, especially on the linear bilevel single-objective case and some special nonlinear bilevel single-objective problems in which all of the functions are convex and differentiable. However, there does not exist too many studies in nonlinear bilevel single-objective problems with nondifferentiable nonconvex functions and bilevel multi-objective optimization problems. On the other hand, the bilevel programming problem with uncertain parameters has received increasing attention, and most of them in literature focus on the fuzzy bilevel programming problem and the stochastic bilevel programming peoblem. But few works are related to the bilevel programming problem under fuzzy random environments. This dissertation is focused on several kinds of complex bilevel optimization problems, including a class of nonlinear bilevel programming problems, semvectorial bilevel programming problem, fuzzy random bilevle programming problem. Taking into account the characteristics of the bilevel problem, a hybrid estimation of distribution algorithm is proposed to solve this class of nonlinear bilevel programming problems and an exact penalty function method is developed to deal with the semvectorial bilevel programming problem. Based on the fuzzy random theory and the bilevel programming methodology, the solution concepts for a fuzzy random bilevle programming problem are proposed and corresponding algorithms are designed to solve it. The main contributions of this dissertation are as follows:1. A class of nonlinear bilevel programming problems where the follower’s problem is linear with respect to the lower level variable are studied. For these problems, a hybrid algorithm based on estimation of distribution algorithm(EDA) and Nelder-Mead simplex method(NM) is proposed. The optimality conditions of linear programming is used to handle the follower’s problem, and a hybrid algorithm by combining EDA with NM is designed to solve the leader’s problems. The proposed hybrid algorithm can effectively balance the exploration and the exploitation abilities, and produces faster convergence.2. The semivectorial bilevel programming problem in which the upper level is a scalar optimization problem and the lower level is a multi-objective optimization problem is addressed. By using Benson’s method and dual theory of linear programming, the original problem is transformed into a single level optimization problem. Then a definition of partial calmness of the transformed problem is given. Based on this definition, an exact penalized problem of the semivectorial bilevel programming is constructed, the optimality condition is given and an algorithm is proposed to solve the problem.3. A kind of linear bilevel programming problem where the coefficients of both objective functions are fuzzy random variables is considered. To deal with such a problem, a computational method for obtaining optimistic Stackelberg solutions is proposed. Based on α- level sets of fuzzy random variables, the fuzzy random bilevel programming problem is first transformed into a stochastic interval linear bilevel programming problem. To minimize the interval objective functions, the order relations which represent the decision maker’s preference are defined by the right limit and the center of random interval simultaneously. Using the order relations and expectation optimization, the stochastic interval linear bilevel programming problem can be converted into a deterministic linear bilevel multiobjective programming problem. According to optimistic anticipation from the upper level decision maker, the optimistic Stackelberg solution is introduced and a computational method is also presented.4. To solve a linear bilevel programming problem with fuzzy random variable coefficients in both objective functions, the mathematical transformation models are constructed and a computational method is proposed based on the theory and methodology of interval programming and bilevel programming. The focus is on the optimal value range of objective function rather than a single optimal value. This provides more information to the decision makers under fuzzy random circumstances, To this end, an interval programming approach based on α- level sets is applied to construct a pair of bilevel mathematical programming models(i.e. the best and worst bilevel models). Through expectation optimization model, the best and worst bilevel problems are transformed into two deterministic problems. By means of the Kth-best algorithm, the best and worst optimal solutions as well as the corresponding range of the objective function values can be obtained. The proposed approaches can get not only the best optimal solution(ideal solution) but also the worst optimal solution, and is more reasonable than the existing approaches which can only get a single solution(ideal solution).5. A class of bilevel programming problems where fuzzy random coefficients are contained in both objective functions and constraint functions are addressed. To deal with these problems, the fuzzy random bilevel programming problem is first transformed into a stochastic interval bilevel linear programming problem in terms of α- level sets. Based on an interval programming approach, the most and least favourable objective functions and the maximum and minimum ranges constraints are determined. Then the best and worst optimal problem are derived. Furthermore, by incorporating expectation optimization model into probabilistic chance constraints, the best and worst optimal problems are transformed into deterministic ones. An estimation of distribution algorithm is designed to derive the best and worst Stackelberg solutions.6. The results of the numerical experiment for various proposed algorithms show that they are effective.