第三章 整数规划
15251412x1?4,1x2?2,z??14
x1?2,12x2?3,z??13
取x1?4对可行域进行分割，
5z??13>z??14，停止分枝。
得到子问题Sub3和Sub4。
x2 4 3 2 1 Sub3 Sub4 x1
Sub-3 min s.t. -3x2 +7x2 +9x2 x2 x1 x2
≤35 ≤36 ≤2 ≤4 ≥0
Sub-4
min s.t. z= 37
4 3 2 x2 1 x1 0 1 2 3 4 5 6 7 0 1 2 3 4 -2x1 5x1 4x1 x1 27 -3x2 +7x2 +9x2 x2 x1 x2 ≤35 ≤36 ≤2 ≥5 ≥0 z= -2x1 5x1 4x1 x1 Sub-3的最优解为 x1=4，x2=2，z=-14
Sub-4的最优解为 x1=5，x2?1取x2?137，z??14
获得整数解，取得上界z??14 停止分枝。
对可行域进行分割
得到子问题Sub-5和Sub-6
x2 4 3 2 1 Sub-5 x1 0 1 2 3 4 5 6 7 Sub-6 x2 4 3 2 1 Sub-3 x1 0 1 2 3 4 5 6 7 16 第三章 整数规划
Sub-5 min s.t. 35 -3x2 +7x2 +9x2 x2 x1 x2 x2
15 ≤35 ≤36 ≤2 ≥5 ≤1 ≥0
Sub-6 min s.t. z= -2x1 5x1 4x1 x1 -3x2 +7x2 +9x2 x2 x1 x2 x2 ≤35 ≤36 ≤2 ≥5 ≥2 ≥0 z= -2x1 5x1 4x1 x1 Sub-5的最优解为
x1?5
Sub-6的可行域是空集，停止分枝。
，x2=1，z??1435取x1?5对可行域进行分割，
得到子问题Sub-7和Sub-8。
4 3 2 1 Sub-7 Sub-8 0 1 2 3 4 5 6 7
Sub-7 min s.t. -3x2 +7x2 +9x2 x2 x1 x2 ≤35 ≤36 ≤2 ≥5 ≤1
Sub-8 min s.t. z= -2x1 5x1 4x1 -3x2 +7x2 +9x2 x2 x1 x2 x1 x2 37 ≤35 ≤36 ≤2 ≥5 ≤1 ≥6 ≥0 z= -2x1 5x1 4x1 x1 Sub-7的最优解为 x1=5，x2=1，z=-13
x1 ≤5 x2 ≥0
x1 Sub-8的最优解为 x1=6，x2?57，z??14
17 第三章 整数规划
获得整数解，停止分枝。 由于z=-13>z??14， 上界仍保持为z??14。
Sub-9 -2x1 -3x2
取x2?57对可行域进行分割，
得到子问题Sub-9和Sub-10。
4 3 2 1 0 1 2 3 4 5 6 7 Sub-9 Sub-10
Sub-10 min s.t. z= -2x1 5x1 4x1 x1 -3x2 +7x2 +9x2 x2 x1 x2 x1 x2 x2 ≤35 ≤36 ≥3 ≥5 ≥2 ≥6 ≥1 ≥0 min z= s.t. 5x1 +7x2 ≤35 4x1 +9x2 ≤36 x1 x2 x1 x2 x1 x2 x2 ≥3 ≥5 ≥2 ≥6 ≤0 ≥0 Sub-9的最优解为x1=7，x2=0，z=-14，
Sub-10的可行域是空集，停止分枝。
获得整数解，z=-14=z??14，上界仍为z??14。
至此已将所有可能分解的子问题都已分解到底，最后得到两个目标函数值相等的最优整数解：（x1，x2）=（4，0）和（x1，x2）=(0，7)，他们的目标函数值都是-14。
以上的搜索过程可以用一个树状图表示，由分枝定界算法可以知道，这个搜索树是一个二叉树。
不同的搜索策略会导致不同的搜索树，如果先搜索Sub-1—Sub-3，就得到上界
z??14，然后再搜索Sub-2，就可以知道Sub-2的目标函数值z??1312已经大于上
界z??14，就可以剪去Sub-2以下所有的分枝。如果先搜索Sub-1—Sub-2，这时还没有得到任何一个整数解，因而还没有得到一个上界，因此Sub-2必须继续分枝。
18 第三章 整数规划
一般情况下，同一层的两个子问题，先搜索目标函数比较小的比较有利，因为这样可能得到数值比较小的上界，上界越小被剪去的分枝越多。
分枝定界算法对于混合整数规划特别有效，对没有整数要求的变量就不必分枝，这将大大减少分枝的数量。在以上的例子中，如果x2没有整数限制，只要一次分枝就可以得到最优解。
19 第三章 整数规划
Sub-9 x1?7x2?0z??14z?z??14原问题 x1?3x2?21217617817 z??14 Sub-2 x2≥3 x2≤2 Sub-1 x1?4x2x1?3x21217121525?3?2z??13z?z??14z??14 Sub-4 x1≥5 x1≤4 Sub-3 x1?5,x2?13727 x1?4x2?2z??14 z??14 Sub-6 x2≤1 x2≥2 Sub-5 x1?5x2?1z??141535z??14无可行解 Sub-8 x1≥6 x1≤5 Sub-7 x1?6x2?5737 x1?5x2?1z??13 z??14 x2≤0 x2≥1 Sub-10 z?z??14 无可行解
20