Study On The Properties And Algorithms Of Bilevel Programming Problems

Hierarchy is one of important characters of system, which is main character especially for large and complicated system. From 1970s, when facing optimization decision problems of hierarchical system such as productive plan, resource distribution, engineering design problem etc, the traditional mathematical optimization methods couldn't solve these problems successfully. As exploring new methods to solve these problems, the notion and technique of multilevel programming were developed. Bilevel programming is the most typical form of multilevel programming, multilevel programming can be regarded as the compounds of bilevel programming.At the beginning, this paper gives a general introduction to the main characteristics and mathematical model of bilevel programming, summarizes the applications of bilevel programming in some fields and the progress of research on solution algorithms, and then the paper researches several special forms of bilevel programming and proposes some solution algorithms to solve them.The paper researches the feature of the solution and optimization conditions of the linear bilevel programming(LBP), at the basis of the optimization conditions of the (BLP), a global convergent algorithm is proposed to solve the (LBP). Convex bilevel programming(CBP), which the upper-level objective function is convex, the lower-level objective function and all constraints are linear, is discussed. Using the penalty function principle, the (CBP) is transformed into a one-level mathematical programming by appending the duality gap of lower-level problem as a penalty to the upper-level function. An algorithm is presented for finding a local optimal solution of the (CBP) by solving a series of convex programs and linear programs. By researching the relationship between the optimal solution of the constructed one-level mathematical programming and the extreme points of the feasible of the lower-level's duality problem, solving the (CBP) is transformed into solving a series of convex programs. A global convergent algorithm for solving the (CBP) is proposed supposed that the upper-level objective function is strict convex.Another important content of the paper is investigation to the mixed integer linear bilevel...