整数规划2-指派问题.ppt

指派问题(assignment problem)
1、指派问题的标准形式及其数学模型:

指派问题的标准形式(以人和事为例)是:
有 n 个人和 n 件事,已知第 i 人做第 j 事的费用为 Cij(i,j = 1,2,…,n),要求确定人和事之间的一一对应的指派方案,使完成这件事的总费用最少。如:
任务
人员
A
B
C
D
甲
乙
丙
丁
2
10
9
7
15
4
14
8
13
14
16
11
4
15
13
9
1
指派问题的标准形式,令:
1 当指派第 i 人完成第 j 项任务
0 当不指派第 i 人完成第 j 项任务
xij =
min z = ∑∑cijxij
∑xij = 1, j = 1,2,…,n
∑xij = 1, i = 1,2,…,n
xij = 1 或 0
2
匈牙利解法:
标准的指派问题是一类特殊的 0-1 整数规划问题,可以用多种相应的解法来求解,如整数规划、0-1规划或运输问题的解法。但是,这些方法都没有充分利用指派问题的特殊性质来有效减少计算量。1955年,库恩()利用匈牙利数学家康尼格(önig)的关于矩阵中独立零元素的定理,提出了指派问题的一种解法,由此,习惯上称之为匈牙利解法。
2、标准形式指派问题的求解
3
匈牙利解法:
匈牙利解法的关键是利用了指派问题最优解的如下性质:
若从指派问题的系数矩阵 C = ( cij )n×n 的某行(或某列)各元素分别减去一个常数 k ,得到一个新的系数矩阵C’= ( c’ij ),则以 C 和 C’为系数矩阵的两个指派问题有相同的最优解。
匈牙利解法的一般步骤:
步骤一: 变换系数矩阵。使其每行及每列至少有一个零元素,同
时不出现负元素。
步骤二: 进行试指派,即确定独立零元素。
步骤三: 继续变换系数矩阵,然后返回步骤二。
4
匈牙利解法的一般步骤:
以上例说明步骤
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
0 13 11 2
6 0 10 11
0 5 7 4
0 1 4 2
2
4
9
7
min
( cij )=
5
匈牙利解法的一般步骤:
以上例说明步骤
0 13 11 2
6 0 10 11
0 5 7 4
0 1 4 2
0 0 4 2
min
0 13 7 0
6 0 6 9
0 5 3 2
0 1 0 0
= ( c’ij )
6
匈牙利解法的一般步骤:
以上例说明步骤
0 13 7 0
6 0 6 9
0 5 3 2
0 1 0 0
此时加圈 0 元素的个数 m = n = 4,所以得到最优解
7
匈牙利解法的一般步骤:
以上例说明步骤
0 0 0 1
0 1 0 0
1 0 0 0
0 0 1 0
( xij )=
8
匈牙利解法的一般步骤:
例2:
任务
人员
A
B
C
D
E
甲
乙
丙
丁
戊
12
8
7
15
4
7
9
17
14
10
9
6
12
6
7
7
6
14
6
10
9
6
9
10
9
9
匈牙利解法的一般步骤:
12 7 9 7 9
8 9 6 6 6
7 17 12 14 9
15 14 6 6 10
4 10 7 10 9
7
6
7
6
4
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5
10