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

指派问题的匈牙利法


指派问题
指派问题是一种特殊的整数规划问题 一、问题的提出 设有m个工人,能做n件事,但效率不 同,并规定每个工人做且只能做一件事, 每件事有且只能有一个工人做,问应该如 何安排他们的工作,使花费的总时间(成 本)最少或效率最高?

二、指派问题的数学模型
设第i个工人做第j件事的时间是 c ij ,决策 变量是

? 1, 第i个工人做第j件事 xij = ? ?0, 第i个工人不做第j件事
则数学模型如下

min z = ∑∑ cij xij
j =1 i =1

n

m

? n ? ∑ xij = 1, i = 1,2, L , m = ? jm1 ? ? ∑ xij = 1, j = 1,2, L , n ? i =1 ? xij = 0,1; i = 1,2, L , m; ? j = 1,2, L , n ?

举例说明 1)表上作业法 2)匈牙利法

例 有四个工人和四台不同的机床,每位工人在不 同的机床上完成给定的任务的工时如表5.12所示, 问安排哪位工人操作哪一台机床可使总工时最少?

任务1 工人1 工人2 工人3 工人4 2 15 13 4

任务2 10 4 14 7

任务3 3 14 16 13

任务4 7 8 11 9

获得初始解:圈零/划零操作
将时间矩阵C的每一行都减去相应行的最小元素 和每一列都减去相应列的最小元素,使每一行 和每一列都含有零; 从最少零数的行或列开始,将“零”圈起来, 并划去它所在行和所在列的其它零; 反复做2),直到所有零被圈起或被划掉为止。 得到初始解。 判断是否为最优解:圈起的零的个数是否等于n。

确定调整行和列
在没有圈起的零所在行上打“√”; 在打“√”行中所有零所在的列打“√”; 在打“√”列中含有圈起零的行上打“√”, 反复执行2)和3)两步,直到不能打“√”为止; 用直线划去打“√”的列和不打“√”的行,没 用直线划去打“ ”的列和不打“ ”的行 有划去的行构成调整的行,划去的列构成调整 列。

调整可行解的方法
在调整行中寻找最小的元素,将它作为调 整量; 将调整行各元素减去调整量,对调整列中 各元素加上调整量。 再次执行“圈零”和“划零”的操作,并 循环以上的步骤,直到圈起的零数等于n 为止。

匈牙利法解例3.3
时间矩阵

? 2 10 3 7 ? ?15 4 14 8 ? ? ? ?13 14 16 11? ? ? ? 4 7 13 9 ? 各行各列减去最小元素后得 ? 0 ?11 ? ?2 ? ?0

8 0 5? ? 0 9 4? 3 4 0? ? 3 8 5?

圈零划零

?0 ?11 ? ?2 ? 0 ?

8 0 5? ? 0 9 4? 3 4 0? ? 3 8 5?

得最优解
将圈起的零改为1,其它元素改为0,即得 最优解如下

?0 ?0 (xij ) = ? ?0 ? ?1
最小总时间为22。

0 1 0? ? 1 0 0? 0 0 1? ? 0 0 0?

再看一例
请求解如下矩阵表达的指派问题

?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 ? ? ?

减去最小元素

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

圈零划零

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

打勾划线确定调整行和列

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


调整可行解

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

0 2 0 3 0 0 8 3 5 8 0 0 4 1 4

2? ? 0? 0? ? 10? 3? ?

再圈零划零

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

0 3 8 8

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

得最优解

