【判断题】用分枝定界法求解一个极大化的整数规划问题时,任何一个可行解的目标函数值是该问题目标函数值的下界。A. 对B. 错

本题考查分枝定界法求解极大化整数规划问题的基本概念。解题思路是明确分枝定界法中可行解与目标函数值上下界的关系。

在分枝定界法求解极大化的整数规划问题时，我们的目标是找到使得目标函数值最大的整数可行解。

设整数规划问题为：
$\max z = f(x)$
$s.t. \begin{cases} g(x) \leq b \\ x \in X \end{cases}$，其中 $X$ 为整数集合。

对于该问题的任意一个可行解 $x^*$，它满足约束条件 $g(x^*) \leq b$ 且 $x^* \in X$。

因为我们是求目标函数的最大值，而 $x^*$ 是一个可行的解，那么其他可行解的目标函数值必然不会小于 $f(x^*)$（如果存在比 $f(x^*)$ 更小的可行解，那就不符合求最大值的逻辑）。也就是说，所有可行解的目标函数值都要大于等于 $f(x^*)$，所以 $f(x^*)$ 就是该问题目标函数值的下界。