首页 | 本学科首页   官方微博 | 高级检索  
     检索      

基于单纯形方法的双层线性规划全局优化算法
引用本文:赵茂先,高自友.基于单纯形方法的双层线性规划全局优化算法[J].应用数学,2006,19(3):642-647.
作者姓名:赵茂先  高自友
作者单位:1. 山东科技大学应用数学系,山东,青岛,266510;北京交通大学系统科学研究所,北京,100044
2. 北京交通大学系统科学研究所,北京,100044
基金项目:国家自然科学基金;国家自然科学基金;北京市自然科学基金
摘    要:通过分析双层线性规划可行域的结构特征和全局最优解在约束域的极点上达到这一特性,对单纯形方法中进基变量的选取法则进行适当修改后,给出了一个求解双层线性规划局部最优解方法,然后引进上层目标函数对应的一种割平面约束来修正当前局部最优解,直到求得双层线性规划的全局最优解.提出的算法具有全局收敛性,并通过算例说明了算法的求解过程.

关 键 词:双层线性规划  全局最优解  单纯形方法  割平面约束  极点
文章编号:1001-9847(2006)03-0642-06
收稿时间:2006-01-04
修稿时间:2006年1月4日

A Global Convergent Algorithm for Solving Bilevel Linear Programming Based on the Simplex Method
ZHAO Mao-xian,GAO Zi-you.A Global Convergent Algorithm for Solving Bilevel Linear Programming Based on the Simplex Method[J].Mathematica Applicata,2006,19(3):642-647.
Authors:ZHAO Mao-xian  GAO Zi-you
Institution:1. Department of Applied Mathematics ,Shandong University of Science and Technology, Qingdao 266510, China ; 2. Institute of System Science, Beijing Jiaotong University, Beijing 100044, China
Abstract: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.
Keywords:Bilevel linear program  Global optimal solution  Simplex method  Cutting plane constraint  Extreme point  
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号