基于单纯形方法的双层线性规划全局优化算法  

A Global Convergent Algorithm for Solving Bilevel Linear Programming Based on the Simplex Method

作　　者：赵茂先[1] 高自友[2] 

机构地区：[1]山东科技大学应用数学系,山东青岛266510 [2]北京交通大学系统科学研究所,北京100044

出　　处：《应用数学》2006年第3期642-647,共6页Mathematica Applicata

基　　金：国家杰出青年科学基金(70225005);国家自然科学基金(70471088);北京市自然科学基金(9042006)

摘　　要：通过分析双层线性规划可行域的结构特征和全局最优解在约束域的极点上达到这一特性,对单纯形方法中进基变量的选取法则进行适当修改后,给出了一个求解双层线性规划局部最优解方法,然后引进上层目标函数对应的一种割平面约束来修正当前局部最优解,直到求得双层线性规划的全局最优解.提出的算法具有全局收敛性,并通过算例说明了算法的求解过程.The structural feature of the feasible region of the bilevel linear programming is discussed. Using the result that a global optimal solution to the bilevel linear programming can occur at an extreme point of its constraint region. An approach for finding a local optimal solution is offered which applies mainly the usual simplex method with an additional rule for determining the entering variable. By adding a cutting plane constraint of the upper level objective function,the local optimal solution is modified until a global optimal solution of the bilevel linear programming is obtained. The proposed algorithm is proved to be finitely convergent. Finally,a simple example is given to illustrate the application of the method.

关 键 词：双层线性规划 全局最优解 单纯形方法 割平面约束 极点 

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