第五章 整数规划 整数规划及其数学模型 用分支定界法求解整数规划 0-1型整数规划 指派问题 3
3 第五章 整 数 规 划 整数规划及其数学模型 用分支定界法求解整数规划 0-1型整数规划 指派问题
第一节整数规划及其数学模型 整数规划数学模型的一般形式 要求一部分或全部决策变量必须取整数值的 规划问题称为整数规划(integer programming, 简记IP)。不考虑整数条件，由余下的目标函数 和约束条件构成的规划问题称为该整数规划问题 的松弛问题(slack problem)。若松弛问题是 个线性规则，则称该整数规划为整数线性规划 (integer linear programming)。整数线性规划 数学模型的一般形式为：
4 一、 整数规划数学模型的一般形式 要求一部分或全部决策变量必须取整数值的 规划问题称为整数规划(integer programming， 简记IP)。不考虑整数条件，由余下的目标函数 和约束条件构成的规划问题称为该整数规划问题 的松弛问题(slack problem)。若松弛问题是一 个线性规则，则称该整数规划为整数线性规划 (integer linear programming)。整数线性规划 数学模型的一般形式为： 第一节 整数规划及其数学模型
第一节整数规划及其数学模型 OptZ=cix1+c2x2+.+cnxm (1-1) ak+a2x2+.+anXn≤ (=,≥) b a21X1+a222+.+a2nXn≤ (=,2) b2 (1-2) am+am22.+amnn ≤ (=,2) x,部分或全部取整(i=1,2,.,n) 5
5 第一节 整数规划及其数学模型 Opt Z = c1 x1 + c2 x2 + . + cn xn (1-1) 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1, 2, , ) ( , ) ( , ) . ( , ) n n n n m m mn n m i i n a x a x a x b a x a x a x b a x a x a x b x = + ++ = + ++ = + ++ = 部分或全部取整（ (1-2)
第一节整数规划及其数学模型 整数线性规划问题分为下列几种类型： 1.纯整数线性规划：指全部决策变量部必 须取整数值的整数线性规划。有时，也称为全 整数规划 2.混合整数线性规划：指决策变量中有 一部分必须取整数值，另一部分可以不取整数 值的整数线性规划 3.0-1型整数线性规划：指决策变量只能 取值0或1的整数线性规划
6 整数线性规划问题分为下列几种类型： 1．纯整数线性规划：指全部决策变量部必 须取整数值的整数线性规划。有时，也称为全 整数规划。 2．混合整数线性规划：指决策变量中有 一部分必须取整数值，另一部分可以不取整数 值的整数线性规划。 3．0-1型整数线性规划：指决策变量只能 取值0或1的整数线性规划。 第一节 整数规划及其数学模型
第一节整数规划及其数学模型 本章仅讨论整数线性规划。后面提到的整数 规划，一般都是指整数线性规划 整数规划的实例很多。例如，我们前面介绍 的生产问题，如果产量的单位是件，则往往就要 求变量取整数。另外，在表示工厂何时开工等问 题时，往往需要利用0-1型整数变量 整数规划解的特点 整数线性规划及其松弛问题，从解的特点上 看，二者之间既有密切的联系，又有本质区别
7 本章仅讨论整数线性规划。后面提到的整数 规划，一般都是指整数线性规划。 整数规划的实例很多。例如，我们前面介绍 的生产问题，如果产量的单位是件，则往往就要 求变量取整数。另外，在表示工厂何时开工等问 题时，往往需要利用0-1型整数变量。 二、 整数规划解的特点 整数线性规划及其松弛问题，从解的特点上 看，二者之间既有密切的联系，又有本质区别。 第一节 整数规划及其数学模型