非线性规划中的分支定界法基础题 题目描述 考虑非线性规划问题： \[ \min f(x) = (x_ 1 - 1.5)^2 + (x_ 2 - 0.5)^2 \] 满足约束： \[ x_ 1 + x_ 2 \leq 2, \quad x_ 1 - x_ 2 \leq 1, \quad x_ 1, x_ 2 \in \mathbb{Z} \] 要求使用分支定界法求解该整数非线性规划问题。 解题过程 1. 问题分析 目标函数 \( f(x) \) 是凸二次函数，但决策变量 \( x_ 1, x_ 2 \) 需为整数。 约束条件为线性，构成一个多边形可行域。 分支定界法的核心思想： 松弛 ：忽略整数约束，求解连续松弛问题。 分支 ：若松弛解不满足整数约束，将问题划分为子问题（例如固定变量的取值范围）。 定界 ：通过上下界（全局最优解的范围）剪枝，避免枚举所有整数解。 2. 求解连续松弛问题 忽略整数约束，求解连续问题： \[ \min f(x) \quad \text{s.t.} \quad x_ 1 + x_ 2 \leq 2, \quad x_ 1 - x_ 2 \leq 1 \] 目标函数梯度为 \( \nabla f = [ 2(x_ 1 - 1.5), 2(x_ 2 - 0.5) ] \)。 约束为线性，可用拉格朗日法或图形法求解。 图形法：约束可行域为多边形顶点 \((0,0), (1,0), (1.5,0.5), (0,2)\)。 计算各顶点函数值： \( f(0,0) = 3.5 \) \( f(1,0) = 1.25 \) \( f(1.5,0.5) = 0 \)（无约束全局最优解，但 \( x_ 1=1.5 \) 非整数） \( f(0,2) = 3.5 \) 连续松弛最优解为 \( x^* = (1.5, 0.5) \)，\( f^* = 0 \)。 当前下界 （对最小化问题）：松弛问题最优值 \( 0 \) 是整数问题下界（整数解不可能更小）。 3. 分支操作 选择非整数变量分支（例如 \( x_ 1 = 1.5 \)）： 子问题1 ：添加约束 \( x_ 1 \leq 1 \)（向下取整）。 子问题2 ：添加约束 \( x_ 1 \geq 2 \)（向上取整）。 子问题1 （\( x_ 1 \leq 1 \)）： 约束条件：原约束 + \( x_ 1 \leq 1 \)。 可行域顶点：\((0,0), (1,0), (1,1)\)（注意 \( x_ 1 - x_ 2 \leq 1 \) 排除 \( x_ 1=1, x_ 2>0 \) 无效）。 计算顶点值： \( f(0,0) = 3.5 \) \( f(1,0) = 0.25 \)（最优解） 子问题1连续松弛解：\( x = (1, 0) \)，\( f = 0.25 \)。 关键点 ：此解满足整数约束，是 可行整数解 。 当前上界 （全局最小值的候选）：\( 0.25 \)。 子问题2 （\( x_ 1 \geq 2 \)）： 约束条件：原约束 + \( x_ 1 \geq 2 \)。 可行域：无解（例如 \( x_ 1=2 \) 时 \( x_ 1 + x_ 2 \leq 2 \) 要求 \( x_ 2 \leq 0 \)，但 \( x_ 1 - x_ 2 \leq 1 \) 要求 \( x_ 2 \geq 1 \)，矛盾）。 子问题2不可行，剪枝。 4. 更新界限与剪枝 当前上界 （最佳整数解）：\( 0.25 \)（来自子问题1）。 当前下界 ：子问题1的松弛解值 \( 0.25 \) 等于上界，说明该子问题无需进一步分支（已找到最优整数解）。 其他子问题已剪枝（子问题2不可行）。 5. 最终解 全局最优整数解为 \( x^* = (1, 0) \)，目标函数值 \( f^* = 0.25 \)。 验证：枚举附近整数点（如 (1,1) 违反 \( x_ 1 - x_ 2 \leq 1 \)，(2,0) 不可行），无更优解。 总结 分支定界法通过松弛、分支、定界三步迭代，逐步缩小搜索范围。本例中，第一次分支后即找到最优整数解，并通过定界剪枝高效终止。对于复杂问题，需多次分支，但核心逻辑一致。