当前位置:首页 >> 数学 >>

匈牙利指派问题


匈牙利指派
主讲人:陈元安 电话:15036669717 E-mail:chya0370@163.com

1

一、指派问题的背景及意义
数学建模是指根据需要针对实际问题组 建数学模型的过程。也就是对某一实际问题, 经过抽象、简化、明确变量和参数,并依据 某种“规律” 建立变量和参数间的一个明确 的数学关系(即数学模型),然后求解该数学问 题的过程。数学模型的过程不仅要进行演绎 推理而且还要对复杂的现实进行总结、归纳 和提炼,这是一个归纳总结与演绎推理相结 合的过程。
2

?

建模时.必须要对现实问题进行去粗取精、 去伪存真、归纳、加工过程,但建模时究竟 保留什么因素,忽略什么因素,并没有一定 的范式,这要根据建模者对实际问题的理解、 研究的目的及其数学背景来完成这个过程, 应该说这是一个创造性的过程。而且不同的 建模者针对同一实际问题完全可以得到不同 的数学模型。

3

?

在现实生活中,经常会遇到把几个任务分派 给不同的对象去完成,由于每个对象的条件 不同,完成任务的效率和效益亦不同,指派 问题的目标就是如何分派使所消耗的总资源 最少(或总体效益最优)。最常见的应用有:给 工人分派工作,给车辆分配道路,给工件分 配机床等等。同时许多网络问题(如旅行问题、 任务分配问题、运输问题等)都可以演化成指 派问题来解决。利用数学建模思想,可以很 好地解决指派问题,本次课通过例子,介绍 指派问题的匈牙利解法的实际应用。
4

?

指派问题又称分配问题,其用途非常广泛, 比如某公司指派n个人去做n件事,各人做不 同的一件事,如何安排人员使得总费用最少? 若考虑每个职工对工作的效率(任务有难易, 人员素质有高低)(如熟练程度等),怎样安 排会使总效率达到最大?这些都是一个企业 经营管理者必须考虑的问题,所以该问题有 重要的应用价值.
5

哪个人应该负责哪项 工作?

6

?

?

虽然指派问题可以用0-1规划问题来解,设X(I,J)是 0-1变量, 用X(I,J)=1表示第I个人做第J件事, X(I,J)=0表示第I个人不做第J件事. 设非负矩阵C(I, J)表示第I个人做第J件事的费用, 但是由于有N^2个0-1变量, 当N很大时,用完全枚举 法解题几乎是不可能的. 而已有的0-1规划都是用隐 枚举法做的,计算量较大. 对于指派问题这种特殊 的0-1规划,有一个有效的方法——匈牙利算法,是 1955年W. W. Kuhn利用匈牙利数学家D.K?nig的二 部图G的最大匹配的大小等于G的最小顶点覆盖的 大小的定理提出的一种算法,这种算法是多项式算 法,
7

匈牙利算法的基本原理是基于以下两个定理. ? 定理1 设C=(Cij)n×n是指派问题的效益矩阵, 若将C中的任一行(或任一列)减去该行 (或该列)中的最小元素,得到新的效率矩 阵C’,则C’对应的新的指派问题与原指派问 题有相同的最优解. ? 定理2 效率矩阵C中独立的0元素的最多个数 等于覆盖所有0元素的最少直线数. 当独立零 元素的个数等于矩阵的阶数时就得到最优解.
?
8

1、指派问题的数学模型
设有n个工作,要由 n个人来 承担,每个工作只能由一个人 承担,且每个人只能承担一个 工作。cij表示第i个人做第j件 事的费用,求总费用最低的指 派方案。
?1 第i个人做第j 人件事 ? x 解:ij ? ? ? 0 第i个人不做第j 人件事 ?
1 1 c11 2 c 21 …? i c i1 …? n c n1 2
c12 c 22 ? ci 2 ? cn 2


? ? ? ? ? ?

j
c1 j c2 j ? c ij ? c nj


? ? ? ? ? ?

n
c1 n c2n ? c in ? c nn

指派问题模型:
min Z ?

??c
j i

ij

x ij

i=1,2, …,n; j=1,2, …,n

Z表示总费用

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? i=1,2, …,n ? s.t ? x1 j ? x 2 j ? ? ? xij ? ? ? x nj ? 1 ? j=1,2, …,n ? x ij ? 0,1 i ? 1,2, ? , n; j ? 1,2, ? ,9n ?

min Z ?

??c
j i

ij

x ij ? c11 x11 ? c12 x12 ? ? ? c1 n x1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nn

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? s .t ? ? x1 j ? x 2 j ? ? ? xij ? ? ? x nj ? 1 ? j=1,2, …,n

? x11 ? x12 ? ? ? x1 j ? ? ? x1n ? 1 ?x ? x ? ? ? x ? ? ? x ? 1 21 22 2j 2n ? ?? ? x n1 ? x n 2 ? ? ? x nj ? ? ? x nn ? 1 s.t ? ? x11 ? x 21 ? ? ? x i1 ? ? ? x n1 ? 1 ? x12 ? x 22 ? ? ? x i 2 ? ? ? x n 2 ? 1 ?? ? x1n ? x 2 n ? ? ? x in ? ? ? x nn ? 1 ?

当n=4时, 有16变量,8个约束方程
10

例:现有4份工作,4个人应聘,由 Z表示总费用 于各人技术专长不同,他们承担 max Z ? 3 x11 ? 5 x12 ? 4 x13 ? 5 x14 各项工作所需费用如下表所示, ? 6 x 21 ? 7 x 22 ? 6 x 23 ? 8 x 24 且规定每人只能做一项工作,每 ? 8 x 31 ? 9 x 32 ? 8 x 33 ? 10 x 34 一项工作只能由一人承担,试求 ? 10 x 41 ? 10 x 42 ? 9 x 43 ? 11 x 44 使总费用最小的分派方案。 ? x 11 ? x 12 ? x 13 ? x 14 ? 1
工作

人 1 2 3 4

1 3 6 8 10

2 5 7 9 10

3 4 4 5 6 8 8 10 9 11

解: ? 1 第i人做第j 件事
i=1,2, 3,4; j=1,2, 3,4

x ij ? ? ? 0 第i人不做第j 件事

?x ? x ? x ? x ?1 21 22 23 24 ? ? x 31 ? x 32 ? x 33 ? x 34 ? 1 ? x 41 ? x 42 ? x 43 ? x 44 ? 1 ?x ? x ? x ? x ?1 21 31 41 ? 11 s .t ? x ? x ? x ? x ? 1 12 22 32 42 ? ? x13 ? x 23 ? x 33 ? x 43 ? 1 ? x14 ? x 24 ? x 34 ? x 44 ? 1 ? x ? 0 ,1 ij 11 ? i ? 1, 2 , ? , n ? j ? 1, 2 , ? , n ?

2、费用矩阵
设有n个工作,要由 n个人来 承担,每个工作只能由一个人 承担,且每个人只能承担一个 工作。cij表示第i个人做第j件 事的费用,求总费用最低的指 派方案。
? c 11 ? c 取 C ? ? 21 ?? ?c ? n1 c 12 c 22 ? cn2 ? ? ? ? c1n ? ? c2n ? ?? c nn ? ?
1 1 c11 2 c 21 …? i c i1 …? n c n1 2
c12 c 22 ? ci 2 ? cn 2


