整数规划解法-匈牙利 算法部分.ppt

1 4 5整数规划的解法 分支定界法割平面法匈牙利法 2 4 5 1整数规划解法 分枝定界法 步骤 1 寻找替代问题并求解2 分枝与定界3 剪枝 3 1 基本思路 整数规划的最优解不会优于相应的线性规划的最优解 对于极大值问题 相应线性规划的最大值成为整数规划目标函数的上界 B 为 A 的松弛问题 1 替代问题的确定 4 2 替代问题的求解 采用相应的方法 如图解法 求解出替代问题的最优解 观察其是否满足整数解的要求 如其最优解就为整数 则结束 如含有分数 则需要进行分支定界操作 5 3 分支与定界 增加约束 如替代问题的解不符合整数条件 则需要对原问题进行分支 分支方法 假设替代问题的解为 i i 1 之间的一个数 则分成两支 一支增加约束xj i 另一支增加约束xj i 1 对上述两个问题进行求解 不考虑整数问题时 求解对应的线性规划问题 观察其最优解是否是整数 如不是 则继续分支定界 直到得到全部整数解为止 6 maxZ 40X1 90X2 例 7 解 先解该整数规划对应的松弛问题 选X1分枝 将 4 5 之间的非整数部分舍去 8 选 2 继续分枝 问题2 问题3 9 分支定界过程 10 4 5 2整数规划解法2 割平面法 割平面法的基本思想 在整数规划问题的松弛问题中依次引进线性约束条件 称Gomory约束 高莫雷约束或割平面 使问题的可行域逐步缩小 但每次切割时 只割去问题的部分非整数解 而不切割任何整数的可行解 直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点 这样就可以用求解线性规划问题的方法找出这个最优解 11 4 5 3整数规划的解法 匈牙利法应用于分配问题或指派问题 分配问题也称指派问题 是一种特殊的整数规划问题 假定有m项任务分配给m个人去完成 并指定每人完成其中一项 每项只交给其中一个人去完成 应如何分配使总的效率为最高 12 1 指派问题一般模型的引出 例 有一份说明书 要分别译成英 日 德 俄四种文字 交甲 乙 丙 丁四个人去完成 因各人专长不同 他们完成翻译不同文字所需的时间 h 如表所示 问 如何分配任务使效率最高 所需总时间最短 从人的角度看 从任务角度看 13 指派问题的一般模型 假设 aij 表示指派问题的效率矩阵xij表示决策变量 决策变量的取值 14 指派问题的一般数学模型 指派问题的一般模型 15 2 指派问题的求解方法 单纯形法表上作业法匈牙利法 16 1 指派问题的求解 匈牙利法 核心思路 基于这样一个事实 如果效率矩阵的所有元素aij 0 而其中存在一组位于不同行 不同列的零元素 则只要令对应于这些零元素的xij 1 分配任务 其余的xij 0 则目标函数z必然会取得最小 0 只需令 x11 1 x23 1 x32 1 x44 1 即第一项各种分配给甲 二工作 丙 三 乙 四 丁 总工作时间最少 效率矩阵 17 问题 要求 效率矩阵中存在零元素 同时存在不在同一行 同一列的零元素 实际的效率矩阵中 是不可能存在0元素的 那么如何获得这种特殊的效率矩阵 如何让效率矩阵中产生零元素 如何让产生的零元素位于不同行和不同列 18 2 零元素的产生方法 匈牙利法的基本定理1 如果从分配问题效率矩阵 aij 的每一行元素中分别减去 或加上 一个常数ui 被称为该行的位势 从每一列分别减去 或加上 一个常数vj 称为该列的位势 得到一个新的效率矩阵 bij 若其中则 bij 的最优解等价于 aij 的最优解 说明 经过变换后 有零的新效率矩阵取得最优解时 原效率矩阵也同时取得最优解 19 3 独立零元素的判断方法 匈牙利法的基本定理2 若矩阵A的元素可分成 0 与非 0 两部分 则覆盖 0 元素的最少直线数等于位于不同行 不同列的 0 元素的最大个数 20 若矩阵A的元素可分成 0 与非 0 两部分 则覆盖 0 元素的最少直线数等于位于不同行 不同列的 0 元素的最大个数 将确定一个效率矩阵中最大独立零元素的个数 转化为寻找覆盖所有零元素所需的最少直线数 21 匈牙利法的计算步骤 基本步骤 在效率矩阵中产生零元素 判断独立的零元素个数是否等于任务数或人数 如是 则对效率矩阵中独立零元素所处的位置进行指派 对应的决策变量为1 完成 如否 则要继续产生足够的独立零元素 通过实例来说明匈牙利法求解指派问题的过程 22 例 有一份说明书 要分别译成英 日 德 俄四种文字 交甲 乙 丙 丁四个人去完成 因各人专长不同 他们完成翻译不同文字所需的时间 h 如表所示 问 如何分配任务使效率最高 23 效率矩阵 24 步骤一 零元素的产生 方法 找出效率矩阵每行的最小元素 并分别从每行中减去它 min 实际含义 从事情的角度来考虑 表示此事分配给此人效率最高 25 步骤二 继续产生零元素方法 再找出矩阵每列的最小元素 再分别从各列中减去它 min0050 实际含义 从人的角度来考虑 表示某人做此事效率最高 26 步骤三 判断零元素是否位于不同行 不同列 经过上述两步变换后 矩阵的每行每列至少都有了一个零元素 确定能否找出m个位于不同行不同列的零元素的集合 本例中m 4 直观法 m很小时 直接判断得到 非直观法 m很大时 根据一定规则寻找 27 直观法 只有3个0元素位于不同行 不同列 28 非直观法 步骤1 试指派过程 1 从第一行开始 若该行只有一个零元素 就对这个零元素打上 号 同时 对打 号零元素所在列画一条直线 表示此列已经确定 人员确定 不能再从事其他行的工作 任务 若该行没有零元素或有两个以上零元素 已划去的零元素不计在内 则转下一行 按照上述方法依次进行到最后一行 29 例 从行开始的独立零元素的寻找与判断 从行开始标定独立零元素时 只能找到两个独立的零元素 30 非直观法 步骤2 2 在行寻找的基础上 从第一列开始 若该列只有一个零元素就对这个零元素打上 号 同样不考虑已划去的零元素 对打 号零元素所在行画一条直线 任务分配完毕 不能再分配给其他人 若该列没有零元素或有两个以上零元素 则转下一列 依次进行到最后一列 31 例 从列开始的独立零元素的寻找与判断 在行标定后的基础上 从第一列开始标定独立零元素时 只能找到一独立的零元素 32 问题 只能对三个零元素进行标定 代表独立的零元素只有三个 后续如何操作 33 非直观法 步骤3 第一种情形 3 重复 1 2 两个步骤 可能出现三种情况 效率矩阵每行都有一个打 号的零元素 很显然 按上述步骤得到的打 号的零元素都位于不同行不同列 只要令对应打 号零元素对应的决策变量xij 1就找到了问题的最优解 34 第一种情形 x11 1 x22 1 x33 1 x44 1 任务一 甲 二 乙 三 丙 四 丁 任务一任务二任务三任务四 甲乙丙丁 35 非直观法 4 第二种情形 打 号的零元素个数小于m 但未被划去的零元素之间存在闭回路 全以0为拐点 这时可顺着闭回路的走向 对每个间隔的零元素打一 号 然后对所有打 号的零元素 或所在行 或所在列画一条直线 一般会出现多种方案 如 36 第二种情形 只能给两个零元素打括号 还有四个零元素不能打上括号 剩下的未被划去和未打括号的零元素存在闭回路 37 x13 1 x22 1 x31 1 x44 1 结论1 38 结论2 x14 1 x22 1 x31 1 x43 1 39 非直观法 5 第三种情形 矩阵中所有零元素或被划去 或打上 号 但打 号的零元素个数小于m 如 打括号的零元素3 m 4 证明0元素产生的还不够 还应继续产生 40 步骤四 继续创造零元素 方法 为设法使每一行都有一个打 号的零元素 需要继续按定理1对矩阵进行变换 1 从矩阵未被直线覆盖的数字中找出一个最小的数k 2 对矩阵的每行 当该行有直线覆盖时 令ui 0 无直线覆盖的 令ui k 3 对矩阵每列 有直线覆盖的列 令vj k 对无直线覆盖的列 令vj 0 4 从原矩阵的每个元素aij中分别减去ui和vj 得到一个新的矩阵 aij ui vj 保证新矩阵中 原打括号的0元素不变 同时产生新的零元素 41 步骤五 回到第三步 反复进行 一直到矩阵的每一行都有一个打 号的零元素为止 即找到了最优分配方案 42 最优分配方案为 甲将说明书译成俄文 乙译成日文 丙译成英文 丁译成德文 全部所需时间为4 4 9 11 28小时 43 回顾 指派问题的计算过程 效率矩阵 44 4 11 4 2 步骤一 产生每行的零元素 方法 从每行中找出最小的元素 与对应的每行元素相减 min 每行减去对应的最小元素 45 步骤二 产生位于每列的零元素方法 再找出矩阵每列的最小元素 再分别从各列中减去 min0050 每列减去对应的最小元素 保证每行 每列都至少有一个0元素 46 步骤三 判断零元素是否位于不同行 不同列 方法 首先从行开始试指派 只有一个零元素时 对零元素打括号 并对所在列画直线 而有多个零元素 或零元素已被画去 则转下一行 行分析完毕后 然后从列开始试指派 对每列只有一个零元素时 打括号 并画去其所在的行 行试指派过程 列试指派过程 47 步骤四 继续创造零元素 方法 从未被画去的元素中 找到一个最小的元素k 1 对行的操作 选择行位势ui 如果行被直线覆盖 则ui 0 如果未被覆盖 ui k 2 列的操作 列位势vj 如果列被直线覆盖 vj k 如果未被覆盖 vj 0 3 产生新的效率矩阵 bij aij ui vj 1 最小元素k 2 2 ui依次为2 2 0和2 3 vj依次取为 2 2 0和0 ui 2 2 0 2 vj 2 2 0 0 bij aij ui vj 48 步骤五 继续判断零元素是否位于不同行 不同列 方法 首先从行开始试指派 只有一个零元素时 对零元素打括号 并对所在列画直线 而有多个零元素 或零元素已被画去 则转下一行 行分析完毕后 然后从列开始试指派 对每列只有一个零元素时 打括号 并画去其所在的行 最终结果 49 步骤六 获得最后结果 方法 对于打括号的零元素处进行指派 即可获得最短时间 x13 1 工作一 丙 x22 1 工作二 乙 x34 1 工作三 丁 x41 1 工作四 甲 最短时间为 9 4 11 4 28h 指派结果 50 4 5 4极大化的指派问题 对于目标为求极大的指派问题 先要对效率矩阵进行处理 1 找出效率矩阵中的最大值 分别用它去减阵中每一元素 得到新矩阵 2 对新得到的矩阵用原匈牙利法求解 51 52 例 有4种机械要分别安装在4个工地 它们在4个工地的工作效率不同 问应如何指派 可使4台机械发挥的总效益最大 53 解 原效益矩阵中maxCij Cij 43所以bij 43 Cij i j 1 2 3 4 54 4 5 5人数和任务数不相等 例 4项工作分配给6个人完成 有人可不做 55 解 虚设两项假想的任务 56 0 0 0 0 0 0 人员安排 1 2 3 4 5休息 6 总的时间为 2 1 3 2 8 57 0 0 0 0 0 0 人员安排 1 2 3 4 5休息 6 总的时间为 2 1 3 2 8 58 例 4人完成5项任务 每人可完成1 2项 59 解 因每个人可担任一至二项任务 因此将4人看作8人 再虚设3项任务 化为平衡指派问题 60 最优解 甲 无乙 C D丙 B E丁 AminZ 129 61 例 4人完成5项任务 其中一人完成两项 其余每人一项 62 解 虚设一人戊 完成各任务时间为甲 乙 丙 丁中最小者 化为平衡指派问题 最优方案 甲 B乙 D C丙 E丁 A最小时间 131 63 P109 4 3有4个工人 要指派他们分别完成4项工作 每人做每项工作所消耗的时间如表所示 问指派哪个人去完成哪项工作 可使总的消耗时间最小 表中时间单位为h 作业 64 P109 4 4已知下列5名运动员各种姿势的游泳成绩 距离为50m 如表所示 试问如何从中选拔一个参加200m混合泳的接力队 四种游泳姿势 使预期比赛成绩最好 表中时间单位为S 思考 。