Study On The Properties And Algorithms Of The Linear Bilevel Programming

Many problems, such as productive plan, resource distribution, engineering design problems need considering the hierarchy character of system, that is a hierarchical decision problem may has more than one decision makers, which have their own decision variables and objectives. The traditional mathematical optimization methods couldn't solve these problems successfully. For this sake, multilevel programming has caught people's attentions. Bilevel programming is the basically form of multilevel programming; multilevel programming can be regarded as the compounds of bilevel programming. So the linear bilevel programming has more research value.The thesis is divided into five chapters: chapter 1 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. Chapter 2 discusses the mathematical model of the linear bilevel programming, gives some basic concepts and properties of the linear bilevel programming, and summarizes the algorithms at the present time.The chapter 3 and chapter 4,5 are the more impotent parts in the thesis. In chapter 3, by analyzing the bilevel linear programming conversion form, we introduce the notion of the equilibrium point, then carry out a demarcation on the upper objection function of the bilevel linear programming, making use of the dichotomy principle, construct a bilinear programming to amend the current boundary, until getting the global optimal solution to the bilevel linear programming. we propose a algorithm to solve the linear bilevel programming problem, and verify the convergent and feasibility of the algorithm.In chapter 4, because the constraints of the linear bilevel programming are linear functions and the simplex method is the most efficient method to solve linear programming. How to transform the linear bilevel programming and solve them using the simplex method is the aim of the thesis. Following this idea, proposes two simplex methods for solving the local solution of linear bilevel programming, Fist, carrying the simplex iteration form the feasible extreme point, and verify the feasibility of the new obtained extreme point; Second, chose the reasonable nonbiased variable as variable that the enter into basis, then carry a iteration, and make sure obtaining a new feasible extreme point.In chapter 5, based on the local optimal solution, and then propose two global algorithms for solving linear bilevel programming, making use of the cutting plane Finally, the paper summarizes the obtained results and prospects what can do for future research.