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

题库2022-08-02 97

问题甲、乙、丙、丁四个人将一份文档翻译为英、日、德、俄四种文字，每人只能翻译一种语言。其翻译文字所需时间如下表所示。

问应派甲翻译（），最少的翻译时间为（请作答此空）。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://www.tihaiku.com/congyezige/2398449.html

高级网络规划设计师

相关试题推荐

随机试题

最新回复(0)