运筹学课件第五章__整数规划.pdf

第五章 整数规划 Integer linear programming 第1页 1 第一节 整数规划的数学模型 一、整数规划问题 整数规划问题（IP ）:是指要求部分 或全部决策变量的取值为整数的规划问 题。 松弛问题：不考虑整数条件，由余 下的目标函数和约束条件构成的规划问 题。 重点研究：整数线性规划问题 第2页 二、整数线性规划问题的模型 n max(min) Z c x j j j 1 n aij x j (, )bi i=1,2,…,m j 1 x 0 j=1,2,…,n j xj 中取部分或全部为整数 第3页 三、整数规划问题的类型： 1.纯整数规划：全部决策变量都取整数 值的线性规划 2. 0-1型整数规划：决策变量只取0 或1的线性规划 3. 混合整数规划：部分决策变量取整数 值的线性规划 第4页 举例 例1: 某服务部门各时段（每2h为一时段）需 要的服务员人数见下表。按规定服务员连续 工作8h （即四个时段）为一班。现要求安排 服务员的工作时间，使服务部门服务员总数 最少？ 时段 1 2 3 4 5 6 7 8 服务员 10 8 9 11 13 8 5 3 最少数目 第5页 解：设在第j 时段开始时上班的服务员人 数为xj minZ= x + x +x +x +x 1 2 3 4 5 x  10 1 x + x  8 1 2 x + x + x 9 1 2 3 x +x + x + x 11 1 2 3 4 x + x + x + x 13 2 3 4 5 x + x + x 8 3 4 5 x + x 5 4 5 x 3 5 x 0 (j =1,…,5 )且为整数