大家好大家好 分分分分枝枝枝枝定定定定界界界界法法法法是是是是20202020世世世世纪纪60606060年年年年代代代代由由由由Land-DoigLand-DoigLand-DoigLand-Doig和和和和DakinDakinDakinDakin等等等等人人人人提提提提出出出出的的的的。这这种种种种方方方方法法法法既既既既可可可可用用用用于于于于纯纯整整整整数数数数规规划划划划问问题题，也可用于混合整数也可用于混合整数也可用于混合整数也可用于混合整数规规划划划划问题问题，而且便于用，而且便于用，而且便于用，而且便于用计计算机求解，所以很快成算机求解，所以很快成算机求解，所以很快成算机求解，所以很快成为为解整数解整数解整数解整数规规划的最主要的方法。划的最主要的方法。划的最主要的方法。划的最主要的方法。分枝定界法分枝定界法分枝定界法分枝定界法 设设有最大化的整数有最大化的整数有最大化的整数有最大化的整数规规划划划划问题问题R R R R，与它相，与它相，与它相，与它相应应的的的的线线性性性性规规划划划划问题为问题为R R R R0 0 0 0，分枝定界法的做法是：，分枝定界法的做法是：，分枝定界法的做法是：，分枝定界法的做法是： 2 2 (1) (1) (1) (1)用用用用观观察法求察法求察法求察法求R R R R的一个可行解，其目的一个可行解，其目的一个可行解，其目的一个可行解，其目标值标值便是便是便是便是R R R R的最的最的最的最优优目目目目标值标值z z z z* * * *的一个下界的一个下界的一个下界的一个下界z z z z。 (2)(2)(2)(2)求解求解求解求解R R R R0 0 0 0，得，得，得，得R R R R0 0 0 0的最的最的最的最优优解解解解x x x x(0)(0)(0)(0)和最和最和最和最优值优值z z z z0 0 0 0。若。若。若。若x x x x(0)(0)(0)(0)符合符合符合符合R R R R的整数条件，的整数条件，的整数条件，的整数条件，则显则显然然然然x x x x(0)(0)(0)(0)也是也是也是也是R R R R的最的最的最的最优优解，解，解，解，结结束；否束；否束；否束；否则则，以，以，以，以R R R R0 0 0 0作作作作为为一个分枝一个分枝一个分枝一个分枝标标明求解的明求解的明求解的明求解的结结果，果，果，果，z z z z0 0 0 0是是是是问题问题R R R R的最的最的最的最优优目目目目标值标值z z z z* * * *的一个上界的一个上界的一个上界的一个上界z z z z。 (3)(3)(3)(3)分枝。取目分枝。取目分枝。取目分枝。取目标标函数函数函数函数值值最大的一个枝最大的一个枝最大的一个枝最大的一个枝R R R Rs s s s，在，在，在，在R R R Rs s s s的解中任的解中任的解中任的解中任选选一不符合整数条件的一不符合整数条件的一不符合整数条件的一不符合整数条件的变变量量量量x x x xj j j j，其，其，其，其值为值为b b b bj j j j，构造两个，构造两个，构造两个，构造两个约约束条束条束条束条件件件件x x x xj j j jbbbbj j j j 和和和和x x x xj j j jbbbbj j j j+1+1+1+1。将两个。将两个。将两个。将两个约约束条件分束条件分束条件分束条件分别别加入加入加入加入问题问题R R R Rs s s s，得两个后，得两个后，得两个后，得两个后继规继规划划划划问题问题R R R Rs1s1s1s1和和和和R R R Rs2s2s2s2。不考。不考。不考。不考虑虑整数条件求解整数条件求解整数条件求解整数条件求解这这两个两个两个两个后后后后继问题继问题，以每个后，以每个后，以每个后，以每个后继问题为继问题为一分枝一分枝一分枝一分枝标标明求解的明求解的明求解的明求解的结结果。果。果。果。 (4)(4)(4)(4)定界。在各分枝中找出目定界。在各分枝中找出目定界。在各分枝中找出目定界。在各分枝中找出目标标函数函数函数函数值值最大者作最大者作最大者作最大者作为为新的上界新的上界新的上界新的上界z z z z；从已符合整数要求的各分枝中，找出目；从已符合整数要求的各分枝中，找出目；从已符合整数要求的各分枝中，找出目；从已符合整数要求的各分枝中，找出目标标函数函数函数函数值值最最最最大者作大者作大者作大者作为为新的下界新的下界新的下界新的下界z z z z。 (5)(5)(5)(5)比比比比较较与剪枝。各分枝的最与剪枝。各分枝的最与剪枝。各分枝的最与剪枝。各分枝的最优优目目目目标标函数函数函数函数值值中如果有小于中如果有小于中如果有小于中如果有小于z z z z者，者，者，者，则则剪掉剪掉剪掉剪掉这这一枝（用打一枝（用打一枝（用打一枝（用打表示），即以后不再考表示），即以后不再考表示），即以后不再考表示），即以后不再考虑虑了。了。了。了。若已没有大于若已没有大于若已没有大于若已没有大于z z z z的分枝，的分枝，的分枝，的分枝，则则已得到已得到已得到已得到R R R R的最的最的最的最优优解，解，解，解，结结束；否束；否束；否束；否则则，转转(3)(3)(3)(3)。3 3例例例例 求解求解求解求解问题问题 Max z=40xMax z=40x1 1+90x+90x2 2 9x 9x1 1+7x+7x2 2 5656 7x 7x1 1+20x+20x2 27070 x x1 1,x ,x2 20, 0, 整数整数整数整数R R0 0: z: z0 0=356=356 x x1 1=4.81=4.81 x x2 2=1.82=1.82R R1 1:z:z1 1=349=349 x x1 1=4.00=4.00 x x2 2=2.10=2.10R R2 2:z:z2 2=341=341 x x1 1=5.00=5.00 x x2 2=1.57=1.57R R1212: :z z1212=327=327x x1 1=1.42=1.42x x2 2=3.00=3.00x x2 233R R1111: :z z1111=340=340x x1 1=4.00=4.00x x2 2=2.00=2.00R R2121: :z z2121=308=308x x1 1=5.44=5.44x x2 2=1.00=1.00R R2222: :无可无可无可无可行解行解行解行解x x1 1 4 4x x1 1 1 1x x1 155x x1 122问题问题R R0 0为为: :Max z=40xMax z=40x1 1+90x+90x2 2 9x 9x1 1+7x+7x2 25656 7x 7x1 1+20x+20x2 27070 x x1 1,x ,x2 200问题问题R R2 2为为: :Max z=40xMax z=40x1 1+90x+90x2 2 9x 9x1 1+7x+7x2 25656 7x 7x1 1+20x+20x2 2 7070 x x1 1 5 5 x x1 1,x ,x2 2 0 0问题问题R R1 1为为: :Max z=40xMax z=40x1 1+90x+90x2 2 9x 9x1 1+7x+7x2 25656 7x 7x1 1+20x+20x2 2 7070 x x1 1 4 4 x x1 1,x ,x2 200x x2 2 2 2问题问题R R1111为为: :Max z=40xMax z=40x1 1+90x+90x2 2 9x 9x1 1+7x+7x2 25656 7x 7x1 1+20x+20x2 2 7070 x x1 1 4 4 x x2 2 2 2 x x1 1,x ,x2 200问题问题R R1212为为: :Max z=40xMax z=40x1 1+90x+90x2 2 9x 9x1 1+7x+7x2 25656 7x 7x1 1+20x+20x2 2 7070 x x1 1 4 4 x x2 2 3 3 x x1 1,x ,x2 2 0 04 4例例 maxZ= 6x1 +5 x2 2x1 + x2 9 5x1 +7 x2 35 x1, x2 0 x1, x2取整数取整数第一步第一步, ,不考不考虑变量的整数量的整数约束束, ,求相求相应LP(LP(问题1)1)的最的最优解：解： x1=28/9，x2 =25/9，Z1=293/9第二步第二步, ,定界定界过程程这个解不个解不满足整数足整数约束，束，这时目目标函函值Z Z1 1是整数是整数规划的目划的目标上界；上界；因因为x1=x2=0=0是整数是整数规划划问题的可行解，所以下界的可行解，所以下界为0 0。第三步第三步, ,分枝分枝过程程 将不将不满足整数足整数约束的束的变量量x1进行分枝，行分枝，x1称称为分枝分枝变量，构造两个新的量，构造两个新的约束条件：束条件： x1 28/9=3， x1 28/9 +1=4 5这样就把相就把相应的的线性性规划的可行域分成两个部分，如划的可行域分成两个部分，如图所示。所示。 5x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=3x1=4问题2：maxZ= 6x1 +5 x2 问题3： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 4 x1, x2 0 x1, x2 0 x1, x2取整数取整数 x1, x2取整数取整数6求解相求解相应的的线性性规划的最划的最优解解问题2相相应的的线性性规划的最划的最优解：解：x1=3，x2 =20/7，Z2=226/7问题3相相应的的线性性规划的最划的最优解：解：x1=4，x2 =1，Z3=29第四步，定界第四步，定界过程程LP3的解的解满足整数足整数约束，不必再分枝，它的目束，不必再分枝，它的目标函数函数值是是29，大于原有下界，大于原有下界0，则新的下界新的下界为29；现有上界有上界为未分枝子未分枝子问题中目中目标函数最大函数最大值，即，即为226/7。LP2的解仍不的解仍不满足整数足整数约束的要求，它的目束的要求，它的目标函数函数值226/7大于大于现有下界，有下界，则应继续分枝。分枝。第五步，分枝第五步，分枝过程程 将不将不满足整数足整数约束的束的变量量x2进行分枝，构造两个新的行分枝，构造两个新的约束条件：束条件： x2 20/7=2， x2 20/7 +1=3 7 5x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3问题4：maxZ= 6x1 +5 x2 问题5： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 3 x22 x2 3 x1, x2 0 x1, x2 0 x1, x2取整数取整数 x1, x2取整数取整数x2 =2 x2=38求解相求解相应的的线性性规划的最划的最优解解问题4相相应的的线性性规划的最划的最优解：解： x1=3，x2 =2，Z4=28问题5相相应的的线性性规划的最划的最优解：解：x1=14/5，x2 =3，Z5=159/5第六步，定界第六步，定界过程程LP4的解的解满足整数足整数约束，不必再分枝，它的目束，不必再分枝，它的目标函数函数值是是28，小于原有下界，小于原有下界29，则下界仍下界仍为29；现有上界有上界为未分枝子未分枝子问题中目中目标函数最大函数最大值，即，即为159/5。LP5的解仍不的解仍不满足整数足整数约束的要求，它的目束的要求，它的目标函数函数值159/5大于大于现有下界有下界2929，则应继续分枝。分枝。第七步，分枝第七步，分枝过程程 将不将不满足整数足整数约束的束的变量量x1进行分枝，构造两个新的行分枝，构造两个新的约束条件：束条件： x1 14/5=2，x1 14/5 +1=3 9问题6：maxZ= 6x1 +5 x2 问题7： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 3 x2 3 x2 3 x12 x1 3 x1, x2 0 x1, x2 0 x1, x2取整数取整数 x1, x2取整数取整数x2 =2 x2=3 5x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3x1=210求解相求解相应的的线性性规划的最划的最优解：解：问题6相相应的的线性性规划的最划的最优解：解： x1=2，x2 =25/7，Z6=209/7问题7相相应的的线性性规划的最划的最优解：无最解：无最优解解第八步，定界第八步，定界过程程LP7的无最的无最优解，不必再分枝，下界仍解，不必再分枝，下界仍为29；现有上界有上界为未分枝子未分枝子问题中目中目标函数最大函数最大值，即，即为209/7。LP6的解仍不的解仍不满足整数足整数约束的要求，它的目束的要求，它的目标函数函数值209/7大于大于现有下界有下界29，则应继续分枝。分枝。第九步，分枝第九步，分枝过程程 将不将不满足整数足整数约束的束的变量量x2进行分枝，构造两个新的行分枝，构造两个新的约束条件：束条件： x2 3， x2 4 11问题8：maxZ= 6x1 +5 x2 问题9： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 3 x2 3 x2 3 x12 x12 x23 x2 4 x1, x2 0 x1, x2 0 x1, x2取整数取整数 x1, x2取整数取整数 5x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3x2=3x1=2x2 =2 x2 =412求解相求解相应的的线性性规划的最划的最优解解问题8相相应的的线性性规划的最划的最优解：解： x1=2，x2 =3，Z8=27问题9相相应的的线性性规划的最划的最优解：解：x1=7/5，x2 =4，Z9=142/5第十步，定界第十步，定界过程程LP8的最的最优解，解，满足整数足整数约束，不必再分枝，下界仍束，不必再分枝，下界仍为29；现有上界有上界为未分枝子未分枝子问题中目中目标函数最大函数最大值，即，即为29。虽然然LP9的解仍不的解仍不满足整数足整数约束的要求，它的目束的要求，它的目标函数函数值142/5小于小于现有下界有下界29，则不再不再继续分枝。分枝。上界上界=下界，得整数下界，得整数规划划问题的最的最优解：解：x1=4，x2 =1，Z=2913分枝定界分枝定界过程程x13x1 4x22x2 3x12x1 3x23x2 414