甲、乙、丙、丁四个任务分配在A、B、c、D四台机器上执行，每台机器执行一个任务，所需的成本(单位：百元)如下表所示。适当分配使总成本最低的最优方案中，任务乙应由机器________执行。

admin2023-02-21 33

问题甲、乙、丙、丁四个任务分配在A、B、c、D四台机器上执行，每台机器执行一个任务，所需的成本(单位：百元)如下表所示。适当分配使总成本最低的最优方案中，任务乙应由机器________执行。

选项 A、A
B、B
C、C
D、D

答案C

解析本题考查应用数学一运筹学-分配(指派)问题的基础知识。本题的实质就是要求在4×4矩阵中找出四个元素，分别位于不同行、不同列，使其和达到最小值。显然，任一行(或列)各元素都减(或加)一常数后，并不会影响最优解的位置，只是目标值(分配方案的各项总和)也减(或加)了这一常数。我们可以利用这一性质使矩阵更多的元素变成0，其他元素保持正，以利于求解。

对该矩阵，从第1、3行可以看出，并不存在全0分配。现在来检查对该矩阵是否有总和为1的分配。显然，第1行必须选元素(1，1)，第3行只能选元素(3,2)。从第4列看，只能选(4，4)，因此，最后一个必须选(2,3)。这样得到的分配方案中，位于(1，1)、(2，3)、(3，2)、(4，4)的元素之和为1，肯定是最小的。因此，分配甲、乙、丙、丁分别在机器A、C、B、D上能达到最低的总成本为20+1=21百元。本题也可用试验法解决。

转载请注明原文地址:https://kaotiyun.com/show/d10D777K

本试题收录于：系统分析师上午综合知识考试题库软考高级分类