? ? ? ? ? ?

j
c1 j c2 j ? c ij ? c nj


? ? ? ? ? ?

n
c1 n c2n ? c in ? c nn

费用矩阵

cij表示第i个人做第j件事的费用

12

例:现有4份工作,4个人应聘,由于个人的技术专长不 同,他们承担各项工作所需费用如下表所示,且规定 每人只能做一项工作,每一项工作只能由一个人承担, 试求使总费用最小的分派方案。
工作

人 1 2 3 4
?1 ? ?0 设C ? ?1 ? ?6 ? ?1

1
3 6 8 10
2 2 0 0 3 3 3 0 5 5

2
5 7 9 10
4 5 5 3 7

3 4
4 5 6 8 8 10 9 11
5? ? 6? 6? ? 9? ? 0?

费用矩阵

? 3 ? ? 6 C ?? 8 ? ? 10 ?

5 7 9 10

4 6 8 9

5? ? 8? 10 ? ? 11 ? ?

对应一个5个人5个工作的指派问题 第2个人做第4个工作的费用 5 第4个人做第2个工作的费用 0
13

3、匈牙利法
定理:在费用矩阵C=(cij)的任一行(列)中 减去一个常数或加上一个常数不改变本 问题的最优解。
? c11 ? c 21 ?? C ?? ? c i1 ?? ?c ? n1 c12 c 22 ? ci2 cn2 ? ? ? ? c1n ? ? c2n ? ? c in ? -b ? c nn ? ?

b ? min ?c i1 , c i 2 , ? , c in ?

c12 ? c11 ? c 21 c 22 ? ? ? C ?? ? c i1 ? b c i 2 ? b ? ? ? c cn2 ? n1

c1 n ? ? c2n ? ? ? c in ? b ? ? ? c nn ? ? ? ?

n个人n个工作 的指派问题1

n个人n个工作 的指派问题2

14

? c 11 ? c 21 ?? C ?? ? c i1 ?? ?c ? n1

c 12 c 22 ? ci2 cn2

? ? ? ?

c1n ? ? c2n ? ? c in ? ? c nn ? ?

-b

? c11 ? c 21 ? ? C ?? ? c i1 ? b ? ? ? c ? n1

c12 ? c1 n ? ? c2n c 22 ? ? ? ? c i 2 ? b ? c in ? b ? cn2 ? c nn ? ? ?

min Z ? c11 x11 ? c12 x12 ? ? ? c1 n x1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i1 x i1 ? c i 2 x i 2 ? ? ? c in x in ? ? c n1 x n1 ? c n 2 x n 2 ? ? ? c nn x nn

min Z ? c11 x11 ? c12 x12 ? ? ? c1 n x1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? ( c i1 ? b ) x i1 ? ( c i 2 ? b ) x i 2 ? ? ? ( c in ? b ) x in ?? ? c n1 x n1 ? c n 2 x n 2 ? ? ? c nn x nn

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? ? s.t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0,1 i ? 1, 2, ? , n; j ? 1, 2, ? , n ? ij

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? ? s.t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0,1 i ? 1, 2, ? , n; j ? 1, 2, ? , n ? ij

15

min Z ? c11 x11 ? c12 x12 ? ? ? c1 n x1 n

? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? ( c i1 ? b ) x i1 ? ( c i 2 ? b ) x i 2 ? ? ? ( c in ? b ) x in ?? ? c n1 x n1 ? c n 2 x n 2 ? ? ? c nn x nn

? c11 x11 ? c12 x12 ? ? ? c1 n x1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i1 x i1 ? c i 2 x i 2 ? ? ? c in x in ?? ? c n1 x n1 ? c n 2 x n 2 ? ? ? c nn x nn ? b ( x i1 ? x i 2 ? ? ? x in )
? c11 x11 ? c12 x12 ? ? ? c1 n x1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i1 x i1 ? c i 2 x i 2 ? ? ? c in x in ?? ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nn ? b

16

? c 11 ? c 21 ?? C ?? ? c i1 ?? ?c ? n1

c 12 c 22 ? ci2 cn2

? ? ? ?

c1n ? ? c2n ? ? c in ? ? c nn ? ?

-b

? c11 ? c 21 ? ? C ?? ? c i1 ? b ? ? ? c ? n1

c12 ? c1 n ? ? c2n c 22 ? ? ? ? c i 2 ? b ? c in ? b ? cn2 ? c nn ? ? ?

? c11 x11 ? c12 x12 ? ? ? c1 n x1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i1 x i1 ? c i 2 x i 2 ? ? ? c in x in ? ? c n1 x n1 ? c n 2 x n 2 ? ? ? c nn x nn

min Z ? Z ? b

min Z ? Z ? b ? c11 x11 ? c12 x12 ? ? ? c1 n x1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i1 x i1 ? c i 2 x i 2 ? ? ? c in x in ?? ? c n1 x n1 ? c n 2 x n 2 ? ? ? c nn x nn ? b

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? ? s.t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0,1 i ? 1, 2, ? , n; j ? 1, 2, ? , n ? ij

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? i=1,2, …,n ? s.t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n 17 ? x ? 0,1 i ? 1, 2, ? , n; j ? 1, 2, ? , n ? ij

? c 11 ? c 21 ?? C ? ? ? c i1 ?? ?c ? n1

c 12 c 22 ? ci2 cn2

? ? ? ?

c1n ? ? c2n ? ? c in ? ? c nn ? ?

-b

? c11 ? c 21 ? ? C ?? ? c i1 ? b ? ? ? c ? n1

c12 ? c1 n ? ? c2n c 22 ? ? ? ? c i 2 ? b ? c in ? b ? cn2 ? c nn ? ? ?

min Z? Z ? b

min Z

? Z ?b

若 X 0 是 min Z的最优解 ,则 X 0 也是 min Z 的最优解

若 Z 0 是 min Z的最优值 ,则若 Z 0 ? b 是 min Z 的最优值

任务:对C的行和列减去某个常数, 将C化的尽可能简单, 简单到可一眼看出该问题的最优解
18

二.指派问题的数学模型
在生活中经常遇到这样的问题,某单位需完成n 项任务,恰好有n 个人可承担这些任务。由于每人的 专长不同,各人完成任务(或所费时间)的效率也 不同。于是产生应指派哪个人去完成哪项任务 使 完成n 项任务的总效率最高(或所需总时间最小)。 这 类 问 题 称 为 指 派 问 题 或 分 配 问 题 ( Assignment problem)。

19

先通过下面的引例了解指派问题的特征
引例:有一份中文说明书,将译成英、日、德、俄 四种文字。分别记作E、J、G、R。现有甲、乙、丙、 丁四人。他们将中文说明书翻译成不同语种的说明 书所需时间如下表所示。问应指派何人去完成何工 作,使所需总时间最少?
任务 人员 甲 乙 丙 丁 E J G R

6 4 3 5

7 5 1 9

11 9 10 8

2 8 4 2
20

类似有:有n 项加工任务,怎样指派到n 台机床 上分别完成任务的问题;有n条航线,怎样指定n艘 船去航行问题…等等,对应每个指派问题,需有类 似上表那样的数表,称为效率矩阵或系数矩阵,其 元素Cij>0(i,j=1,2…,n)表示指派第i人去完成 第j项任务时的效率(或时间、成本等)。解题时需 引入变量xij;其取值只能是1或0,并令:

