【摘要】 用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系,通过求得下层问题的对偶问题可行域上的极点,将双层线性规划转化为有限个线性规划问题,从而用线性规划方法求得问题的全局最优解.由于下层对偶问题可行域上只有有限个极点,所以方法具有全局收敛性.更多还原

【Abstract】 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.更多还原