- [2、第二步 : 试指派操作示例 ( 方法一 :克尼格定理 )](https://cloud.tencent.com/developer)
- [3、打 √ ( 方法二 : 直线覆盖 )](https://cloud.tencent.com/developer)
- [4、直线覆盖 ( 方法二 : 直线覆盖 )](https://cloud.tencent.com/developer)
匈牙利法 主要用于解决指派问题 , 其主要依据是 克尼格定理 ;
指派问题 参考 【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 ) 博客 ;
克尼格定理 :
分配问题 效率矩阵
中 ,
每一行元素 中加上或减去一个常数
,
每一列元素 中加上或减去一个常数
,
得到新的效率矩阵
,
两个效率矩阵
与
分配问题的 最优解相同 ;
克尼格定理示例 : 指派问题 , 给
个人指派
个岗位 , 每个人在不同的岗位产生的利润不同 , 如何安排使得利润最高 ;
| 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 |
甲
乙
丙
丁
给 甲 对应的行加上所有表格都加上
, 变为如下表格 ,
| 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 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 |
甲
乙
丙
丁
分派任务时 , 给每个人分配其所用时间最小的工作 ,
任务 , 其只用 2 时间即可完成该任务 , 耗时最小 ;
任务 , 其只用 4 时间即可完成该任务 , 耗时最小 ;
任务 , 其只用 1 时间即可完成该任务 , 耗时最小 ;
任务 ,
任务已经分配给了其它人 , 只能给 丁 分配
任务 ;
如果 为每个人选择了耗时最小的任务 , 正好位于不同行 , 不同列 , 那么当前的指派 , 就是该问题的 最优解 ;
但是上述示例中 , 给 丁 分配任务时 , 合适的任务都分配给了甲乙丙 , 只能分配
任务 ;
这时就需要讨论给 丁 指派
任务是否是最优的 ;
这里就需要 引入 匈牙利法 解决上述问题 ;
指派问题求解步骤 :
1 . 使行列出现
元素 : 指派问题系数矩阵
变换为
系数矩阵 , 在
矩阵中 每行 每列 都出现
元素 ;
元素 :
系数矩阵中 , 每行都 减去该行最小元素 ;
元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ;
注意必须先变行 , 然后再变列 , 行列不能同时进行改变 ; 否则矩阵中会出现负数 , 该矩阵中 不能出现负数 ;
2 . 试指派 : 进行尝试指派 , 寻求最优解 ;
在
系数矩阵 中找到尽可能多的 独立
元素 , 如果能找到
个独立
元素 , 以这
个独立
元素对应解矩阵
中的元素为
, 其余元素为
, 这样就得到最优解 ;
元素示例
上一篇博客 【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 ) 中的指派问题 :
| 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 |
甲
乙
丙
丁
系数矩阵
使每行都出现
元素 :
系数矩阵中 , 每行都 减去该行最小元素 ;
第
行减去
,
第
行减去
,
第
行减去
,
第
行减去
,
得到新的系数矩阵 系数矩阵
每列都出现
元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ; 观察矩阵后发现 , 只有第三列没有
元素 , 这里将第
列 , 都减去最小值
, 得到如下矩阵 :
这样就得到每行每列都有
元素的矩阵 ;
在 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 ) 博客示例基础上 , 已经得到了行列都有
元素的系数矩阵 :
下面进行试指派操作 , 试指派就是找独立
元素 , 独立
元素就是位于不同行不同列的
元素 ;
第
行只有
个
, 选第
个 ; 每行每列只能选择
个 , 第
行第
列的
元素就不能再用了 ;
第
行只有
个
, 选第
个 ;
第
行有
个
, 都可以选择 , 这里选择第
个 ;
最终试指派结果 :
上面只找到了
个独立的
元素 , 应该找出
个独立
元素 ;
调整上述系数矩阵
, 每行每列同时增加或减去一个数 , 且不能出现负数 ;
第
行都减去
, 得到如下矩阵 :
第
行第
列出现了
, 这里在将第
列都加上
, 得到如下矩阵 :
第一行此时没有独立的
了 , 第一行再减去
, 得到如下矩阵 :
再次进行试指派 , 找到了如下独立
元素 ;
在上述没有找到
个独立
元素后 , 由于在第
行没有找到
元素 , 开始从第
行进行调整 ,
调整时将非
的最小值转为
, 这样本行就多出一个
, 以及负数 , 负数有需要再对应列加上一个值 , 保持矩阵中所有的值都是非负的 ;
分析 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第二步 : 试指派操作示例 ) 博客中试指派调整矩阵的原理 ;
下面的矩阵是完成第一步操作后 , 得到的行列都有
的元素的系数矩阵
:
试指派后的结果如下 :
定位一个没有独立
元素的行 : 先对没有
元素的行打钩 √ : 第
行没有独立
元素 , 第
行打 √ ;
讨论第
行 : 第
行没有独立的
元素 , 但是有废弃的
元素 , 因为在第一步已经保证了每行每列都有
元素 ;
在第
行
元素所在列 , 即第
列 , 打 √ ;
讨论第
列 : 上述打钩的列中 , 查看是否有 独立的
元素 , 如果有对应的行就打 √ ;
第
行有独立的
元素 , 在第
行位置打 √ ;
讨论第
行 : 查看第
行是否有废弃的
元素 , 如果有就继续打 √ , 如果没有就停止 ;
第
行没有废弃的
元素 , 直接停止 ;
讨论 行 的时候讨论的是 废弃的
元素 ,
讨论 列 的时候讨论的是 独立的
元素 ;
打 √ 完毕 , 开始讨论覆盖 ,
没有 打 √ 的行划线 , 打 √ 的列划线 , 三条线就将所有的
元素覆盖了 ,
在没有被覆盖的元素中 , 找最小的元素
, 将没有覆盖的行
, 覆盖的列
; 这里的情况是没有覆盖的行 ;
第
行
,
第
列
;
最终得到如下矩阵 :
四人分别完成四项工作所用时间 :
| 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 |
甲
乙
丙
丁
先写出指派问题的系数矩阵 :
使每行都出现
元素 :
系数矩阵中 , 每行都 减去该行最小元素 ;
行减去最小值
;
行减去最小值
;
行减去最小值
;
行减去最小值
;
此时发现有两列 , 第
列 , 第
列 , 没有
元素 , 这两列每列都减去最小值 :
列减去最小值
;
列减去最小值
;
最终得到行列都有
元素的系数矩阵
:
基于上一步的行列都有
元素的系数矩阵 ,
进行试指派 ;
找出每行的独立
元素 ,
优先从唯一选择开始 ,
第
行只有
个
元素 , 该元素是独立
元素 ;
第
行只有
个
元素 , 该元素是独立
元素 ( 红色矩形框 ) , 位于第
列 ; 同时第
列中的其它
元素标记为 废弃
元素 ( 绿色矩形框 );
第
行和第
行都有多个
元素 ;
然后从列里面找独立
元素 , 第
列 和 第
列都已经找到了
元素 , 这里看 第
列 和 第
列 ;
第
列有 独立
元素 ( 红色矩形框 ) ; 位于第
行 , 将第
行的其它
元素标记为 废弃
元素 ( 绿色矩形框 ) ;
第
列有 独立
元素 ( 红色矩形框 ) ; 位于第
行 , 将第
行的其它
元素标记为 废弃
元素 ( 绿色矩形框 ) , 已经标记过了 , 不用再进行标记 ;
这里第一次指派就找到了最优解 ;
四人分别完成四项工作所用时间 :
| 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 |
甲
乙
丙
丁
戊
先写出指派问题的系数矩阵 :
使每行都出现
元素 :
系数矩阵中 , 每行都 减去该行最小元素 ;
行减去最小值
;
行减去最小值
;
行减去最小值
;
行减去最小值
;
行减去最小值
;
此时发现有两列 , 第
列 , 第
列 , 没有
元素 , 这两列每列都减去最小值 :
列减去最小值
;
列减去最小值
;
最终得到行列都有
元素的系数矩阵
:
基于上一步的行列都有
元素的系数矩阵 ,
进行试指派 ;
找出每行的独立
元素 ,
优先从唯一选择开始 ,
第
行只有
个
元素 , 该元素是独立
元素 ( 红色矩形框 ) , 位于第
列 ;
同时第
列中的其它
元素标记为 废弃
元素 ( 绿色矩形框 );
第
行只有
个
元素 , 该元素是独立
元素 ( 红色矩形框 ) , 位于第
列 ;
同时第
列中的其它
元素标记为 废弃
元素 ( 绿色矩形框 );
第
行中原来有两个
元素 , 有一个被标记为 废弃
元素 , 因此只剩下一个
元素 , 标记为独立
元素 ;
第
行没有独立
元素 , 第
行都有多个
元素 ;
然后从列里面找独立
元素 , 第
列都已经找到了
元素 , 这里看 第
列 ;
第
列有 独立
元素 ( 红色矩形框 ) ; 位于第
行 , 将第
行的其它
元素标记为 废弃
元素 ( 绿色矩形框 ) ;
这里只找到了
个独立
元素 , 红色矩形框中 ;
使用最少的直线 , 覆盖所有的
元素 ;
本步骤的目的是使用最少的直线 , 将所有的
元素都覆盖住 , 如果能一眼看出来最好 , 如果不能 , 就需要使用打钩的方法 ;
定位一个没有独立
元素的行 : 先对没有
元素的行打钩 √ : 第
行没有独立
元素 , 第
行打 √ ;
讨论第
行 : 第
行没有独立的
元素 , 但是有废弃的
元素 , 因为在第一步已经保证了每行每列都有
元素 ;
在第
行 的 废弃
元素所在列 , 即第
列 , 打 √ ;
讨论第
列 : 上述打钩的列中 , 查看是否有 独立的
元素 , 如果有对应的行就打 √ ;
第
行有独立的
元素 , 在第
行位置打 √ ;
讨论第
行 : 查看第
行是否有废弃的
元素 , 如果有就继续打 √ , 如果没有就停止 ;
第
行没有废弃的
元素 , 直接停止 ;
讨论 行 的时候讨论的是 废弃的
元素 ,
讨论 列 的时候讨论的是 独立的
元素 ;
本步骤的目的是使用最少的直线 , 将所有的
元素都覆盖住 , 如果能一眼看出来最好 , 如果不能 , 就需要使用打钩的方法 ;
打 √ 完毕 , 开始讨论覆盖 ,
没有 打 √ 的行划线 , 打 √ 的列划线 , 四条线就将所有的
元素覆盖了 ,
在没有被覆盖的元素中 , 找最小的元素
, 将该元素所在的没有覆盖的行
, 覆盖的列
;
第
行中的元素
, 第
列中的元素
;
最终得到如下矩阵 :
本质 : 没有覆盖的元素统一减去最小值 , 被覆盖的行列交叉值增加了该最小元素值 ;
再次进行试指派此时发现 , 试指派还是
个独立
元素 ,
先找有独立
元素的行 , 找到后 标记为 独立
元素 ( 红色矩形框 ) , 将对应列的
元素标记为废弃 ( 绿色矩形框 ) ;
然后找有独立
元素的列 ;
再次执行 打 √ ,
没有
元素的行为起点 :
将该行废弃
元素列打钩 , 有两个 :
将废弃
元素列中对应的 独立
元素 行 打钩 :
上述两行对应的 废弃
元素的列打钩 :
在上述打钩的列中 , 将独立
元素所在行打钩 :
直线覆盖 : 没打勾的行画一条直线 , 打钩的列画一条直线 ; 目的是使用最少的直线覆盖住所有的
;
在没有被覆盖的元素中 , 找最小的元素
, 将该最小元素所在的没有覆盖的行
, 覆盖的列
;
第
行中的元素
, 第
列中的元素
;
最终矩阵为 :
本质 : 没有覆盖的元素统一减去最小值 , 被覆盖的行列交叉值增加了该最小元素值 ;
这个矩阵
很多 , 选出
个独立
元素 , 成立的解有好多个 ;
如下指派 , 正好能找出
个独立
元素 ;