SHUFE 第二节分枝定界法 定界的含义: 整数规划是在相应的线性规划的基础上增加变量为整数的 约束条件,整数规划的最优解不会优于相应线性规划的最 优解。 对极大化问题来说,相应线性规划的目标函数最优值是原 整数规划函数值的上界; 对极小化问题来说,相应线性规划的目标函数的最优值是 原整数规划目标函数值的下界。 上海财经大学国际工商管理学院上海财经大学国际工商管理学院 SHUFE 10 第二节 分枝定界法 • 定界的含义： ▪ 整数规划是在相应的线性规划的基础上增加变量为整数的 约束条件，整数规划的最优解不会优于相应线性规划的最 优解。 ▪ 对极大化问题来说，相应线性规划的目标函数最优值是原 整数规划函数值的上界； ▪ 对极小化问题来说，相应线性规划的目标函数的最优值是 原整数规划目标函数值的下界