Properties And Algorithms Of Some Bilevel Programming Problems

With the development of society, the scale of the practical problems becomes larger and larger and the structure of them is more and more complex. It is the multilevel programming problem that describes the complex system and has developed recent years. In this thesis, several special kinds of bilevel programming problems are mainly studied. There are four chapters.In the first chapter, the content,definition, features and development of the multilevel programming problems are introduced simply, and the plans and the methods of the following chapters for the three special kinds of bilevel programming problems are also mentioned.In the second chapter, bilevel linear fractional programming problem, in which the constraint region is polyhedral,is discussed. Several optimality conditions are derived based on dual fractional program and Kuhn-Tucker conditions. An efficient method is given with the help of the PCP algorithm.In the third chapter, linear-quadratic bilevel programming problem is studied. The very efficient algorithm is proposed based on that the inducible region is piecewise linear and that the upper objective is linear. A new algorithm which is very efficient is proposed with the help of the kth-best algorithm. Furthermore, a numerical example is given to highlight the results.In the last chapter,bilevel multiobjective linear programming problem is studied. Based on the definition of multiobjective programming problem's efficient solution a single-level formulation for its equivalent is provided byKuhn-Tucker condition. The optimal solution of bilevel multiobjective linear programming occurs at a vertex of a special polyhedral relating to the constraint region, which is proved on the base of dual theory. In the end, the algorithm is given too.