5.2 分支界定解法ppt课件

1、1;. 如果通过对全体可行的整数解逐个比较优劣，如果通过对全体可行的整数解逐个比较优劣，得到最优解的方法，得到最优解的方法，称为完全枚举法（穷举法）。称为完全枚举法（穷举法）。但在解的个数很多时，这往往是不可能的。但在解的个数很多时，这往往是不可能的。 如果能通过仅对部分可行整数解的讨论，如果能通过仅对部分可行整数解的讨论，就得到原问题的最优解，就得到原问题的最优解，称为部分枚举法或隐枚举法。称为部分枚举法或隐枚举法。分枝定界法就是一种隐枚举法，分枝定界法就是一种隐枚举法，这是一种应用很广的求解方法。这是一种应用很广的求解方法。v分枝定界法可以用来求解纯整数规划和混合整数规划，它是整数规划的常

2、分枝定界法可以用来求解纯整数规划和混合整数规划，它是整数规划的常用解法。用解法。2;.算法的依据：算法的依据：“对于目标函数值来讲对于目标函数值来讲, ,整数规划的整数规划的 最优解不会更优于最优解不会更优于相应的线性规划问题相应的线性规划问题的最优解的最优解”。具体说就是，对具体说就是，对极大化极大化问题，问题，与整数规划问题相应的线性规划问题（即松弛问题）与整数规划问题相应的线性规划问题（即松弛问题）的目标函数值，的目标函数值，是该整数规划问题目标函数的上界；是该整数规划问题目标函数的上界；任何满足整数条件的可行解的目标函数值将是其下界。任何满足整数条件的可行解的目标函数值将是其下界。下面

3、给出分枝定界法具体作法下面给出分枝定界法具体作法3;. 首先，删去首先，删去， 把原整数规划把原整数规划。其次，其次，。 主要主要特征特征就是就是。最后，最后，如果相应线性规划没有可行解，如果相应线性规划没有可行解， 则原整数规划也没有可行解。则停止；则原整数规划也没有可行解。则停止； 如果相应线性规划有最优解，如果相应线性规划有最优解， 且符合原整数规划问题的整数条件，且符合原整数规划问题的整数条件， 则这个最优解也是原整数规划的最优解，则这个最优解也是原整数规划的最优解， 那么整个计算过程结束；那么整个计算过程结束；4;. 如果相应线性规划有最优解，如果相应线性规划有最优解，但不符合原整数

4、规划问题的整数条件，但不符合原整数规划问题的整数条件，则这个最优解不是原整数规划的最优解，则这个最优解不是原整数规划的最优解， 记此最优值为原整数规划问题记此最优值为原整数规划问题Z*的上界的上界, 然后然后, 用观察法求出下界，用观察法求出下界，转入第二步。转入第二步。5;. 主要主要特征特征是是。 具体作法：具体作法： 从相应线性规划的最优解中，从相应线性规划的最优解中，任意选择一个不满足原整数规划整数条件任意选择一个不满足原整数规划整数条件的决策变量的决策变量x xj j=b bj j以使相应线性规划增加一个约束条件；以使相应线性规划增加一个约束条件；（或（或），），因而得到两个新的线性

5、规划称为分支，因而得到两个新的线性规划称为分支，也称为后继问题也称为后继问题 。列出两分支各自的数学模型，列出两分支各自的数学模型，计算每支的最优解和最优值。计算每支的最优解和最优值。 6;. 经过分支之后，就有如下经过分支之后，就有如下结论结论：分支后并没有减少整数解，分支后并没有减少整数解，故原整数规划的可行域故原整数规划的可行域两两支支可行域的并集。可行域的并集。原整数规划的最优解原整数规划的最优解两两支支最优值的最大值。最优值的最大值。7;. 主要主要特征特征就是就是. . ：以每个后继问题为一分支标明求解的结果，以每个后继问题为一分支标明求解的结果，与其他问题的解的结果中，与其他问题

6、的解的结果中，找出最优目标函数值最大者作为新的上界找出最优目标函数值最大者作为新的上界 ；从已符合整数条件的各分支中，从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界找出目标函数值为最大者作为新的下界z，若无可行解，若无可行解， z=0 z8;. 各分支的最优目标函数中若有小于各分支的最优目标函数中若有小于 z z 者，者，则剪掉这支，即以后不再考虑了。则剪掉这支，即以后不再考虑了。若有大于若有大于z z , ,但不符合整数条件，则继续分支，但不符合整数条件，则继续分支，一直到最后得到一直到最后得到z z* *=z z为止，为止，得最优整数解得最优整数解x xj j* *，j=1

7、j=1，n n用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。若变量数目很大，其计算工作量也是相当可观的。9;.它属于最大化纯整数规划。为便于叙述，我们将其记作它属于最大化纯整数规划。为便于叙述，我们将其记作A A。现在利用分枝定界。现在利用分枝定界法求解之。法求解之。 , 2, 1, 0 x,x6xx45x9x5x8x5yMax2

