文章目录

• 一、克尼格定理
• 二、匈牙利法引入

一、克尼格定理

---

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

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

克尼格定理 :

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

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

总结

以上是生活随笔为你收集整理的【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。