YSA020205:如何指派运输任务
某物流公司的一份说明
,要分别译成英、日、德、俄、韩五种文字(分别称为任务A,B,C,D,E),交甲、乙、丙、丁、戊去完成,每人完成一种。已知各人完成不同任务所需时间(小时数)如
1-11所示。问如何分派,才能使总用时量最少?
表1-11 完成任务时数
任务
人
A
B
C
D
E
甲
乙
丙
丁
戊
5
3
5
6
7
6
4
5
7
4
8
6
7
5
6
4
6
9
7
2
5
1
8
6
8
解:该问题的价值系数矩阵为
按步骤(一),得:
-4
-1
-5
-5
-2
因C 2每列已含0元素,不必对列进行简约化。
按步骤(三),得:
覆盖所有0元的最少直线数m = 4, 4<5, 按步骤(四)中m
方案,得:
+1 +1
-1
-1
-1
回到步骤(三):
覆盖所有0元的最少直线数m =5=n,回到步骤(四)中m=n方案,得:
(找0元的顺序之一用中括号里的数字标出)
回顾
故在该分配问题中,最优目标函数值为5+1+5+5+2=18;即让甲去完成任务A,乙去完成任务E,丙去完成任务B,丁去完成任务C,戊去完成任务D,这样可使总用时量最少(18时)。