北大中文核心期刊
中国科学引文数据库（CSCD）来源期刊
中国科技核心期刊
入选数学领域高质量科技期刊
Scopus
EBSCO 

运筹学学报 ›› 2014, Vol. 18 ›› Issue (3): 71-78.

• 运筹学 • 上一篇    下一篇

求解0-1线性整数规划问题的有界单纯形法

张惠珍, 魏欣, 马良   

  1. 1. 上海理工大学管理学院, 上海 200093,
    2. 上海理工大学超网络 (中国) 研究中心, 上海 200093
  • 出版日期:2014-09-15 发布日期:2014-09-15
  • 通讯作者: 张惠珍 E-mail:zhzzywz@gmail.com
  • 基金资助:

    上海市一流学科建设项目(No. S1201YLXK), 高等学校博士学科点专项科研基金(No. 20123120120005), 上海高校青年教师培养资助计划(No. slg12010), 上海市教育委员会科研创新项目(No. 14YZ090), 上海理工大学国家级项目培育课题(No. 13XGQ07), 沪江基金(No. A14006)

The bounded simplex method to solve the 0-1 linear integer programming problem

ZHANG Huizhen1,2,*, WEI Xin1, MA Liang1   

  1. 1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China, 2. Center for Supernetworks Research, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2014-09-15 Published:2014-09-15

PDF

953

被引次数

6

摘要： 提出了一种求解0-1线性整数规划问题的有界单纯形法, 不仅通过数学论证, 讨论了该方法的合理性, 奠定了其数学理论基础, 而且通过求解无容量设施选址问题, 验证了该方法的可行性. 在此基础上, 就该有界单纯形法的不足和存在的问题, 给出了进一步改进的途径和手段.

关键词: 单纯形法, 0-1规划, 有界单纯形法, 旋转迭代

Abstract: In this paper, a bounded simplex method to solve the 0-1 linear integer programming problem is proposed. Not only is the reasonability of this method proved from the point of mathematical theory, which establishes its theoretic foundation, but also is its feasibility validated from the point of numerical experiments by solving the un-capacitated facility location problem. Furthermore, the further improvement approach and techniques are discussed to overcome the shortcoming of this simplex method.

Key words: simplex method, 0-1 programming, bounded simplex method, pivoting iteration