文章目录

• 一、使用匈牙利法求解下面的指派问题
• 二、第一步 : 变换系数矩阵 ( 每行每列都出现 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})=\left[\begin{array}{ccccccc}& 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{array}\right]$

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

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

$(c_{ij}^{\prime })=\left[\begin{array}{ccccccc}& 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{array}\right]$

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

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

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

$(b_{ij})=\left[\begin{array}{ccccccc}& 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{array}\right]$

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

---

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

$(b_{ij})=\left[\begin{array}{ccccccc}& 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{array}\right]$

进行试指派 ;

找出每行的独立 $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})=\left[\begin{array}{ccccccc}& 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{array}\right]$

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

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

---

再次进行试指派此时发现 , 试指派还是 $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})=\left[\begin{array}{ccccccc}& 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{array}\right]$

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

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

如下指派 , 正好能找出 $5$ 个独立 $0$ 元素 ;

总结

以上是生活随笔为你收集整理的【运筹学】匈牙利法 ( 匈牙利法示例 2 | 第一步 : 变换系数矩阵 | 第二步 : 试指派 | 行列打√ | 直线覆盖 | 第二轮试指派 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。