【运筹学】匈牙利法 ( 匈牙利法示例 )

韩曙亮

发布于 2023-03-28 20:52:06

1.1K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、使用匈牙利法求解下面的指派问题

四人分别完成四项工作所用时间 :

	A A A	B B B	C C C	D D D
甲	2 2 2	15 15 15	13 13 13	4 4 4
乙	10 10 10	4 4 4	14 14 14	15 15 15
丙	9 9 9	14 14 14	16 16 16	13 13 13
丁	7 7 7	8 8 8	11 11 11	9 9 9

A

B

C

D

甲

2

15

13

4

乙

10

4

14

15

丙

9

14

16

13

丁

7

8

11

9

二、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )

先写出指派问题的系数矩阵 :

(c_{ij}) =\begin{bmatrix} & 2 & 15 & 13 & 4 & \\\\ & 10 & 4 & 14 & 15 & \\\\ & 9 & 14 & 16 & 13 & \\\\ & 7 & 8 & 11 & 9 & \\ \end{bmatrix}

使每行都出现

0

元素 :

(c_{ij})

系数矩阵中 , 每行都减去该行最小元素 ;

第

1

行减去最小值

2

;

第

2

行减去最小值

4

;

第

3

行减去最小值

9

;

第

4

行减去最小值

7

;

(c_{ij}') =\begin{bmatrix} & 0 & 13 & 11 & 2 & \\\\ & 6 & 0 & 10 & 11 & \\\\ & 0 & 5 & 7 & 4 & \\\\ & 0 & 1 & 4 & 2 & \\ \end{bmatrix}

此时发现有两列 , 第

4

列 , 第

5

列 , 没有

0

元素 , 这两列每列都减去最小值 :

第

3

列减去最小值

4

;

第

4

列减去最小值

2

;

最终得到行列都有

0

元素的系数矩阵

(b_{ij})

:

(b_{ij}) =\begin{bmatrix} & 0 & 13 & 7 & 0 & \\\\ & 6 & 0 & 6 & 9 & \\\\ & 0 & 5 & 3 & 2 & \\\\ & 0 & 1 & 0 & 0 & \\ \end{bmatrix}

三、第二步 : 试指派 ( 找独立 0 元素 )

基于上一步的行列都有

0

元素的系数矩阵 ,

(b_{ij}) =\begin{bmatrix} & 0 & 13 & 7 & 0 & \\\\ & 6 & 0 & 6 & 9 & \\\\ & 0 & 5 & 3 & 2 & \\\\ & 0 & 1 & 0 & 0 & \\ \end{bmatrix}

进行试指派 ;

找出每行的独立

0

元素 ,

优先从唯一选择开始 ,

第

2

行只有

1

个

0

元素 , 该元素是独立

0

元素 ;

第

3

行只有

1

个

0

元素 , 该元素是独立

0

元素 ( 红色矩形框 ) , 位于第

1

列 ; 同时第

1

列中的其它

0

元素标记为废弃

0

元素 ( 绿色矩形框 );

第

1

行和第

4

行都有多个

0

元素 ;

然后从列里面找独立

0

元素 , 第

1

列和第

2

列都已经找到了

0

元素 , 这里看第

3

列和第

4

列 ;

第

3

列有独立

0

元素 ( 红色矩形框 ) ; 位于第

4

行 , 将第

4

行的其它

0

元素标记为废弃

0

元素 ( 绿色矩形框 ) ;

第

4

列有独立

0

元素 ( 红色矩形框 ) ; 位于第

1

行 , 将第

1

行的其它

0

元素标记为废弃

0

元素 ( 绿色矩形框 ) , 已经标记过了 , 不用再进行标记 ;

这里第一次指派就找到了最优解 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-01-14，如有侵权请联系 cloudcommunity@tencent.com 删除

工作

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

工作

登录后参与评论

0 条评论

热度