一、克尼格定理

---

匈牙利法 主要用于解决指派问题 , 其主要依据是 克尼格定理 ;

指派问题 参考 【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 ) 博客 ;

克尼格定理 :

分配问题 效率矩阵 $[a_{ij}]$ 中 ,

每一行元素 中加上或减去一个常数 $u_i$ ,

每一列元素 中加上或减去一个常数 $v_j$ ,

得到新的效率矩阵 $[b_{ij}]$ ,

两个效率矩阵 $[a_{ij}]$ 与 $[b_{ij}]$ 分配问题的 最优解相同 ;

克尼格定理示例 : 指派问题 , 给 $4$ 个人指派 $4$ 个岗位 , 每个人在不同的岗位产生的利润不同 , 如何安排使得利润最高 ;

	$A$	$B$	$C$	$D$
甲	$85$	$92$	$73$	$90$
乙	$95$	$87$	$78$	$95$
丙	$82$	$83$	$79$	$90$
丁	$86$	$90$	$80$	$88$

给 甲 对应的行加上所有表格都加上 $5$ , 变为如下表格 ,

	$A$	$B$	$C$	$D$
甲	$90$	$97$	$78$	$95$
乙	$95$	$87$	$78$	$95$
丙	$82$	$83$	$79$	$90$
丁	$86$	$90$	$80$	$88$

甲 今天状态好 , 不管四个工作 , 哪个分配给 甲 , 其产生的利润都会增加 ;

最终计算出来的指派问题的最优解是不变的 ;

二、匈牙利法引入

---

给 甲乙丙丁 四人分配 $ABCD$ 四项工作 , 每人做每项工作的耗时如下 , 如何指派问题使得耗时最小 ;

	$A$	$B$	$C$	$D$
甲	$6$	$7$	$11$	$2$
乙	$4$	$5$	$9$	$8$
丙	$3$	$1$	$10$	$4$
丁	$5$	$9$	$8$	$2$

分派任务时 , 给每个人分配其所用时间最小的工作 ,

• 给 甲 分配 $D$ 任务 , 其只用 2 时间即可完成该任务 , 耗时最小 ;
• 给 乙 分配 $A$ 任务 , 其只用 4 时间即可完成该任务 , 耗时最小 ;
• 给 丙 分配 $B$ 任务 , 其只用 1 时间即可完成该任务 , 耗时最小 ;
• 给 丁 分配 $C$ 任务 , $ABD$ 任务已经分配给了其它人 , 只能给 丁 分配 $C$ 任务 ;

如果 为每个人选择了耗时最小的任务 , 正好位于不同行 , 不同列 , 那么当前的指派 , 就是该问题的 最优解 ;

但是上述示例中 , 给 丁 分配任务时 , 合适的任务都分配给了甲乙丙 , 只能分配 $C$ 任务 ;

这时就需要讨论给 丁 指派 $C$ 任务是否是最优的 ;

这里就需要 引入 匈牙利法 解决上述问题 ;

三、指派问题求解步骤

---

指派问题求解步骤 :

1 . 使行列出现 $0$ 元素 : 指派问题系数矩阵 $(c_{ij})$ 变换为 $(b_{ij})$ 系数矩阵 , 在 $(b_{ij})$ 矩阵中 每行 每列 都出现 $0$ 元素 ;

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

• 每列都出现 $0$ 元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ;

注意必须先变行 , 然后再变列 , 行列不能同时进行改变 ; 否则矩阵中会出现负数 , 该矩阵中 不能出现负数 ;

2 . 试指派 : 进行尝试指派 , 寻求最优解 ;

在 $(b_{ij})$ 系数矩阵 中找到尽可能多的 独立 $0$ 元素 , 如果能找到 $n$ 个独立 $0$ 元素 , 以这 $n$ 个独立 $0$ 元素对应解矩阵 $(x_{ij})$ 中的元素为 $1$ , 其余元素为 $0$ , 这样就得到最优解 ;

四、匈牙利法示例 1

---

1、第一步 : 使行列出现 $0$ 元素示例

上一篇博客 【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 ) 中的指派问题 :

	$A$	$B$	$C$	$D$
甲	$6$	$7$	$11$	$2$
乙	$4$	$5$	$9$	$8$
丙	$3$	$1$	$10$	$4$
丁	$5$	$9$	$8$	$2$

