一、问题引入
指派问题
有n项不同的工作或任务，需要n个人去完成，要求每人只完成一项工作。由于每人的知识、能力、经验等不同，故各人完成不同任务所需的时间不同。问应指派何人完成何项工作，使完成n项工作总耗时最少。这就是指派问题，指派问题也是整数规划问题。
最小化指派问题的数学模型
目标函数是最小化问题
第i个人只能完成一项工作
指定一项工作，只能由n个人中的一个人完成
0,1整数规划问题
匈牙利算法
指派问题是线性规划问题，是一类特殊的运输问题。但由于其数学结构的特殊性，可用比求解运输问题更简便的方法求解指派问题。这就是所谓的匈牙利算法，由匈牙利数学家狄.考尼格提出。
二、匈牙利算法的基本原理
将指派问题数学模型中效率系数cij排成一个nxn的矩阵，称为效率矩阵或价值系数矩阵，即
定理1 设指派问题的效率矩阵为C=(cij)(nxn),若该矩阵的某一行或列的各元素都减去同一个常数t，得到新的效率矩阵C’=c'ij(nxn),则C’为效率矩阵的新指派问题与原指派问题的最优解相同。但其最优解比原来最优值较少t文章来源：https://www.toymoban.com/news/detail-453879.html
证明 根据指派问题的定义文章来源地址https://www.toymoban.com/news/detail-453879.html
到了这里，关于指派问题与匈牙利算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
