运筹学_分支定界法.ppt

一 基本思路 考虑纯整数问题 整数问题的松弛问题 第三节分枝定界法 考虑纯整数问题 整数问题的松弛问题 判断题 整数问题的最优函数值总是小于或等于其松弛问题的最优函数值 例一 用分枝定界法求解整数规划问题 用图解法计算 记为 IP 二 例题 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 5 LP21x1 12 5 x2 3Z 21 17 4 LP22无可行解 LP211x1 2 x2 3Z 211 17 LP212x1 3 x2 5 2Z 212 15 5 x1 1 x1 2 x2 3 x2 4 x1 2 x1 3 例一 用分枝定界法求解整数规划问题 用图解法计算 记为 IP 解 首先去掉整数约束 变成一般线性规划问题 记为 LP 用图解法求 LP 的最优解 如图所示 x1 x2 3 3 x1 x2 3 3 18 11 40 11 x1 18 11 x2 40 11Z 0 218 11 19 8 即Z也是 IP 最大值的上限 LPx1 18 11 x2 40 11Z 0 19 8 x1 x2 3 3 18 11 40 11 对于x1 18 11 1 64 取值x1 1 x1 2对于x2 40 11 3 64 取值x2 3 x2 4 x1 18 11 x2 40 11Z 0 218 11 19 8 即Z也是 IP 最大值的上限 先将 LP 划分为 LP1 和 LP2 取x1 1 x1 2 现在只要求出 LP1 和 LP2 的最优解即可 先将 LP 划分为 LP1 和 LP2 取x1 1 x1 2 有下式 LP1x1 x2 Z 1 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 x2 Z 2 x1 1 x1 2 x1 x2 3 3 先求 LP1 如图所示 1 1 A x1 x2 3 3 先求 LP1 如图所示 1 1 B A 此时B在点取得最优解 x1 1 x2 3 Z 1 16 LP1x1 x2 Z 1 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 x2 Z 2 x1 1 x1 2 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 x2 Z 2 x1 1 x1 2 x1 x2 3 3 1 1 B A 求 LP2 如图所示 x1 x2 3 3 1 1 在C点取得最优解 即x1 2 x2 10 3 Z 2 56 3 18 7 B A C 求 LP2 如图所示 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 x2 Z 2 x1 1 x1 2 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 7 x1 1 x1 2 找到整数解 此枝停止计算 在C点取得最优解 即x1 2 x2 10 3 Z 2 56 3 18 7 x1 x2 3 3 1 1 B A C 求 LP2 如图所示 Z2 Z1 16 原问题可能有比 16 更大的最优解 但x2不是整数 故利用x2 3 x2 4加入条件 LP 划分为 LP1 和 LP2 x1 1 x1 2 对于LP2 加入条件 x2 3 x2 4有下式 只要求出 LP21 和 LP22 的最优解即可 x1 1 x1 2 x2 4 x2 3 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 7 LP21x1 x2 Z 21 LP22x1 x2 Z 22 找到整数解 此枝停止计算 x1 x2 3 3 1 1 B A C 先求 LP21 如图所示 x1 x2 3 3 1 1 B A C 先求 LP21 如图所示 D 此时D在点取得最优解 即x1 12 5 2 4 x2 3 Z 21 87 5 17 4 x1 x2 3 3 1 1 B A C D 求 LP22 如图所示 无可行解 不再分枝 x1 1 x1 2 x2 4 x2 3 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 7 LP21x1 x2 Z 21 LP22x1 x2 Z 22 找到整数解 此枝停止计算 x1 1 x1 2 x2 4 x2 3 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 7 LP21x1 2 4 x2 3Z 21 17 4 LP22无可行解 找到整数解 此枝停止计算 x1 x2 3 3 1 1 B A C LP21 如图所示 在D点取得最优解 即x1 12 5 2 4 x2 3 Z 3 87 5 17 4 D x1 2 4不是整数 可继续分枝 即x1 2 x1 3 在 LP21 的基础上继续分枝 加入条件x1 2 x1 3有下式 只要求出 LP211 和 LP212 的最优解即可 x1 2 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 5 LP21x1 2 4 x2 3Z 21 17 4 LP22无可行解 LP211x1 x2 Z 211 LP212x1 x2 Z 212 x1 1 x1 2 x2 3 x2 4 x1 3 找到整数解 此枝停止计算 先求 LP211 x1 3 3 1 1 B A C D x2 先求 LP211 x1 3 3 1 1 B A C D E x2 如图所示 此时E在点取得最优解即x1 2 x2 3 Z 211 17 x1 x2 3 3 1 1 B A C D E 求 LP212 x1 x2 3 3 1 1 B A C D E 求 LP212 F 如图所示 此时F在点取得最优解 x1 3 x2 2 5 Z 212 31 2 15 5 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 5 LP21x1 2 4 x2 3Z 21 17 4 LP22无可行解 LP211x1 2 x2 3Z 211 17 LP212x1 3 x2 5 2Z 212 15 5 x1 1 x1 2 x2 3 x2 4 x1 2 x1 3 找到整数解 此枝停止计算 找到整数解 此枝停止计算 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 5 LP21x1 2 4 x2 3Z 21 17 4 LP22无可行解 LP211x1 2 x2 3Z 211 17 LP212x1 3 x2 5 2Z 212 15 5 x1 1 x1 2 x2 3 x2 4 x1 2 x1 3 找到最优解 找到整数解 此枝停止计算 找到整数解 此枝停止计算 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 5 LP21x1 2 4 x2 3Z 21 17 4 LP22无可行解 LP211x1 2 x2 3Z 211 17 LP212x1 3 x2 5 2Z 212 15 5 x1 1 x1 2 x2 3 x2 4 x1 2 x1 3 至此 原问题 IP 的最优解为 x1 2 x2 3 Z Z 211 17以上的求解过程可以用一个树形图表示如右 练习 用分枝定界法求解整数规划问题 图解法 x1 1 x1 2 x2 2 x2 3 x1 2 x1 3 解 用单纯形法解对应的 LP 问题 如表所示 获得最优解 初始表 最终表 例二 用分枝定界法求解整数规划问题 单纯形法 x1 13 4x2 5 2Z 0 59 4 14 75选x2进行分枝 即增加两个约束 x22 x2 3有下式 分别在 LP1 和 LP2 中引入松弛变量x5和x6 将新加约束条件加入上表计算 即x2 x5 2 x2 x6 3得下表 x1 7 2 x2 2Z 1 29 2 14 5继续分枝 加入约束x1 3 x1 4 LP1 LP2 x1 5 2 x2 3Z 2 27 2 13 5 Z 2 Z 1 先不考虑分枝 接 LP1 继续分枝 加入约束x1 3 x1 4有下式 分别引入松弛变量x7和x8 然后进行计算 x1 3 x2 2Z 3 13找到整数解 问题已探明 停止计算 LP3 x1 4 x2 1Z 4 14找到