求解二层线性规划的极点算法  

Extreme Points Algorithm for Solving Bilevel Linear Programming

作　　者：赵礼阳 霍永亮[2] 

机构地区：[1]重庆师范大学数学学院,重庆401331 [2]重庆文理学院数学与财经学院,重庆402160

出　　处：《重庆师范大学学报（自然科学版）》2016年第4期1-5,共5页Journal of Chongqing Normal University:Natural Science

基　　金：重庆高校创新团队建设计划项目(No.KJ301321)

摘　　要：给出了求解二层线性规划全局最优解的极点搜索方法。该方法首先通过单纯形方法分别求出原问题约束域和下层对偶问题约束域的极点,并按照上层目标函数值的大小顺序将原问题约束域的极点进行排序,然后把下层对偶问题约束域的极点依次和原问题约束域中有序极点进行组合,利用下层对偶问题的对偶间隙等于零来验证极点的有效性,以此确定问题的全局最优解。最后通过算例验证算法的有效性和可行性。该方法具有简单易行、可操作性强的优点。This paper puts forward a pole search method to find the global optimal solution of bilevel linear programming. The given method in this paper firstly finds out the constrained domain poles of both original and the follower＇s dual problems by means of sim- plex method and sorts the former ones by the size of optimal value of the upper-level objective function. Then the paper combines the constrained domain pole points of original problems with lower-level dual problem, by using the truth that the interval of lower- level dual problem equals to zero for verifies the validation, so that confirm the required global optimal resolution. Finally, the paper verifies the effectiveness and feasibility of the algorithm by an example and the result shows it＇s simple and strongly operable.

关 键 词：二层线性规划 约束条件 全局最优解 极点算法 

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