分配问题与匈牙利法.ppt

分配问题与匈牙利法 指派问题的数学模型的标准形式 设n个人被分配去做n件工作 规定每个人只做一件工作 每件工作只有一个人去做 已知第i个人去做第j件工作的效率 时间或费用 为Cij i 1 2 n j 1 2 n 并假设Cij 0 问应如何分配才能使总效率 时间或费用 最高 设决策变量 分配问题与匈牙利法 指派问题的数学模型为 分配问题与匈牙利法 克尼格定理 如果从分配问题效率矩阵 aij 的每一行元素中分别减去 或加上 一个常数ui 从每一列中分别减去 或加上 一个常数vj 得到一个新的效率矩阵 bij 则以 bij 为效率矩阵的分配问题与以 aij 为效率矩阵的分配问题具有相同的最优解 分配问题与匈牙利法 指派问题的求解步骤 1 变换指派问题的系数矩阵 cij 为 bij 使在 bij 的各行各列中都出现0元素 即从 cij 的每行元素都减去该行的最小元素 再从所得新系数矩阵的每列元素中减去该列的最小元素 2 进行试指派 以寻求最优解 在 bij 中找尽可能多的独立0元素 若能找出n个独立0元素 就以这n个独立0元素对应解矩阵 xij 中的元素为1 其余为0 这就得到最优解 分配问题与匈牙利法 找独立0元素 常用的步骤为 从只有一个0元素的行开始 给该行中的0元素加圈 记作 然后划去 所在列的其它0元素 记作 这表示该列所代表的任务已指派完 不必再考虑别人了 依次进行到最后一行 从只有一个0元素的列开始 画 的不计在内 给该列中的0元素加圈 记作 然后划去 所在行的0元素 记作 表示此人已有任务 不再为其指派其他任务了 依次进行到最后一列 若仍有没有划圈的0元素 且同行 列 的0元素至少有两个 比较这行各0元素所在列中0元素的数目 选择0元素少这个0元素加圈 表示选择性多的要 礼让 选择性少的 然后划掉同行同列的其它0元素 可反复进行 直到所有0元素都已圈出和划掉为止 分配问题与匈牙利法 若 元素的数目m等于矩阵的阶数n 即 m n 那么这指派问题的最优解已得到 若m n 则转入下一步 3 用最少的直线通过所有0元素 其方法 对没有 的行打 对已打 的行中所有含 元素的列打 再对打有 的列中含 元素的行打 重复 直到得不出新的打 号的行 列为止 对没有打 号的行画横线 有打 号的列画纵线 这就得到覆盖所有0元素的最少直线数l 注 l应等于m 若不相等 说明试指派过程有误 回到第2步 另行试指派 若l m n 表示还不能确定最优指派方案 须再变换当前的系数矩阵 以找到n个独立的0元素 为此转第4步 分配问题与匈牙利法 4 变换矩阵 bij 以增加0元素在没有被直线通过的所有元素中找出最小值 没有被直线通过的所有元素减去这个最小元素 直线交点处的元素加上这个最小值 新系数矩阵的最优解和原问题仍相同 转回第2步 分配问题与匈牙利法 例4 6有一份中文说明书 需译成英 日 德 俄四种文字 分别记作A B C D 现有甲 乙 丙 丁四人 他们将中文说明书译成不同语种的说明书所需时间如下表所示 问如何分派任务 可使总时间最少 分配问题与匈牙利法 解 1 变换系数矩阵 增加0元素 5 2 试指派 找独立0元素 找到3个独立零元素但m 3 n 4 分配问题与匈牙利法 3 作最少的直线覆盖所有0元素 独立零元素的个数m等于最少直线数l 即l m 3 n 4 4 没有被直线通过的元素中选择最小值为1 变换系数矩阵 将没有被直线通过的所有元素减去这个最小元素 直线交点处的元素加上这个最小值 得到新的矩阵 重复2 步进行试指派 分配问题与匈牙利法 试指派 得到4个独立零元素 所以最优解矩阵为 即完成4个任务的总时间最少为 2 4 1 8 15 分配问题与匈牙利法 例4 7已知四人分别完成四项工作所需时间如下表 求最优分配方案 分配问题与匈牙利法 解 1 变换系数矩阵 增加0元素 2 试指派 找独立0元素 独立0元素的个数为4 指派问题的最优指派方案即为甲负责D工作 乙负责B工作 丙负责A工作 丁负责C工作 这样安排能使总的工作时间最少 为4 4 9 11 28 分配问题与匈牙利法 例4 8已知五人分别完成五项工作耗费如下表 求最优分配方案 分配问题与匈牙利法 1 2 解 1 变换系数矩阵 增加0元素 分配问题与匈牙利法 2 试指派 找独立0元素 独立0元素的个数l 4 5 故画直线调整矩阵 分配问题与匈牙利法 选择直线外的最小元素为1 直线外元素减1 直线交点元素加1 其他保持不变 分配问题与匈牙利法 l m 4 n 5 选择直线外最小元素为1 直线外元素减1 直线交点元素加1 其他保持不变 得到新的系数矩阵 分配问题与匈牙利法 总费用为 5 7 6 6 4 28 注 此问题有多个最优解 分配问题与匈牙利法 总费用为 7 9 4 3 5 28 分配问题与匈牙利法 总费用为 8 9 4 3 4 28 分配问题与匈牙利法 课堂练习 用匈牙利法求解下列指派问题 练习1 练习2 分配问题与匈牙利法 48 21 答案 分配问题与匈牙利法 非标准型的指派问题 匈牙利法的条件是 模型求最小值 效率cij 0 当遇到各种非标准形式的指派问题时 处理方法是先将其转化为标准形式 然后用匈牙利法来求解 分配问题与匈牙利法 1 最大化指派问题 处理方法 设m为最大化指派问题系数矩阵C中最大元素 令矩阵B m cij nn则以B为系数矩阵的最小化指派问题和原问题有相同的最优解 例4 9某人事部门拟招聘4人任职4项工作 对他们综合考评的得分如下表 满分100分 如何安排工作使总分最多 分配问题与匈牙利法 解 M 95 令 用匈牙利法求解C 最优解为 即甲安排做第二项工作 乙做第三项 丙做第四项 丁做第三项 最高总分Z 92 95 90 80 357 分配问题与匈牙利法 2 不平衡的指派问题 当人数m大于工作数n时 加上m n项虚拟工作 例如 当人数m小于工作数n时 加上n m个人 例如 分配问题与匈牙利法 3 一个人可做几件事的指派问题 若某人可做几件事 则将该人化作相同的几个 人 来接受指派 且费用系数取值相同 例如 丙可以同时任职A和C工作 求最优指派方案 分配问题与匈牙利法 4 某事一定不能由某人做的指派问题 将该人做此事的效率系数取做足够大的数 可用M表示 例4 10分配甲 乙 丙 丁四个人去完成A B C D E五项任务 每个人完成各项任务的时间如表所示 由于任务数多于人数 考虑任务E必须完成 其他4项中可任选3项完成 试确定最优分配方案 使完成任务的总时间最少 分配问题与匈牙利法 解 1 这是不平衡的指派问题 首先转换为标准型