2. 计算机
  3. 甲、乙、丙、丁四人加工A、B、C、D四种工件所需工时如下表所示。指派每人加工一种工件，四人加工四种工件其总工时最短的最优方案中，工件B应由_________加工。

甲、乙、丙、丁四人加工A、B、C、D四种工件所需工时如下表所示。指派每人加工一种工件，四人加工四种工件其总工时最短的最优方案中，工件B应由_________加工。

admin2016-11-11  34
问题 甲、乙、丙、丁四人加工A、B、C、D四种工件所需工时如下表所示。指派每人加工一种工件，四人加工四种工件其总工时最短的最优方案中，工件B应由_________加工。
选项 A、甲
B、乙
C、丙
D、丁
答案D
解析 本题考查数学(运筹学)应用的能力。
    本题属于指派问题：要求在4×4矩阵中找出四个元素，分别位于不同行，不同列，使其和达到最小值。
    显然，任一行(或列)各元素都减(或加)一常数后，并不会影响最优解的位置，只是目标值(指派方案的各项总和)也减(或加)了这一常数。
    我们可以利用这一性质使矩阵更多的元素变成0，其他元素保持正，以利于求解。

    对该矩阵，并不存在全0指派。位于(1，3)、(2，1)、(3，4)、(4，2)的元素之和为1是最小的。因此，分配甲、乙、丙、丁分别加工C、A、D、B能达到最少的总工时28+1=29。
    更进一步，再在第三行上都加1，在第2、4列上都减1，可得到更多的0元素：
，这样就断定上述位置是唯一的全0(最优)指派。
转载请注明原文地址:https://www.kaotiyun.com/show/sMQZ777K
本试题收录于： 系统架构师上午综合知识考试题库软考高级分类
0

系统架构师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)