8、1212121 利用分枝定界法求解：利用分枝定界法求解：A由由A A得到相应线性规划，记作得到相应线性规划，记作B B。10;. 采取图解法或单纯形法，求得采取图解法或单纯形法，求得B B的的最优解（最优解（x x1 1 , , x x2 2）=（ 2.25 , 3.75 2.25 , 3.75 ） 最优值最优值 y ymax max = 41.25= 41.25。 0 x,x6xx45x9x5x8x5yMax21212121B B B的最优解不满足的最优解不满足A A的整数条件，所以它并非的整数条件，所以它并非A A的最优解。的最优解。11;. 0 x,x3x6xx45x9x5x8x5yMa

9、x212212121 2. 2.由由B B的最优解（的最优解（x x1 1 , , x x2 2）= = （ 2.25 , 3.75 2.25 , 3.75 ）中，选择决）中，选择决策变量策变量x x2 2=3.75=3.75，按照既定的原则写出，按照既定的原则写出B B的两枝：的两枝： 0 x,x4x6xx45x9x5x8x5yMax212212121把它们依次记作把它们依次记作B B1 1和和B B2 2。 解解B B1 1得：最优解（得：最优解（x x1 1，x x2 2）=（3 3，3 3）, ,最优值最优值 y ymaxmax= 39= 39解解B B2 2得：最优解（得：最优解（x

10、 x1 1，x x2 2）=（1.8,41.8,4）, ,最优值最优值 y ymaxmax= 41= 41B1B212;. B x1=2.25x2=3.75y=41.25 B1 x1=3 x2=3 y=39 B2 x1=1.8 x2=4 y=41x23x24UB=41.25UB=41.25LB=0LB=0UB=41UB=41LB=39LB=3913;.由图可知。界为由图可知。界为max 39max 39，41 = 4141 = 41。于是。于是 界枝是界枝是B B2 2。但。但是，是，B B2 2的最优解不满足的最优解不满足A A的整数条件，的整数条件， 从而它不是从而它不是A A的最优解。因

11、的最优解。因此，应当再次分枝。此，应当再次分枝。由由B B2 2的最优解中，选择决策变量的最优解中，选择决策变量 x x1 1= 1.8= 1.8， 写出写出B B2 2的两枝：的两枝： 0 x,x1x4x6xx45x9x5x8x5yMax2112212121 0 x,x2x4x6xx45x9x5x8x5yMax2112212121解解B B2121得：最优解（得：最优解（x x1 1，x x2 2）=（1 1，4 4），最优值），最优值y ymaxmax=40.=40.解解B B2222得得: : B B2222无可无可行解。行解。B21B2214;. B x1=2.25 x2=3.75 y

12、 =41.25 B1 x1=3 x2=3 y =39 B2 x1=1.8 x2=4 y =41 B21 x1=1 x2=40/9 y=365/9 B22 无无 可可 行行 解解x23x24x11x12UB=41.25UB=41.25LB=0LB=0UB=41UB=41LB=39LB=39UB=UB=365/9LB=39LB=3915;. 0 x,x4x1x4x6xx45x9x5x8x5yMax21212212121 0 x,x5x1x4x6xx45x9x5x8x5yMax21212212121解解B B211211得：最优解（得：最优解（x x1 1, , x x2 2）=（1, 41, 4）

13、, ,最优值最优值 y ymax max = 37= 37。解解B B212212得：最优解（得：最优解（x x1 1, , x x2 2）=（0, 50, 5）, ,最优值最优值 y ymax max = 40= 40。B212 B211由上图可知，界为由上图可知，界为max 39max 39， 365/9 = 365/9 365/9 = 365/9 。界枝为。界枝为B B2121. . 因因为为B B2121最优解不满足最优解不满足A A的整数条件，不是的整数条件，不是A A的最优解。的最优解。944x2 由由B B2121最优解中，选择变量最优解中，选择变量把把B B2121分成两枝：分

14、成两枝：16;. 现在，已完成的求解过程和所得到的计算结果见下图：现在，已完成的求解过程和所得到的计算结果见下图： B x1=2.25 x2=3.75 y =41.25 B1 x1=3 x2=3 y=39 B2 x1=1.8 x2=4 y=41 B21 x1=1 x2=40/9 y =365/9 B22 无无 可可 行行 解解x2 3x2 4x1 1x1 2B211x1=1x2=4y=37B212x1=0 x2=5y=40 x2 5x2 4UB=41.25UB=41.25LB=0LB=0UB=41UB=41LB=39LB=39UB=UB=365/9LB=39LB=39UB=UB=40LB=40

