运筹学_分支定界法

.,（一）、基本思路,考虑纯整数问题：,整数问题的松弛问题：,第三节分枝定界法,.,考虑纯整数问题：,整数问题的松弛问题：,判断题：整数问题的最优函数值总是小于或等于其松弛问题的最优函数值。,.,例一：用分枝定界法求解整数规划问题（用图解法计算）,记为（IP）,（二）、例题,.,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP21x1=12/5,x2=3Z(21)17.4,LP22无可行解,LP211x1=2,x2=3Z(211)17,LP212x1=3,x2=5/2Z(212)15.5,x11,x12,x23,x24,x12,x13,.,例一：用分枝定界法求解整数规划问题（用图解法计算）,记为（IP）,解：首先去掉整数约束，变成一般线性规划问题,记为（LP）,.,用图解法求（LP）的最优解，如图所示。,x1,x2,3,3,.,x1,x2,3,3,(18/11,40/11),x118/11,x2=40/11Z(0)=218/11(19.8)即Z也是（IP）最大值的上限。,.,LPx1=18/11,x2=40/11Z(0)19.8,.,x1,x2,3,3,(18/11,40/11),对于x118/111.64，取值x11，x12对于x2=40/113.64，取值x23，x24,x118/11,x2=40/11Z(0)=218/11(19.8)即Z也是（IP）最大值的上限。,先将（LP）划分为（LP1）和（LP2）,取x11,x12,.,现在只要求出（LP1）和（LP2）的最优解即可。,先将（LP）划分为（LP1）和（LP2）,取x11,x12，有下式：,.,LP1x1=？,x2=？Z(1)？,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=？,x2=？Z(2)？,x11,x12,.,x1,x2,3,3,先求（LP1）,如图所示。,1,1,A,.,x1,x2,3,3,先求（LP1）,如图所示。,1,1,B,A,此时B在点取得最优解。x11,x2=3,Z(1)16,.,LP1x1=？,x2=？Z(1)？,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=？,x2=？Z(2)？,x11,x12,.,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=？,x2=？Z(2)？,x11,x12,.,x1,x2,3,3,1,1,B,A,求（LP2）,如图所示。,.,x1,x2,3,3,1,1,在C点取得最优解。即x12,x2=10/3,Z(2)56/318.7,B,A,C,求（LP2）,如图所示。,.,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=？,x2=？Z(2)？,x11,x12,.,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.7,x11,x12,找到整数解，此枝停止计算,.,在C点取得最优解。即x12,x2=10/3,Z(2)56/318.7,x1,x2,3,3,1,1,B,A,C,求（LP2）,如图所示。,Z2Z116原问题可能有比（16）更大的最优解，但x2不是整数，故利用x23，x24加入条件。,.,（LP）划分为（LP1）和（LP2）,x11,x12,.,对于LP2,加入条件：x23,x24有下式：,只要求出（LP21）和（LP22）的最优解即可。,.,x11,x12,x24,x23,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.7,LP21x1=？,x2=？Z(21)？,LP22x1=？,x2=？Z(22)？,找到整数解，此枝停止计算,.,x1,x2,3,3,1,1,B,A,C,先求（LP21）,如图所示。,.,x1,x2,3,3,1,1,B,A,C,先求（LP21）,如图所示。,D,此时D在点取得最优解。即x112/5=2.4,x2=3,Z(21)87/5=17.4,.,x1,x2,3,3,1,1,B,A,C,D,求（LP22），如图所示。无可行解，不再分枝。,.,x11,x12,x24,x23,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.7,LP21x1=？,x2=？Z(21)？,LP22x1=？,x2=？Z(22)？,找到整数解，此枝停止计算,.,x11,x12,x24,x23,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.7,LP21x1=2.4,x2=3Z(21)17.4,LP22无可行解,找到整数解，此枝停止计算,.,x1,x2,3,3,1,1,B,A,C,（LP21）,如图所示，在D点取得最优解。即x112/5=2.4,x2=3,Z(3)87/5=17.4,D,x12.4不是整数，可继续分枝。即x12，x13,.,.,在（LP21）的基础上继续分枝。加入条件x12，x13有下式：,只要求出（LP211）和（LP212）的最优解即可。,.,x12,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP21x1=2.4,x2=3Z(21)17.4,LP22无可行解,LP211x1=？,x2=？Z(211)？,LP212x1=？,x2=？Z(212)？,x11,x12,x23,x24,x13,找到整数解，此枝停止计算,.,先求（LP211）,x1,3,3,1,1,B,A,C,D,x2,.,先求（LP211）,x1,3,3,1,1,B,A,C,D,E,x2,如图所示，此时E在点取得最优解即x12,x2=3,Z(211)17,.,x1,x2,3,3,1,1,B,A,C,D,E,求（LP212）,.,x1,x2,3,3,1,1,B,A,C,D,E,求（LP212）,F,如图所示。此时F在点取得最优解。x13,x2=2.5,Z(212)31/2=15.5,.,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP21x1=2.4,x2=3Z(21)17.4,LP22无可行解,LP211x1=2,x2=3Z(211)17,LP212x1=3,x2=5/2Z(212)15.5,x11,x12,x23,x24,x12,x13,找到整数解，此枝停止计算,找到整数解，此枝停止计算,.,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP21x1=2.4,x2=3Z(21)17.4,LP22无可行解,LP211x1=2,x2=3Z(211)17,LP212x1=3,x2=5/2Z(212)15.5,x11,x12,x23,x24,x12,x13,找到最优解,找到整数解，此枝停止计算,找到整数解，此枝停止计算,.,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP21x1=2.4,x2=3Z(21)17.4,LP22无可行解,LP211x1=2,x2=3Z(211)17,LP212x1=3,x2=5/2Z(212)15.5,x11,x12,x23,x24,x12,x13,至此，原问题（IP）的最优解为：x1=2，x2=3,Z*=Z(211)17以上的求解过程可以用一个树形图表示如右：,.,练习：用分枝定界法求解整数规划问题（图解法）,.,x11,x12,x22,x23,x12,x13,.,解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。,初始表,最终表,例二、用分枝定界法求解整数规划问题（单纯形法）,.,x1=13/4x2=5/2Z(0)=59/4=14.75选x2进行分枝，即增加两个约束，x22,x23有下式：,分别在(LP1)和(LP2)中引入松弛变量x5和x6，将新加约束条件加入上表计算。即x2+x5=2,x2+x6=3得下表:,.,x1=7/2,x2=2Z(1)=29/2=14.5继续分枝，加入约束x13,x14,LP1,.,LP2,x1=5/2,x2=3Z(2)=27/2=13.5Z(2)Z(1)先不考虑分枝,.,接(LP1)继续分枝，加入约束x13，x14有下式：,分别引入松弛变量x7和x8，然后进行计算。,.,x1=3,x2=2Z(3)=13找到整数解，问题已探明，停止计算。,LP3,.,x1=4,x2=1Z(4)=14