当前位置: article > 正文

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

作者：盐析白兔 | 2024-06-02 16:52:29

踩

匈牙利法

文章目录

一、使用匈牙利法求解下面的指派问题
二、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )
三、第二步 : 试指派 ( 找独立 0 元素 )
四、第二步 : 试指派 ( 打 √ )
五、第二步 : 试指派 ( 直线覆盖 )
五、第二步 : 试指派 ( 第二轮 )

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

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

	$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{matrix} 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{matrix}]

$\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}$

(c_{i j}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 79874512536974678116951199611 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

使每行都出现 $0$ 元素 : $c_{ij})$ 系数矩阵中 , 每行都减去该行最小元素 ;

第 $1$ 行减去最小值 $5$ ;
第 $2$ 行减去最小值 $7$ ;
第 $3$ 行减去最小值 $4$ ;
第 $4$ 行减去最小值 $3$ ;
第 $5$ 行减去最小值 $4$ ;

$(c_{ij}') =$

[\begin{matrix} 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{matrix}]

$\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}$

(c_{i j}^{'}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 2244005102400333426162537 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

此时发现有两列 , 第 $4$ 列 , 第 $5$ 列 , 没有 $0$ 元素 , 这两列每列都减去最小值 :

第 $4$ 列减去最小值 $1$ ;
第 $5$ 列减去最小值 $2$ ;

最终得到行列都有 $0$ 元素的系数矩阵 $b_{ij})$ :

$(b_{ij}) =$

[\begin{matrix} 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{matrix}]

$\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}$

(b_{i j}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 2244005102400332315040315 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

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

基于上一步的行列都有 $0$ 元素的系数矩阵 ,

$(b_{ij}) =$

[\begin{matrix} 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{matrix}]

$\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}$

(b_{i j}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 2244005102400332315040315 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

进行试指派 ;

找出每行的独立 $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{matrix} 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{matrix}]

$\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}$

(b_{i j}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1243006203300231314030305 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

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

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

再次进行试指派此时发现 , 试指派还是 $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{matrix} 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{matrix}]

$\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}$

(b_{i j}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0132006204300240203030306 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤

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

这个矩阵 $0$ 很多 , 选出 $5$ 个独立 $0$ 元素 , 成立的解有好多个 ;

如下指派 , 正好能找出 $5$ 个独立 $0$ 元素 ;
在这里插入图片描述

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/663521