高项题库-2021下-综合知识第70题(单选题)
分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务多于人数,故规定其中有一个人可兼完成两项任务,其余三人每人完成一项。为了花费时间最少,()应该完成两项任务。
![图片[1]-高项题库-2021下-综合知识-第70题-象网](https://www.xiang.net/static/tikupic/itpm1_202111_1_70.jpg)
A.甲
B.乙
C.丙
D.丁
【答案】B
【解析】
![图片[2]-高项题库-2021下-综合知识-第70题-象网](https://www.xiang.net/static/tikupic/itpm1_202111_1_70_1.jpg)
此题采用匈牙利法解决资源分配问题。具体步骤如下:
第一步:使每行每列至少有一个元素为“0”,每行数字减去该行最小的数值,比如第一行减去25,得到下表。
第二步:使每行每列至少有一个元素为“0”,对没有“0”元素的列进行变换,比如第三列需减去5,得到下表。
第三步:“0”元素所对应的任务就是每个人的最优任务。根据最优任务可以有如下方案:
方案一:甲完成任务1 和任务2,丁完成任务4,乙完成任务3,丙完成任务5 。花费时间=50+23+25+32= 130;
方案二:乙完成任务3 和任务4,丁完成任务1,甲完成任务2,丙完成任务5。花费时间==45+23+25+32= 125
方案三:丙完成任务2 和任务3,甲完成任务1,乙完成任务4,丁完成任务5。花费时间=27+32+25+20+40=144
方案四:丙完成任务2 和任务5,甲完成任务1,丁完成任务4,乙完成任务2 。花费时间==59+25+23+33=140
方案五:丙完成任务3 和任务5,乙完成任务4,丁完成任务1,甲完成任务2。花费时间==64+23+23+25=135
方案六:丁完成任务1 和任务4,甲完成任务2,乙完成任务3,丙完成任务5。花费时间==63+25+25+32=145
综上所述,方案二花费时间最少,故乙完成两项任务,答案选B。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END