21

?1 当 指 派 第 i个 人 去 完 成 第 j 项 任 务 x ij ? ? ? 0 当 不 指 派 第 i个 人 去 完 成 第 j 项 任 务

当问题要求极小化时数学模型是: Min z= ? ? c ij x ij
i j

① ② ③ ④
22

?
i

x ij ? 1
ij

,j=1,2?n

?x
j

? 1 ,i=1,2?n

xij=1 或 0

约束条件②说明第j项任务只能由1人去完成;约束 条件③说明第i人只能完成1项任务。满足约束条件的可 行解也可写成表格或矩阵形式,称为解矩阵。如引例 的一个可行解矩阵是

?0 1 0 0? ? ? 0 0 1 0 ? ( x ij ) ? ? ?1 0 0 0 ? ? ? ? 0 0 0 1?
显然,这是最优。解矩阵中各行各列的元素 之和都是1。

23

三.指派问题解的特性
指派问题是运输问题的特例,也是线性规划 (0 – 1规划)的特例,当然可用求运输问题、整 数规划或0-1规划的解法去求解。这就如同用单纯 形法求运输问题一样是不合算的。利用指派问题 的特点可有更简便的解法。这就是匈牙利解法:

即系数矩阵中独立 0 元素的最多个数等于能 覆盖所有 0 元素的最少直线数。
24

指派问题的最优解的性质:若从系数矩阵 (cij )的一行(列)各元素中分别减去该行(列) 的最小元素,得到新矩阵(bij ),那么以(bij ) 为系数矩阵求得最优解和用原系数矩阵求得最优 解相同。 利用这个性质,可使原系数矩阵变为含有很 多0元素的新系数矩阵,而最优解保持不变。

在系数矩阵(bij )中,我们关心位于不同行 不同列的0元素。简称为独立的0元素。
25

四、匈牙利法的基本思路:
对费用矩阵C的行和列减去某个常数,将C化成 有n 个位于不同行不同列的零元素,令这些零元 素对应的变量取1,其余变量取零,既得指派问 题的最优解

26

例:有一份说明书要分别译成英、 工作 日、德、俄四种文字,现交给甲、 人 甲 乙丙、丁四个人去完成,每人完 乙 成一种。由于个人的专长不同, 丙 翻译成不同文字所需的时间(小 丁 时数)如右表,问应派哪个人去 完成哪个任务,可使总花费时间 最少?
? ? ? -4 ? 10 4 14 15 ? 丙翻译英文 ?6 0 C ?? ? -9 ? ? 9 14 16 13 0 5 ? ? ? ? 7 8 11 9 ? -7 总费用:28小时 ? 0 1 ? ? ?

英 日 德 俄 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9

最优方案: 4 ? -2 甲翻译俄文 ,乙翻译日文 ? 2 15 13 ? 0 13 ? 0 13 11 2 ?

? ? 10 11 ? ,丁翻译德文 ?6 0 ? ? ?0 5 7 4 ? ? ?0 1 ? 4 2? ? -4 -2

7 6 3 0

0? ? 9? 2? ? 0? ?

?
27

最优解 x14 ? 1 x 22 ? 1, x 31 ? 1, x 43 ? 1 , 其余 x ij ? 0 ,

? 2 15 13 4 ? -2 ? 0 13 11 2 ? ?0 ? ? ? ? ? -4 ? 10 4 14 15 ? ? 6 0 10 11 ? ?6 C ?? ?? ?? 9 14 16 13 ? -9 0 5 7 4? 0 ? ? ? ? ? ? 7 8 11 9 ? -7 ?0 1 4 2 ? ?0 ? ? ? ? ?

? 13
0 5 1

7 6 3 0

-4

-2

?

?

0? ? 9? 2? ? 0? ?

最优解的取法: 从含0元素最少的行或列开始,圈出一个0元 素,用 ○表示,然后划去该○所在的行和列 中的其余0元素,用×表示,依次类推,若能 得到n个○,则得最优解X0
最优解 x14 ? 1 x 22 ? 1, x 31 ? 1, x 43 ? 1 , 其余 x ij ? 0 ,

最优值: Z ?

??c
j ?1 i ?1

4

4

ij

x ij ? c14 ? c 22 ? c 31 ? c 43 ? 28

28

例:求费用矩阵为右表的 指派问题的最优解

工作



A B C 12 8 7 15 4 7 9 17 14 10 9 6 12 6 7

D 7 6 14 6 10

E 9 6 12 10 6

甲 乙 丙 丁 戊

? 12 ? ?8 C ??7 ? ? 15 ? ?4

7 9 17 14 10

9 6 12 6 7

7 6 14 6 10

9 ? -7 ? 6 ? -6 12 ? -7 ? 10 ? -6 ? 6 ? -4

?5 0 ? 2 3 ? ? ? 0 10 ?9 8 ?0 6 ?

?

0 ? 2 ?? 0 ?? 0 ? 7 5? 0 ? 4 ?? 6 2 2 0 5 0 3 ?

得4个○,且不存在没打×的0

修改方法!

29

对n阶费用矩阵C,若C有n 个位于不同行不同列的 零元素,即可得最优解X0。否则,对C进行调整。
?5 0 ? 2 3 ? ? ? 0 10 ?9 8 ?0 6 ?

?

最优解 x12 ? 1 x 23 ? 1, x 31 ? 1, x 43 ? 1 , x 55 ? 1 , 其余 x ij ? 0 ,


+2

? 2 ?? ? ? 0? 5? 4? ? 2 ??-2
2 0 0 0 5 7 0 0 3 6



?7 0 ? 4 3 ? ? ? 2 10 ? 11 8 ?0 4 ?

2 0 5 0 1

0 0 7 0 4

?7 2? ? ? 4 0 ? ? -2 ??0 5? ? 11 4? ?0 0? ? ?

?

0 3 8 8 4

?

2 0 3 0 1

0 2 ? 0 ?? 0 ? ?? 5 3? 0 4? 4 0? ?

最优指派方案:甲做B工作 ,乙做C工作 丙做A工作 ,丁做D工作

戊做E工作

30

当C没有n 个位于不同行不同列的零元素时, 对C进行调整。具体步骤: 第一步:做能复盖所有0元素的最小直线集合: 1)对没有○的行打√号
?5 2)对打√号的行上所有0元 ? 2 ? 素的列打√号 ? ?0 ?9 3)再对打√号的列上所有○的 ?0 ? 行打√号 √ 4)重复以上步骤直到得不出新的 打√号为止 5)对没有打√号的行画横线,所有 打√号的列画纵线,所得到的直线 既是复盖所有0元素的最小直线集合 0 3 10 8 6 2 0 5 0 3

?

0 ? 2 ?? 0 ?? 0 ? 7 5 ?√ 0 ? 4 ???√ 6 2

31

第二步:在没有被直线复盖的元素中找出最 小元素,让打√号的列加上这个元 素,打√号的行减去这个元素
+2
?5 0 ? 2 3 ? ? ? 0 10 ?9 8 ?0 6 ? 0 ? 2 ?? 0 ? ? 0√ ? 7 5? 0 ? 4 ?? 6 2 2 0 5 0 3 ? √

