（一）、基本思路 考虑纯整数问题：整数问题的松弛问题：第三节 分枝定界法考虑纯整数问题：整数问题的松弛问题：判断题：整数问题的最优函数值总是小于或等于其松弛问题的最优函数值。例一：用分枝定界法求解整数规划问题（用图解法计算）记为（IP）（二）、例题LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22无可行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11 x12x23 x24x12x13 例一：用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般线性规划问题记为（LP）用图解法求（LP）的最优解，如图所示。x1x233x1x233(18/11,40/11) x118/11, x2 =40/11 Z(0) =218/11(19.8)即Z 也是（IP）最大值的上限。LPx1=18/11, x2=40/11Z(0) 19.8x1x233(18
