在采用分支定界法求解某极大化整数规划问题时,该整数规划问题分为两个子问题,子问题1对应的松弛问题最优解为(1,2,4),最优值分别为15;子问题2对应的松弛问题最优解为(2.2,4,3),最优值分别20。下列说法不正确的是:（ ）A 整数规划问题的上界为20 B 整数规划问题的下界为15 C 整数规划问题的最优解可能小于15D 下一步应该对子问题2进行分支,构造x1≤2与x1≥3这两个分支

解答：

正确答案是 C 整数规划问题的最优解可能小于15。

解释：

分支定界法 的核心思想是通过不断地将问题分解成子问题，并利用松弛问题的解来估计目标函数的上界和下界，逐步缩小搜索范围，最终找到最优解。

上界: 任何一个子问题的松弛问题最优值都是原整数规划问题最优值的上界，因为松弛问题允许变量取分数，所以它的最优值必然大于等于整数规划问题的最优值。因此，子问题2的松弛问题最优值20是原问题的上界，选项A正确。

下界: 任何一个子问题的可行解（即满足整数约束的解）都是原整数规划问题最优值的下界，因为可行解是原问题解空间的一个子集，所以它的目标函数值必然小于等于原问题的最优值。子问题1的松弛问题最优解（1, 2, 4）满足整数约束，所以它是原问题的可行解，其目标函数值15是原问题的下界，选项B正确。

分支: 分支定界法会选择最优值最大的子问题进行分支，因为该子问题更有可能包含原问题的最优解。因此，下一步应该对子问题2进行分支。

选项C错误： 整数规划问题的最优解不可能小于15。因为子问题1的可行解（1, 2, 4）的目标函数值为15，而原问题的最优解必然大于等于任何一个子问题的可行解的目标函数值。