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

admin2016-11-11  23

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

选项 A、甲
B、乙
C、丙
D、丁

答案D

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

    对该矩阵,并不存在全0指派。位于(1,3)、(2,1)、(3,4)、(4,2)的元素之和为1是最小的。因此,分配甲、乙、丙、丁分别加工C、A、D、B能达到最少的总工时28+1=29。
    更进一步,再在第三行上都加1,在第2、4列上都减1,可得到更多的0元素:,这样就断定上述位置是唯一的全0(最优)指派。
转载请注明原文地址:https://kaotiyun.com/show/UCQZ777K
0

最新回复(0)