分支定界法 Page 16 分支定界法的解题步骤： 1)求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下 一步； 2)分支与定界： 任意选一个非整数解的变量x,在松弛问题中加上约束： x和x2+1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题 是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目 标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数 值大于(ax)等于其它分枝的目标值，则将其它分枝剪去不再计算，若 还存在非整数解并且目标值大于(ax)整数解的目标值，需要继续分枝， 再检查，直到得到最优解
分支定界法 Page 16 1）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下 一步； 2）分支与定界： 任意选一个非整数解的变量xi，在松弛问题中加上约束： xi≤[xi ] 和 xi≥[xi ]+1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题 是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目 标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数 值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若 还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝， 再检查，直到得到最优解。 分支定界法的解题步骤：
分支定界法 Page 17 例4.4用分枝定界法求解整数规划问题 min Z=-x-5x, X1-x2≥-2 5x1+6x2≤30 P x ≤4 x1,x2之0且全为整数 解：首先去掉整数约束，变成一般线性规划问题（原整数规划 问题的松驰问题 min Z=-x-5x, x1-x2≥-2 5x1+6x2≤30 LP x ≤4 x1,x2≥0
分支定界法 Page 17 例4.4 用分枝定界法求解整数规划问题 + − − = − − , 0且全为整数 4 5 6 30 2 min 5 1 2 1 1 2 1 2 1 2 x x x x x x x Z x x 解：首先去掉整数约束，变成一般线性规划问题(原整数规划 问题的松驰问题) + − − = − − , 0 4 5 6 30 2 min 5 1 2 1 1 2 1 2 1 2 x x x x x x x Z x x LP IP
分支定界法 Page 18 用图解法求松弛问题的最优解，如图所示。 x1=18/11,x2=40/11 Z=-218/11≈(-19.8) X2 (1) 即Z也是P最小值的下限。 8/11,40/11) 对于x1=18/11≈1.64， 3 取值x1≤1，x1≥2 对于x2=40/113.64,取值x2 ≤3，X2≥24 先将(LP)划分为(LP1) 和(LP2),取x1≤1，x1≥2
分支定界法 Page 18 用图解法求松弛问题的最优解，如图所示。 x1 x2 ⑴ ⑵ 3 (18/11,40/11) ⑶ 2 1 1 2 3 x1＝18/11, x2 =40/11 Z=－218/11≈(－19.8) 即Z 也是IP最小值的下限。 对于x1＝18/11≈1.64， 取值x1 ≤1， x1 ≥2 对于x2 =40/11 ≈3.64，取值x2 ≤3 ，x2 ≥4 先将（LP）划分为（LP1） 和（LP2）,取x1 ≤1, x1 ≥2
分支定界法 Page 19 分支： min Z=-x-5x, min Z =-x-5x, x1-x2≥-2 x1-x2≥-2 5x,+6x2≤30 5x1+6x2≤30 (IP1) 1 ≤4 (IP2) X1 ≤4 xI ≤1 xI ≥2 x1,x2≥0且为整数 x1,x2≥0且为整数 分别求出(LPI)和(LP2)的最优解
分支定界法 Page 19 分支： + − − = − − , 0且为整数 1 4 5 6 30 2 ( 1) min 5 1 2 1 1 1 2 1 2 1 2 x x x x x x x x IP Z x x + − − = − − , 0且为整数 2 4 5 6 30 2 ( 2) min 5 1 2 1 1 1 2 1 2 1 2 x x x x x x x x IP Z x x 分别求出（LP1）和（LP2）的最优解
分支定界法 Page 20 先求LP1,如图所示。此时在B 点取得最优解。 x1=1,x2=3,Z0=-16 X2 (1) 811,40/11) 找到整数解，问题已探明，此 枝停止计算。 3 同理求LP2,如图所示。在C点 取得最优解。即： x7=2,x2=10/3, Z2)=-56/3≈-18.7 .Z2)<Z0=-16 .原问题有比-16更小的最优 解，但x2不是整数，故继续 分支
分支定界法 Page 20 先求LP1,如图所示。此时在B 点取得最优解。 x1＝1, x2 =3, Z(1)＝－16 找到整数解，问题已探明，此 枝停止计算。 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C 同理求LP2,如图所示。在C点 取得最优解。即: x1＝2, x2 =10/3, Z(2)＝－56/3≈－18.7 ∵Z(2)< Z(1)＝－16 ∴原问题有比－16更小的最优 解，但 x2 不是整数，故继续 分支