- 一、克尼格定理
- 二、匈牙利法引入
匈牙利法 主要用于解决指派问题 , 其主要依据是 克尼格定理 ;
指派问题 参考 【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 ) 博客 ;
克尼格定理 :
分配问题 效率矩阵 [ 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 任务是否是最优的 ;
这里就需要 引入 匈牙利法 解决上述问题 ;
