1、1第五章 整数规划第 五 章 整数规划学时安排： 8学时教学目的： 掌握若干特殊整数规划的解法教学内容：1.整数规划问题及特点2.分枝定界法与割平面法3.0-1规划4.指派问题 教学重点： 割平面法与指派问题 教学难点： 分枝定界法与割平面法2第 五 章 整数规划教学内容第一节 整数规划 问题的提出第二节 解纯整数规划的割平面法 第三节 分支定界法 第四节 -整数规划 第五节 指派问题3第一节 整数规划问题的提出1. 整数规划问题基本概念2. 整数规划问题的数学模型3. 整数规划解的特点第 五 章 整数规划41. 基本概念 整数规划：要求部分或全部决策变量取整数值的规划问题。 整数规划问题的松
2、弛问题：不考虑整数条件的规划问题。 整数线性规划：整数规划为线性规划纯整数线性规划（ pure integer linear programming)混合整数线性规划（ mixed integer linear programming）0-1整数线性规划 (zero-one integer linear programming）注意： 后面提到的整数规划，一般指的都是整数线性规划。第 五 章 整数规划52. 整数规划数学模型的一般形式第 五 章 整数规划63. 整数规划解的特点问题：能否将松弛问题最优解的近似值（取整、四舍五入）作为整数规划问题的最优解？例 1：求下述整数规划的最优解。第 五
3、章 整数规划7第 五 章 整数规划1 2 3 4 5 6 7x115234x2A (3.25,2.5)2x1+3x2=14X1+0.5x2 =4.5Z=3x1+2x2最优解为 (4,1)8第 五 章 整数规划结论： 不能把松弛问题的最优解通过 “四舍五入 ”或“截尾 ”（即凑整）处理后作为整数规划的最优解。不过，在变量取值很大时，用上述方法得到的解与最优解差别不大。 点 (4,1)不是可行域的顶点，所以直接用图解法或单纯形法无法求出整数规划问题的最优解9第 五 章 整数规划整数线性规划的解与松弛问题的解既有联系，又有本质的区别。设 IP的松弛问题的可行域为C， IP的可行域为 C，则有 C C 整数规划的可行解是松弛问题可行解集合的一个子集。所以 ： IP的可行解一定是它的松弛问题的可行解。 IP的最优值不会优于其松弛问题的最优值。10第二节 割平面法1. 割 平面方法的基本思想和 步骤2. 构造割平面约束的方法3. 示例第五章 整数规划
