管理运筹学第5章-整数规划.ppt

第五章整数规划 IP 整数规划问题 整数规划的割平面算法 整数规划的分支定界算法0 1整数规划指派问题 引例 1 一般最优生产计划问题某工厂拟用集装箱托运甲 乙两种货物 有关资料如下表 问 甲乙两种货物各托运多少箱 可以获得最大利润 4 1整数规划问题 设X1 X2分别表示甲 乙两种货物的托运箱数 LP 模型如下 IP 模型如下 X1 X2 N X1 X2 R 引例 2 约束条件可选择最优生产计划问题 如果引例 1 中的集装箱运输有汽运和水运两种方式可供选择 其体积限制条件分别如下 5X1 4X2 24 汽运 7X1 5X2 32 水运 问 如何建立整数规划模型 可使工厂获得最大利润 设y S T 5X1 4X2 0X1 X2 N y 0 1 MaxZ 20X1 10X2 1 采用汽运方式 0 采用水运方式 则可建立 IP 模型 一 整数规划 IP 问题的性质 1 可行域 KLP KIP 2 最优解 X LP X IP 引例 1 需要研究整数规划问题的专用算法 问 如何求解上述整数规划问题 1 四舍五入法 可能不可行 2 完全枚举法 可能不实际 二 整数规划问题的分类 1 纯整数规划 AIP 2 混合整数规划 MIP 3 0 1规划 BIP 这里 Cj均为整数 j 1 2 n 4 2一般整数规划的分支定界算法 一 算法思想 设有最大化整数规划问题A 与他对应的线性规划问题B 若其最优解不符合A的整数条件 那么B的最优目标函数必是A的最优目标函数Z 的上界 而A的任意可行解的目标函数值将是Z 的下界 分支定界法就是将B的可行域分成子区域 分支 逐步减小上界 增大下界 逐步寻找到整数最优解 4 2一般整数规划的分支定界算法 例1 求解下述 AIP maxz 40 x1 90 x2s t 9x1 7x2 567x1 20 x2 70 xj 0 整数 j 1 2 二 引例 二 分支定界法步骤 极大化问题 将要求解的整数规划问题成为A 将与之对应的线性规划问题称为B 一 解问题B 会出现以下情况 1 B无可行解 则A无可行解 STOP 2 B有最优解 并符合A的整数条件 最优解 3 B有最优解 但不符合A的整数条件 迭代 二 分支定界法步骤 极大化问题 二 用观察法找A的一个整数可行解 求其目标函数值 记为下界Z一般找x 0 得到z 0 成为下界 二 分支定界法步骤 极大化问题 三 分支与定界1 分支B的最优解中 任选一个不符合整数条件的x 其值为b 设 b 为小于b的最大整数 增加两个约束条件x b 1 x b 将两个约束加入到问题中 求后继问题B1 B2的解2 定界以每一个后继问题为一个分支 标明求解结果 与其它问题的解的结果中 找到目标函数值最大者为新的上界Z 从已符合整数条件的各分支中 找最大目标函数值为新的下界z 二 分支定界法步骤 极大化问题 四 比较与剪支各分支中的最优目标函数中若有小于下界者 此支剪掉 不予考虑若大于下界者 且不符合整数条件的 重复第一步直到找到Z 下界z 找到最优解 二 分支定界法步骤 极大化问题 注意 1 下界z 必须是满足整数条件的解 得到的目标函数值2 上界Z 不需要满足整数条件3 当Z 下界z 得到最优解 三 例题与习题 例1 求解下述 AIP maxz 3x1 4x2s t 2x1 5x2 0 整数 j 1 2 4 3纯整数规划的割平面算法 一 算法思想 增加约束条件 割平面 至少切割掉X LP 切割区域不包含整数解 关键 如何增加割平面 用解线性规划的方法求解整数规划问题 首先 不考虑变量x是整数这一条件 但增加线性的约束条件 几何术语称谓割平面 使的原可行域中切割掉一部分 这部分只包含非整数解 没有切割掉任何证书可行解 此方法就是要怎么找到适当的割平面 不一定一次找到 使切割后最终得到这样的可行域 则它的一个整数坐标的极点就是原问题的最优解 例 1 Maxz x1 x2s t x1 x2 13x1 x2 4x1 x2 0 整数 二 示例 三 求一个切割方程的步骤 P121简述 0 1整数规划 X 0或11 投资场所的选定 相互排斥的计划2 相互排斥的约束条件3 关于固定费用问题 解0 1规划的方法 1 穷举法 检查变量取值为0或1的每一组组合 比较目标函数值 求最优值 2 隐枚举法 只检查变量取值的一部分 就能求到问题的最优解 设计这样的方法 叫 分支定界法也是一种隐枚举法 例题p124 1 用穷举法找所有的解 求目标函数值 比较 32次计算2 设计一个方法 检查解适合的条件 只要有不适合的 后面的计算省略 24次计算3 改进方法 将检查的解范围缩小 更快的找到最优解 11次计算 4 5指派问题 引例1 今有4辆装载不同货物的待卸车 派班员要分派给4个装卸班组 每个班组卸1辆 由于各个班组的技术特长不同 各个班组卸不同车辆所需时间如下表 问 派班员应如何分配卸车任务 可以使卸车所花费的总车辆小时最小 一 指派问题及其模型特征 引例2 一份中文说明书需要译成英 日 德 俄四种文字 E J G R 现有甲 乙 丙 丁四人可以完成上述任务 他们将说明书翻译成不同语种的文字所需时间如下表 且一项任务只能由一人去完成 每人只能完成一项任务 问 指派何人完成何工作 可使总花费时间最少 1 n项工作怎样分配给n个工作人员去完成 可以使总花费时间最省 2 n项加工任务怎样分配给n台机床去完成 可以使总费用最低 3 n条航线 怎样指定艘班轮去完成航行任务 可以使总运输费用最低 该类问题是运输问题的特殊形式 称为指派问题 一 指派问题 二 指派问题的基本特征 性质 特殊的运输问题 特殊0 1规划问题 特征 1 决策变量为0 1变量 2 发点数m 收点数n 3 ai bj 1i j 1 2 n 三 指派问题的基本模型 目标函数系数矩阵 Cij 与指派问题左边模型一一对应 四 匈牙利算法 一 基本概念 1 系数矩阵Cij 2 解矩阵 Xij 3 解矩阵的特征 各行各列的元素之和为1 如果对指派问题的系数矩阵 Cij 的任一行列各元素分别减去该行 列 的最小元素 得到新的矩阵 Bij 则以 Bij 为系数矩阵的新指派问题的最优解 Xij 和原指派问题的最优解 Xij 相同 Bij 称为 Cij 的等效矩阵 二 基本定理 定理1的直观意义 定理1的求解意义 2 推论 等效系数矩阵 Bij 的n个独立 0 元素对应的解矩阵的n个独立 1 元素为指派问题的最优解 原因为 BijXij 0 为最小 则原问题有最优解 取到最小值 三 基本算法步骤 第一步 是指派问题的系数矩阵经变换后 在各行各列出现0元素 1 从系数矩阵的每行元素减去该行最小元素 2 再从所得的系数矩阵的每列元素减去该列最小元素 注意 某行 列 已经有0元素 就不必再减 得到一个新的系数矩阵B 由定理可知二者具有相同的最优解 三 基本算法步骤 第二步 试指派 以求最优解在等效系数矩阵B中寻找n个独立 0 元素 1 从只有一个 0 元素的行 列 开始 给 0 元素加圈 然后划去其所在列 0 元素 2 从只有一个 0 元素的列 行 开始 给该 0 元素加圈 然后划去其所在行 0 元素 3 反复以上2步骤 直至所有 0 元素被括出或被划去为止 4 若画圈的 0 元素的个数m 矩阵的阶数n 则它们即为等效矩阵的n个独立 0 元素 其对应的解矩阵的个独立 1 元素即为最优解 若m n 则未找到最优解 进行第三步 三 基本算法步骤 第三步 做最少的直线覆盖所有的0元素1 对没有画圈的0的行 打 2 对已经打 的行中 含有的列 打 3 再对有 的列中含有圈的0的行 打 4 重复2 3步 直到没有新的 出现5 对没有画 的行已经画 的列画直线 若直线数l小于系数矩阵阶数n 则转入下一步 三 基本算法步骤 第四步 增加0元素 找新的等效矩阵 在未被直线覆盖的部分找出最小元素a未划去的元素减