运筹学分支定界法0整数规划课件ppt课件.ppt

第三节分支定界法 BranchandBound 简称B B 基本思想如下 首先不考虑变量的整数约束 求解相应的线性规划问题 得到线性规划的最优解 设线性规划问题 最优解为Z 则Z为IP问题解Z 的上界 Z Z 它的可行域为图中OABCDE 示意图 并设最优解位于C 如果这个最优解中所有的变量都是整数 则已经得到整数规划的最优解 如果其中某一个变量Xr不是整数 则在可行域中除去一块包含这个最优解但不包含任何整数解的区域Ir Xr Ir 1 其中Ir是变量Xr的整数部分 线性规划的可行域被划分成不相交的两部分 分别以这两部分区域作为可行域 用原来的目标函数 构造两个子问题Sub1和Sub2 EDC B Sub1Sub2 IrXrIr 1A X2 O X1 分枝 Sub1Sub2由于这两个子问题的可行域都是原线性规划问题可行域的子集 这两个子问题的最优解的目标函数值都不会比原线性规划问题的最优解的目标函数值更大 如果这两个问题的最优解仍不是整数解 则继续选择一个非整数的变量 继续将这个子问题分解为两个更下一级的子问题 这个过程称为 分支 Branch 每一次分支得到的子问题最优解的目标函数值 都小于或等于分支前问题的最优解的目标函数值 非整数解的最大值作为新的上界 如果某一个子问题的最优解是整数解 就作为整数规划最优目标函数值的下界 多个时取最大值 最后的下界为整数规划的最优解 如果某一个子问题的解还不是整数解 但这个非整数解的目标函数值已经小于这个下界 那么这个子问题就不必再进行分支 不然需重复进行分支 确定整数解目标函数值上下界并不断更新 剪除 目标函数值小于下界的分支的过程 称为定界 Bound 整数规划问题的求解方法分支定界法图解整数规划 松弛问题MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 X2 0 该整数规划松弛问题的解为 X1 X2 3 2 10 3 Z1 29 6 松弛问题MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 X2 0 3 2 10 3 Z1 29 6 B1MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 2X1 X2 0 B2MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 1X1 X2 0 B2 解 1 7 3 Z21 10 3 B1 解 2 23 9 Z11 41 9 1 2 3 2 10 3 Z1 29 6 B1MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 2X1 X2 0 B2 解 1 7 3 Z21 17 3 B1 解 2 23 9 Z11 41 9 B11MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 2X2 3X1 X2 0 B12MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 2X2 2X1 X2 0 B12 解 33 14 2 Z12 61 14 3 2 10 3 Z1 29 6 B2 解 1 7 3 Z21 10 3 B12MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 2X2 2X1 X2 0 B12 解 33 14 2 Z12 61 14 B121MaxZ X1 X214X1 9X2 51 6X1 3X2 1X1 3X2 2X1 X2 0 B122MaxZ X1 X214X1 9X2 51 6X1 3X2 12 X1 2X2 2X1 X2 0 B121 解 3 1 Z121 4 B122 解 2 2 Z122 4 B1 解 2 23 9 Z11 41 9 说明 1 在B121 B122的可行域中不可能存在比以上所求解的2个最优解更好的解 2 目标函数值maxZ 4作为IP规划的最优解的目标函数的一个界限 MAX 下界 MIN 上界 求极小问题时 LP问题的解是IP问题的下界 每次分支后的子问题最优解的目标函数值都大于或等于分支前的最优值 如分支中得到整数解 则最小的整数解为上界 如分支的目标函数值大于上界 则停止分支 AX1 3 2 X2 10 3Z 29 6 BX1 2 X2 23 9Z 41 9 CX1 1 X2 7 3Z 10 3 无可行解 DX1 33 14 X2 2Z 61 14 FX1 2 X2 2Z 4 EX1 3 X2 1Z 4 x1 1 x1 2 x2 2 x2 3 x1 2 x1 3 不同的搜索策略会导致不同的搜索树 一般情况下 同一层的两个子问题 先搜索目标函数比较大的较有利 如果是极小问题 则应先搜索目标函数值小的较为有利 这样可能得到数值比较大的下界 下界越大被剪去的分支越多 分支定界算法对于混合整数规划特别有效 对没有整数要求的变量就不必分支 这将大大减少分支的数量 第四节0 1型整数规划 一 0 1变量及其应用某些特殊问题 只做是非选择 故变量设置简化为0或1 1代表选择 0代表不选择 一 0 1规划数学模型 例 固定费用问题有三种资源被用于生产三种产品 资源量 产品单件费用 资源消耗量以及生产产品的固定费用 要求制定一个生产计划 总收益最大 产品 资源 解 xj是生产第j种产品的产量 总收益等于销售减去所生产的产品的总费用 建立数学模型时 无法确定某种产品是否生产 不能确定相应的固定费用是否发生 用0 1变量解决此问题 分析 如果生产第j种产品 xj 0 约束条件xj Mjyj yj 1 如果不生产第j种产品 xj 0 约束条件xj Mjyj yj 1或0 当yj 1不利于目标函数的最大化 因此在最优解必然是yj 0 例含有相互排斥的约束条件的问题 设工序B的每周工时约束条件为0 3x1 0 5x2 150 式 1 现有一新的加工方式 相应的每周工时约束条件为0 2x1 0 4x2 120 式 2 如果工序B只能选择一种 那么 1 和 2 变成相互排斥的约束条件 当y1 1 y2 0 采用新工艺 2 式成立 多余的约束 例选址问题某公司在城市的东 西 南三区建立门市部 拟议中有7个位置 地点 Ai i 1 2 7 可供选择 公司规定在东区 由A1 A2 A3三个点中至多选两个 在南区 由A4 A5两个点中至少选一个 在西区 由A6 A7两个点中至少选一个 如果选用Ai点 设备投资估计为bi元 每年可获利润估计为ci元 但投资总额不能超过B元 问公司选择哪几个点可使年总利润最大 建立模型引入0 1变量 1当Ai点被选用0当Ai没点被选用 xi i 1 2 7 maxz cixi bixi Bx1 x2 x3 2x4 x5 1x6 x7 1xi 0 或1 二 0 1型整数规划的解法 求解思路 检测可行解的目标函数值 根据其目标函数值可以产生一个过滤条件 对于目标函数数值比它差的变量组合删除 这样有效减少运算次数 使最优解快速找到 解 求解过程可以列表表示 在求解0 1整数规划问题 为了进一步减少运算量 常按照目标函数中各个变量系数的大小顺序重新排列各个变量 以便于最优解有可能较早出现 对于最大化问题 可以按照从小到大的顺序排列 对于最小化问题 可以按照从大到小的顺序排列 运算3