系数矩阵 $(c_{ij})=\left[\begin{array}{cccccc}& 6& 7& 11& 2& \\ & & & & & \\ & 4& 5& 9& 8& \\ & & & & & \\ & 3& 1& 10& 4& \\ & & & & & \\ & 5& 9& 8& 2& \end{array}\right]$

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

第 $1$ 行减去 $2$ ,
第 $2$ 行减去 $4$ ,
第 $3$ 行减去 $1$ ,
第 $4$ 行减去 $2$ ,

得到新的系数矩阵 系数矩阵 $\left[\begin{array}{cccccc}& 4& 5& 9& 0& \\ & & & & & \\ & 0& 1& 5& 4& \\ & & & & & \\ & 2& 0& 9& 3& \\ & & & & & \\ & 3& 7& 6& 0& \end{array}\right]$

每列都出现 $0$ 元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ; 观察矩阵后发现 , 只有第三列没有 $0$ 元素 , 这里将第 $3$ 列 , 都减去最小值 $5$ , 得到如下矩阵 :

$(b_{ij})=\left[\begin{array}{cccccc}& 4& 5& 4& 0& \\ & & & & & \\ & 0& 1& 0& 4& \\ & & & & & \\ & 2& 0& 4& 3& \\ & & & & & \\ & 3& 7& 1& 0& \end{array}\right]$

这样就得到每行每列都有 $0$ 元素的矩阵 ;

2、第二步 : 试指派操作示例 ( 方法一 :克尼格定理 )

在 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 ) 博客示例基础上 , 已经得到了行列都有 $0$ 元素的系数矩阵 :

$(b_{ij})=\left[\begin{array}{cccccc}& 4& 5& 4& 0& \\ & & & & & \\ & 0& 1& 0& 4& \\ & & & & & \\ & 2& 0& 4& 3& \\ & & & & & \\ & 3& 7& 1& 0& \end{array}\right]$

下面进行试指派操作 , 试指派就是找独立 $0$ 元素 , 独立 $0$ 元素就是位于不同行不同列的 $0$ 元素 ;

第 $1$ 行只有 $1$ 个 $0$ , 选第 $4$ 个 ; 每行每列只能选择 $1$ 个 , 第 $4$ 行第 $4$ 列的 $0$ 元素就不能再用了 ;

第 $3$ 行只有 $1$ 个 $0$ , 选第 $2$ 个 ;

第 $2$ 行有 $2$ 个 $0$ , 都可以选择 , 这里选择第 $1$ 个 ;

最终试指派结果 :

上面只找到了 $3$ 个独立的 $0$ 元素 , 应该找出 $4$ 个独立 $0$ 元素 ;

调整上述系数矩阵 $(b_{ij})$ , 每行每列同时增加或减去一个数 , 且不能出现负数 ;

第 $4$ 行都减去 $1$ , 得到如下矩阵 :

$(b_{ij})=\left[\begin{array}{cccccc}& 4& 5& 4& 0& \\ & & & & & \\ & 0& 1& 0& 4& \\ & & & & & \\ & 2& 0& 4& 3& \\ & & & & & \\ & 2& 6& 0& -1& \end{array}\right]$

第 $4$ 行第 $4$ 列出现了 $-1$ , 这里在将第 $4$ 列都加上 $1$ , 得到如下矩阵 :

$(b_{ij})=\left[\begin{array}{cccccc}& 4& 5& 4& 1& \\ & & & & & \\ & 0& 1& 0& 5& \\ & & & & & \\ & 2& 0& 4& 4& \\ & & & & & \\ & 2& 6& 0& 0& \end{array}\right]$

第一行此时没有独立的 $0$ 了 , 第一行再减去 $1$ , 得到如下矩阵 :

$(b_{ij})=\left[\begin{array}{cccccc}& 3& 4& 3& 0& \\ & & & & & \\ & 0& 1& 0& 5& \\ & & & & & \\ & 2& 0& 4& 4& \\ & & & & & \\ & 2& 6& 0& 0& \end{array}\right]$

再次进行试指派 , 找到了如下独立 $0$ 元素 ;

在上述没有找到 $4$ 个独立 $0$ 元素后 , 由于在第 $4$ 行没有找到 $0$ 元素 , 开始从第 $4$ 行进行调整 ,

调整时将非 $0$ 的最小值转为 $0$ , 这样本行就多出一个 $0$ , 以及负数 , 负数有需要再对应列加上一个值 , 保持矩阵中所有的值都是非负的 ;

3、打 √ ( 方法二 : 直线覆盖 )

