整数规划1.整数规划的数学模型及解的特点2.分支定界法、割平面法3.0-1整数规划4.指派问题
整数规划 1.整数规划的数学模型及解的特点 2.分支定界法、割平面法 3.0-1整数规划 4.指派问题
1.整数规划的数学模型及解的特点整数规划数学模型的一般形式一部分或全部决策变量取整数值的规划问题一整数规划整数规划中不考虑整数条件是对应的规划问题一一该整数规划的松弛问题松弛问题为线性规划的整数规划问题一整数线性规划
1.整数规划的数学模型及解的特点 整数规划数学模型的一般形式 一部分或全部决策变量取整数值的规划问题 ——整数规划 整数规划中不考虑整数条件是对应的规划问题 ——该整数规划的松弛问题 松弛问题为线性规划的整数规划问题 ——整数线性规划
整数线性规划一般形式：max(min) z=≥cjxj(a)2af, ≤(=,2)h,.... (b)j=1x, ≥0....(c)Xi，X2，··"，Xn中部分或全部取整数·...（d）
整数线性规划一般形式： = = = = , , , ( ) 0 ( ) ( , ) ( ) max(min) ( ) 1 2 1 1 x x x d x c a x b b z c x a n j i n j i j j n j j j 中部分或全部取整数
整数线性规划的几种类型纯整数线性规划混合整数线性规划0-1型整数线性规划例如选择投资项目问题页（0-1规划问题
整数线性规划的几种类型 纯整数线性规划 混合整数线性规划 0-1型整数线性规划 例如选择投资项目问题（0-1规划问题）
整数规划的例子例1：生产计划问题例2：某服务部门各时段（每2小时为一时段）需要的服务员人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少6712358时段453服务员988111310最少人数
整数规划的例子 例1：生产计划问题。 例2：某服务部门各时段（每2小时为一时段） 需要的服务员人数见下表。按规定服务员连续 工作8小时为一班。现要求安排服务员的工作 时间，使服务部门服务员总数最少。 时段 1 2 3 4 5 6 7 8 服务员 最少人数 10 8 9 11 13 8 5 3