重庆工商大学：《管理运筹学》课程教学课件（讲稿）第五章 整数线性规划

第五章整数线性规划整数规划问题的提出分支定界法割平面解法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

52467813时段88531091113服务员最少人数解：设在第j时段开始上班的人数为x，则minZ=X+X2+X3+X4+X5xi ≥ 10j最大=5X+X ≥ 8Xi+X2+x3≥9Xi+X+X+4≥11X2+X3+X4+Xs≥13s.t.-X3+x4+Xs≥8X4+x,≥5Xs ≥3X1,×2,,4,×≥0且取整数

解：设在第j时段开始上班的人数为 ，则 min 1 2 3 4 5 z  x  x  x  x  x j x 时段 1 2 3 4 5 6 7 8 服务员最少人数 10 8 9 11 13 8 5 3 j 最大取值？=5 10 x1  x 2  x 3  x 4  x 5  13 x1  x 2  8 x1  x 2  x 3  9 11 x1  x 2  x 3  x 4  x 3  x 4  x 5  8 x1 , x 2 , x 3 , x 4 , x 5  0且取整数 x 5  3 x 4  x 5  5 s.t

解的特点整数线性规划及其松弛问题比较，前者的最优解的目标函数值不会优于后者的例2：考虑下面的整数规划问题z=x +4x2max- 2x +3x2≤ 3xi + 2 x2 ≤ 8Xi,×2≥0且取整数

解的特点 整数线性规划及其松弛问题比较，前者的 最优解的目标函数值不会优于后者的。 例2：考虑下面的整数规划问题              , 0且取整数 2 8 - 2 3 3 max 4 1 2 1 2 1 2 1 2 x x x x x x z x x

增加一个约束条件从图上分析：目标函数值将不会比原来变好松弛问题的最优解整数规划最优解D12345678解的特点整数线性规划及其松问题比较，前者的最优解的目标函数值不会优于后者的

从图上分析： 0 1 2 3 4 5 6 7 8 B P C * A 整数规划 最优解 松弛问题 的最优解 解的特点 整数线性规划及其松弛问题比较，前者的最优解的目 标函数值不会优于后者的。 增加一个约束条件， 目标函数值将不会 比原来变好

例3：某厂拟用集装箱托运两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表。问两种货物各托运多少箱，可使获得的利润最大？货物体积(米3/箱）重量（百公斤/箱）利润（百元/箱）5甲22054乙1024米3托运限制13百公斤z = 20 x, +10 x2max不考虑整数约束5x + 4x2≤ 24的最优解为：x,=4.8, x2=0,2 xj + 5x2 ≤ 13max z= 96Xi,X2≥ 0且取整数

例3：某厂拟用集装箱托运两种货物，每箱的 体积、重量、可获利润以及托运所受限制如下表。 问两种货物各托运多少箱，可使获得的利润最大？ 货物 体积（米3/箱） 重量（百公斤/箱） 利润（百元/箱） 20 10 2 5 5 4 甲 乙 托运限制 24米3 13百公斤 不考虑整数约束 的最优解为： x1=4.8, x2=0,  max z = 96            , 0且取整数 2 5 13 5 4 24 max 20 10 1 2 1 2 1 2 1 2 x x x x x x z x x

从图上分析：X2z = 96z = 903(4, 1)2(4.8, 0)112345678OX

从图上分析： 0 1 2 3 4 5 6 7 8 1 x1 B C 2 x2 3 z = 90 z = 96 (4.8, 0) (4, 1)