运筹学 最大化指派问题 医药信息工程学院 信息资源管理教研室 欧 阳 婷 提出问题 科 长 科 长 科 长 某卫生防疫站准备选拔防疫科、食品科、总务科 、检验科的四名科长,几经筛选，仅剩下赵、钱、孙 、李四名候选人，根据民主评选的统计结果，他们主 持各个科的工作能力（以得分多少来衡量）如下表所 示，试从工作能力出发，确定最优选择科长方案。 防疫 食品 总务检验 工作能力（分） 赵89 85 8182 钱80 77 7876 孙79 81 8082 李83 80 8580 提出问题 建立数学模型 模型求解 最优解 最优值 定理：若效率矩阵aij各元素的最大值是a，则效 率矩阵为aij的最大化指派问题与效率矩阵为 a- aij的最小化指派问题具有相同最优解。 模型求解 最大化指派问题求解 最小化指派问题求解 求出最大化指派问题 的最优解 找出a 将矩 阵 aij 转化 为 a-aij a=maxaij|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 00 0 1 00 0 0 01 0 0 10 赵、钱、孙、李四 人分别担任防疫科、 食品科、检验科、总 务科科长职务 最优值为：89+77+82+85=333（分） 本讲小结 分析问题 建立数学模型 转化为最小化指派问题进行求解 将最优解代入目标函数中求出最优值 【作业】 P356 第二题 谢谢大家！