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

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

求解0-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 Huizhen^1,2,*, WEI Xin¹, MA Liang¹

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

摘要/Abstract

摘要： 提出了一种求解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

张惠珍, 魏欣, 马良. 求解0-1线性整数规划问题的有界单纯形法[J]. 运筹学学报, 2014, 18(3): 71-78.

ZHANG Huizhen, WEI Xin, MA Liang. The bounded simplex method to solve the 0-1 linear integer programming problem[J]. Operations Research Transactions, 2014, 18(3): 71-78.