甲、乙、丙、丁四个人将一份文档翻译为英、日、德、俄四种文字,每人只能翻译一种语言

题库2022-08-02  35

问题 甲、乙、丙、丁四个人将一份文档翻译为英、日、德、俄四种文字,每人只能翻译一种语言。其翻译文字所需时间如下表所示。问应派甲翻译( ),最少的翻译时间为(请作答此空)。A. 26B.28C.30D.32

选项 A. 26
B.28
C.30
D.32

答案 B

解析 指派问题是那些派完成任务效率最高的人去完成任务的问题。该问题可以抽象为,设有n个工作,由 n个人来承担,每个工作只能一人承担,且每个人只能承担一个工作,求总费用最低的指派方案。题目给出的表可转换为费用矩阵,表示某人完成某工作的费用,该矩阵如下:使用匈牙利法步骤如下:第一步:使得费用矩阵各行各列都出现0元素。累计所减总数为2+4+9+7+4+2=28。第二步:进行试指派(画○)方法:从含0元素最少的行或列开始,圈出一个0元素,用○表示,然后划去该○所在的行和列中的其余0元素,用×表示,依次类推。可以知道矩阵(1,4)、(2,2)、(3,1)、(4,3)元素和为0,可以达到最小值。因此,甲、乙、丙、丁分别翻译俄、日、英、德可以达到最优,花费总工时最小为28+1=29。
转载请注明原文地址:https://tihaiku.com/congyezige/2398449.html

最新回复(0)