√ 第三步:对所得到的矩阵画○,若能得到n个○, 则得最优解,否则重复以上步骤,直至得 到n个○。

?

?7 0 ? 4 3 ? ? ? 2 10 ? 11 8 ?2 6 ?

2 0 5 0 3

0 0 7 0 6

2? ? 0 ? 5 ? -2? 4? 2 ?-2 ?

?7 ? 4 ? ?0 ? 11 ?0 ?

?

0 3 8 8 4

?

2 0 3 0 1

0 2 ? 0 ?? 0 ?? ? 5 0 4 3? 4? 0? ?

32

例:求费用矩阵为下表的 指派问题的最优解 最优指派方案:甲做B工作 乙做C工作 ,丙做A工作 丁做D工作 ,戊做E工作

工作



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 12 10 6

最优值 Z =32 ,即总费用为 32
? 12 7 9 7 9 ? -7 ? ? ? 8 9 6 6 6 ? -6 C ? ? 7 17 12 14 12 ? -7 ? ? ? ? 15 14 6 6 10 ? -6 ? ? 4 10 7 10 6 ? -4 ?

?5 0 ? 2 3 ? ? 0 10 ?9 8 ?0 6 ?

+2

?


2 0 ? 5 0 3

0 ? 0 ?

2? ?7 0 ? ? 0 4 3 ? ? 7 5 √ -2 ? ? 0 8 ? 0 4? ? 11 8 ? ? ?0 4 6 2 √ -2 ? ?

?

?

2 0 3 0 1

0 2 ? 0 ?? 0 ?? ? 5 0 4 3? 4? 0? ?

最优解 x12

? 1 x 23 ? 1, x 31 ? 1, x 44 ? 1 , x 55 ? 1 , 其余 x ij ? 0 ,
33

指派问题解法的具体步骤
第一步:变换指派问题的系数矩阵(cij )为(bij),使 在(bij)的各行各列中都出现0元素,即 (1) 从(cij)的每行元素都减去该行的最小元素; (2) 再从所得新系数矩阵的每列元素中减去该列的最 小元素。

34

第二步:进行试指派,以寻求最优解。 在(bij)中找尽可能多的独立0元素,若能找出n个独 立0元素,就以这n个独立0元素对应解矩阵(xij)中的元 素为1,其余为0,这就得到最优解。找独立0元素,常 用的步骤为: (1)从只有一个0元素的行(列)开始,给这个0元素加 圈,记作◎ 。然后划去◎ 所在列(行)的其它0元素,记 作? ;这表示这列所代表的任务已指派完,不必再考 虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈,记作 ◎;然后划去◎ 所在行的0元素,记作? . (3)反复进行(1),(2)两步,直到尽可能多的0元素都 被圈出和划掉为止。

(4)若仍有没有划圈的0元素,且同行(列)的0元素至 少有两个,则从剩有0元素最少的行(列)开始,比较这 行各0元素所在列中0元素的数目,选择0元素少的那列 的这个0元素加圈(表示选择性多的要“礼让”选择性 少的)。然后划掉同行同列的其它0元素。可反复进行, 直到所有0元素都已圈出和划掉为止。
(5)若◎ 元素的数目m 等于矩阵的阶数n,那么这指 派问题的最优解已得到。若m < n, 则转入下一步。

第三步:作最少的直线覆盖所有0元素。 (1)对没有◎的行打√号; (2)对已打√号的行中所有含?元素的列打√号; (3)再对打有√号的列中含◎ 元素的行打√号;

(4)重复(2),(3)直到得不出新的打√号的行、列为止; (5)对没有打√号的行画横线,有打√号的列画纵线, 这就得到覆盖所有0元素的最少直线数 l 。l 应等于m, 若不相等,说明试指派过程有误,回到第二步(4),另 行试指派;若 l=m < n,须再变换当前的系数矩阵,以 找到n个独立的0元素,为此转第四步。 第四步:变换矩阵(bij)以增加0元素。 在没有被直线覆盖的所有元素中找出最小元素,然后 打√各行都减去这最小元素;打√各列都加上这最小元 素(以保证系数矩阵中不出现负元素)。新系数矩阵 的最优解和原问题仍相同。若得到n各独立的0元素, 则问题已取得最优解,否则再回到第二步重复进行。

例二:
任务

人员

A 2
10 9 7

B 15
4 14 8

C 13
14 16 11

D 4
15 13 9


乙 丙 丁

? 2 15 13 4 ? 2 ? ? 4 10 4 14 15 ? ? ? 9 14 16 13 ? 9 ? ? 7 8 11 9 ? 7 ?

? 0 13 ? 6 0 ? ?0 5 ? ?0 1

11 10 7 4

2? ? 11 ? 4? ? 2?

?0 ? 6 ? ?0 ? ?0

13 0 5 1

11 10 7 4
4

2? ? 11 ? 4? ? 2?
2

?0 ? 6 ? ?0 ? ?0

13 0 5 1

7 6 3 0

0? ? 9 ? 2? ? 0?
40

? ? 0 13 ? ◎ 6 0 ? ◎ ?0 5 ? ? 0 1 ?

7 6 3
◎ 0



0? ? 9 ? 2? ? ? 0?

?0 ? 0 ? ?1 ? ?0

0 1 0 0

0 0 0 1

1? ? 0 ? 0? ? 0?
41

例一求解过程如下:
第一步,变换系数矩阵:
?6 ? 4 ? ( c ij ) ? ?3 ? ?5 7 5 1 9 11 9 10 8 2? ? 8 ? 4? ? 2? ?2 ?4 ?1 ?2

?4 ? 0 ? ?2 ? ?3

5 1 0 7

9 5 9 6

0? ? 4 ? 3? ? 0?

?4 ? 0 ? ?2 ? ?3

5 1 0 7

4 0 4 1

0? ? 4 ? 3? ? 0?

第二步,试指派:
?4 ?◎ ? ?2 ? ?3 5

-5
4 ◎? ? 1 ? 4 ? ◎ 4 3? ? ?? 7 1

找到 3 个独立零元素 但 m =3 <n=4

第三步,作最少的直线覆盖所有0元素
? 4 5 4 ◎? √ ? ? ◎ 1 ? 4 ? ? ?2 ◎ 4 3? ? ?√ ?3 7 1 ? ?

√ 独立零元素的个数m等于最少直线数l,即l=m=3<n=4; 第四步,变换矩阵(bij)以增加0元素:没有被直线 覆盖的所有元素中的最小元素为1,然后打√各行都减 去1;打√各列都加上1,得如下矩阵,并转第二步进 行试指派:

? 4 5 4 ◎? √ ?◎ ? 4? 1 ? ? ?2 ◎ 4 3? ? ? ?? √ ?3 7 1



?3 ? ◎ ? ?2 ? ?2

3 ◎? ? 5? 1 ? ◎ 4 4? ? ?? 6 0 4

?3 ? 0 ? ?2 ? ?2
?0 ? 1 ? ?0 ? ?0

4 1
0

3
0

4
0

6

0? ? 5 ? 4? 0? ?

?3 ?◎ ? ?2 ? ?2

