求解弱线性双层规划问题的一种全局优化方法

A global optimization method for solving the weak linear bilevel programming problems

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.

Bilevel programming has been widely applied to economics, transportation, ecology, engineering and other fields. At present, the research of bilevel program- ming is mainly based on the strong bilevel programming and the weak bilevel program- ming. However, there are few studies on the solution methods to the weak bilevel programming. In this paper, we present a global optimization method for solving the weak linear bilevel programming problems （WLBPP）. We first give the relations between the WLBPP and its relaxation problem with respect to their optimal solutions. Using the dual theory of linear programming and penalty function method, we then discuss the relations between the relaxation problem and its penalized problem. Furthermore, we develop a global optimization method, whose advantage is that it only requires solving several linear programming problems to obtain a globally optimal solution of the original problem, for solving the WLBPP. Finally, a simple example illustrates that the proposed method is feasible.