【运筹学】指派问题、匈牙利法总结 ( 指派问题 | 克尼格定理 | 匈牙利法 | 行列出现 0 元素 | 试指派 | 打 √ | 直线覆盖 ) ★★★
一、克尼格定理、二、匈牙利法引入、三、指派问题求解步骤、四、匈牙利法示例 1、1、第一步 : 使行列出现 00 元素示例、2、第二步 : 试指派操作示例、3、打 √、4、直线覆盖、五、匈牙利法示例 2、六、匈牙利法示例 3、1、使用匈牙利法求解下面的指派问题、2、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )、3、第二步 : 试指派 ( 找独立 0 元素 )、4、第二步 : 试指派
一、克尼格定理
匈牙利法 主要用于解决指派问题 , 其主要依据是 克尼格定理 ;
指派问题 参考 【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 ) 博客 ;
克尼格定理 :
分配问题 效率矩阵 [ a i j ] [a_{ij}] [aij] 中 ,
每一行元素 中加上或减去一个常数 u i u_i ui ,
每一列元素 中加上或减去一个常数 v j v_j vj ,
得到新的效率矩阵 [ b i j ] [b_{ij}] [bij] ,
两个效率矩阵 [ a i j ] [a_{ij}] [aij] 与 [ b i j ] [b_{ij}] [bij] 分配问题的 最优解相同 ;
克尼格定理示例 : 指派问题 , 给 4 4 4 个人指派 4 4 4 个岗位 , 每个人在不同的岗位产生的利润不同 , 如何安排使得利润最高 ;
A A A | B B B | C C C | D D D | |
---|---|---|---|---|
甲 | 85 85 85 | 92 92 92 | 73 73 73 | 90 90 90 |
乙 | 95 95 95 | 87 87 87 | 78 78 78 | 95 95 95 |
丙 | 82 82 82 | 83 83 83 | 79 79 79 | 90 90 90 |
丁 | 86 86 86 | 90 90 90 | 80 80 80 | 88 88 88 |
给 甲 对应的行加上所有表格都加上 5 5 5 , 变为如下表格 ,
A A A | B B B | C C C | D D D | |
---|---|---|---|---|
甲 | 90 90 90 | 97 97 97 | 78 78 78 | 95 95 95 |
乙 | 95 95 95 | 87 87 87 | 78 78 78 | 95 95 95 |
丙 | 82 82 82 | 83 83 83 | 79 79 79 | 90 90 90 |
丁 | 86 86 86 | 90 90 90 | 80 80 80 | 88 88 88 |
甲 今天状态好 , 不管四个工作 , 哪个分配给 甲 , 其产生的利润都会增加 ;
最终计算出来的指派问题的最优解是不变的 ;
二、匈牙利法引入
给 甲乙丙丁 四人分配 A B C D ABCD ABCD 四项工作 , 每人做每项工作的耗时如下 , 如何指派问题使得耗时最小 ;
A A A | B B B | C C C | D D D | |
---|---|---|---|---|
甲 | 6 6 6 | 7 7 7 | 11 11 11 | 2 2 2 |
乙 | 4 4 4 | 5 5 5 | 9 9 9 | 8 8 8 |
丙 | 3 3 3 | 1 1 1 | 10 10 10 | 4 4 4 |
丁 | 5 5 5 | 9 9 9 | 8 8 8 | 2 2 2 |
分派任务时 , 给每个人分配其所用时间最小的工作 ,
- 给 甲 分配 D D D 任务 , 其只用 2 时间即可完成该任务 , 耗时最小 ;
- 给 乙 分配 A A A 任务 , 其只用 4 时间即可完成该任务 , 耗时最小 ;
- 给 丙 分配 B B B 任务 , 其只用 1 时间即可完成该任务 , 耗时最小 ;
- 给 丁 分配 C C C 任务 , A B D ABD ABD 任务已经分配给了其它人 , 只能给 丁 分配 C C C 任务 ;
如果 为每个人选择了耗时最小的任务 , 正好位于不同行 , 不同列 , 那么当前的指派 , 就是该问题的 最优解 ;
但是上述示例中 , 给 丁 分配任务时 , 合适的任务都分配给了甲乙丙 , 只能分配 C C C 任务 ;
这时就需要讨论给 丁 指派 C C C 任务是否是最优的 ;
这里就需要 引入 匈牙利法 解决上述问题 ;
三、指派问题求解步骤
指派问题求解步骤 :
1 . 使行列出现 0 0 0 元素 : 指派问题系数矩阵 ( c i j ) (c_{ij}) (cij) 变换为 ( b i j ) (b_{ij}) (bij) 系数矩阵 , 在 ( b i j ) (b_{ij}) (bij) 矩阵中 每行 每列 都出现 0 0 0 元素 ;
-
每行都出现 0 0 0 元素 : ( c i j ) (c_{ij}) (cij) 系数矩阵中 , 每行都 减去该行最小元素 ;
-
每列都出现 0 0 0 元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ;
注意必须先变行 , 然后再变列 , 行列不能同时进行改变 ; 否则矩阵中会出现负数 , 该矩阵中 不能出现负数 ;
2 . 试指派 : 进行尝试指派 , 寻求最优解 ;
在 ( b i j ) (b_{ij}) (bij) 系数矩阵 中找到尽可能多的 独立 0 0 0 元素 , 如果能找到 n n n 个独立 0 0 0 元素 , 以这 n n n 个独立 0 0 0 元素对应解矩阵 ( x i j ) (x_{ij}) (xij) 中的元素为 1 1 1 , 其余元素为 0 0 0 , 这样就得到最优解 ;
四、匈牙利法示例 1
1、第一步 : 使行列出现 0 0 0 元素示例
上一篇博客 【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 ) 中的指派问题 :
A A A | B B B | C C C | D D D | |
---|---|---|---|---|
甲 | 6 6 6 | 7 7 7 | 11 11 11 | 2 2 2 |
乙 | 4 4 4 | 5 5 5 | 9 9 9 | 8 8 8 |
丙 | 3 3 3 | 1 1 1 | 10 10 10 | 4 4 4 |
丁 | 5 5 5 | 9 9 9 | 8 8 8 | 2 2 2 |
系数矩阵 ( c i j ) = [ 6 7 11 2 4 5 9 8 3 1 10 4 5 9 8 2 ] (c_{ij}) =\begin{bmatrix} & 6 & 7 & 11 & 2 & \\\\ & 4 & 5 & 9 & 8 & \\\\ & 3 & 1 & 10 & 4 & \\\\ & 5 & 9 & 8 & 2 & \\ \end{bmatrix} (cij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡643575191191082842⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
使每行都出现 0 0 0 元素 : ( c i j ) (c_{ij}) (cij) 系数矩阵中 , 每行都 减去该行最小元素 ;
第
1
1
1 行减去
2
2
2 ,
第
2
2
2 行减去
4
4
4 ,
第
3
3
3 行减去
1
1
1 ,
第
4
4
4 行减去
2
2
2 ,
得到新的系数矩阵 系数矩阵 [ 4 5 9 0 0 1 5 4 2 0 9 3 3 7 6 0 ] \begin{bmatrix} & 4 & 5 & 9 & 0 & \\\\ & 0 & 1 & 5 & 4 & \\\\ & 2 & 0 & 9 & 3 & \\\\ & 3 & 7 & 6 & 0 & \\ \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡4023510795960430⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
每列都出现 0 0 0 元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ; 观察矩阵后发现 , 只有第三列没有 0 0 0 元素 , 这里将第 3 3 3 列 , 都减去最小值 5 5 5 , 得到如下矩阵 :
( b i j ) = [ 4 5 4 0 0 1 0 4 2 0 4 3 3 7 1 0 ] (b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 3 & 7 & 1 & 0 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡4023510740410430⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
这样就得到每行每列都有 0 0 0 元素的矩阵 ;
2、第二步 : 试指派操作示例 ( 方法一 :克尼格定理 )
在 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 ) 博客示例基础上 , 已经得到了行列都有 0 0 0 元素的系数矩阵 :
( b i j ) = [ 4 5 4 0 0 1 0 4 2 0 4 3 3 7 1 0 ] (b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 3 & 7 & 1 & 0 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡4023510740410430⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
下面进行试指派操作 , 试指派就是找独立 0 0 0 元素 , 独立 0 0 0 元素就是位于不同行不同列的 0 0 0 元素 ;
第 1 1 1 行只有 1 1 1 个 0 0 0 , 选第 4 4 4 个 ; 每行每列只能选择 1 1 1 个 , 第 4 4 4 行第 4 4 4 列的 0 0 0 元素就不能再用了 ;
第 3 3 3 行只有 1 1 1 个 0 0 0 , 选第 2 2 2 个 ;
第 2 2 2 行有 2 2 2 个 0 0 0 , 都可以选择 , 这里选择第 1 1 1 个 ;
最终试指派结果 :
上面只找到了 3 3 3 个独立的 0 0 0 元素 , 应该找出 4 4 4 个独立 0 0 0 元素 ;
调整上述系数矩阵 ( b i j ) (b_{ij}) (bij) , 每行每列同时增加或减去一个数 , 且不能出现负数 ;
第 4 4 4 行都减去 1 1 1 , 得到如下矩阵 :
( b i j ) = [ 4 5 4 0 0 1 0 4 2 0 4 3 2 6 0 − 1 ] (b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 2 & 6 & 0 & -1 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡402251064040043−1⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
第 4 4 4 行第 4 4 4 列出现了 − 1 -1 −1 , 这里在将第 4 4 4 列都加上 1 1 1 , 得到如下矩阵 :
( b i j ) = [ 4 5 4 1 0 1 0 5 2 0 4 4 2 6 0 0 ] (b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 1 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡4022510640401540⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
第一行此时没有独立的 0 0 0 了 , 第一行再减去 1 1 1 , 得到如下矩阵 :
( b i j ) = [ 3 4 3 0 0 1 0 5 2 0 4 4 2 6 0 0 ] (b_{ij}) = \begin{bmatrix} & 3 & 4 & 3 & 0 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡3022410630400540⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
再次进行试指派 , 找到了如下独立 0 0 0 元素 ;
在上述没有找到 4 4 4 个独立 0 0 0 元素后 , 由于在第 4 4 4 行没有找到 0 0 0 元素 , 开始从第 4 4 4 行进行调整 ,
调整时将非 0 0 0 的最小值转为 0 0 0 , 这样本行就多出一个 0 0 0 , 以及负数 , 负数有需要再对应列加上一个值 , 保持矩阵中所有的值都是非负的 ;
3、打 √ ( 方法二 : 直线覆盖 )
分析 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第二步 : 试指派操作示例 ) 博客中试指派调整矩阵的原理 ;
下面的矩阵是完成第一步操作后 , 得到的行列都有 0 0 0 的元素的系数矩阵 ( b i j ) (b_{ij}) (bij) :
( b i j ) = [ 4 5 4 0 0 1 0 4 2 0 4 3 3 7 1 0 ] (b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 3 & 7 & 1 & 0 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡4023510740410430⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
试指派后的结果如下 :
定位一个没有独立 0 0 0 元素的行 : 先对没有 0 0 0 元素的行打钩 √ : 第 4 4 4 行没有独立 0 0 0 元素 , 第 4 4 4 行打 √ ;
讨论第 4 4 4 行 : 第 4 4 4 行没有独立的 0 0 0 元素 , 但是有废弃的 0 0 0 元素 , 因为在第一步已经保证了每行每列都有 0 0 0 元素 ;
在第 4 4 4 行 0 0 0 元素所在列 , 即第 4 4 4 列 , 打 √ ;
讨论第 4 4 4 列 : 上述打钩的列中 , 查看是否有 独立的 0 0 0 元素 , 如果有对应的行就打 √ ;
第 1 1 1 行有独立的 0 0 0 元素 , 在第 1 1 1 行位置打 √ ;
讨论第 1 1 1 行 : 查看第 1 1 1 行是否有废弃的 0 0 0 元素 , 如果有就继续打 √ , 如果没有就停止 ;
第 1 1 1 行没有废弃的 0 0 0 元素 , 直接停止 ;
讨论 行 的时候讨论的是 废弃的 0 0 0 元素 ,
讨论 列 的时候讨论的是 独立的 0 0 0 元素 ;
4、直线覆盖 ( 方法二 : 直线覆盖 )
打 √ 完毕 , 开始讨论覆盖 ,
没有 打 √ 的行划线 , 打 √ 的列划线 , 三条线就将所有的 0 0 0 元素覆盖了 ,
在没有被覆盖的元素中 , 找最小的元素 1 1 1 , 将没有覆盖的行 − 1 -1 −1 , 覆盖的列 + 1 +1 +1 ; 这里的情况是没有覆盖的行 ;
第
1
,
4
1,4
1,4 行
−
1
-1
−1 ,
第
4
4
4 列
+
1
+1
+1 ;
最终得到如下矩阵 :
( b i j ) = [ 3 4 3 0 0 1 0 5 2 0 4 4 2 6 0 0 ] (b_{ij}) = \begin{bmatrix} & 3 & 4 & 3 & 0 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡3022410630400540⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
五、匈牙利法示例 2
四人分别完成四项工作所用时间 :
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 |
1、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )
先写出指派问题的系数矩阵 :
( c i j ) = [ 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 ] (c_{ij}) =\begin{bmatrix} & 2 & 15 & 13 & 4 & \\\\ & 10 & 4 & 14 & 15 & \\\\ & 9 & 14 & 16 & 13 & \\\\ & 7 & 8 & 11 & 9 & \\ \end{bmatrix} (cij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡2109715414813141611415139⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
使每行都出现 0 0 0 元素 : ( c i j ) (c_{ij}) (cij) 系数矩阵中 , 每行都 减去该行最小元素 ;
- 第 1 1 1 行减去最小值 2 2 2 ;
- 第 2 2 2 行减去最小值 4 4 4 ;
- 第 3 3 3 行减去最小值 9 9 9 ;
- 第 4 4 4 行减去最小值 7 7 7 ;
( c i j ′ ) = [ 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 ] (c_{ij}') =\begin{bmatrix} & 0 & 13 & 11 & 2 & \\\\ & 6 & 0 & 10 & 11 & \\\\ & 0 & 5 & 7 & 4 & \\\\ & 0 & 1 & 4 & 2 & \\ \end{bmatrix} (cij′)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡06001305111107421142⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
此时发现有两列 , 第 4 4 4 列 , 第 5 5 5 列 , 没有 0 0 0 元素 , 这两列每列都减去最小值 :
- 第 3 3 3 列减去最小值 4 4 4 ;
- 第 4 4 4 列减去最小值 2 2 2 ;
最终得到行列都有 0 0 0 元素的系数矩阵 ( b i j ) (b_{ij}) (bij) :
( b i j ) = [ 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 ] (b_{ij}) =\begin{bmatrix} & 0 & 13 & 7 & 0 & \\\\ & 6 & 0 & 6 & 9 & \\\\ & 0 & 5 & 3 & 2 & \\\\ & 0 & 1 & 0 & 0 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡06001305176300920⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
2、第二步 : 试指派 ( 找独立 0 元素 )
基于上一步的行列都有 0 0 0 元素的系数矩阵 ,
( b i j ) = [ 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 ] (b_{ij}) =\begin{bmatrix} & 0 & 13 & 7 & 0 & \\\\ & 6 & 0 & 6 & 9 & \\\\ & 0 & 5 & 3 & 2 & \\\\ & 0 & 1 & 0 & 0 & \\ \end{bmatrix} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡06001305176300920⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
进行试指派 ;
找出每行的独立 0 0 0 元素 ,
优先从唯一选择开始 ,
第 2 2 2 行只有 1 1 1 个 0 0 0 元素 , 该元素是独立 0 0 0 元素 ;
第 3 3 3 行只有 1 1 1 个 0 0 0 元素 , 该元素是独立 0 0 0 元素 ( 红色矩形框 ) , 位于第 1 1 1 列 ; 同时第 1 1 1 列中的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 );
第 1 1 1 行和第 4 4 4 行都有多个 0 0 0 元素 ;
然后从列里面找独立 0 0 0 元素 , 第 1 1 1 列 和 第 2 2 2 列都已经找到了 0 0 0 元素 , 这里看 第 3 3 3 列 和 第 4 4 4 列 ;
第 3 3 3 列有 独立 0 0 0 元素 ( 红色矩形框 ) ; 位于第 4 4 4 行 , 将第 4 4 4 行的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 ) ;
第 4 4 4 列有 独立 0 0 0 元素 ( 红色矩形框 ) ; 位于第 1 1 1 行 , 将第 1 1 1 行的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 ) , 已经标记过了 , 不用再进行标记 ;
这里第一次指派就找到了最优解 ;
六、匈牙利法示例 3
1、使用匈牙利法求解下面的指派问题
四人分别完成四项工作所用时间 :
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 |
2、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )
先写出指派问题的系数矩阵 :
( c i j ) = [ 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 ] (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} (cij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡79874512536974678116951199611⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
使每行都出现 0 0 0 元素 : ( c i j ) (c_{ij}) (cij) 系数矩阵中 , 每行都 减去该行最小元素 ;
- 第 1 1 1 行减去最小值 5 5 5 ;
- 第 2 2 2 行减去最小值 7 7 7 ;
- 第 3 3 3 行减去最小值 4 4 4 ;
- 第 4 4 4 行减去最小值 3 3 3 ;
- 第 5 5 5 行减去最小值 4 4 4 ;
( c i j ′ ) = [ 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 ] (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} (cij′)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡2244005102400333426162537⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
此时发现有两列 , 第 4 4 4 列 , 第 5 5 5 列 , 没有 0 0 0 元素 , 这两列每列都减去最小值 :
- 第 4 4 4 列减去最小值 1 1 1 ;
- 第 5 5 5 列减去最小值 2 2 2 ;
最终得到行列都有 0 0 0 元素的系数矩阵 ( b i j ) (b_{ij}) (bij) :
( b i j ) = [ 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 ] (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} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡2244005102400332315040315⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
3、第二步 : 试指派 ( 找独立 0 元素 )
基于上一步的行列都有 0 0 0 元素的系数矩阵 ,
( b i j ) = [ 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 ] (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} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡2244005102400332315040315⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
进行试指派 ;
找出每行的独立 0 0 0 元素 ,
优先从唯一选择开始 ,
第 1 1 1 行只有 1 1 1 个 0 0 0 元素 , 该元素是独立 0 0 0 元素 ( 红色矩形框 ) , 位于第 2 2 2 列 ;
同时第 2 2 2 列中的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 );
第 3 3 3 行只有 1 1 1 个 0 0 0 元素 , 该元素是独立 0 0 0 元素 ( 红色矩形框 ) , 位于第 3 3 3 列 ;
同时第 3 3 3 列中的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 );
第 2 2 2 行中原来有两个 0 0 0 元素 , 有一个被标记为 废弃 0 0 0 元素 , 因此只剩下一个 0 0 0 元素 , 标记为独立 0 0 0 元素 ;
第 4 4 4 行没有独立 0 0 0 元素 , 第 5 5 5 行都有多个 0 0 0 元素 ;
然后从列里面找独立 0 0 0 元素 , 第 2 , 3 , 5 2,3,5 2,3,5 列都已经找到了 0 0 0 元素 , 这里看 第 1 , 4 1,4 1,4 列 ;
第 1 1 1 列有 独立 0 0 0 元素 ( 红色矩形框 ) ; 位于第 5 5 5 行 , 将第 5 5 5 行的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 ) ;
这里只找到了 4 4 4 个独立 0 0 0 元素 , 红色矩形框中 ;
使用最少的直线 , 覆盖所有的 0 0 0 元素 ;
4、第二步 : 试指派 ( 打 √ )
本步骤的目的是使用最少的直线 , 将所有的 0 0 0 元素都覆盖住 , 如果能一眼看出来最好 , 如果不能 , 就需要使用打钩的方法 ;
定位一个没有独立 0 0 0 元素的行 : 先对没有 0 0 0 元素的行打钩 √ : 第 4 4 4 行没有独立 0 0 0 元素 , 第 4 4 4 行打 √ ;
讨论第 4 4 4 行 : 第 4 4 4 行没有独立的 0 0 0 元素 , 但是有废弃的 0 0 0 元素 , 因为在第一步已经保证了每行每列都有 0 0 0 元素 ;
在第 4 4 4 行 的 废弃 0 0 0 元素所在列 , 即第 2 2 2 列 , 打 √ ;
讨论第 2 2 2 列 : 上述打钩的列中 , 查看是否有 独立的 0 0 0 元素 , 如果有对应的行就打 √ ;
第 1 1 1 行有独立的 0 0 0 元素 , 在第 1 1 1 行位置打 √ ;
讨论第 1 1 1 行 : 查看第 1 1 1 行是否有废弃的 0 0 0 元素 , 如果有就继续打 √ , 如果没有就停止 ;
第 1 1 1 行没有废弃的 0 0 0 元素 , 直接停止 ;
讨论 行 的时候讨论的是 废弃的 0 0 0 元素 ,
讨论 列 的时候讨论的是 独立的 0 0 0 元素 ;
5、第二步 : 试指派 ( 直线覆盖 )
本步骤的目的是使用最少的直线 , 将所有的 0 0 0 元素都覆盖住 , 如果能一眼看出来最好 , 如果不能 , 就需要使用打钩的方法 ;
打 √ 完毕 , 开始讨论覆盖 ,
没有 打 √ 的行划线 , 打 √ 的列划线 , 四条线就将所有的 0 0 0 元素覆盖了 ,
在没有被覆盖的元素中 , 找最小的元素 1 1 1 , 将该元素所在的没有覆盖的行 − 1 -1 −1 , 覆盖的列 + 1 +1 +1 ;
第 1 , 4 1, 4 1,4 行中的元素 − 1 -1 −1, 第 2 2 2 列中的元素 + 1 +1 +1 ;
最终得到如下矩阵 :
( b i j ) = [ 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 ] (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} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡1243006203300231314030305⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
本质 : 没有覆盖的元素统一减去最小值 , 被覆盖的行列交叉值增加了该最小元素值 ;
6、第二步 : 试指派 ( 第二轮 )
再次进行试指派此时发现 , 试指派还是 4 4 4 个独立 0 0 0 元素 ,
先找有独立 0 0 0 元素的行 , 找到后 标记为 独立 0 0 0 元素 ( 红色矩形框 ) , 将对应列的 0 0 0 元素标记为废弃 ( 绿色矩形框 ) ;
然后找有独立 0 0 0 元素的列 ;
再次执行 打 √ ,
没有 0 0 0 元素的行为起点 :
将该行废弃 0 0 0 元素列打钩 , 有两个 :
将废弃 0 0 0 元素列中对应的 独立 0 0 0 元素 行 打钩 :
上述两行对应的 废弃 0 0 0 元素的列打钩 :
在上述打钩的列中 , 将独立 0 0 0 元素所在行打钩 :
直线覆盖 : 没打勾的行画一条直线 , 打钩的列画一条直线 ; 目的是使用最少的直线覆盖住所有的 0 0 0 ;
在没有被覆盖的元素中 , 找最小的元素 1 1 1 , 将该最小元素所在的没有覆盖的行 − 1 -1 −1 , 覆盖的列 + 1 +1 +1 ;
第 1 , 2 , 3 , 4 1, 2,3,4 1,2,3,4 行中的元素 − 1 -1 −1, 第 2 , 3 , 4 2,3,4 2,3,4 列中的元素 + 1 +1 +1 ;
最终矩阵为 :
( b i j ) = [ 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 ] (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} (bij)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡0132006204300240203030306⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
本质 : 没有覆盖的元素统一减去最小值 , 被覆盖的行列交叉值增加了该最小元素值 ;
这个矩阵 0 0 0 很多 , 选出 5 5 5 个独立 0 0 0 元素 , 成立的解有好多个 ;
如下指派 , 正好能找出
5
5
5 个独立
0
0
0 元素 ;
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)