3 ◎? ? 5? 1 ? ◎ 4 4? ? ◎ ?? 6 4

得到4个独 立零元素, 所以最优解 矩阵为:

0 0 1 0

0 0 0 1

1? ? 0 ? 0? ? 0?
15

练习:
费 工作 用 人员

A
7

B
5

C
9

D
8

E
11




丙 丁 戊

9
8 7 4

12
5 3 6

7
4 6 7

11
6 9 5

9
8 6 11

? 7 5 9 8 11 ? ? 5 ? ? 9 12 7 11 9 ? 7 ? ? ?8 5 4 6 9 ? ? 4 ? ? 7 3 6 9 6??3 ? ? 4 6 7 5 11 ? ? 4 ? ?

?2 ? 2 ? ?4 ? 4 ? ?0 ?

0 5 1 0 2

4 0 0 3 3

3 4 2 6 1

6? ? 2 ? 5? ? 3? 7? ?
46

-1 -2

?2 ? 2 ? ?4 ? 4 ? ?0 ?

0 5 1 0 2

4 0 0 3 3

2 3 1 5 0

4? ? 0 ? 3? ? 1? 5? ?

?2 ? 2 ? ?4 ? 4 ? ?◎ ?0

◎ 0

4
? 0
◎ 0

2 3 1 5
? 0

5 1
? 0

3 3

2

4? ? ◎ 0 ? 3? ? 1? 5? ?
47

?2 ? 2 ? ?4 ? 4 ? ?◎ ?0

◎ 0

4
? 0
◎ 0

2 3 1 5
? 0

5 1
? 0

3 3

2


4? ? ◎ 0 ? 3? ? 1? 5? ?





l =m=4 < n=5

48

?2 ? 2 ? ?4 ? 4 ? ?◎ ?0

◎ 0

4
? 0
◎ 0

2 3 1 5
? 0

5 1
? 0

3 3

2

4? ? ◎ 0 ? 3? ? 1? 5? ?

?1 ? 2 ? ?4 ? 3 ? ?0 ?

0 6 2 0 3

3 0 0 2 3

1 3 1 4 0

3? ? 0 ? 3? ? 0? 5? ?
49

?1 ? 2 ? ?4 ? 3 ? ?0 ?

0 6 2 0 3

3 0 0 2 3

1 3 1 4 0

3? ? 0 ? 3? ? 0? 5? ?

?1 ? 2 ? ?4 ? 3 ? ?◎ ?0

◎ 0

3
◎ 0

1 3 1 4
? 0

6 2
? 0

? 0

2 3


3


3? √ ?√ ? 0 ? 3? √ ? ◎ √ 0? 5? ?

50

?1 ? 2 ? ?4 ? 3 ? ?◎ ?0

◎ 0

3

1

6 2
? 0

◎ 0 3

0 ? 2 3


1 4
? 0

3


3? ? 0 ? ? 3? ? ◎ 0? 5? ?


√ √ √ √

l =m=4 < n=5

?1 ? 2 ? ?4 ? 3 ? ?◎ ?0

◎ 0

3
◎ 0

1 3 1 4
? 0

6 2
? 0

? 0

2 3


3


3? ? ? 0 ? 3? ? ◎ 0? 5? ?


√ √ √ √

?0 ? 1 ? ?3 ? 2 ? ?0 ?

0 6 2 0 4

3 0 0 2 4

0 2 0 3 0

3? ? 0 ? 3? ? 0? 6? ?
52

?0 ? 1 ? ?3 ? 2 ? ?0 ?

0 6 2 0 4

3 0 0 2 4

0 2 0 3 0

3? ? 0 ? 3? ? 0? 6? ?

? ?0 ? 1 ? ?3 ? 2 ? ?◎ ?0

◎ 0

3
◎ 0

6 2
? 0

0 ? 2 4
28

4

0 3? ? ? 2 ? 0 ? ◎ 0 3? ? 3 ◎? 0 ? 0 6? ?
53

此问题有多个最优解

◎ ?0 ? 1 ? ?3 ? 2 ? ?0 ? ?

? 0

3
? 0
◎ 0

? 0

6 2


2
? 0

0 4

2 4

3
◎ 0

3? ? ◎ 0 ? 3? ? ? 0? 6? ?
54

0 ?? ? 1 ? ?3 ? 2 ? ◎ ?0 ?

? 0

3
? 0
◎ 0



0 2
? 0

6 2


0 4

2 4

3
? 0

3? ? ◎ 0 ? 3? ? ? 0? 6? ?
55

用匈牙利法求解下列指派问题,已知效率矩 阵分别如下:

? 7 9 10 12 ? ? ? 13 12 16 17 ? ? ? 15 16 14 15 ? ? ? 11 12 15 16 ? ? ? ?

?3 8 ? ?8 7 ?6 4 ? ?8 4 ? 9 10 ?

2 2 2 2 6

10 9 7 3 9

3 ? ? 7 ? 5 ? ? 5 ? ? 10 ?

56

例:现有4份工作,4个人应聘,由于个人的技术专 长不同,他们承担各项工作所需费用如下表所示, 且规定每人只能做一项工作,每一项工作只能由一 个人承担,试求使总费用最小的分派方案。
工作

人 1 2 3 4

1 15 19 26 19

2 18 23 17 21

3 4 21 22 16 23 24 18 19 17

? 15 ? ? 19 C ?? 26 ? ? 19 ?

18 23 17 21

21 22 16 23

24 ? ? 18 ? 19 ? ? 17 ? ?

最优解 x11 ? 1 x 24 ? 1, x 33 ? 1, ,

x 42 ? 1

, 其余 x ij ? 0

最优方案: 第一个人做第一件事 ; 第二个人做第四件事 ; 第三个人做第三件事 ; 第四个人做第二件事 ;总费用:70

57

? 15 ? ? 19 C ?? 26 ? ? 19 ?

18 23 17 21

21 22 16 23

24 ? ? 18 ? ?? 19 ? 17 ? ?



?0 3 6 ? 1 5 4 ? ? 10 1 0 ?2 4 6 ?

?0 ? 1 ? ? ? 10 ?2 ?
?0 ? 0 ? ? ? 12 ?1 ?

2 4 0 3

6 10 ? ? 0 2 ? ? 4 1 0 3 ?? ? 0 4 ? ? 10 0 6 1? ?1 2 ? ?

?

?

0 4 ?1 ?1 0 ?0

6 10 ?√ ?2 2 ? ? 3 0√ 2 3 ? ?? 0 4? ? 12 0 ?3 2 5 0 ?√ ? ?



9? ? 0 ? ? 3? 0? ?

?0 ? 1 ? ? 10 ?2 ?


2 4 0 3

?

6 4 0 6

?

9? ? 0√ ? 3? 0 ?√ ?

?

6 12 ? ? 3 2 ? 0 6? 5 2? ?

10 ? ? 0 ? 6? 0 3 0? ?

最优解 x11 ? 1 x 24 ? 1, x 33 ? 1, ,

?

x 42 ? 1 , 其余 x ij ? 0
58

一般的指派问题 (1)求maxZ的指派问题 (2)人数与工作数不等的指派问题 (3)一个人可做几件事的指派问题 (4)某事一定由(不能由)某人做的指派问题

59

