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

第二节分支定界解法分支定界法是枚举法基础上的改进。分支定界法的关键是分支和定界。10@思路：利用其相应的线性规划问题（即松弛问题）的最优解值）来分支定界。，设最大化的整数规划问题A，与它相应的线性规划为问题B从解问题B开始，若最优解不符合A的整数条件，则B的最Z优目标函数值必是A的最优目标函数值z*的上界，记作而A的任意可行解的目标函数值将是z*下界Z分支定界法就是将B的可行域分成子区域（称为分支）的方法，逐步减少艺和增大最终求到zZ

 分支定界法是枚举法基础上的改进。  分支定界法的关键是分支和定界。  思路：利用其相应的线性规划问题（即松弛问题）的最优解（ 值）来分支定界。  设最大化的整数规划问题A，与它相应的线性规划为问题B  从解问题B开始，若最优解不符合A的整数条件，则B的最 优目标函数值必是A的最优目标函数值z * 的上界，记作 ； 而A的任意可行解的目标函数值将是z*下界  分支定界法就是将B的可行域分成子区域（称为分支）的方 法，逐步减少 和增大 ，最终求到z * 第二节 分支定界解法 z z z z

例：求解整数规划问题A整数规划问题A松弛问题Bz = 40 x + 90 x2z = 40 x + 90 x2maxmax9 x + 7 x2 ≤ 569 x + 7 x2 ≤ 567 x, + 20 x, ≤ 707 x, + 20 x2 ≤ 70x1,×2≥0且为整数Xi,X2 ≥ 0设问题A的最优目标函数值为z*≤Z初始上界

例：求解整数规划问题A             , 0     7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x 且为整数 松弛问题B 设问题A的最优目标函数值为 整数规划问题A 初始上界             , 0     7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x z ~ z* 

z = 40 x + 90 x2max图解法分析：9x1 + 7x2 ≤ 567 x1 + 20 x2 ≤ 70不是问题A解X1, X2 ≥ 08但 z*≤Zo7B, : x ≤ 464.81Xi =*5X2 = 1.82B2 : xi ≥ 54Zo = 3563B2≥ = 0, z = 35685679102340

图解法分析： 、 、 、 、 、 、 、 、 、 、 、 0 1 2 3 4 5 6 7 8 9 10 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - B 356 1 .82 4 .81 0 2 1    z x x B1 : x 1  4 B 2 : x 1  5 z  0 , z  356             , 0     7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x 不是问题A解 但 0 z*  z

图解法分析：32BXAB56734201

图解法分析： 0 1 2 3 4 5 6 7 4 3 2 1 B1 : x 1  4 B 2

xi = 4.81图解法分析：x2 = 1.82X≤4B: x = 4.00Zo =356x2=2.10Xi≥5Z = 349DB2:x,=5.003X2 =1.57Z2 = 3412BXA0z = 349BZ三57623401

图解法分析： 0 1 2 3 4 5 6 7 4 3 2 1 B1 : x 1  4 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 z  0 z  349 B 2 356 1.82 4.81 0 2 1    z x x x1  5 x1  4