第六章指派问题(第8讲).pptVIP

第六章 指派问题 第六章 指派问题 第六章 指派问题 经典分配问题（AP） 第六章 指派问题 §3 指派问题的应用 分 配 人 工作 时间 A E 2 B J 4 A G 9 A R 7 总时间 = 22 解松弛问题，得：下界为 22 . 显然，不是可行解 . 考虑最优解中，任务 E 必为 A、B、C、D 四人中一人完 成 . 所以分成四支，每支先 确定一人完成 E ，余下三项 按前述松弛问题处理 . 第一支 A E ， 不可行，得 下界为 27 . 分 配 人 工作 时间 A E 2 B J 4 D G 13 B R 8 总时间 = 27 类似得到： 第二支 B E ，etc . 分 配 人 工作 时间 B E 15 A J 10 A G 9 A R 7 总时间 = 41 第六章 指派问题 1 22 2 27 3 41 4 33 6 36 7 24 8 34 12 37 11 28 13 39 9 28 10 31 A E E E E D C B D E, 5 24 E J J J C B A C A G G 可行 可行 * J J J D C B * 可行 * * * 经计算 13 次 (几乎是可行解的一 半) 找到最优解， B J A G, C R zmin = 28 §4 瓶颈分配问题 §4 瓶颈分配问题 9 11 8 7 D 13 16 14 9 C 15 14 4 10 B 4 13 15 2 A R G J E 任务 人员 每人完成一个任务 每个任务一人完成 条件： 目标： 总完成时间最少 总效益最佳 数学模型： 求解方法： 匈牙利算法 s.t. 第六章 指派问题 瓶颈分配问题(BAP) 每人完成一个任务 每个任务一人完成 条件： 目标： 最大完成时间最小 经典分配问题： z = 5 瓶颈分配问题： z = 2 数学模型： 当分配第 i 人完成第 j 项任务 否则 设 §4 瓶颈分配问题 9 11 8 7 D 13 16 14 9 C 15 14 4 10 B 4 13 15 2 A R G J E 任务 人员 第一个任务的完成时间： s.t. 这是非线性的 第六章 指派问题 求解方法： 首先会想到 什么方法 一、化为经典分配问题 1 1 4 4 4 13 40 40 13 求效益矩阵 (dij) 的经典分配： 所以， fmin = 2 §4 瓶颈分配问题 对原效益矩阵 C 的元素 cij 的不同的值按从小到大 的顺序排序 . c(k) 为第 k 个值，用 s 表示不同 c(k) 值的个数，则 定义数列 d(t) 如下： 构建新的效益矩阵 D ： 对 当 令 则 效益矩阵 D 的经典分配问题 的最优解即为原问题的最优解 . 如前例 有什么缺点吗？ 计算量 如： s = 20，n = 10 这给计算机的存储和运算带来巨大困难. 第六章 指派问题 二、阀门算法 几个记号： 1、yk 表示第 k 个可行方案的最大完成时间 2、 表示矩阵 中擦去 的矩阵, 3、 表示矩阵 的最大匹配数 算法步骤： Step 1 任给初始可行方案 ，令 k = 1; Step 2 计算 yk , 在 中擦去 得 求 的最大匹配 Mk+1 ； Step 3 若 则 Mk 为最优解，fmin= yk 否则，令 k = k+1，go to step 2 . §4 瓶颈分配问题 见前例： 取 x11=1, x22=1, x33=1 其