3.3匈牙利算法PPT课件

第1页 匈牙利法求解指派问题 第2页 指派问题 分配问题 AssignmentProblem 例5有一份中文说明书 需翻译成英 日 德 俄四种文字 分别记作E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成英 日 德 俄四种文字所需时间如下 问应该如何分配工作 使所需总时间最少 第3页 第4页 类似有 有n项加工任务 怎样分配到n台机床上分别完成 有n条航线 怎样指定n艘船分别去航行 等 表中数据称为效益矩阵或系数矩阵 其元素大于零 表示分配第i人去完成第j项任务时的效益 或时间 成本等 第5页 引入0 1变量xij 1分配第i人去完成第j项任务 xij 0不分配第i人去完成第j项任务 分配问题的数学模型 MinZ cijxijs t xij 1 j 1 2 n xij 1 i 1 2 n xij 0或1 i 1 2 n j 1 2 n 第6页 xij 1 j 1 2 n 表示第j项任务只能由一人去完成 xij 1 i 1 2 n 第i人只能完成一项任务 满足约束条件的解称为可行解可写成矩阵形式 X 010000100000001 称为解矩阵其各行各列元素之和为1 第7页 匈牙利算法依据 对同一工作i来说 所有机床的效率都提高或降低同一常数 不会影响最优分配 同样 对同一机床j来说 做所有工作的效率都提高或降低同一常数 也不会影响最优分配 第8页 匈牙利法基本思想 通过变换修改系数矩阵的行和列的元素 使在每一行或每一列中至少有一个0元素 直到在不同行 不同列中至少有一个0元素 从而得到与这些0元素相对应的一个完全分配方案 关键 寻找n个独立0元素 第9页 例5有一份中文说明书 需翻译成英 日 德 俄四种文字 分别记作E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成英 日 德 俄四种文字所需时间如下 问应该如何分配工作 使所需总时间最少 第10页 第11页 匈牙利算法的步骤 第一步 使分配问题的系数矩阵经变换 在各行各列中都出现0元素 从系数矩阵的每行元素减去该行的最小元素 再从所得系数矩阵的每列元素减去该列的最小元素 若某行已经有0元素 就不必再减了 第12页 cij 21513441415914161378119 2497 01311260101105740142 42 01370606905320100 第13页 第二步 进行试分配 以寻找最优解 从只有一个0元素的行 或列 开始 给这个0元素加圈 记 然后划去 所在的列 或行 的其他0元素 记作 给只有一个0元素的列 或行 的0元素加圈 记 然后划去 所在的行 或列 的其他0元素 记作 反复进行上述两步 直到所有的0元素都被圈出和划掉为止 第14页 若还有没有划圈的0元素 且同行 或列 的0元素至少有二个 从剩有0元素最少的行 或列 开始 比较这行各0元素所在列中0元素的数目 选择0元素少的那列的0元素加圈 然后划掉同行同列的其他0元素 可反复进行 直到所有的0元素都被圈出和划掉为止 若 元素的数目m等于矩阵阶数n 那么这分配问题的最优解已得到 若m n 则转下一步 第15页 013706 6905320100 从只有一个0元素的行 或列 开始 给这个0元素加圈 记 第16页 013706 69 5320100 从只有一个0元素的行 或列 开始 给这个0元素加圈 记 第17页 13706 69 532 100 然后划去 所在的列的其他0元素 记作 第18页 13706 69 532 1 0 给只有一个0元素的列的0元素加圈 记 第19页 13706 69 532 1 然后划去 所在的行的其他0元素 记作 第20页 137 6 69 532 1 给最后一个0元素加圈 记 第21页 0001010010000010 可见m n 4 得到最优解 即甲译俄文 乙译日文 丙译英文 丁译德文所需时间最少 Z 28小时 第22页 例6分配问题效率矩阵 第23页 76764 第24页 第25页 从只有一个0元素的行开始 给这个0元素加圈 记 第26页 然后划去 所在的列的其他0元素 记作 第27页 从只有一个0元素的列开始 给这个0元素加圈 记 第28页 然后划去 所在的行的其他0元素 记作 第29页 从只有一个0元素的列开始 给这个0元素加圈 记 第30页 然后划去 所在的行的其他0元素 记作 第31页 从只有一个0元素的列开始 给这个0元素加圈 记 第32页 然后划去 所在的行的其他0元素 记作 第33页 的个数m 4 而n 5 m n 转下一步 第34页 第三步 作最少的直线覆盖所有的0元素 以确定该系数矩阵中能找到最多的独立元素数 对没有 的行 打 对已打 行中所有含0元素的列打 再对打 列中含0元素的行打 重复上述两步 直到得不出新的打 行列为止 对没有打 行画横线 有打 列画纵线 就得到覆盖所有0元素的最少直线数 第35页 对没有 的行 打 第36页 对已打 行中所有含0元素的列打 第37页 再对打 列中含0元素的行打 第38页 对没有打 行画横线 第39页 有打 列画纵线 第40页 第四步 在没有被直线覆盖的部分中找出最小元素 然后在打 行各元素都减去这最小元素 而在打 列中各元素都加上这最小元素 以保证原来0元素不变 这样得到新的系数矩阵 它的最优解和原问题相同 若得到n个独立的0元素 则已经得到最优解 否则回到第三步重复进行 第41页 没有被直线覆盖的最小元素为2 第42页 第43页 在打 行各元素都减去这最小元素2 第44页 在打 列中各元素都加上这最小元素2 第45页 重复第二步 寻找独立0元素 第46页 从只有一个0元素的行开始 给这个0元素加圈 记 第47页 然后划去 所在的列的其他0元素 记作 第48页 从只有一个0元素的行开始 给这个0元素加圈 记 第49页 然后划去 所在的列的其他0元素 记作 第50页 从只有一个0元素的列开始 给这个0元素加圈 记 第51页 然后划去 所在的行的其他0元素 记作 第52页 下面有二种分配方案 第53页 下面有二种分配方案 第一种 第54页 最优解如下 Z 32 第55页 分配问题结果如下 Z 32 第56页 下面有二种分配方案 第二种 第57页 最优解如下 Z 32 第58页 分配问题结果如下 Z 32 第59页 如何安排讲座的日程 使不能出席的学生总数最少 例7 某学校为提高学生的学习兴趣和加强学术讨论的气氛 决定举办生态学 能源 运输和生物工程四个学术讲座 每个讲座每周下午举行一次 经调查 周一至五不能出席某一讲座的学生人数如下 第60页 解 这是一个不平衡的的分配问题 需虚设一个讲座 且Ci 5 0 i 1 2 5 第61页 最优安排为 第62页 指派问题 分配问题 AssignmentP