最大化指派问题[精选].ppt

最大化指派问题 运筹学最大化指派问题 医药信息工程学院 信息资源管理教研室 欧 阳 婷 某卫生防疫站准备选拔防疫科、食品科、总务科、检验科的四名科长,几经筛选，仅剩下赵、钱、孙、李四名候选人，根据民主评选的统计结果，他们主持各个科的工作能力（以得分多少来衡量）如下表所示，试从工作能力出发，确定最优选择科长方案。 定理：若效率矩阵[aij]各元素的最大值是a，则效 率矩阵为[aij]的最大化指派问题与效率矩阵为 [a- aij]的最小化指派问题具有相同最优解。 分析问题 建立数学模型 转化为最小化指派问题进行求解 将最优解代入目标函数中求出最优值 【作业】 P356 第二题 谢谢大家！ * * 提出问题 科长 科长 科长 防疫 食品 总务 检验 工作能力（分） 赵 89 85 81 82 钱 80 77 78 76 孙 79 81 80 82 李 83 80 85 80 提出问题 建立数学模型 模型求解 最优解 最优值 模型求解 最大化指派问题求解 最小化指派问题求解 求出最大化指派问题的最优解 找出a 将矩阵 [aij] 转化为 [a-aij] a=max{aij|i，j=1,2,3,4}=89 0 4 8 7 9 12 11 13 10 8 9 7 6 9 4 9 [a-aij]= 0 4 8 7 0 3 2 4 3 1 2 0 2 5 0 5 -0 -9 -7 -4 0 3 8 7 0 2 3 4 3 0 2 0 2 4 0 5 0 1 6 5 0 0 1 2 5 0 2 0 4 5 0 5 （0） 0 （0） （0） 0 √ √ ①在没有（0）的行，标上“√”；②在标上“√”的行中?所在的列，标上“√”；③在标上“√”的列中（0）所在的行标上“√”； 在没有标上“√”的行或已经标上“√”的列，都画上一条直线； √ （0） 0 （0） 0 （0） （0） 最优解为： 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ∴赵、钱、孙、李四人分别担任防疫科、食品科、检验科、总务科科长职务 最优值为：89+77+82+85=333（分） 本讲小结