【运筹学】匈牙利法 ( 匈牙利法示例 2 | 第一步 : 变换系数矩阵 | 第二步 : 试指派 | 行列打√ | 直线覆盖 | 第二轮试指派 )

韩曙亮

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

1.2K0

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

文章目录

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

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

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

A

B

C

D

甲

7

15

13

4

乙

9

4

14

15

丙

8

14

16

13

丁

7

8

11

9

戊

4

8

11

9

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

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

(c_{ij}) =\begin{bmatrix} & 7 & 5 & 9 & 8 & 11 & \\\\ & 9 & 12 & 7 & 11 & 9 & \\\\ & 8 & 5 & 4 & 6 & 9 & \\\\ & 7 & 3 & 6 & 9 & 6 & \\\\ & 4 & 6 & 7 & 5 & 11 & \\ \end{bmatrix}

使每行都出现

0

元素 :

(c_{ij})

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

第

1

行减去最小值

5

;

第

2

行减去最小值

7

;

第

3

行减去最小值

4

;

第

4

行减去最小值

3

;

第

5

行减去最小值

4

;

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

此时发现有两列 , 第

4

列 , 第

5

列 , 没有

0

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

第

4

列减去最小值

1

;

第

5

列减去最小值

2

;

最终得到行列都有

0

元素的系数矩阵

(b_{ij})

:

(b_{ij}) =\begin{bmatrix} & 2 & 0 & 4 & 2 & 4 & \\\\ & 2 & 5 & 0 & 3 & 0 & \\\\ & 4 & 1 & 0 & 1 & 3 & \\\\ & 4 & 0 & 3 & 5 & 1 & \\\\ & 0 & 2 & 3 & 0 & 5 & \\ \end{bmatrix}

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

基于上一步的行列都有

0

元素的系数矩阵 ,

(b_{ij}) =\begin{bmatrix} & 2 & 0 & 4 & 2 & 4 & \\\\ & 2 & 5 & 0 & 3 & 0 & \\\\ & 4 & 1 & 0 & 1 & 3 & \\\\ & 4 & 0 & 3 & 5 & 1 & \\\\ & 0 & 2 & 3 & 0 & 5 & \\ \end{bmatrix}

进行试指派 ;

找出每行的独立

0

元素 ,

优先从唯一选择开始 ,

第

1

行只有

1

个

0

元素 , 该元素是独立

0

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

2

列 ;

同时第

2

列中的其它

0

元素标记为废弃

0

元素 ( 绿色矩形框 );

第

3

行只有

1

个

0

元素 , 该元素是独立

0

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

3

列 ;

同时第

3

列中的其它

0

元素标记为废弃

0

元素 ( 绿色矩形框 );

第

2

行中原来有两个

0

元素 , 有一个被标记为废弃

0

元素 , 因此只剩下一个

0

元素 , 标记为独立

0

元素 ;

第

4

行没有独立

0

元素 , 第

5

行都有多个

0

元素 ;

然后从列里面找独立

0

元素 , 第

2,3,5

列都已经找到了

0

元素 , 这里看第

1,4

列 ;

第

1

列有独立

0

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

5

行 , 将第

5

行的其它

0

元素标记为废弃

0

元素 ( 绿色矩形框 ) ;

这里只找到了

4

个独立

0

元素 , 红色矩形框中 ;

使用最少的直线 , 覆盖所有的

0

元素 ;

四、第二步 : 试指派 ( 打 √ )

本步骤的目的是使用最少的直线 , 将所有的

0

元素都覆盖住 , 如果能一眼看出来最好 , 如果不能 , 就需要使用打钩的方法 ;

定位一个没有独立

0

元素的行 : 先对没有

0

元素的行打钩 √ : 第

4

行没有独立

0

元素 , 第

4

行打 √ ;

讨论第

4

行 : 第

4

行没有独立的

0

元素 , 但是有废弃的

0

元素 , 因为在第一步已经保证了每行每列都有

0

元素 ;

在第

4

行的废弃

0

元素所在列 , 即第

2

列 , 打 √ ;

讨论第

2

列 : 上述打钩的列中 , 查看是否有独立的

0

元素 , 如果有对应的行就打 √ ;

第

1

行有独立的

0

元素 , 在第

1

行位置打 √ ;

讨论第

1

行 : 查看第

1

行是否有废弃的

0

元素 , 如果有就继续打 √ , 如果没有就停止 ;

第

1

行没有废弃的

0

元素 , 直接停止 ;

讨论行的时候讨论的是废弃的

0

元素 ,

讨论列的时候讨论的是独立的

0

元素 ;

五、第二步 : 试指派 ( 直线覆盖 )

本步骤的目的是使用最少的直线 , 将所有的

0

元素都覆盖住 , 如果能一眼看出来最好 , 如果不能 , 就需要使用打钩的方法 ;

打 √ 完毕 , 开始讨论覆盖 ,

没有打 √ 的行划线 , 打 √ 的列划线 , 四条线就将所有的

0

元素覆盖了 ,

在没有被覆盖的元素中 , 找最小的元素

1

, 将该元素所在的没有覆盖的行

-1

, 覆盖的列

+1

;

第

1, 4

行中的元素

-1

, 第

2

列中的元素

+1

;

最终得到如下矩阵 :

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

本质 : 没有覆盖的元素统一减去最小值 , 被覆盖的行列交叉值增加了该最小元素值 ;

五、第二步 : 试指派 ( 第二轮 )

再次进行试指派此时发现 , 试指派还是

4

个独立

0

元素 ,

先找有独立

0

元素的行 , 找到后标记为独立

0

元素 ( 红色矩形框 ) , 将对应列的

0

元素标记为废弃 ( 绿色矩形框 ) ;

然后找有独立

0

元素的列 ;

再次执行打 √ ,

没有

0

元素的行为起点 :

将该行废弃

0

元素列打钩 , 有两个 :

将废弃

0

元素列中对应的独立

0

元素行打钩 :

上述两行对应的废弃

0

元素的列打钩 :

在上述打钩的列中 , 将独立

0

元素所在行打钩 :

直线覆盖 : 没打勾的行画一条直线 , 打钩的列画一条直线 ; 目的是使用最少的直线覆盖住所有的

0

;

在没有被覆盖的元素中 , 找最小的元素

1

, 将该最小元素所在的没有覆盖的行

-1

, 覆盖的列

+1

;

第

1, 2,3,4

行中的元素

-1

, 第

2,3,4

列中的元素

+1

;

最终矩阵为 :

(b_{ij}) =\begin{bmatrix} & 0 & 0 & 3 & 0 & 3 & \\\\ & 1 & 6 & 0 & 2 & 0 & \\\\ & 3 & 2 & 0 & 0 & 3 & \\\\ & 2 & 0 & 2 & 3 & 0 & \\\\ & 0 & 4 & 4 & 0 & 6 & \\ \end{bmatrix}

本质 : 没有覆盖的元素统一减去最小值 , 被覆盖的行列交叉值增加了该最小元素值 ;

这个矩阵

0

很多 , 选出

5

个独立

0

元素 , 成立的解有好多个 ;

如下指派 , 正好能找出

5

个独立

0

元素 ;

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

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

工作

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

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

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

工作

登录后参与评论

0 条评论

热度