第六章任务分派方案的优化方法ppt课件.ppt

引例 一个任务分派问题优化方法 匈牙利法应用和推广 第六章任务分派方案的优化方法 第一节一个任务分派问题 安排甲 乙 丙 丁四人完成车 铣 刨 磨床工作 不同工人对不同机床的熟练程度有区别 根据以往的资料 估算出每个工人对各种工种的预制工夹具等准备时间的数据如下表 一个工人担任一个工种 一个工种工作由一个工人来完成 如何合理的分配任务 使得所有工人化费的准备时间总和尽可能的小 有n项任务 恰好n个人承担 第i人完成第j项任务的花费 时间或费用等 为cij 0 如何指派使总花费最省 第j项工作由一个人做 第i人做一项工作 标准形式的任务分派问题 可行的分派方案 每人一项任务 每项任务由一个人承担 可行解可表示为 例有一份中文说明书 需译成英 日 德 俄四种文字 分别记作E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成不同语种的说明书所需时间如下表 问应指派何人去完成何工作 使所需总时间最少 第二节优化方法 阶数 写出费用矩阵 已知条件可用系数矩阵 效率矩阵 表示为 其可行解也可用每行仅有一个1 每列也仅有一个1的矩阵表示 如 2 4 11 4 若某行 列 已有0元素 那就不必再减了 例中的计算为 根据结论1 结论2进行行列缩减 使系数矩阵各行 各列出现零元素 作法 系数矩阵各行元素减去所在行的最小元素 再从所得矩阵的各列减去所在列最小元素 费用矩阵行列缩减 试求最优解 如能找出n个位于不同行不同列的零元素 独立0 令对应的xij 1 其余xij 0 得最优解 结束 否则下一步 画线盖0 调整0的布局 独立0的个数 n 最优分派 未得到最优分配方案 以最少的直线数覆盖所有的0 未被直线覆盖的最小元素为cij 未被直线覆盖处减去cij 仅被一条直线覆盖的元素不变 直线交叉点元素加上cij 得新效益矩阵 对新矩阵 重新试分配 2 可以分派 求最优解 最优分派方案是甲 刨床乙 铣床丙 磨床丁 车床 总的准备时间 5 4 11 4 24小时 第三节应用和推广 一 工人与任务的广泛含义 166页例 工会应怎样安排 使缺席听课的职工人数最少 工人 任务 解 费用矩阵 费用矩阵行列缩减 30 20 20 10 10 画线盖0 调整0的布局 重复上述步骤 标号法分派 多重最优解 周二 美学周三 史学周四 文学周五 哲学 总缺席人数 50 20 20 10 100人 二 最大总收益问题有六名工人在六个岗位上的效率以百分数表示如下 求使总效率最高的任务分配方案 设最大总收益问题的收益矩阵为B bij i 1 2 n j 1 2 n 如果则令构成矩阵 那末 以为费用矩阵的最优方案就是原最大总收益问题的最优方案 本例 对C行列缩减 画线盖0 调整0的布局 再次调整0的布局 回到原问题 得最优解 工人1 岗位6 工人2 岗位3 工人3 岗位5 工人4 岗位2 工人5 岗位1 工人6 岗位4 最大总效率 99 98 99 97 84 86 563 三 非标准形式的任务分派问题 应选哪几名运动员组成4 100的接力队 总费用最小的问题 工人数 任务数 称为非标准的任务分派问题 如果工人数 任务数 虚设一个工人 如果工人数 任务数