• 论文 • 上一篇    下一篇

退化线性规划的一个新的改进的单纯形方法

  

  1. 河北工业大学理学院, 天津 300401
  • 收稿日期:2011-05-24 出版日期:2012-06-15 发布日期:2012-06-13
  • 基金资助:
    国家自然科学基金 (10971047) 和 河北省自然科学基金 (A2010000011).

赵海峰,  刘新为. 退化线性规划的一个新的改进的单纯形方法[J]. 数值计算与计算机应用, 2012, 33(2): 109-120.

Zhao Haifeng, Liu Xinwei. A NEW REVISED SIMPLEX METHOD FOR DEGENERATE LINEAR PROGRAMS[J]. Journal of Numerical Methods and Computer Applications, 2012, 33(2): 109-120.

A NEW REVISED SIMPLEX METHOD FOR DEGENERATE LINEAR PROGRAMS

Zhao Haifeng, Liu Xinwei   

  1. Hebei University of Technology, School of Science, Tianjin 300401, China
  • Received:2011-05-24 Online:2012-06-15 Published:2012-06-13
本文讨论退化线性规划单纯形方法最优解的判定准则和有限主元规则. 首先改进简约价值系数向量, 提出线性规划单纯形方法最优解的判定准则.并且利用本文的判定准则给出[3]中定理2.3.5 (P.84)的一个新的证明. 然后提出一种新的混合有限主元规则, 在退化情形下通过对单纯形表使用新的混合有限主元规则进行迭代, 可以判断当前退化基本可行解或为最优解或给出下次迭代的主元并且跳出循环. 最后给出在一组经典的退化线性规划例子下, 改进的单纯形方法好的计算表现.
We consider optimality criterion and finite pivoting rule of the simplex method for degenerate linear programs (LP). First, improving the reduced cost vector, we present a optimality criterion of the simplex method for LP. Moreover, we give a new proof of theorem 2.3.5 (page 84) in [3] with our optimality criterion. Then a new hybrid finite pivoting rule is proposed either to obtain a optimal basic solution for LP or to choice the pivot of the next iteration in the tableau under the degeneracy. Based on this new hybrid finite pivoting rule, cycling is avoided. In addition, we report on computing performance with this procedure which is promising via some classical degenerate LP problems in the literature.

MR(2010)主题分类: 

()
[1] 张建中, 许绍吉. 线性规划[M]. 北京:科学出版社, 1990.
[2] 林诒勋. 线性规划与网络流[M]. 开封:河南大学出版社, 1996.
[3] 孙文瑜, 徐成贤, 朱德通. 最优化方法$($第二版$)$[M]. 北京: 高等教育出版社, 2010.
[4] 李 炜. 线性规划主元算法研究[D]. 东南大学博士论文, 2004.
[5] 岳红伟. 投影主元标单纯形算法[D]. 东南大学硕士论文, 2006.
[6] Avis D, Chvat′al V. Notes on bland’s pivoting rule[J]. Mathematical Programming Study, 1978, 8: 24-34.
[7] Balinski M L, Tucker A W. Duality theory of linear programs: a constructive approach with applications[J]. SIAM Review, 1969, 11(3): 347-377.
[8] Bland R G. New finite pivoting rules for the simplex method[J]. Mathematics of Operations Research, 1977, 2: 103-107.
[9] Charnes A. Optimality and degeneracy in linear programming[J]. Econometrica, 1952, 20: 160- 170.
[10] Garc′?a P G, Palomo A S. Phase I cycling under the most-obtuse-angle pivot rule[J]. European Journal of Operational Research, 2005, 167: 20-27.
[11] Gass S I, Vinjamuri S. Cycling in linear programming problems[J]. Computers & Operations Research, 2004, 31: 303-311.
[12] Hoffman A J. Cycling in the simplex algorithm[R]. Washington, DC: National Bureau of Standards, 1953.
[13] Pan P Q. Practical finite pivoting rules for the simplex method[J]. OR Spektrum, 1990, 12: 219- 225.
[1] 张凯, 杜世民, 杨润萍. 基于整数线性规划的后布图线长优化方法[J]. 数值计算与计算机应用, 2018, 39(4): 265-273.
阅读次数
全文


摘要