(1)求maxZ的指派问题
设有n个工作,要由 n个人来 承担,每个工作只能由一个 人承担,且每个人只能承担 一个工作。cij表示第i个人做 第j件事的收益,求总收益最大 的指派方案。
?1 第i个人做第j 人件事 ? x 解:ij ? ? ? 0 第i个人不做第j 人件事 ?
1 1 c11 2 c 21 …? i c i1 …? n c n1 2
c12 c 22 ? ci 2 ? cn 2


? ? ? ? ? ?

j
c1 j c2 j ? c ij ? c nj


? ? ? ? ? ?

n
c1 n c2n ? c in ? c nn

指派问题模型:
max Z ?

??c
j i

ij

x ij

i=1,2, …,n; j=1,2, …,n

Z表示总收益

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? i=1,2, …,n ? s.t ? x1 j ? x 2 j ? ? ? xij ? ? ? x nj ? 1 ? j=1,2, …,n 60 ? x ij ? 0,1 i ? 1,2, ? , n; j ? 1,2, ? , n ?

令 M ? max ?c ij ?
工作

人 1 2 … i … n

1
c11 c 21 ? c i1 ? c n1

2
c12 c 22 ? ci 2 ? cn 2


? ? ? ? ? ?

j
c1 j c2 j ? c ij ? c nj


? ? ? ? ? ?

n
c1 n c2n ? c in ? c nn

? M ? c11 M ? c12 ? ? M ? c 21 M ? c 22 做C ? ? ? ? ? ?M ?c M ? cn 2 n1 ?

? M ? c1n ? ? ? M ? c2 n ? ? ? ? ? ? M ? c nn ? ?

?0

指派问题最大化的数学模型:

max Z ?

??c
j i

ij

x ij
i=1,2, …,n

用 匈 指派问题最小化的数学模型: 牙 min Z ? ? ? ? ?M ? c ij ?x ij 利 j i 法 ?Mx ? c x ? ?

??
j i j i

ij

ij

ij

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? s .t ? x1 j ? x 2 j ? ? ? xij ? ? ? x nj ? 1 j=1,2, …,n ? xij ? 0,1 i ? 1, 2, ? , n; j ? 1, 2, ? , n ?

?

? ? Mx

ij

?

??c
j i

ij

x ij

?M ?Z

? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? s .t ? x1 j ? x 2 j ? ? ? xij ? ? ? x nj ? 1 j=1,2, …,n 61 ? xij ? 0,1 i ? 1,2, ? , n; j ? 1,2, ? , n ?

M ? max ?c ij ?
min Z ? ? ? ? ?M ? c ij ?x ij ? M ? Z max Z ? ? ? c ij x ij j i j i ? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? s .t ? x1 j ? x 2 j ? ? ? xij ? ? ? x nj ? 1 j=1,2, …,n s .t ? x ? x ? ? ? x ? ? ? x ? 1 j=1,2, …,n ? 1j 2 j ij nj ?xij ? 0,1 i ? 1, 2, ? , n; j ? 1, 2, ? , n ?x ? 0 ,1 i ? 1, 2 , ? , n ; j ? 1, 2 , ? , n ? ? ij 设 X 1, X 2 是 min Z ?的可行解, 则 X 1, X 2 也是 max Z 的可行解, ? ? 且对应的目标函数值 Z1 ? Z 2 对应的目标函数值 Z , Z
1 2

? 由 Z 1? ? Z 2
? M ? Z1 ? M ? Z 2

因此,若 X 0 是 min Z ?的最优解 即 X 0 是 min Z ?的可行解 ? 且使 min Z ?取到最小值 Z 0

? Z1 ? Z 2

则 X 0 也是 max Z 的可行解
且使 max Z取到最大值 Z 0
? Z0 ? M ? Z0

62

对maxZ的指派问题
令 M ? max ?c ij ?

工作

人 1 2 … i … n
M ? c1n ? ? M ? c2 n ? ? ? ? M ? c nn ? ?

1
c11 c 21 ? c i1 ? c n1

2
c12 c 22 ? ci 2 ? cn 2


? ? ? ? ? ?

j
c1 j c2 j ? c ij ? c nj


? ? ? ? ? ?

n
c1 n c2n ? c in ? c nn

? M ? c11 ? ? M ? c 21 做C ? ? ? ? ?M ?c n1 ?

M ? c12 M ? c 22 ?

? ? ?

M ? cn 2 ?

用匈牙利法求C, 得最优解 X 0 及最优值 Z 0
则 X 0 就是 max Z 问题的最优解, , 最优值为 M ? Z 0
63

(2)人数与工作数不等的指派问题
设有n个工作,要由 m个人来承担,每个工作 只能由一个人承担,且每个人只能承担一个工 作。cij表示第i个人做第j件事的费用,求总费用 最低的指派方案。 用匈牙利法 (a)m>n
工作

求解
1 2
c12 c 22 ? ci 2 ? cm 2




? ? ? ? ? ?

j
c1 j c2 j ? c ij ? c mj


? ? ? ? ? ?

n
c1 n c2n ? c in ? c mn

n+1 n+2 …m
0 0 ? 0 ? 0 0 0 ? 0 ? 0 ?0 ?0 ? ?0 ? ?0
64

c11 1 2 c 21 … ? c i1 i … ? m c m1

例:现有4份工作,6个人应聘, 由于个人的技术专长不同,他 人 们承担各项工作所需时间如下 表所示,且规定每人只能做一 项工作,每一项工作只能由一 个人承担,试求使总时间最少 的分派方案。
? 12 ? ?7 ? 15 C ?? ?4 ? 6 ? ?4 ? 7 17 14 10 5 5 9 12 6 7 5 7 7 14 6 10 8 6 0 0 0 0 0 0 0? ?8 ? ? 0? 3 ? 11 0? ??? ?0 0? ?2 ? 0 ? ? ? ?0 0?

工作

1
1 2 3 4 5 6 12 7 15 4 6 4

2
7 17 14 10 5 5

3 4
9 12 6 7 5 7 7 14 6 10 8 6

5 6

0 0 0 0 0 0

0 0 0 0 0 0

?

?

2 12 9 5 0 0

4 7 1 2 0 2

1 8 0 4 4 2

? 0? 0 ??? 0 ??? 0 ? ?? 0? ? ??

0 0 0 0 0 0

0 ?? 分派方案: ?

第1、2个人没工作 第3个人第4项工作 第4个人第1项工作 第5个人第3项工作 第6个人第2项工作 65 总时间= 6+4+5+5=20

(b)m<n
工作



1
c11 c 21 ? c i1 ? c m1
0 0 ? 0

2
c12 c 22 ? ci 2 ? cm 2
0 0 ? 0


? ? ? ? ? ?

j
c1 j c2 j ? c ij ? c mj


? ? ? ? ? ?
? ? ? ?

n
c1 n c2n ? c in ? c mn
0 0

1 2 … i … m m+1 m+2 … n

?0 ?0 ?0

0

用匈牙利法 求解

66

