分枝定界法的步骤包含以下()。A. 求整数规划的松弛问题最优解B. 若松弛问题的最优解满足整数要求,得到整数规划的最优解。C. 分枝D. 检查所有分枝的解及目标函数值,进行相关检查后,直到得到最优解。

分枝定界法是解决整数规划问题的经典算法，其核心思路是通过系统地分枝和剪枝来缩小搜索范围，最终找到最优解。本题考查对分枝定界法基本步骤的掌握，需明确每个步骤的作用：

1. 松弛问题求解：忽略整数约束，先求解线性规划问题，得到目标函数的界。
2. 整数解验证：若松弛解满足整数要求，则直接得到最优解。
3. 分枝操作：对不满足整数条件的变量进行分枝，生成子问题。
4. 全局检查与剪枝：通过比较目标函数值，排除不可能得到最优解的分支，最终确定全局最优解。

分枝定界法的完整步骤如下：

步骤1：求解松弛问题（选项A）

• 忽略整数约束，将整数规划转化为线性规划问题（松弛问题），求其最优解。这一步的目的是获得目标函数值的初始界。

步骤2：验证整数解（选项B）

• 若松弛问题的最优解满足所有变量为整数，则该解即为整数规划的最优解，算法终止。

步骤3：分枝操作（选项C）

• 若松弛解不满足整数要求，选择一个非整数变量（如$x_i = k + f$，$0 < f < 1$），生成两个子问题：
  • 子问题1：添加约束$x_i \leq k$
  • 子问题2：添加约束$x_i \geq k + 1$

步骤4：全局检查与剪枝（选项D）

• 对所有子问题重复上述步骤，计算每个子问题的目标函数值。
• 剪枝条件：若某子问题的目标函数值劣于已找到的最优解，则剪枝（无需进一步分枝）。
• 当所有有效分支被处理完毕，剩余未剪枝的分支中必包含最优解。