第五章整数线性规划整数规划问题的提出分支定界法割平面解法0-1型整数规划指派问题
第五章 整数线性规划 整数规划问题的提出 分支定界法 割平面解法 0-1型整数规划 指派问题
第一节整数规划问题的提出整数规划数学模型的一般形式一部分或全部决策变量取整数值的规划问题整数规划整数规划中不考虑整数条件所对应的规划问题该整数规划的松弛问题松弛问题为线性规划的整数规划问题整数线性规划
第一节 整数规划问题的提出 整数规划数学模型的一般形式 一部分或全部决策变量取整数值的规划问题 ——整数规划 整数规划中不考虑整数条件所对应的规划问题 ——该整数规划的松弛问题 松弛问题为线性规划的整数规划问题 ——整数线性规划
整数线性规划一般形式：(min）z=maxCij=1Zajx ≤ (=,≥)b,j=1x,≥0,X2.…，x,中部分或全部取整数
整数线性规划一般形式： n中部分或全部取整数 j i n j ij j n j j j x x x x a x b z c x , ,., 0 ( , ) max min 1 2 1 1
整数线性规划的几种类型纯整数线性规划混合整数线性规划0-1型整数线性规划例如选择投资项目问题（0-1规划问题）
整数线性规划的几种类型 纯整数线性规划 混合整数线性规划 0-1型整数线性规划 例如选择投资项目问题（0-1规划问题）
整数规划的例子例1：某服务部门各时段（每2小时为一时段）需要的服务员人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。6583472时段183895101113服务员最少人数
整数规划的例子 例1：某服务部门各时段（每2小时为一时段） 需要的服务员人数见下表。按规定服务员连续 工作8小时为一班。现要求安排服务员的工作 时间，使服务部门服务员总数最少。 时段 1 2 3 4 5 6 7 8 服务员最少人数 10 8 9 11 13 8 5 3