0-1整数规划的算法及其应用.doc

摘 要 整数规划；0-1整数规划；枚举法；组合直接搜寻法 0-1 integer linear programming plays an important role in integer programming. In many practical problems, such as assignment problem, site selection problem and deliver goods problem, they are all boiled down to 0-1 integer linear programming problem. And just because of the 0-1 integer linear programming has profound background and widely used, it is very necessary and important practical sense to study its algorithm. In this paper, we mainly study the algorithms for 0-1 integer linear programming and its applications. Firstly, we introduce the related concepts, features and functions, and set up the mathematical model based on the practical problems in the paper. Secondly, we study three algorithms about method of exhaustion, implicit enumeration method (which includes filter implicit enumeration, branch and bound method and branch-implied enumeration) and the method of combination and direction-finding. And then, we apply the algorithms to work out the practical examples of calculation. At last, we compare and expound the advantages and disadvantages of every algorithm in this paper. Key words integer programming；0-1 integer linear programming；enumeration method；the method of combination and direction-finding 1 1.1 研究背景及意义 1 1.2 国内外研究方法综述 1 1.3 本文主要研究内容 2 第2章 0-1整数规划的数学模型 3 2.1 0-1整数规划的特点及作用 3 2.2 0-1变量的定义 5 2.3 0-1整数规划的应用举例 5 2.4 本章小结 9 第3章 穷举法 10 3.1 穷举法的介绍 10 3.2 穷举法的计算实例 10 3.3 对穷举法的评价 11 3.4 本章小结 11 第4章 隐枚举法 12 4.1 过滤隐枚举法 12 4.1.1 过滤隐枚举法的介绍 12 4.1.2 过滤隐枚举法的计算实例 12 4.1.3 对过滤隐枚举法的评价 14 4.2 分枝定界法 14 4.2.1 分枝定界法的介绍 14 4.2.2 分枝定界法的计算实例 16 4.2.3 对分枝定界法的评价 17 4.3 分枝―隐枚举法 17 4.3.1 分枝―隐枚举法的介绍 17 4.3.2 分枝―隐枚举法的计算实例 18 4.3.3 对分枝―隐枚举法的评价 19 4.4 本章小结 20 第5章 组合直接搜寻法 21 5.1 组合直接搜寻法的介绍 21 5.2 组合直接搜寻法的计算实例 24 5.3 对组合直接搜寻法的评价 25 5.4 本章小结 25 结 论 26 参考文献 27 致 谢 28 第1章 绪论 1.1 研究背景及意义 在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，通常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。变量全部或部分取整数的线性规划统称为整数线性规划（Integer Programming，简记为IP）。其中变量全部取整数的线性规划称为纯整数线性规划。只要