丁
86 90 80 88
x14 x24 x34 x44 1 xij 0或1，i、j 1,2,3,4
●求解指派问题的方法：匈牙利算法
匈牙利算法是匈牙利数学家克尼格（Konig）证明了下面两个基本 定理，为计算分配问题奠定了基础。因此，基于两个定理基础上建 立起来的解分配问题的计算方法被称为匈牙利法。
ij
【例4.9】某人事部门拟招聘4人任职4项工作，对他们综合考评 的 得分如下表（满分100分），如何安排工作使总分最高。
甲 85 92 73 90
乙 C＝丙
95 82
87 83
78 79
95 90
丁 86 90 80 88
【解】M＝95，令 C (95 cij )
10 3 22 5
C
＝
0
8 17 0
0
0
0
0
3 0 2 1 2 M 0 7 0 2 5 1 0 0 0 0
0 1 0 0 X＝0 0 1 0
1 0 0 0 0 0 0 1
88
数学模型如下：
min Z 85x11 92x12 73x13 90x14 95x21 87x22
78x23 95x24 82x31 83x32 79x33 90x34
86x41 90x42 80x43 88x44
x11 x12 x13 x14 1
x21 x22 x23 x24 1
【定理4.1 】如果从分配问题效率矩阵[cij]的每一行元素中分别减去 （或加上）一个常数ui（被称为该行的位势），从每一列分别减去 （或加上）一个常数vj（称为该列的位势），得到一个新的效率矩
阵[bij]，若其中bij=cij－ui－vj,则[bij]的最优解等价于[cij]的最优解。这
里cij、bij均非负。
工作 A
B
C
D
x31 x32 x33 x34 1
人员
甲
x41 x42 x43 x44 1
乙
x11 x21 x31 x41 1
x12 x22 x32 x42 1
丙
85 92 73 90 95 87 78 95 82 83 79 90
x13 x23 x33 x43 1
位置
一
二
三
四
机器
A
13
10
12
11
B
15
--
13
20
C
5
7
10
6
解：1）在（B，二）处添上一个很大的数M，以排除机器B安 装在二号位置的可能。
2）在第四行虚设一行。
13 10 12 11
C＝15 M 13 20 5 7 10 6
0
0
0
0
13 10 12 11
C＝15 M 13 20 5 7 10 6
● 求最大值的指派问题
匈牙利法的条件是：模型求最小值、效率cij≥0
设C=(cij)m×m 对应的模型是求最大值
将其变换为求最小值
令
M
max i, j
cij
max z
cij xij
ij
C (M cij )
则
min w
cij xij
ij
与
max z
cij xij 的最优解相同。
管理优化之—
指派问题
1 指派问题及其数学模型
【例1 】指派问题或分配问题。人事部门欲安排四人到四个不同岗 位工作，每个岗位只能一个人。经考核四人在不同工作岗位完成的 时间如下表所示，如何安排他们的工作使总时间最少。
工作 A
B
C
D
人员
甲
85
92
73
90
乙
95
87
78
95
丙
82
83
79
90
丁
86
90
80
【定理4.2 】 若矩阵A的元素可分成“ 0”与非“ 0”两部分，则覆盖 “ 0”元素的最少直线数等于位于不同行不同列的“ 0”元素（称为 独立元素）的最大个数。
如果最少直线数等于m，则存在m个独立的“ 0”元素，令这些零元 素对应的xij等于1，其余变量等于0，得到最优解。定理4.1告诉我们 如何将效率表中的元素转换为有零元素，定理4.2告诉我们效率表中 有多少个独立的“ 0”元素。
0 0
0 1
0 0 1 0
即甲安排做第二项工作、乙做第一项、丙做第四项、丁做第三项。 总分为：Z＝92＋95＋90＋80＝357
某工厂订购了3台机器(A、B、C），有4个位置可供机器安装，但B 机器不能安装在第二号位置。由于这4个安装位置离工厂中心的远
近不同，所需要的运送费用也就不同，见下表。问这些机器安装在 哪几个位置合适，可使总的运送费用达到最小。
13 12 16 5
9
5 15 7
用匈牙利法求解：
10 3 22 5
C＝
0
8 17 0
13 12 16 5
9
5
15 7
7 0 19 2 C＝0 8 17 0
8 7 11 0 4 0 10 2
7 0 9 2 C＝0 8 7 ×0
8 7 1 0 4 ×0 0 2
0 1 0 0
最优解：
X＝1 0
0 0
【例4.8 】已知四人分别完成四项工作所需时间如下表，求最优分 配方案。
85 92 73 90 C＝95 87 78 95
82 83 79 90 86 90 80 88
工作 A
B
C
D
人员
1
X＝
1
1
1
甲
85
92
73
90
乙
95
87
78
95
丙
82
83
79
90
最优分配
丁
86
90
80
88
甲→C 乙→B 丙→A 丁→D
● 不平衡的指派问题
1．当人数m小于工作数n时，加上n－m个人，例如
15 20 10 9
6
5
4
0 9 9
6
5
4
7
4
10 13 16 17 10
0
0
0
0
0
6 11 1 0
2 1 0 3
0 3 6 7
×0 0 ×0 ×0
0 0 0 1
X＝0 0 1 0 1 0 0 0 0 1 0 0