首页    期刊浏览 2025年06月30日 星期一
登录注册

文章基本信息

  • 标题:SMALL DEGENERATE SIMPLICES CAN BE BAD FOR SIMPLEX METHODS
  • 本地全文:下载
  • 作者:Shinji Mizuno ; Noriyoshi Sukegawa ; Antoine Deza
  • 期刊名称:日本オペレーションズ・リサーチ学会論文誌
  • 印刷版ISSN:0453-4514
  • 电子版ISSN:2188-8299
  • 出版年度:2017
  • 卷号:60
  • 期号:4
  • 页码:419-428
  • DOI:10.15807/jorsj.60.419
  • 语种:English
  • 出版社:Japan Science and Technology Information Aggregator, Electronic
  • 摘要:

    We show that the simplex method with Dantzig's pivoting rule may require an exponential number of iterations over two highly degenerate instances. The feasible region of the first instance is a full dimensional simplex, and a single point for the second one. In addition, the entries of the constraint matrix, the right-hand-side vector, and the cost vector are {0,1,2}-valued. Those instances, with few vertices and small input data length, illustrate the impact of degeneracy on simplex methods.

  • 关键词:Linear programming;simplex methods;small degenerate instances
国家哲学社会科学文献中心版权所有