运筹学 指派问题 PPT课件.ppt

运筹学__指派问题_PPT课件第五节指派问题
本节内容的安排
指派问题的数学模型
匈牙利算法
在实际中经常会遇到这样的问题,
有n 项不同的任务,
需要n 个人分别完成其中的一项,
但由于任务的性质和各人的专长不同,
因此各人去完成不同的任务的效率
(或花费的时间或费用)也就不同。
于是产生了一个问题:
应指派哪个人去完成哪项任务,
使完成 n 项任务的总效率最高(或所需时间最少),
这类问题称为指派问题或分派问题。
例7: 有一份中文说明书,
要分别译成英、日、德、俄四种文字,
分别记作E 、 J 、 G 、 R ,交与甲、乙、丙、丁四个人去完成.
因个人专长不同,
他们完成翻译不同语种的说明书所需的时间(h)如表所示.
应如何指派,使四个人分别完成这四项任务总时间为最小?
任务
人员
E
J
G
R
甲
2
15
13
4
乙
10
4
14
15
丙
9
14
16
13
丁
7
8
11
9
一、指派问题的数学模型
(一)举例
这是一个标准型的指派问题
类似有:有n项加工任务,怎样指派到n台机床上分别完成;
有n条航线,怎样指定n艘船分别去航行….. 等。
对应每个指派问题,需有类似上表那样的数表,
表中数据称为效率矩阵或系数矩阵,
其元素cij>0(i,j=1,2,…n),
表示指派第i人去完成第j 项任务时的效率(或时间、成本等)
效率矩阵
或
系数矩阵
C=(cij)n×n=
c11 c12 … c1n
c21 c22 … c2n
………………
1 … cnn
C=(cij )4×4=
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
则该指派问题的数学模型为:
求解题时通常需引入0-1变量:
∑xij=1 (i=1,2,3,4)
表示第i人只能完成一项任务
xij=1 (j=1,2,3,4)
表示第j 项任务只能由一人去完成。
满足约束条件的解称为可行解,
可写成矩阵形式,叫作解矩阵。
可以看到指派问题既是0-1 规划问题,也是运输问题,
所以也可用整数规划,0-1 规划,
或运输问题的解法去求解。
(二)指派问题的数学模型
1. 指派问题的一般提法:
设m个人被指派去做m件工作,
规定每个人只做一件工作,
每件工作只有一个人去做。
已知第i个人去做第j 件工作的的效率( 时间或费用)
为cij (i=…m;j=…m) ,并假设cij ≥0。
问应如何指派才能使总效率最高或总时间﹑
总费用最低?