?0 ?0 ? (x ( xij ) = ?0 ? 0 ? ?1 ?

1 0 0 0? ? 0 1 0 0? 0 0 0 1? ? 0 0 1 0? 0 0 0 0? ?

另一最优解
?0 ?0 ? ( xij ) = ?0 ? 0 ? ?1 ? 1 0 0 0? ? 0 0 1 0? 0 0 0 1? ? 0 1 0 0? 0 0 0 0? ?

最小时间(成本)min z=32

匈牙利算法示例

)、解题步骤 解题步骤: (二)、解题步骤: 指派问题是0-1 规划的特例,也是运输问题的特例, 指派问题是 规划的特例,也是运输问题的特例, 当然可用整数规划, 当然可用整数规划,0-1 规划或运输问题的解法去求 解,这就如同用单纯型法求解运输问题一样是不合算 利用指派问题的特点可有更简便的解法, 的。利用指派问题的特点可有更简便的解法,这就是 匈牙利法, 匈牙利法,即系数矩阵中独立 0 元素的最多个数等于 能覆盖所有 0 元素的最少直线数。 元素的最少直线数。 第一步: 变换指派问题的系数矩阵( 第一步 : 变换指派问题的系数矩阵 ( cij ) 为 (bij), 使 , 的各行各列中都出现0元素 在(bij)的各行各列中都出现 元素,即 的各行各列中都出现 元素, (1) 从(cij)的每行元素都减去该行的最小元素; 的每行元素都减去该行的最小元素; (2) 再从所得新系数矩阵的每列元素中减去该列的最 小元素。 小元素。

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

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

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

例一: 例一:
任务

人员

A 2 10 9 7

B 15 4 14 8

C 13 14 16 11

D 4 15 13 9

甲 乙 丙 丁

?2 ?10 ? ?9 ? ?7

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

?0 13 11 2 ? ?6 0 10 11? ? ? ?0 5 7 4 ? ? ? ?0 1 4 2 ?

?0 13 11 2 ? ?6 0 10 11? ? ? ?0 5 7 4 ? ? ? ?0 1 4 2 ?
4 2

?0 13 7 0? ?6 0 6 9? ? ? ? 0 5 3 2? ? ? ?0 1 0 0?

? 0 ?0 13 7 ◎ ? ?6 0 6 9? ◎ ? ? ◎ ? 0 5 3 2? ? ? ◎ ? 0 ?0 1 0 ? ?

?0 ?0 ? ?1 ? ?0

0 0 1? ? 1 0 0? 0 0 0? ? 0 1 0?

例二、 例二、 有一份中文说明书,需译成英、 有一份中文说明书,需译成英、日、德、俄四种
文字,分别记作A、 、 、 。现有甲、 文字,分别记作 、B、C、D。现有甲、乙、丙、丁四 人,他们将中文说明书译成不同语种的说明书所需时 间如下表所示,问如何分派任务,可使总时间最少? 间如下表所示,问如何分派任务,可使总时间最少?
任务

人员

A 6 4 3 5

B 7 5 1 9

C 11 9 10 8

D 2 8 4 2

甲 乙 丙 丁

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

?4 ?0 ? ?2 ? ?3

5 9 0? 1 5 4? ? 0 9 3? ? 7 6 0?

?4 ?0 ? ?2 ? ?3

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

第二步,试指派: 第二步,试指派:

-5

?4 ?◎ ? ?2 ? ?3

4 ◎? ? 1 ? 4? ◎ 4 3? 找到 3 个独立零元素 ? ?? 但 m = 3 < n = 4 7 1 5

第三步,作最少的直线覆盖所有0元素: 第三步,作最少的直线覆盖所有0元素:

?4 ?◎ ? ?2 ? ?3

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

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

?4 ?◎ ? ?2 ? ?3

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

?3 ?◎ ? ?2 ? ?2

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

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

4 1
0

6
0 0 1 0

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

?3 ?◎ ? ?2 ? ?2

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

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

练习: 练习:
费 工作 用 人员

A 7 9 8 7 4

B 5 12 5 3 6

C 9 7 4 6 7

D 8 11 6 9 5

E 11 9 8 6 11

甲 乙 丙 丁 戊

?7 ?9 ? ?8 ? 7 ? ?4 ?

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

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

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

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

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

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



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

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



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





√ l =m=4 < n=5

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



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

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

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

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

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

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



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



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



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

√ √ √ √



l =m=4 < n=5

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



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

√ √ √ √

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

0 3 0 3? ? 6 0 2 0? 2 0 0 3? ? 0 2 3 0? 4 4 0 6? ?



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

0 3 0 3? ? 6 0 2 0? 2 0 0 3? ? 0 2 3 0? 4 4 0 6? ?

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



0 3 0 3? ? ? ◎ 6 0 2 ?? 0 2 0 0 3? ? ◎ ? ? 2 3 ◎ 0 0? ? 4 4 0 6? ?
28

此问题有多个最优解

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

? 0

3
? 0
◎ 0 2

? 0

6 2 ◎ 0 4

2
? 0 3
◎ 0

4

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

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

?

0 6

3
? 0
◎ 0 2



0 2
? 0 3 ? 0

2 ◎ 0 4

4

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

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

?7 ? 13 ? ?15 ? ?11 ?

9 12 16 12

10 16 14 15

12? ? 17? 15? ? ? 16?

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

2 10 3 ? ? 2 9 7? 2 7 5? ? 2 3 5? ? 6 9 10 ?


相关文章:
浅析指派问题的匈牙利解法成稿
浅析指派问题的匈牙利解法成稿 - 洛阳师范学院本科毕业论文 浅析指派问题的匈牙利解法 胡小芹 数学科学学院 数学与应用数学 指导教师:苏孟龙 学号:040414057 摘要:...
求解指派问题的匈牙利算法.doc
求解指派问题的匈牙利算法.doc_理学_高等教育_教育专区。该文档结合实际例子对指派问题的匈牙利算法做了详细的分析求解 3.2 求解指派问题的匈牙利算法 由于指派问题的...
匈牙利算法在企业员工指派问题的应用(最终版)
对于这一问题,匈牙利算法就是一个很好的解法.本文首先给出企业员工指派问 题的数学模型,它分为两大类,一类是标准指派问题(即企业指派员工数与任务 数相等) 另...
运筹学指派问题的匈牙利法
运筹学指派问题的匈牙利法_数学_自然科学_专业资料。指派问题的匈牙利法运筹学课程设计 指派问题的匈牙利法 专业: 姓名: 学号: 1. 算法思想:匈牙利算法的基本思想是...
匈牙利算法在企业员工指派问题的应用(最终版)
匈牙利算法在企业员工指派问题的应用(最终版) - 闽江学院 本科毕业论文 题目 匈牙利算法在企业员工指派问题的应用 张雯 学生姓名 学系年专号别级业 120080901139 ...
更多相关标签: