Study On The Theory And Algorithms Of Multilevel Programming Problem

The thesis deal with theory issues(properties, existence of solution, optimality condition and so on), algorithms and numerical results for multilevel programming problem(MLPP), especially for bilevel programming problem(BLPP). Several theoretical issues on multilevel linear progranuning problem are discussed in chapter 2. First, problems of the multilevel modeling are described from different point. Then it is shown that bilevel linear programming problem with follower responding marginal function to leader (BLLPPFRMFL) can be reduced to a linear max-mm problem, and BLLPPFRMFL is also equivalent to a common mathematical programs with linear separable constraints. Dual feasible solution of bilevel linear programming problem with multi- followers(BLLPPMF) is put forward. Furthermore, the feasible solution set and dual feasible solution set are presented in the united frame under the weak condition by the face of BLLPPMF constraint set. The fact that two propositions concerned with bilevel programming problem are wrong is illustrated with Counterexamples. The global algorithms for solving bilevel linear programming problem(BLLPP) and trilevel linear programming problem(TLLPP) are studied with numerical experiment in chapter 3. It is shown that several exact penalty methods for solving BLLPP are identical. An outer approximation realization of the exact penalty approach is presented on the basis of the discussion of choosing the original value of and the adaptive increasing in penalty factor. BLLPP is reduced to a parameter concave minimization problem, based on which, an increasing feasible extreme point search algorithm is presented. Finally, a realization of the -Th best algorithm for TLLPP is discussed which employs the connectedness of the feasible solution set. In chapter 4, first the geometrical properties and the existence of optima of special bilevel linear mixed integer programming problem are discussed. Afterwards, three solutions of BLLPP with leader variables 0-1, which are the branch and bound algorithm, the approach of reducing to the continuos BLLPP and the genetic algorithm, are given and compared by means of numerical results. Chapter 5 is devoted to the existence of optima and optimality condition of BLPP. Firstly, relations of different definitions of the optimal solution of BLPP are given, and the existence of strong and weak optima is discussed. Secondly, several sufficient conditions guaranteeing the convexity of BLPP with follower responding marginal function to leader are presented. Based on which, the optimality conditions are given. Thirdly, it is shown that the FJ optimality conditions of BLPP based on the marginal function and on the KKT optimality condition of lower level problem are trivial, and the optimality condition of BLPP is discussed on the basis of the partial calmness of special constraint of its equivalent common programs. In chapter 6, the properties, convergence and the relation with Stackelberg game decision-making process of penalty function method for BLPP based on the dual gap functionof lower level problem are discussed, together with the Largange dual problem of BLPP, its corresponding dual theory and a global realization of the approach. A differential evolution algorithm for solving BLPP is designed and proved to be effective with numerical examples. In chapter 7, with vectors d1 and d2 being arbitrarily generated, a BLLPP is constructed whose optima is not Pareto optimal. The sufficient condition guaranteeing the...