（一）、基本思路 考虑纯整数问题： 整数问题的松弛问题 ： 第三节 分枝定界法考虑纯整数问题： 整数问题的松弛问题 ： 判断题：整数问题的最优函 数值总是小于或等于其松弛 问题的最优函数值。例一：用分枝定界法求解整数规划问题（用图解法计算 ） 记为（IP） （二）、例题LP1 x 1 =1, x 2 =3 Z (1) 16 LP x 1 =18/11, x 2 =40/11 Z (0) 19.8 LP2 x 1 =2, x 2 =10/3 Z (2) 18.5 LP21 x 1 =12/5, x 2 =3 Z (21) 17.4 LP22 无可 行解 LP211 x 1 =2, x 2 =3 Z (211) 17 LP212 x 1 =3, x 2 =5/2 Z (212) 15.5 x 1 1 x 1 2 x 2 3 x 2 4 x 1 2 x 1 3 例一：用分枝定界法求解整数规划问题（用图解法计算 ） 记为（IP） 解：首先去掉整数约束，变成一般线性规划问题 记为（LP）用图解法求（LP）的最 优解，如图所示。 x 1 x 2 3 3 x 1 x 2 3 3 (18/11,40/
