分配问题指派问题与匈牙利法

第 5讲 分配问题（指派问题）与匈牙利法 分配问题的提出 分配问题的提出 若干项 工作或任务 需要若 干个人 去完成 。 由于每人的知识 、 能力 、 经验的不同 ， 故各人完成不同任务所需要的时间不同 （ 或其他资源 ） 。 问： 应指派哪个人完成何项工作 ， 可使完成所有工作所 消 耗的总资源最少 ？ 分配问题的提出 设某公司准备派 n 个工人 x1， x2， ， xn ， 去作 n 件工作 y1， y2， ， yn。 已知工人 xi完成工作 yj 所需 时间为 cij (i,j=1,2, ,n)。 现问：如何确定一个分派工人去工作的方案 ， 使 得工人们完成工作的 总时间为最少 。 台 机 床 加 工 项 任 务 ； 条 航 线 有 艘 船 去 航 行 等 。 n n n n 还比如： 整体解题思路总结 例题： 工作者 1 工作者 2 工作者 3 工作者 4 工作者 5 工作 1 4 8 7 15 12 工作 2 7 9 17 14 10 工作 3 6 9 12 8 7 工作 4 6 7 14 6 10 工作 5 6 9 12 10 6 单位：小时 标准形式的分配问题 标准形式的分配问题 分派方案满足下述两个条件： 1.任一个工人都不能去做两件或两件以上的工作 2.任一件工作都不能同时接受两个及以上的工人去做 设某公司准备派 n 个工人 x1， x2， ， xn ， 去作 n 件工作 y1， y2， ， yn。 已知工人 xi完成工作 yj 所需时间为 cij (i,j=1,2, ,n)。 现问：如何确定一个分派工人去工作的方案 ， 使得工人们 完成工作的 总时间为最少 。 标准形式的分配问题 n个人 n件事 每件 事 必有且只有一个人去做 每个 人 必做且只做一件事 数学模型 n个人 n件事 cij： 第 i人做第 j事的费用 xij 1 若指派第 i人做第 j事 0 若指派第 i人不做第 j事 总费用 ： 11 nn ij ij ijcx i， j 1, ., n j 1,.,n i 1,.,n n i ijx 1 1 n j ijx 1 1 每件 事 必有且只有一个人去做 每个 人 必做且只做一件事 时间、原料、 金钱等资源 数学模型 n i n j ijij xcz 1 1 m in n i ijx 1 1 n j ijx 1 1 j 1,.,n i 1,.,n ,. .,n,i ,jx ij 21 10 或 s.t. 线性规划问题 运输问题 0-1型整数规划问题 匈牙利 法 1955年由美国数学家 W.W.kuhn(库恩 )提出 ， 利用了 匈牙利数学家 D.Konig(康尼格 )证明的 2个定理 。 nnnn n n ccc ccc ccc C . . . . 11 22221 11211 nnnn n n xxx xxx xxx X . . . . 11 22221 11211 系数矩阵 (效率矩阵 ) 解矩阵 (决策变量矩 阵 ) n个人 n件事 定义 ： 在系数矩阵 C中 ， 处在不同行不同列 的一 组零元素 ， 称为 独立零元素组 ， 其中每个元素 称为 独立零元素 。 0084 7650 0032 0205 C 44313212 43312412 , , cccc cccc 44313241 , cccc 0100 0001 1000 0010 X n i n j ijij xcz 1 1 m in 最优解 0 1 4 丙 0 8 5 乙 2 1 0 甲 C B A 时 工作 间 人员 0丙 7乙 0甲 时 间 4 5 8 丙 4 12 9 乙 9 8 7 甲 C B A 时 工作 间 人员 定理： 若 将分配问题系数矩阵的 每一行 及 每一列 分别 减去 各行及各列的 最小元素 ， 则 新分配问题与原分配 问题有 相同的最优解 ， 只有最优值差一常数 。 相关定理 使每行每列 都出现零元素 步骤 1： 变换系数矩阵，使其每行每列都出现 0元素 把各 行 元素分别减去本行元素的最小值 ， 然后 在此基础上 再把每 列 元素减去本列中的最小值 。 6 10 12 9 6 10 6 14 7 6 7 8 12 9 6 10 14 17 9 7 12 15 7 8 4 0 4 3 2 0 4 0 5 0 0 1 2 3 2 0 3 7 7 1 0 8 11 0 3 0 0 4 6 3 0 4 0 8 1 0 1 2 6 3 0 3 7 01 2 0 8 11 3 4 0 6 6 6 7 4 min 00310m in 此时每行及每列中肯定都有 0元素 步骤 2： 进行试分配，判断是否存在 n个独立零元素 尝试对所有零元素做 标记 ， 确定 独立零元素 。 （ 1）逐 行 检验 对 只有一个 未标记 的零元素的 行 ， 用 记号 O将该零元素圈起 ， 然后 将 被圈起的零元素所在列 的其他 未标记的零元素 用 记号 /划去 。 0 1 3 7 0 6 0 6 9 0 5 3 2 0 1 0 0 重复行检验 ， 直到 每一行都没有未被标记 的零元素 或 至少有两个未 被标记 的零元素为止 。 表示此人只能做该事 （此事只能由该人做） 表示此事已不能由 其他人来做 （此人已不能做其他事） 04320 40500 12320 37710 811030 圈 0即独立零元素 步骤 2： 进行试分配，判断是否存在 n个独立零元素 尝试对所有零元素做 标记 ， 确定 独立零元素 。 （ 2）逐 行 检验 步骤 2： 进行试分配，判断是否存在 n个独立零元素 尝试对所有零元素做 标记 ， 确定 独立零元素 。 （ 2）逐 列 检验 与行检验类似： 对只有一个未标记的零元素的 列 ， 用记号 O将该 零元素圈起 ， 然后将被圈起的零元素所在 行 的其他未标记的零元 素用记号 /划去 。 重复 列 检验 ， 直到 没有未被标记 的零元素 或 至少有两个未被标记 的零元素为止 。 0 1 3 7 0 6 0 6 9 0 5 3 2 0 1 0 0 04320 40500 12320 37710 811030 圈 0即独立零元素 步骤 2： 进行试分配，判断是否存在 n个独立零元素 尝试对所有零元素做 标记 ， 确定 独立零元素 。 （ 2）逐 列 检验 可能出现三种情况 1.每一行均有圈 0出现 ， 圈 0的个数恰好等于 n 2.存在未标记过的零元素 ， 但它们所在的行和列中 ， 未被标 记过的零元素的个数均至少有两个 。 3.不存在未被标记过的零元素 ， 但圈 0的个数 n 可进行分配：令 圈 0位置的决策变量取值 为 1， 其他为 0 （ 3）判断 独立零元素 的个数 0 1 3 7 0 6 0 6 9 0 5 3 2 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 可能出现三种情况 2.存在未标记过的零元素 ， 但它们所在的行和列中 ， 未被标 记过的零元素的个数均至少有两个 。 3.不存在未被标记过的零元素 ， 但圈 0的个数 n 从某 行 （ 列 ） 的 两个 未被标记过的零元素中 任选一个 加上 圈 ， 然后给 同 列 、 同 行 的其他未被标记的零元素都加 /， 然后再 进行行 、 列检验 ， 可能出现情况 1或 3。 （ 3）判断 独立零元素 的个数 5 0 2 0 9 2 3 0 0 8 0 1 0 5 7 5 9 8 0 0 4 0 6 3 6 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 圈 0个数 等于 n=5 多重最优解 5 0 2 0 9 2 3 0 0 8 0 1 0 5 7 5 9 8 0 0 4 0 6 3 6 0 5 0 2 0 9 2 3 0 0 8 0 1 0 5 7 5 9 8 0 0 4 0 6 3 6 0 5 0 2 0 9 2 3 0 0 8 0 1 0 5 7 5 9 8 0 0 4 0 6 3 6 0 可能出现三种情况 3.不存在未被标记过的零元素 ， 但圈 0的个数 n （ 3）判断 独立零元素 的个数 圈 0个数 4 n=5 作 最少直线覆盖当前所有零元素 ， 便 于下步增加独立零元素的个数 。 04320 40500 12320 37710 811030 定理： 系数矩阵 C中 独立零元素的最多个数 等于 能覆 盖所有零元素的 最少线数 。 由匈牙利数学家 D.Konig(康尼格 )所证明 5 0 2 0 2 3 0 0 0567 4 8 0 0 5 0 2 0 2 2 3 0 0 0 0 1 0 5 7 2 9 8 0 0 4 0 6 3 6 5 例 ：分别求下列矩阵中的独立零元素的最多个数。 4 4 独立零元素 的个数最多： 对 不含圈 0的行打 ； 在打 的行中 ， 对所有零元素所在 列 打 ； 在所有打 的列中 ， 对圈 0所在 行 打 ； 重复 2,3步 ， 直到不能 打 为止 。 对 未打 的每一行 画一横线 ， 对 已打 的每一列 画 一纵线 ， 即得到覆盖当前 0元素的 最少直线 集 。 04320 40500 12320 37710 811030 找未被直线覆盖的最小数字 k； 对矩阵的每行：当该行 有直线覆盖时 ， 令 ui=0； 当该行 无直线覆盖 时 ， 令 ui=k。 04320 40500 12320 37710 811030 ui 0 1 1 0 对矩阵的每列：当该列 有直线覆盖时 ， 令 vj=-k； 当该 列 无直线覆盖 时 ， 令 vj=0。 vj -1 0 0 0 0 04320 40500 12320 37710 811030 ui 0 1 1 0 vj -1 0 0 0 0 04320 40500 01210 26600 811030 从原矩阵的每个元素 aij 中分别减去 ui和 vj， 得到新元 素 再次寻找独立零元素 04320 40500 01210 26600 811030 逐 列 检验 10000 01000 00001 00010 00100 6 10 12 9 6 10 6 14 7 6 7 8 12 9 6 10 14 17 9 7 12 15 7 8 4 原题： 分配方案 A=7+9+6+6+6=34 再次寻找独立零元素 04320 40500 01210 26600 811030 逐 列 检验 00001 01000 10000 00010 00100 6 10 12 9 6 10 6 14 7 6 7 8 12 9 6 10 14 17 9 7 12 15 7 8 4 分配方案 B=7+9+7+6+6=35 对 不含圈 0的行打 ； 在打 的行中 ， 对所有零元素所在 列 打 ； 在所有打 的列中 ， 对圈 0所在 行 打 ； 重复 2,3步 ， 直到不能 打 为止 。 对 未打 的每一行 画一横线 ， 对 已打 的每一列 画 一纵线 ， 即得到覆盖当前 0元素的 最少直线 集 。 5 0 2 0 2 2 3 0 0 0 0 1 0 5 7 2 9 8 0 0 4 0 6 3 6 5 5 0 2 0 2 2 3 0 0 0 0 1 0 5 7 2 9 8 0 0 4 0 6 3 6 5 圈 0个数 4 n=5 找未被直线覆盖的最小数字 k； 对矩阵的每行：当该行 有直线覆盖时 ， 令 ui=0； 当该行 无直线覆盖 时 ， 令 ui=k。 ui 0 0 2 0 2 对矩阵的每列：当该列 有直线覆盖时 ， 令 vj=-k； 当该 列 无直线覆盖 时 ， 令 vj=0。 vj -2 0 0 0 0 5 0 2 0 2 2 3 0 0 0 0 1 0 5 7 2 9 8 0 0 4 0 6 3 6 5 34140 40089 05380 00032 20205 从原矩阵的每个元素 aij 中分别减去 ui和 vj， 得到新元 素 ui 0 0 2 0 2 vj -2 0 0 0 0 5 0 2 0 2 2 3 0 0 0 0 1 0 5 7 2 9 8 0 0 4 0 6 3 6 5 34140 40089 05380 00032 20205 再次寻找独立零元素 分配方案 B 00001 00100 10000 01000 00010 34140 40089 05380 00032 20205 再次寻找独立零元素 分配方案 B 00001 01000 10000 00100 00010 整体解题思路总结 整体解题思路总结 例题： 人 1 人 2 人 3 人 4 人 5 工作 1 4 8 7 15 12 工作 2 7 9 17 14 10 工作 3 6 9 12 8 7 工作 4 6 7 14 6 10 工作 5 6 9 12 10 6 单位：小时 整体解题思路总结 6 10 12 9 6 10 6 14 7 6 7 8 12 9 6 10 14 17 9 7 12 15 7 8 4例题： 步骤 1： 变换系数矩阵，使其每行每列都出现 0元素 把各 行 元素分别减去本行元素的最小值 ， 然后 在此基础上 再把每 列 元素减去本列中的最小值 。 6 10 12 9 6 10 6 14 7 6 7 8 12 9 6 10 14 17 9 7 12 15 7 8 4 0 4 3 2 0 4 0 5 0 0 1 2 3 2 0 3 7 7 1 0 8 11 0 3 0 0 4 6 3 0 4 0 8 1 0 1 2 6 3 0 3 7 01 2 0 8 11 3 4 0 6 6 6 7 4 min 00310m in 此时每行及每列中肯定都有 0元素 04320 40500 12320 37710 811030 圈 0即独立零元素 步骤 2： 进行试分配，判断是否存在 n个独立零元素 尝试对所有零元素做 标记 ， 确定 独立零元素 。 （ 2）逐 行 检验 可能出现三种情况 3.不存在未被标记过的零元素 ， 但圈 0的个数 n （ 3）判断 独立零元素 的个数 圈 0个数 4 n=5 作 最少直线覆盖当前所有零元素 ， 便 于下步增加独立零元素的个数 。 04320 40500 12320 37710 811030 对 不含圈 0的行打 ； 在打 的行中 ， 对所有零元素所在 列 打 ； 在所有打 的列中 ， 对圈 0所在 行 打 ； 重复 2,3步 ， 直到不能 打 为止 。 对 未打 的每一行 画一横线 ， 对 已打 的每一列 画 一纵线 ， 即得到覆盖当前 0元素的 最少直线 集 。 04320 40500 12320 37710 811030 找未被直线覆盖的最小数字 k； 对矩阵的每行：当该行 有直线覆盖时 ， 令 ui=0； 当该行 无直线覆盖 时 ， 令 ui=k。 04320 40500 12320 37710 811030 ui 0 1 1 0 对矩阵的每列：当该列 有直线覆盖时 ， 令 vj=-k； 当该 列 无直线覆盖 时 ， 令 vj=0。 vj -1 0 0 0 0 04320 40500 12320 37710 811030 ui 0 1 1 0 vj -1 0 0 0 0 04320 40500 01210 26600 811030 从原矩阵的每个元素 aij 中分别减去 ui和 vj， 得到新元 素 再次寻找独立零元素 04320 40500 01210 26600 811030 逐 列 检验 10000 01000 00001 00010 00100 6 10 12 9 6 10 6 14 7 6 7 8 12 9 6 10 14 17 9 7 12 15 7 8 4 原题： 分配方案 A=7+9+6+6+6=34 再次寻找独立零元素 04320 40500 01210 26600 811030 逐 列 检验 00001 01000 10000 00010 00100 6 10 12 9 6 10 6 14 7 6 7 8 12 9 6 10 14 17 9 7 12 15 7 8 4 分配方案 B=7+9+7+6+6=35