《运筹学》第三章 整数规划模型.pdf

（二） 《运筹学》 • 第三章 整数规划模型 第一节 引言 第二节 整数规划问题及其数学模型 第三节 分枝定界法 第四节 0—1规划的解法 第五节 指派问题及其解法 2010-9-18 《整数规划》 1 第一节 引言 1、在线性规划问题的讨论中，（LP）模型的解仅限定非负，可以为分数或 小数，而在许多经济管理的实际问题中，决策变量的取值只有取非负的整 数才有实际意义。例如：调度的车辆数、销售网点的设置数、指派工作的 人数等等。 2、称变量限制为非负正数的数学规划为整数规划问题。若全部变量限制为非 负正数的数学规划为纯整数规划；若部分变量限制为非负正数的数学规划 为混合整数规划。 3、本章讨论的是约束条件和目标函数均为线性的整数规划问题，即线性整数 规划问题（简称整数规划） 2010-9-18 《整数规划》 2 4 、整数规划的数学模型的一般形式： n min(max)Z c x j j j 1 n a x b (i 1,2,3, m)  ij j i j 1   xj 0 (j 1,2,3, n)   x 皆为整数或部分为整数  j 5、称决策变量均为0—1变量的整数规划为0—1规划。 6、“用舍入取整”的方法得到整数规划的解是不可取的，这样得到的解行可能 远远偏离最优解，甚至是非可行解。 2010-9-18 《整数规划》 3 第二节 整数规划问题及其数学模型 一、生产计划问题 例1 某厂生产A 、A 两种产品，产品分别由B 、B 两种部件组装而成，每件 1 2 1 2 产品所用的部件数量和部件的产量限额以及产品的利润等资料由下表给 出，应如何安排生产使之获取最大利润？ 产品 部件 B1 B2 利润（百元） A1 6 1 15 A2 4 3 20 部件的最大产量