对(P)问题: 其松弛问题为: max z= CX max z= CX AX=b AX=6 s t 1x,为整数 X≥0 ①)伊P的可行解域∝松弛问题的可行解域 →若松弛问题无可行解则P无可行解 ②)的最优值≤松弛冋题的最优值 松弛问题的最优值是原整数规划 的目标函数值的上界 (3)若松弛问题可以找到一个整数解X 则X的目标函数值是P最优值的下界 ④4若松弛问题的最优解X*为整数解 则X*也是P的最优解     = = 为整数 对（ ）问题： x j X AX b st z CX IP . 0 max     = = 0 . max X AX b st z CX 其松弛问题为： （1）IP的可行解域 松弛问题的可行解域 （2）IP的最优值 ≤ 松弛问题的最优值是原整数规划 的目标函数值的上界 若松弛问题无可行解， (3)若松弛问题可以找到一个整数解X， （4）若松弛问题的最优解X *为整数解 则X *也是IP的最优解 则X的目标函数值是IP最优值的下界 则IP无可行解 松弛问题的最优值