线性规划的一种外点单纯形算法

journal6 ›› 2003, Vol. 24 ›› Issue (3): 32-36.

线性规划的一种外点单纯形算法

(中南大学铁道校区数学科学与计算技术学院，湖南长沙 410075)

出版日期:2003-09-15 发布日期:2012-11-07
作者简介:高培旺(1964-)，男，湖南省宁远县人，博士，中南大学铁道校区数学科学与计算技术学院副教授，硕士生导师，主要从事运筹学及系统可靠性工程研究.

An Infeasible Simplex Algorithm for Linear Programming

(College of Mathematics and Computations,Central South University,Changsha 410075,China)

Online:2003-09-15 Published:2012-11-07

摘要/Abstract

摘要：提出了一种求解线性规划(LP) 的改进的单纯形法，其迭代过程产生的一部分极点可能出现在可行域外成为不可行极点，因此称之为外点单纯形法.虽然该方法还不能通过复杂性分析证明只需至多n次迭代便可收敛到最优解，但比较Dantzig的沿可行域内边界进行的单纯形法，一般能更快地迭代到达最优点，且在选择旋转主元时，计算量只有温和的增加.

关键词： 线性规划, 可行域, 外点, 单纯形法

Abstract: This paper presents an improved (infeasible) simplex method for linear programming,in which some of vertex points,corresponding to the iterative process,can be out of the feasible domain of (LP).The algorithm would performs the iterations no more than the simplex method and simultaneously,can overcome the iterative loop caused by degeneracy.

Key words: linear programming, feasible domain, exterior point, simplex method

高培旺, 范国兵. 线性规划的一种外点单纯形算法[J]. journal6, 2003, 24(3): 32-36.

GAO Pei-Wang, FAN Guo-Bing. An Infeasible Simplex Algorithm for Linear Programming[J]. journal6, 2003, 24(3): 32-36.

[1]	周盛康, 李娇, 贺陵, 何阿玲, 常燕姿, 李洪毅. 基于核心景点评价体系的湘西自治州旅游路线规划[J]. 吉首大学学报（自然科学版）, 2021, 42(6): 41-47.
[2]	杨伍梅，刘淘文. 基于线性规划的企业生产计划编制问题[J]. 吉首大学学报（自然科学版）, 2019, 40(2): 84-87.
[3]	李双飞，陈卓，王仙云. 基于层次分析法与最短路径算法的乡村游路线设计——以湘西土家族苗族自治州古丈县为例[J]. 吉首大学学报（自然科学版）, 2017, 38(5): 88-91.
[4]	杨玉英. 线性规划问题的灵敏度分析及其应用[J]. journal6, 2009, 30(5): 32-35.
[5]	李光辉, 尹建新. 基于单纯形法的自动优化稳定域技术[J]. journal6, 2000, 21(4): 44-46.