资源描述：
《浅析指派问题的匈牙利解法成稿》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、洛阳师范学院本科毕业论文浅析指派问题的匈牙利解法胡小芹数学科学学院数学与应用数学学号:040414057指导教师:苏孟龙摘要:对于指派问题,可以利用许多理论进行建模并加以解决,但匈牙利解法是解决指派问题的一种非常简单有效的方法,并且可以解决多种形式的指派问题,但匈牙利算法本身存在着一些问题,本文主要介绍了匈牙利算法的基本思想,基本步骤,以及它的改进方法.在匈牙利算法的基础上,本文还介绍了两种更简便实用的寻找独立零元素的方法——最小零元素消耗法和对角线法.关键词:指派问题;匈牙利解法;最小零元素消耗法;对角线法0引言在现实生活中经常会遇到把几个任务
2、分派给几个不同的对象去完成,由于每个对象的条件不同,完成任务的效率和效益亦不同.指派问题的目标就是如何分派使所消耗的总资源最少（或总效益最优）,如给工人分派工作,给车辆分配道路,给工人分配机床等等,同时许多网络问题（如旅行问题,任务分配问题,运输问题等）,都可以演化成指派问题来解决.在现实生活中,指派问题是十分常见的问题,而匈牙利解法是解决指派问题的一种非常简单有效的方法.本文主要介绍匈牙利解法的基本原理及思想,解题步骤,不足与改进,以使匈牙利法更能有效地解决指派问题.1指派问题及其数学模型指派问题是指由项任务,需要个人来承担,每人只能承担一项任
3、务,且每项任务只能有一人来承担,由于各人的专长不同,各人完成的任务不同,导致其效率也各不相同.因此,就产生怎样科学地指派任务,才能使完成各项任务所消耗的总资源最少（或总成本最低等）,由于不同,指派问题可分为以下三种情况:18洛阳师范学院本科毕业论文第一、当时,即为每人指派一项任务.第二、当时,即任务数〉人数,这时可虚设个人构成的效率矩阵,并且这个人在执行这项任务时的效率应该是效率最高.第三、当时,即配置人数〉任务数,这时应虚设项任务,并且这个人在执行这项任务时的成本最低.通过虚设任务或人,指派问题的效率矩阵都可以转化成方阵.匈牙利解法要求指派问题
4、最小化,其数学模型为设用表示指派第个人去完成第项任务时所用的时间,定义决策变量则问题可转化为0-1线性规划问题:如果指派问题要求的是最大化问题如,则可以转化为最小化问题,一般方法是:取令,则.2指派问题的解法——匈牙利解法“匈牙利解法”最早是由匈牙利数学家D.Konig用来求矩阵中元素的一种方法,由此他证明了“矩阵中独立元素的最大个数等于能覆盖所有元素的最少直线数”.1955年由W.W.Knhu在求解著名的指派问题时引用了这一结论,并对具体解法做了改进,仍称为匈牙利解法.18洛阳师范学院本科毕业论文2.1匈牙利解法的基本原理和解题思想从根本上讲,
5、求指派问题的最优解就是要在阶方阵中找到个这样的元素,它们分布在不同行不同列上,并且这些元素之和为最小,而要使这些元素之和为最小,就要使其中的每一个元素尽可能的小——最好这些元素都是其所在行所在列上的最小元素.而指派问题的最优解又具有这样的性质（定理1）:若从系数矩阵的每行（列）各元素中分别减去该行（列）的最小元素,得到的新矩阵,那么以为系数矩阵求得的最优解与用求得最优解相同.由于新矩阵中每行每列都有最小元“”,因此,求原指派问题的最优解转化为在中指出个分布在不同行不同列上的“”元素（简称为独立元素）,而根据考尼格（Konig）证明的定理（定理2）
6、:矩阵中独立元素的最多个数等于能覆盖所有零元素的最少直线数,利用这一定理,就可以通过寻找“能覆盖所有零元素的最少直线数”来确定中独立元素的具体数量.若中独立元素的个数少于矩阵的阶数,就要继续对矩阵进行化简,直到找到个独立元素为止,这就是匈牙利解法的基本原理和解题思想.2.2匈牙利解法的解题步骤第一步:变换效益矩阵,使新矩阵中的每行每列至少有一个.（1）行变换:找出每行最小元素,再从该行各元素中减去这个最小元素.（2）列变换:从所得新矩阵中找出每列中的最小元素,再从该列各元素中减去这个最小元素.第二步:进行试指派,以寻找最优解.（1）逐行检查从第一
7、行开始,如果该行只有一个零元素,就对这个零元素打上括号,划去与打括号零元素同在一列的其他零元素,如果该行没有零元素,或有两个或多个零元素（已划去的不计在内）,则转下行.打括号的意义可理解为该项任务已分配给某人.如果该行只有一个,说明只能有唯一分配.划掉同列括号零元素可理解为该任务已分配,此后不再考虑分配给18洛阳师范学院本科毕业论文他人.当该行有两个或更多的零元素时,不计括号内的,其理由是至少有两个分配方案,为使以后分配时具有一定的灵活性,故暂不分配.（2）逐列检查在行检查的基础上,由第一列开始检查,如果该列只有一个零元素,就对这个零元素打括号,
8、再划去与打括号零元素同行的其它零元素.若该列没有零元素或有两个以上零元素,则转下一列.（3）重复（1）、（2）两步后,可能出现以下三种情
