第四章第3节 分枝定界法 2

第4章整数规划与分配问题14.3分枝定界法分枝定界法(BranchandBoundMethod)基本思想：先求出整数规划相应的LP(即不考虑整数限制)的最优解，若求得的最优解符合整数要求，则是原LP的最优解；若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。24.3分枝定界法定界的含义：整数规划是在相应的线性规划的基础上增加变量为整数的约束条件，整数规划的最优解不会优于相应线性规划的最优解。对极大化问题来说，相应线性规划的目标函数最优值是原整数规划函数值的上界；对极小化问题来说，相应线性规划的目标函数的最优值是原整数规划目标函数值的下界。34.3分枝定界法例1maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解：

x1=28/9，x2=25/9，Z1=293/9第二步,定界过程这个解不满足整数约束，这时目标函值Z1是整数规划的目标上界；因为x1=x2=0是整数规划问题的可行解，所以下界为0。第三步,分枝过程将不满足整数约束的变量x1进行分枝，x1称为分枝变量，构造两个新的约束条件：

x1≤[28/9]=3，x1≥[28/9]+1=444.3分枝定界法这样就把相应的线性规划的可行域分成两个部分，如图所示。••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=3x1=4问题2：maxZ=

6x1+5x2问题3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数54.3分枝定界法求解相应的线性规划的最优解问题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

6••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=34.3分枝定界法问题4：maxZ=

6x1+5x2问题5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=374.3分枝定界法求解相应的线性规划的最优解问题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大于现有下界29，则应继续分枝。第七步，分枝过程将不满足整数约束的变量x1进行分枝，构造两个新的约束条件：

x1≤[14/5]=2，x1≥[14/5]+1=3

84.3分枝定界法问题6：maxZ=

6x1+5x2问题7：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=3••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=294.3分枝定界法求解相应的线性规划的最优解：问题6相应的线性规划的最优解：

x1=2，x2=25/7，Z6=209/7问题7相应的线性规划的最优解：无最优解第八步，定界过程LP7的无最优解，不必再分枝，下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为209/7。LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于现有下界29，则应继续分枝。第九步，分枝过程将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：

x2≤3，x2≥4

104.3分枝定界法问题8：maxZ=

6x1+5x2问题9：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x2=3x1=2x2=2

x2=4114.3分枝定界法求解相应的线性规划的最优解问题8相应的线性规划的最优解：

x1=2，x2=3，Z8=27问题9相应的线性