摘要
用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系,通过求得下层问题的对偶问题可行域上的极点,将双层线性规划转化为有限个线性规划问题,从而用线性规划方法求得问题的全局最优解.由于下层对偶问题可行域上只有有限个极点,所以方法具有全局收敛性.
In this paper, the relationship between the optimal solution of the bilevel linear programming problem and the extreme points of the feasible region of the follower's dual problem is discussed using the duality theory of linear program. This relationship leads to the decomposition of the composite problem into a series of linear programming problems leading to an efficient algorithm. The proposed algorithm can terminate at a global optimal solution to the problem in finite number of steps. Finally, a simple numerical example is given to illustrate the application of the algorithm.
出处
《运筹学学报》
CSCD
北大核心
2005年第2期57-62,共6页
Operations Research Transactions
基金
This paper was partly supported by National Outstanding Young Investigator Grant (70225005) of National Natural Science Foundation of China and Teaching & Research Award Program for Outstanding Young Teachers (2001) in Higher Education Institutions of Ministry of Education, China.
