SHUFE 分枝定界法 分枝定界法( Branch and bound method 基本思想: 先求出整数规划相应的线性规划(即不考虑整数限制)的最优解, 若求得的最优解符合整数要求,则这个解就是原整数规划的最优 解 若不满足整数条件,则任选一个不满足整数条件的变量来构造新 的约束,在原可行域中剔除部分非整数解。 然后,再在缩小的可行域中求解新构造的线性规划的最优解,这 样通过求解一系列线性规划问题,最终得到原整数规划的最优解。 定界的含义: 整数规划是在相应的线性规划的基础上增加变量为整数的约束条 件,整数规划的最优解不会优于相应线性规划的最优解。 对极大化问题来说,相应线性规划的目标函数最优值是原整数规 划函数值的上界; 上海财经大学国际工商管理学院上海财经大学国际工商管理学院 SHUFE 2 分枝定界法 • 分枝定界法(Branch and Bound Method) • 基本思想： ▪ 先求出整数规划相应的线性规划(即不考虑整数限制)的最优解， ▪ 若求得的最优解符合整数要求，则这个解就是原整数规划的最优 解； ▪ 若不满足整数条件，则任选一个不满足整数条件的变量来构造新 的约束，在原可行域中剔除部分非整数解。 ▪ 然后，再在缩小的可行域中求解新构造的线性规划的最优解，这 样通过求解一系列线性规划问题，最终得到原整数规划的最优解。 • 定界的含义： ▪ 整数规划是在相应的线性规划的基础上增加变量为整数的约束条 件，整数规划的最优解不会优于相应线性规划的最优解。 ▪ 对极大化问题来说，相应线性规划的目标函数最优值是原整数规 划函数值的上界；