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

不是问题A解: xi = 4.004≤图解法剪枝x2 =2.10Zi=349=1.42B4:X1X2≥3X2 = 3.00X2 ≤2Z4=327B, : Xi4.00三340二NIN=2.00X2341=Z3=340是问题A解B但 Z≤27035614

图解法分析： 4 3 2 1 340 2 .00 : 4 .00 3 2 3 1    z x B x 327 3 .00 : 1 .42 4 2 4 1    z x B x 0 1 2 3 4 5 6 7 341 340   z z 341 340   z z 349 2.10 : 4.00 1 2 1 1    z x B x x2  3 x2  2 B 4 B 3 是问题A解 但 z ~ z 3  不是问题A解 而 剪枝 z  z 4

B2 : x = 5.00图解法分析：x2 =1.57Z2 =341340=≥2X2x ≤1341=5.44B, : X1B6= 1.00X2无可行解3085=Z532B75236401

图解法分析： 0 1 2 3 4 5 6 7 4 3 2 1 308 1 .00 : 5 .44 5 2 5 1    z x B x 无可行解 : B 6 341 1.57 : 5.00 2 2 2 1    z x B x x2 1 x2  2 341 340   z z 341 340   z z B 5

分支定界的全过程4.81B :xi二≥ = 0, z = 3561.82二X2356二Z0x≤4x≥55.00B2:X1=4.00B,: x1三≥=0=1.57X22.10二NX2= 349341Z2=349Z二1X2 ≤2≥3X24.00= 1.42B, : xiB4 : Xi三= 340NIIN=2.003.00=X2X2341三23 = 340Z4=327X

分支定界的全过程： 356 1 . 82 : 4 . 81 0 2 1    z x B x 349 2 . 10 : 4 . 00 1 2 1 1    z x B x 341 1 .57 : 5 .00 2 2 2 1    z x B x 340 2 .00 : 4 .00 3 2 3 1    z x B x 327 3 .00 : 1 .42 4 2 4 1    z x B x z  0 , z  356 349 0   z z 341 340   z z 4 x1  5 x1  x2  2 x2  3

B, : Xi=5.00= 4.00B : xi=0Zx2 =1.57x2 = 2.10N=349Z2 =341Z1 =3492X2. ≥3X24.00B3: XiB4 : x = 1.42=福z = 340=2.00X2 = 3.00X2一≥= 341340Z4=327=<≥2X2X25.44Bs : x=B= z* = 340ZX2 =1.00无可行解308=Z5.X

308 1 .00 : 5 .44 5 2 5 1    z x B x 无可行解 : B 6 x2 1 x2  2 349 2.10 : 4.00 1 2 1 1    z x B x 341 1.57 : 5.00 2 2 2 1    z x B x 340 2.00 : 4.00 3 2 3 1    z x B x 327 3.00 : 1.42 4 2 4 1    z x B x 349 0   z z 341 340   z z x2  2 x2  3 340 * z  z 

整数规划(最大化)的步骤第一步:将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B：第二步：买求解问题B，可得以下情况之一：B没有可行解，则A也没有可行解，求解过程停止。1B有最优解，且符合问题A的整数条件，则B的最优解2即为A的最优解，求解过程停止。B有最优解，但不符合A的整数条件，记其目标函数值3为

整数规划（最大化）的步骤 第一步： 将求解的整数规划问题称为A，将与其相对应的线性规划 问题称为B： 第二步：求解问题B，可得以下情况之一： ① B没有可行解，则A也没有可行解，求解过程停止。 ② B有最优解，且符合问题A的整数条件，则B的最优解 即为A的最优解，求解过程停止。 ③ B有最优解，但不符合A的整数条件，记其目标函数值 为 。0 z