第2节分支定界解法 令应寻找仅检査可行的整数组合的一部分,就能定出最优的 整数解的方法。分支定界解法就是其中之 ◆分支定界法可用于解纯整数或混合整数线性规划问题 o20世纪60年代初由 Land Doig和 Dakin等提出,是解整数线性规划的 重要方法之一。 今分支定界法的基本思想 o考虑最大化整数线性规划问题A,与它相应的线性规划记为问题B。 我们从解问题B开始,若其最优解不符合A的整数条件,那么B的 最优目标函数必是A的最优目标函数值z的上界,记作2;而A的 任意可行解的目标函数值将是z的一个下界。分支定界法就是将B 的可行域分成子区域(称为分支)的方法,逐步减小和增太,最 终求到z。 清华大学出版社
清华大学出版社 12 第2节 分支定界解法 z ❖ 应寻找仅检查可行的整数组合的一部分，就能定出最优的 整数解的方法。分支定界解法就是其中之一。 ❖ 分支定界法可用于解纯整数或混合整数线性规划问题。 20世纪60年代初由Land Doig和Dakin等提出，是解整数线性规划的 重要方法之一。 ❖ 分支定界法的基本思想 考虑最大化整数线性规划问题A，与它相应的线性规划记为问题B。 我们从解问题B开始，若其最优解不符合A的整数条件，那么B的 最优目标函数必是A的最优目标函数值z *的上界，记作 ；而A的 任意可行解的目标函数值将是z *的一个下界 。分支定界法就是将B 的可行域分成子区域(称为分支)的方法，逐步减小 和增大 ，最 终求到z *。 z z z
第2节分支定界解法 冷例2求解问题A maxz=40x1+90x,① 9x+7x256② 7x1 +20x2≤70 (52) x1,x,≥0④ x1,x2整数⑤ 清华大学出版社
清华大学出版社 13 第2节 分支定界解法 ❖ 例2 求解问题A max z=40x1+90x2 ① 9x1+7x2 ≤56 ② 7x1+20x2 ≤70 ③ (5.2) x1，x2 ≥0 ④ x1，x2整数 ⑤
第2节分支定界解法 令解:先不考虑条件⑤,即解相应的线性规划B,①~④(见 图5-2),得最优解x1=4.81,x2=1.82,z0=356 可见它不符合整数条件⑤。 这时zo是问题A的最优目标函数值z 的上界,记作z=2 9x1+7x2=56 而在x1=0,x2=0时, 显然是问题A的一个整数可行解, 这时z=0,是z*的一个下界 记作2=0,即0≤z米≤356 B 71+20x2=70 012345678910x1
清华大学出版社 14 第2节 分支定界解法 ❖ 解：先不考虑条件⑤，即解相应的线性规划B,①～④(见 图5-2)，得最优解x1 =4.81，x2 =1.82，z0 =356 可见它不符合整数条件⑤。 这时z0是问题A的最优目标函数值z* 的上界，记作z0 = 。 而在x1 =0，x2 =0时， 显然是问题A的一个整数可行解， 这时z=0，是z*的一个下界， 记作 =0，即0≤z*≤356 。 z z
第2节分支定界解法 首先注意到相应的线性规划问题(问题B)的解中有一个非 整数变量,如x=481 于是,在原问题中增加两个约束条件:x≤4和x1≥5,将原问 题分解为两个子问题B1和B2即两支) 给每支增加一个约束条件后,如图5-3所示,并不影响问题 A的可行域。 仍然不考虑整数条件约束,解问题B和B2,得到最优解为: 问题B问题B z1=349z2=341 1=4.00|x1=5.00 x2=2.10x2=1.57 清华大学出版社
清华大学出版社 15 第2节 分支定界解法 ❖ 首先注意到相应的线性规划问题（问题B）的解中有一个非 整数变量，如x1 =4.81。 ❖ 于是，在原问题中增加两个约束条件：x1 ≤4和x1 ≥5，将原问 题分解为两个子问题B1和B2 (即两支)。 ❖ 给每支增加一个约束条件后，如图5-3所示，并不影响问题 A的可行域。 ❖ 仍然不考虑整数条件约束，解问题B1和B2，得到最优解为： 问题 B1 问题 B2 z1=349 x1=4.00 x2=2.10 z2=341 x1=5.00 x2=1.57
第2节分支定界解法 x1<4,x1>5 问题B1 问题B2 图53 0123456x1 16 清华大学出版社
清华大学出版社 16 第2节 分支定界解法 ❖ x1 ≤4，x1 ≥5 图5-3