用于求解0-1型整数规划问题的新算法研究  

A New Algorithm for Zero-one Integer Linear Programming

作　　者：赵宁[1] 宓为建[1] 王东胜[1] 

机构地区：[1]上海海事大学,上海201306

出　　处：《运筹与管理》2012年第5期107-114,共8页Operations Research and Management Science

基　　金：国家863计划重点项目(2009AA043001);上海市教委项目(J50604&09ZZ163)

摘　　要：本文针对0-1型整数规划问题的求解算法进行研究,在分析了常用典型算法的求解原理和过程的基础上,提出了一种新的算法———Cards-flipping算法。该算法在此类问题的计算上具有通用性,其可靠性与精度等效于枚举法,求解过程中无需遍历各中间解的目标值即可按照最优顺序依次检验中间解,找到的第一个可行解即为最优解,因此求解效率较高。通过对该算法的数学证明以及大量的算例分析,证明了算法的有效性和实用性。This paper discusses the problem of solving zero-one integer linear programming models.Based on the analysis of different commonly used algorithms,we put forward a new algorithm named cards-flipping algorithm which demonstrates reliability and accuracy equivalent to enumeration methods.The correctness and the practicability of the method are verified with mathematical proofs and a great deal of examples.

关 键 词：运筹学 Cards-flipping算法 翻牌序列 0-1型整数规划 

分 类 号：O221.4[理学—运筹学与控制论]