| Bilevel programming problem(BPP) is a system decision-making problem with a hierarchy structure of two levels. The mathematical model of BPP contains two optimization problems, the upper level and the lower level which have different objective functions and constraints. They are independent and influence each other. The constraint condition of the upper level is bound up with the optimal solution of the lower level, the optimal solution of the lower level is also affected by the decision variables of the upper level. Because BPP is a kind of NP-hard problem, its theory and algorithm developed slowly. That doesn’t affect its application in real-life. Until now, BPP has been widely applied in market competition, environmental protection, the design of traffic network, resource allocation, logistics management, price control etc. This paper make a brief review on the theory and algorithm of the BPP. Then we study the theory of two kinds of multi-objective bilevel programming problems (MOBPP), and design corresponding algorithms. The article is organized as follows.In chapter 1. We describe the mathematical model of the BPP. Introducing BPP’s research background and development status. Include several commonly used solving algorithms, such as pole search algorithm, branch and bound method, penalty function method etc. Their solving ideas, advantages, disadvantages are summarized. Its application on traffic and management is also introduced. Finally, We introduce the main work in this paper.In chapter 2. We introduce the preliminary knowledge related to this article. Mainly include:some mathematical concepts, such as closed set, continuous function, convex set, differentiable functions, local minimum (maximum) points etc. Mathematical models and the property of solutions of the linear and nonlinear BLPP. Mathematical model, optimality conditions, main target solving method about multi-objective optimization problem (MOOP). The concept of fuzzy set and how to determining membership function. The above content provides the theoretical basis for chapter 3 and 4.In chapter 3. For a class of MOBPP which the upper has more then one objective functions and the lower has only one, we design the main target method. In the first section, we introduce its mathematical model and the definition of pareto-optimal solution. Relevant variables in the model are also introduced. In section two, we assume that the lower level problem is a convex programming problem. The MOBPP is transformed into MOOP with complementarity constraints by using K-T optimality condition. Through using complementary constraints as penalty terms, we construct its penalty function. By proving its convergence, we can get that the pareto-optimal solution of the penalty problem must be the pareto-optimal solution the MOBPP. In section three, a main target method for solving penalty function problem is proposed, the concrete solving steps are also given. In section four, by solving relevant examples, we can prove that the main target method we designed in this paper is effective. Finally, the advantage and disadvantage of the method are analyzed.In chapter 4. We design the fuzzy decision making method for the linear semivector bilevel programming problem(LSBPP) which the upper is single objective and the lower is multi-objective. The solving approach is as follows: Firstly, the linear weighting method is used to transform the lower level problem into single objective programming problem. Namely, the LSBPP is transformed into single objective BPP. Next, based on fuzzy set theory, we set up the corresponding membership function, which is used to describe the satisfaction of objective functions. Afterwards, we construct new fuzzy goals evaluation function, specific steps of fuzzy decision making method are also given. In the end, Specific example is used to verify it rationality and feasibility.In chapter 5. We summarize the advantages and disadvantages of the algorithms. |
PDF Full Text Request