运筹学基础及应用第五版 胡运权第四章.ppt

第四章整数规划与分配问题 1 整数规划的特点及作用 2 分配问题与匈牙利法 3 分枝定界法 4 割平面法 5 解0 1规划问题的隐枚举法 1 整数规划的特点及应用 在实际问题中 全部或部分变量的取值必须是整数 比如人或机器是不可分割的 选择建厂地点可以设置逻辑变量等 在一个线性规划问题中要求全部变量取整数值的 称纯整数线性规划或简称纯整数规划 只要求一部分变量取整数值的 称为混合整数规划 对整数规划问题求解 有人认为可以不考虑对变量的整数约束 作为一般线性规划问题求解 当解为非整数时 用四舍五入或凑整方法寻找最优解 我们从下面的例子说明这样的方法是不合适的 例1 求下述整数规划问题的最优解 解 如果不考虑整数约束 称为整数规划问题的松弛问题 用图解法得最优解为 3 25 2 5 考虑到整数约束 用凑整法求解时 比较四个点 4 3 4 2 3 3 3 2 前三个都不是可行解 第四个虽然是可行解 但z 13不是最优 实际问题的最优解为 4 1 这时z 14 逻辑 0 1 变量在建立数学模型中的作用 1 m个约束条件中只有k个起作用 设m个约束条件可以表示为 定义逻辑变量 又设M为任意大的正数 则约束条件可以改写为 定义逻辑变量 此时约束条件可以改写为 3 两组条件满足其中一组 若x1 4 则x2 1 第一组条件 否则当x1 4时 x2 3 第二组条件 定义逻辑变量 又设M为任意大正数 则问题可表达为 需注意 当约束为大于时 右端项中用减号 4 用以表示含固定费用的函数 用xj代表产品j的生产数量 其生产费用函数表示为 其中Kj是同产量无关的生产准备费用 问题的目标是使所有产品的总生产费用为最小 即 定义逻辑变量 表示是否生产产品j 又设M为任意大正数 为了表示上述定义 引入约束 显然 当xj 0时 yj 1 将目标函数与约束条件合起来考虑有 由此看出 当xj 0时 为使z极小化 应有yj 0 2 分配问题与匈牙利法 一 问题的提出与数学模型 分配问题也称指派问题 assignmentproblem 是一种特殊的整数规划问题 假定有m项任务分配给m个人去完成 并指定每人完成其中一项 每项只交给其中一个人去完成 应如何分配使总的效率为最高 如果完成任务的效率表现为资源消耗 考虑的是如何分配任务使得目标极小化 如果完成任务的效率表现为生产效率的高低 则考虑的是如何分配使得目标函数极大化 在分配问题中 利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表 表格中数字组成效率矩阵 例2 有一份说明书 要分别翻译成英 日 德 俄四种文字 交甲 乙 丙 丁四个人去完成 因各人专长不同 使这四个人分别完成四项任务总的时间为最小 效率表如下 效率矩阵用 aij 表示 为 定义逻辑变量 则分配问题的数学模型写为 二 匈牙利法 用表上作业法来求解分配问题时 单位运价表即效率表 产销平衡表中产量和销量都设为1即可 匈牙利数学家克尼格 Konig 求解分配问题的计算方法被成为匈牙利法 他证明了如下两个定理 定理1如果从分配问题效率矩阵 aij 的每一行元素中分别减去 或加上 一个常数ui 被称为该行的位势 从每一列分别减去 或加上 一个常数vj 被称为该列的位势 得到一个新的效率矩阵 bij 若其中bij aij ui vj 则 bij 的最优解等价于 aij 的最优解 定理2若矩阵A的元素可分成 0 与非 0 两部分 则覆盖 0 元素的最少直线数等于位于不同行不同列的 0 元素的最大个数 结合例2说明匈牙利法的计算步骤 第一步 找出效率矩阵每行的最小元素 并分别从每行中减去 第二步 找出矩阵每列的最小元素 分别从各列中减去 第三步 经过上述两步变换后 矩阵的每行每列至少都有了一个零元素 下面确定能否找出m个位于不同行不同列的零元素的集合 该例中m 4 也就是看要覆盖上面矩阵中的所有零元素 至少需要多少条直线 1 从第一行开始 若该行只有一个零元素 就对这个零元素打上 对打括号的零元素所在的列画一条线 若该行没有零元素或者有两个以上零元素 已划去的不算在内 则转下一行 依次进行到最后一行 2 从第一列开始 若该列只有一个零元素 就对这个零元素打上 同样不考虑已划去的零元素 再对打括号的零元素所在行画一条直线 若该列没有零元素或有两个以上零元素 则转下一列 依次进行到最后一列为止 3 重复上述步骤1 2 可能出现三种情况 效率矩阵每行都有打括号的零元素 只要对应这些元素令xij 1就找到了最优解 打括号的零元素个数少于m 但未被划去的零元素之间存在闭回路 这时顺着闭回路的走向 对每个间隔的零元素打一个括号 然后对所有打括号的零元素所在行 或列 画一条直线 同样得到最优解 矩阵中所有零元素或被划去 或打上括号 但打括号的零元素少于m 这时转入第四步 第四步 按定理1进行如下变换 1 从矩阵未被直线覆盖的数字中找出一个最小的k 2 对矩阵中的每行 当该行有直线覆盖时 令ui 0 无直线覆盖的 令ui k 3 对矩阵中有直线覆盖的列 令vj k 对无直线覆盖的列 令vj 0 4 从原矩阵的每个元素aij中分别减去ui和vj 第五步 回到第三步 反复进行 直到矩阵的每一行都有一个打括号的零元素为止 即找到最优分配方案 由于调整后的矩阵中新出现了一个零 因此对打括号的元素重新进行调整 得到如下矩阵 这时只要把打括号元素所对应的决策变量取值为1 就得到最优解 该问题中 最优值为 4 4 9 11 28h 三 两点说明 1 分配问题中人数和工作任务不相等时 当人数多于工作任务数时 可以添加假想任务使得人数与工作任务数相同 因为工作任务是假想的 因此完成这些任务的时间是零 当任务数多于人数时 可添加假想的人 这样的方法和运输问题中处理的方法类似 2 当问题目标变为求极大时 可改写为 此时效率矩阵中元素都变为了负值 可利用定理1 使效率矩阵中全部元素都变为非负的 就可以利用匈牙利法进行求解 3 分枝定界法 记待解的整数规划问题为L 相应的线性规划问题 去掉了整数约束 即松弛问题 为L0 整数规划的最优值为z 分枝定界法的基本思想 1 先不考虑整数条件 即先求解相应线性规划L0的最优解 若得到的是整数解 则问题得到解决 否则 这个非整数解必是原整数规划问题L的最优解z 的上界 记为 而L的任一整数解 可以看作一个下界 记为 2 从得到的L0的最优解中 任选一个非整数的变量xk 在L0中增加约束条件xk xk 构成一个新的线性规划问题L1 它实际上是L0的一个分枝 在L0中增加另一约束条件xk xk 1 又得到一个L0的分支 记为L2 分别求出L1和L2的最优解 判断这两个解是否是最优解 若是 问题得到解决 若不是 调整和 将它们再分枝 直到求出最优整数解为止 分枝定界法实质是将L0的可行域分成若干子区域 称为分枝 逐渐减小和增大 最终求出z 例 用分枝定界法求解整数规划问题 解 1 求解对应的松弛问题L0 其最优解为 最优值为 这样松弛问题L0变为了求解下述两个问题 L0分解为L1和L2 定界 这时两个问题的最优值中较大的一个是14 5 比原来的上界要小 因此修改上界 令 又由于目前没有出现更好的整数界 所以下界仍然是0 分枝 选取最优值较大的子问题优先进行分枝 将L1分解为L11和L12两个子问题 L11和L12两个子问题的可行域为 继续分枝定界 最后剪枝求解得最优解 4 1 最优解为14 见P93 图4 5 4 割平面法 割平面法是求解整数规划问题最早提出的一种方法 1958年由高莫雷 Gomory 提出 基本思路是不断引进适当的线性约束条件 使得可行域逐步缩小 但每次切割只是割去问题的部分非整数解 直到使问题的目标值达到最优的整数点成为缩小后可行域的一个顶点 这样就可以用求解线性规划的方法找出这个最优解 例 用割平面法求解整数规划问题 解 1 约束条件系数化整 忽略整数约束 用单纯形法求解对应的松弛问题 得最终单纯形表 2 找出非整数解变量中分数部分最大的基变量 并写下这行约束 4 重复第一至第三步一直到找出问题的整数最优解为止 具体求解过程P95 在这个问题的求解过程中 依次加入了两个约束条件 割了两次平面 问题变为 图示割平面 最优解为 4 1 这时z 14 1 2 步骤 化标准形 隐枚举法 1 目标函数极小化2 约束条件化成 3 使目标函数系数皆为非负 若xj系数为负值 则令xj 1 xj 4 使目标函数按变量系数由小 大顺序排列 约束条件变量排列的顺序要与之对应 令所有变量xj 0 计算边界目标函数值z 检查是否满足所有约束条件 若满足 即为最优解 否则 分枝计算 分枝 按变量次序依次令各变量取 1 和 0 值 计算边界值 然后检查是否满足所有约束 若满足 转下步 否则继续分枝 剪枝 在得到一个可行解后 分枝过程中要进行剪枝工作 a 对可行解 保留边界值最小的一枝zmin 其余全剪掉 b zmin分枝 剪掉 c 能判断出为无可行解的分枝 剪掉 d 非上述情况 继续分枝 5 解0 1规划问题的隐枚举法 例 求解下述0 1规划问题 Maxz 8x1 2x2 4x3 7x4 5x5st 3x1 3x2 x3 2x4 3x5 45x1 3x2 2x3 x4 x5 4xj 0或1 j 1 2 3 4 5 1 目标函数极小化 minz 8x1 2x2 4x3 7x4 5x5 化标准形 2 约束条件 3