摘要
通过对线性双层规划下层问题对偶间隙的讨论,定义了一种凹性割,利用该凹性割的性质,给出了一个求解线性双层规划的割平面算法。由于线性双层规划全局最优解可在其约束域的极点上达到,提出的算法能求得问题的全局最优解,并通过一个算例说明了算法的有效性。
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.
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2012年第1期48-52,共5页
Operations Research and Management Science
基金
国家自然科学基金资助项目(70971079)
山东省自然科学基金资助项目(A2008A01)
关键词
运筹学
割平面算法
凹性割
线性双层规划
operational research
cutting plane algorithm
concavity cut
linear bilevel programming