The Algorithm Research On Linear Bilevel Programming

In practice, the hierarch y of the system in many problems needs to be considered, such as the allocation of resources, price, engineering design, and even force deployment, etc. This kind of problem have some comm on characteristics that there is not on ly one decision maker in the system, there is hierarchical relationships among different decision makers, and each layer has its own objectiv e functions and decision variables. System like that is called multi-layer planning problem. With the globalization of social economy, the application of m ulti-layer planning is increasing. The attention degree of people is becoming higher and higher, and people has made some achievements in the study. In the discussion of m ultilayer planning people found that multilay er planning can be comprised of several bilevel programming. Then the status of the bilevel programming is obvious. The linear bilevel programm ing as the simplest form of bilevel programm ing, its upper and lower level of the objective function and constraint conditions are all linear.This paper is divided into five chapters to discuss. Chapter 1 is the introduction, introduced the model and characteristics of bilevel programming, and its application and research situation were revi ewed. Linear bilevel programm ing is m ainly discussed in chapter 2, there we p resent the models, properties, and the process of transforming the two level programm ing into a single layer planning is given through the K-T condition and the penalty function principle. Th is is to m ake a simple generalization of the solving method and the main idea, and lay the foundation for the following algorithm.Chapter 3 introduces th e concept of the equilibrium point. We analyzed the linear bilevel programming through the equilibrium point. and we were inspired by the cutting plane method. Then we considered adding a cutting plane constraint conditions to the linear bilevel programming, so that we constructed a bi-lin ear programming problem to realize the iteration of equilibriu m points. And then we can get the ?-global optimal solution. Chapter 4 is on the basis of the given transformation form in chapter 2. We were inspired by the f easible direction algorithm of nonlinear programm ing, used the linear first-order Taylor approximation approach the objective function, and proposed the linear approximation algorithm of the linear bilevel programming problem.Finally, the fifth chapter made a summary, and we pointed out the focus of the work of research in the future.