例:某商业公司计划开办五家新商 每家公司最多可 店。为了尽早建成营业,商业公司 承建两家商店: B1 B2 B3 B4 B5 决定由3家建筑公司分别承建。已 A11 ? 4 8 7 15 12 ? 知第Ai(i=1,2,3)个建筑公司对第 ? ? 4 8 7 15 12 A12 Bj(j=1,2,3,4,5)家新商店的建造费用 ? 7 9 17 14 10 ? A21 ? ? 的报价如下表,为保证工程进度, ? 7 9 17 14 10 ? A22 ? 6 9 12 8 7 ? A31 每家建筑公司最多只能承建两个商 ? 6 9 12 8 7 ? A ? ? 32 店,且由于某种原因,第B3家商店 人数≠工作数: 不能由第A1个建筑公司承办,求使 B1 B2 B3 B4 B5 B6 总费用最少的指派方案 A11 50
商店

建筑公司 A1 A2 A3

B1 B2 B3 B4 B5 4 8 7 15 12 7 9 17 14 10 6 9 12 8 7

?4 ? 4 ? ?7 ?7 ?6 ? ?6

8 7 15 8 50 15 7 9 17 14 9 17 14 9 12 8 9 12 8

12 12 10 10 7 7

0? ? 0 A12 ? 0 ?A21 0 ?A22 0 ?A31 ? 0 ?A
67 32

B3不能由A1承办:

?4 ? 4 ? 7 C ?? ?7 ?6 ? ?6
?2 ? 2 ? 4 ?? ?4 ?4 ? ?4

8 8 9 9 9 9

50 50 17 17 12 12

15 15 14 14 8 8

12 12 10 10 7 7

0 ? ? 0 0 38 7 5 ? ? 0 0 38 7 5 0 ? ? ? 0? ? 3 1 5 6 3 ? 0? ? 3 1 5 6 3 0 ? ?2 1 0 0 0 ? ? 0 ? ?2 1 0 0 0 ?

?

?



0 ??? 0 ?? 0? ? 0? ? 0 ? 0? ?

?? ? ? ? ?
1? ? 1 ? 0? 0? 3? ? 3?

√ ?√

?0 ? 0 ? 2 ?? ?2 ?2 ? ?2

√√

?

0 ? 38


5 5 2 2 0 0

? ?

7 0 38 7 0 4 5 0 4 5 1 0 0 1 0 0

?? ? ?

?

1√ ? ? 1√ ? √ 0? 0 ?√ 1? ? 1?

2 38 7 5 2 38 7 5 2 4 5 2 2 4 5 2 3 0 0 0 3 0 0 0

3? ? 0 0 36 5 3 ? ? 3 0 0 36 5 3 ? ? 2? 2 0 2 3 0 ?? ?2 0 2 3 0 2? ?4 3 0 0 0 3? ? ? 3? ?4 3 0 0 0

?

?

? ?

? ?? ? ?

?

A11 A12 A21 A22 A31 A32

B1 B2 B3 B4 B5 B6

指派方案: 1承建B1、B2 ,由A2承建B5 由A 由A3承建B3、B4 总费用=42

68

? 非标准型的指派问题:
匈牙利法的条件是:模型求最小值、效率cij≥0。 当遇到各种非标准形式的指派问题时,处理方法是先将 其转化为标准形式, 1、人数和事数不相等的指派问题:人少事情多,虚拟 “人”,做各事的费用系数为0;人多事情少,虚拟 “事”,各人做的费用系数为0。 2、对于求极大化的问题,只要经如下变换,仍可利用 匈牙利算法进行求解。 3、一个人可以做几件事情的指派问题:可以将该人化 作相同的几个“人”来接受指派,费用一样。 4、某事一定不能由某人做的指派问题,费用系数为“M” 然后用匈牙利法来求解。
69

? 1.

最大化指派问题

例4.9 某人事部门拟招聘4人任职4项工作,对他们综合考评的 得分如下表(满分100分),如何安排工作使总分最多。 处理方法:设m为最大化指派问题系数矩阵C中最大元素。 令矩阵B=(m-cij)nn则以B为系数矩阵的最小化指派问题和 原问题有相同的最优解。
甲 ? 85 ? 乙 95 C= ? 丙 ? 82 ? 丁 ? 86 92 87 83 90 73 78 79 80 90 ? ? 95 ? 90 ? ? 88 ?

70

C ? ? (95 ? c ij )

?

解: M=95,令

?10 ? 0 ? C ?= ?13 ? ?9
1 0 0 0 0 0 0 1

3 8 12 5
0? ? 0 ? 1? ? 0?

22 17 16 15

5? ? 0 ? 5? ? 7?

用匈牙利法求解C’,最优解为:
?0 ? 1 ? X= ?0 ? ?0

即甲安排做第二项工作、乙做第三项、丙做第四项、丁做 第三项, 最高总分Z=92+95+90+80=357

71

? 2.

不平衡的指派问题
? 5 ? 11 ? ? 8 ? ? 6 ? 3 ? 9 6 14 4 2 10 ? ? 3 ? 17 ? ? 5 ? 1 ? ? ?5 ? 11 ? ?8 ? ?6 ?3 ? 9 6 14 4 2 10 3 17 5 1 0 0 0 0 0 0? ? 0 ? 0? ? 0? 0? ?

当人数m大于工作数n时,加上m-n项虚拟工作,例如:

当人数m小于工作数n时,加上n-m个人,例如
?15 ? 6 ? ?10 ? 20 5 13 10 4 16 9? ? 7 ? 17 ? ?
? 15 ? 6 ? ? 10 ? ? 0 20 5 13 0 10 4 16 0 9 ? ? 7 ? 17 ? ? 0 ?
72

? 3.

一个人可做几件事的指派问题

若某人可做几件事,则将该人化作相同的几个“人”来接受 指派,且费用系数取值相同。 例如:丙可以同时任职A和C工作,求最优指派方案。
甲 乙 丙 ?15 ? 6 ? ?10 ? 20 5 13 10 4 16 9? ? 7 ? 17 ? ?
? 15 ? 6 ? ? 10 ? ? 10 20 5 13 13 10 4 16 16 9 ? ? 7 ? 17 ? ? 17 ?

73

? 4.

某事一定不能由某人做的指派问题

将该人做此事的效率系数取做足够大的数,可用M表示。
例4.10 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项 任务。每个人完成各项任务的时间如表所示。由于任务数多于人 数,考虑任务E必须完成,其他4项中可任选3项完成。试确定最 优分配方案,使完成任务的总时间最少。

任务 人员 甲 乙 丙

A 25 39 34

B 29 38 27

C 31 26 28

D 42 20 40

E 37 33 32

74

?
?

解: 1) 这是不平衡的指派问题,首先转换为标准型,再 用匈牙利法求解。 2) 由于任务数多于人数,所以假定一名虚拟人,设为戊。 因为工作E必须完成,故设戊完成E的时间为M(M为非 常大的数),其余效率系数为0,则标准型的效率矩阵表 示为:

任务 人员 甲 乙 丙 丁 戊

A 25 39 34 24 0

B 29 38 27 42 0

C 31 26 28 36 0

D 42 20 40 23 0

E 37 33 32 45 M

75

?

用匈牙利法求出最优指派方案为:
?0 ? 0 ? ?0 ? ?1 ?0 ? 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0? ? 0 ? 1? ? 0? 0? ?

即甲-B,乙-D,丙-E,丁-A, 任务C放弃。 最少时间为105。

76