分析 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第二步 : 试指派操作示例 ) 博客中试指派调整矩阵的原理 ;

下面的矩阵是完成第一步操作后 , 得到的行列都有 $0$ 的元素的系数矩阵 $(b_{ij})$ :

$(b_{ij})=\left[\begin{array}{cccccc}& 4& 5& 4& 0& \\ & & & & & \\ & 0& 1& 0& 4& \\ & & & & & \\ & 2& 0& 4& 3& \\ & & & & & \\ & 3& 7& 1& 0& \end{array}\right]$

试指派后的结果如下 :

定位一个没有独立 $0$ 元素的行 : 先对没有 $0$ 元素的行打钩 √ : 第 $4$ 行没有独立 $0$ 元素 , 第 $4$ 行打 √ ;

讨论第 $4$ 行 : 第 $4$ 行没有独立的 $0$ 元素 , 但是有废弃的 $0$ 元素 , 因为在第一步已经保证了每行每列都有 $0$ 元素 ;

在第 $4$ 行 $0$ 元素所在列 , 即第 $4$ 列 , 打 √ ;

讨论第 $4$ 列 : 上述打钩的列中 , 查看是否有 独立的 $0$ 元素 , 如果有对应的行就打 √ ;

第 $1$ 行有独立的 $0$ 元素 , 在第 $1$ 行位置打 √ ;

讨论第 $1$ 行 : 查看第 $1$ 行是否有废弃的 $0$ 元素 , 如果有就继续打 √ , 如果没有就停止 ;

第 $1$ 行没有废弃的 $0$ 元素 , 直接停止 ;

讨论 行 的时候讨论的是 废弃的 $0$ 元素 ,

讨论 列 的时候讨论的是 独立的 $0$ 元素 ;

4、直线覆盖 ( 方法二 : 直线覆盖 )

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

没有 打 √ 的行划线 , 打 √ 的列划线 , 三条线就将所有的 $0$ 元素覆盖了 ,

在没有被覆盖的元素中 , 找最小的元素 $1$ , 将没有覆盖的行 $-1$ , 覆盖的列 $+1$ ; 这里的情况是没有覆盖的行 ;

第 $1,4$ 行 $-1$ ,
第 $4$ 列 $+1$ ;

最终得到如下矩阵 :

$(b_{ij})=\left[\begin{array}{cccccc}& 3& 4& 3& 0& \\ & & & & & \\ & 0& 1& 0& 5& \\ & & & & & \\ & 2& 0& 4& 4& \\ & & & & & \\ & 2& 6& 0& 0& \end{array}\right]$

五、匈牙利法示例 2

---

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

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

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

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

$(c_{ij})=\left[\begin{array}{cccccc}& 2& 15& 13& 4& \\ & & & & & \\ & 10& 4& 14& 15& \\ & & & & & \\ & 9& 14& 16& 13& \\ & & & & & \\ & 7& 8& 11& 9& \end{array}\right]$

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

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

$(c_{ij}^{\prime })=\left[\begin{array}{cccccc}& 0& 13& 11& 2& \\ & & & & & \\ & 6& 0& 10& 11& \\ & & & & & \\ & 0& 5& 7& 4& \\ & & & & & \\ & 0& 1& 4& 2& \end{array}\right]$

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

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

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

$(b_{ij})=\left[\begin{array}{cccccc}& 0& 13& 7& 0& \\ & & & & & \\ & 6& 0& 6& 9& \\ & & & & & \\ & 0& 5& 3& 2& \\ & & & & & \\ & 0& 1& 0& 0& \end{array}\right]$

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

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

$(b_{ij})=\left[\begin{array}{cccccc}& 0& 13& 7& 0& \\ & & & & & \\ & 6& 0& 6& 9& \\ & & & & & \\ & 0& 5& 3& 2& \\ & & & & & \\ & 0& 1& 0& 0& \end{array}\right]$

进行试指派 ;

找出每行的独立 $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$ 元素 ( 绿色矩形框 ) , 已经标记过了 , 不用再进行标记 ;

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

六、匈牙利法示例 3

---

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

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

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

2、第一步 : 变换系数矩阵 ( 每行每列都出现 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]$

3、第二步 : 试指派 ( 找独立 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$ 元素 ;

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

本步骤的目的是使用最少的直线 , 将所有的 $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$ 元素 ;

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

本步骤的目的是使用最少的直线 , 将所有的 $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]$

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

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

再次进行试指派此时发现 , 试指派还是 $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$ 元素 ;