列表

详情


分配甲乙丙丁四人去完成5项任务。每人完成各项任务时间如表所示,由于任务多于人数,故其中有1人可兼完成2项任务,其余3人每人完成一项。为了花费时间最少,(  )应该完成两项任务。

A. 甲

B. 乙

C. 丙

D. 丁

参考答案: B

详细解析:

任务指派问题,使用匈牙利算法。

假设增加一个人戊完成各项工作的时间取任务1、任务2、任务3、任务4、任务5最小值。

得效率矩阵为:

  任务1 任务2  任务3 任务4 任务5

甲  25   25  31  43  33

乙  38   33  25  20  28

丙  41  27  32  45  32

丁  23  37  35  23  40

戊  23   25  25 20   28

每一行元素减去该行的最小元素;得到如下矩阵:

0    0    6  18  8

18  13  5   0   8

14   0   5  18  5

0   14  12  0  17

3    5    5   0    8

没有0的列,减去该列的最小值:

0    0    1  18  3

18  13  0   0   3

14   0   0  18  0

0   14  12  0  12

3    5    0   0    3

找独立的【0】元素,

     任务1 任务2  任务3 任务4 任务5

甲   0     (0)   1     18   3

乙   18  13    (0)       3

丙   14   0     0     18    (0)

   (0)  14   7      0    12

戊   3     5     0      (0)     3

指派结果:

甲----任务2-----25;

乙-----任务3、任务4---25、20

丙----任务5----32

丁----任务1---23

最少需要的时间为125。

故本题选B。


上一题