15、LB=4017;.12121212max322314. .0.54.5,0,zxxxxs txxxx 且均取整数值且均取整数值18;.第一步：放宽第一步：放宽删除整数条件删除整数条件 0 x,x5 . 4x5 . 0 x14x3x2. t . sx2x3zmax21212121L L0 0：L L0 0的最优解为的最优解为(3.25(3.25，2.5)2.5)，z z* *=14.75=14.75转第二步转第二步. .12121212max322314. .0.54.5,0,zxxxxs txxxx 且且均均取取整整数数值值得整数规划的松弛问题如下：得整数规划的松弛问题如下：19;.x x1

16、1x x2 2OO第二步：分支与定界第二步：分支与定界. .L L0 0的最优解为的最优解为 (3.25(3.25，2.5). 2.5). z z* *=14.75=14.75 0 x,x2x5 . 4x5 . 0 x14x3x2. t . sx2x3zmax212212121L L1 1： 0 x,x3x5 . 4x5 . 0 x14x3x2. t . sx2x3zmax212212121L L2 2：L L1 1的最优解为的最优解为(3. 5(3. 5，2)2)，z z1 1=14.5=14.5L L2 2的最优解为的最优解为(2. 5(2. 5，3)3)，z z2 2=13.5=13.5

17、 2 23 3未失去整数解未失去整数解即整数规划的可行域被全即整数规划的可行域被全部保留部保留其中其中1 1zz2 2，对，对L L1 1继续分枝继续分枝20;.L L1 1的最优解为的最优解为 (3. 5(3. 5，2)2)，z z1 1=14.5=14.5将整数解化为一个将整数解化为一个分枝的可行域的极分枝的可行域的极点点x x1 1x x2 2 OO图图4-44-4 0 x,x3x2x5 . 4x5 . 0 x14x3x2. t . sx2x3zmax2112212121L L1111：L L11 11的最优解为的最优解为(3(3，2)2)，z z11 11=13=13L L1212的最

18、优解为的最优解为(4(4，1) 1)，z z1212=14=14L L1212： 0 x4x2x5 . 4x5 . 0 x14x3x2. t . sx2x3zmax212212121其中其中11 11zz1212 0 x,x2x5.4x5.0 x14x3x2. t . sx2x3zmax212212121L L1 1：L L2 2的最优解为的最优解为(2. 5(2. 5，3)3)，z z2 2=13.5=13.521;.第三步第三步: :比较与剪枝比较与剪枝L L0 0 x x1 1=3.25 x=3.25 x2 2=2.5=2.5z=14.75z=14.75L L1 1x x1 1=3. 5

19、 x=3. 5 x2 2=2=2z=14.5z=14.5L L2 2x x1 1=2.5 x=2.5 x2 2=3=3z=13.5z=13.5L L1212x x1 1=4 x=4 x2 2=1=1z=14z=14L L1111x x1 1=3 x=3 x2 2=2=2z=13z=13x x2 2 2 2x x2 2 3 3x x1 1 3 3x x1 1 4 4UB=14. 5UB=14. 5LB=0LB=0UB=14. 75UB=14. 75LB=0LB=0UB=14UB=14LB=14LB=1422;.A A问题为问题为MaxZ=40 x1+90 x29x1+7x2567x1+20 x2

20、 70 x1,x20 x1,x2 都为整数都为整数MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 B B问题为问题为23;. 问题问题B x1=4.81 ,x2=1.82 Z=356Z=356 Z=0 问题问题B1 x1=4,x2=2.1 Z=349 问题问题B 2 x1=5 ,x2=1.57 Z=341x14x15Z=349 Z=0 x22x23问题问题B3 x1=4, x2=2 Z=340问题问题B4 x1=1.42 x2=3 Z=327Z=341Z=340 x21x22问题问题B5 x1=5.44 x2=1 Z=308Z*=340问题问题B6 无

21、可行解无可行解Z=340Z=34024;.整数解整数解整数解整数解非整数解非整数解非整数解非整数解无可行解无可行解无可行解无可行解此整数解即最优解此整数解即最优解无可行解无可行解整数解整数解较优的一个为最优解较优的一个为最优解整数解整数解问题问题1停止分枝停止分枝(剪枝剪枝)，其整数解为，其整数解为下界，对问题下界，对问题2继续分枝继续分枝非整数解，目标函非整数解，目标函数优于问题数优于问题1问题问题1继续分枝继续分枝无可行解无可行解取较优的一个继续分枝，得三个分枝，取较优的一个继续分枝，得三个分枝，再比较再比较非整数解非整数解此整数解即最优解此整数解即最优解整数解，目标函数整数解，目标函数值优于问题值优于问题1非整数解非整数解问题问题2继续分枝继续分枝非整数解非整数解此整数解即最优解此整数解即最优解整数解整数解无可行解无可行解无可行解无可行解无可行解无可行解789465321说说 明明问题问题2问题问题1序号序号