结语 ? 指派问题的目标就是在解决问题时,如何分 派使所消耗的总资源最少(或总体效益最优)。 如:给工人分派工作,给车辆分配道路,给 工件分配机床等等。同时许多网络问题(如旅 行问题、任务分配问题、运输问题等)都可以 演化成指派问题来解决。在现实生活中,指 派问题是十分常见的实际问题,利用数学建 模思想,匈牙利解法可以很好地解决指派问 题。
?
77

作业:
1、 6个人应聘4份工作,由于个人的技术专长不同, 他们承担各项工作所获得的收益如下表,且规定每 人只能做一项工作,每一项工作只能由一个人承担, 试求使总收益最大的指派方案。 工作 分派方案: 1 2 3 4 人 第1、2个人没工作 1 3 5 4 5 2 6 7 6 8 第3个人第2项工作 3 8 9 8 10 第4个人第3项工作 10 10 9 11 4 第5个人第1项工作 5 12 11 10 12 6 13 12 11 13 第6个人第4项工作
78

?

? ? ? ?

?
?

2、某施工企业现有A、B、C、D、E共5台同类机 械,需要派其中4台去完成4个任务,由以往的统计 资料,各机械完成任务所消耗的资源如表1所示。 现已知,每项任务只能一台机械去完成,每台机械 最多承担一项任务,而且A必须分配到一项任务,D 不能够承担第4项任务,问如何分派,才能够使完 成4项任务所消耗的总资源最少? 表1 各机械完成任务所消耗的资源 A B C D E 第1项 2O 12 13 25 19 第2项 15 2O 25 12 14 第3项 25 15 24 17 25 第4项 3O 25 28 16 18
79

?

3、某游泳队有4名运动员(记为A、B 、C、D),他 们的100 in自由泳、蛙泳、蝶泳、仰泳的成绩如下 表所示,现要组成一个4×100 in混合泳接力队,问 如何指派,才能使总成绩最好?

各运动员完成项目所需要的时间

80

? ? ? ? ? ? ? ? ? ? ? ? ?

?
? ? ? ? ? ? ? ? ? ?

MATLAB程序: clear all; C=[20 12 13 25 19;15 20 25 12 14;25 15 24 17 25;30 25 28 100 18;100 0 0 0 0];%效率矩 阵C n=size(C,1);%计算C的行列数n C=C(:);%计算目标函数系数,将矩阵C按列排成一个列向量即可。 A=[];B=[];%没有不等式约束 Ae=zeros(2*n,n^2);%计算等约束的系数矩阵a for i=1:n for j=(i-1)*n+1:n*i Ae(i,j)=1; end for k=i:n:n^2 Ae(n+i,k)=1; end end Be=ones(2*n,1);%等式约束右端项b Xm=zeros(n^2,1);%决策变量下界Xm XM=ones(n^2,1);%决策变量上界XM [x,z]=linprog(C,A,B,Ae,Be,Xm,XM);%使用linprog求解 x=reshape(x,n,n);%将列向量x按列排成一个n阶方阵 disp('最优解矩阵为:');%输出指派方案和最优值 Assignment=round(x)%使用round进行四舍五入取整 disp('最优解为:'); z 81

Q&A
谢谢!再见!
82

三.非标准指派问题的处理 ? 1.人数与事数不等 (1)人多事少:若有m项工作n个人,且m<n,这时 可以虚增n-m项工作,系数矩阵新增加一列,费用按 题意要求的设定,就象运输问题中设定单位运费一样 (若不考虑人空闲时的损失,系数为零,否则为损失 费用),从而可以把原问题化为标准指派问题。 (2)事多人少:若有m项工作n个人,且m>n,这时 可以虚增m-n个人,系数矩阵新增加一行,费用按题 意要求的设定,就象运输问题中设定单位运费一样 (若不考虑缺人所造成的损失,系数为零;否则,为 损失费用),从而可以把原问题化为标准指派问题。
83

?

2.一个人可做几件事的指派问题

若某个人可做好几件事,则可将该人化作相同 的几个人来接受指派。这几个做同一件事的费用系 数都一样
?

3.某事一定不能由某人来做的指派问题

若某事一定不能由某人来做,则可将相应的费 用系数取作足够大的数M

84

4.对于极大化指派问题,可令新的系数矩阵中的元素 bij= M-cij 其中M是足够大的常数(一般选取cij中的最 大元素为M)这时系数矩阵可变换为B={bij} 其中, bij≥0,满足匈牙利算法的条件。目标函数经过变换后, 解

min z ? ?

??b
i j

ij

x ij

所得的最小值就是原问题的最大值。因为:
min

??b
i j

ij

x ij ? min

? ? (M
i j

? c ij ) x ij ? nM ? max

??c
i j

ij

x ij

85

常数


相关文章:
运筹学指派问题的匈牙利法实验报告
运筹学指派问题匈牙利法实验报告_数学_自然科学_专业资料。指派问题匈牙利法实验报告 运筹学课程设计报告 专业: 班级: 学号: 姓名: 2012 年 6 月 20 日 ...
匈牙利算法在企业员工指派问题的应用(最终版)
对于这一问题,匈牙利算法就是一个很好的解法.本文首先给出企业员工指派问 题的数学模型,它分为两大类,一类是标准指派问题(即企业指派员工数与任务 数相等) 另...
运筹学指派问题的匈牙利法
运筹学指派问题匈牙利法_数学_自然科学_专业资料。指派问题匈牙利法运筹学课程设计 指派问题匈牙利法 专业: 姓名: 学号: 1. 算法思想:匈牙利算法的基本思想是...
指派问题的匈牙利解法
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 指派问题匈牙利解法 指派问题匈牙利解法指派问题匈牙利解法隐藏>> ...
匈牙利算法在企业员工指派问题的应用(最终版)
匈牙利算法在企业员工指派问题的应用(最终版)_人力资源管理_经管营销_专业资料。闽江学院 本科毕业论文题 目 匈牙利算法在企业员工指派问题的应用 张雯 学生姓名 学...
求解指派问题的匈牙利算法.doc
3.2 求解指派问题匈牙利算法 由于指派问题的特殊性,又存在着由匈牙利数学家 D.Konig 提出的更为简便的解法— 匈牙利算法。算法主要依据以下事实:如果系数矩阵 C...
运输问题与指派问题
运输问题与指派问题_人力资源管理_经管营销_专业资料。运筹学天津理工大学 课程论文运筹学 运输问题与指派问题——匈牙利法 姓名: 系别: 机械工程系 开始日期: 2013...
指派问题(含非标准指派问题)
但是,这些解法都没有充分利用指派问题的特 殊性质,有效地减少计算量。1955 年,库恩(W.W.Kuhn)提出了匈牙利法。 定理 1:设指派问题的效率矩阵为 C= (cij ) ...
运筹学指派问题
匈牙利解法的依据是指派问题的最优解的一下性 质:设指派问题的系数矩阵 C=(cij)n*n.若将 C 的一行或列分别减去一个常数 K,则得到 一个新的矩阵 C'=(c...
指派问题的算法分析与实现
在运筹学中求解整数 规划的指派问题通常是通过匈牙利算法来求解,但指派问题也可以归结为一个 0-1 整数规划问题,本文先对指派问题进行陈述,引出对实际问题的求解。...
更多相关标签: