最大化指派问题

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