一、克尼格定理

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

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

克尼格定理 :

分配问题 效率矩阵 [ 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 任务是否是最优的 ;

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