基于凹性割的线性双层规划全局优化算法  

A Global Optimization Algorithm for Solving Linear Bilevel Programming Based on the Cconcavity Cut

作　　者：赵茂先[1] 宋爱美[1] 王向荣[1] 

机构地区：[1]山东科技大学信息科学与工程学院,山东青岛266510

出　　处：《运筹与管理》2012年第1期48-52,共5页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(70971079);山东省自然科学基金资助项目(A2008A01)

摘　　要：通过对线性双层规划下层问题对偶间隙的讨论,定义了一种凹性割,利用该凹性割的性质,给出了一个求解线性双层规划的割平面算法。由于线性双层规划全局最优解可在其约束域的极点上达到,提出的算法能求得问题的全局最优解,并通过一个算例说明了算法的有效性。A concavity cut is defined by discussing the duality gap of the lower problem of the linear bilevel programming.Based on the feature of the concavity cut,a cutting plane algorithm for solving linear bilevel programming is given.Based on the result that a global optimal solution to linear bilevel programming occurs at an extreme point of its constraint region,the proposed algorithm can obtain a global optimal solution.Finally,a example is given to demonstrate the effectiveness of the algorithm.

关 键 词：运筹学 割平面算法 凹性割 线性双层规划 

分 类 号：O221.1[理学—运筹学与控制论]