浅析指派问题的匈牙利解法成稿

洛阳师范学院本科毕业论文

浅析指派问题的匈牙利解法

胡小芹

数学科学学院 数学与应用数学 学号:040414057

指导教师:苏孟龙

摘要:对于指派问题,可以利用许多理论进行建模并加以解决,但匈牙利解法是解决指派问题的一种非常简单有效的方法,并且可以解决多种形式的指派问题,但匈牙利算法本身存在着一些问题,本文主要介绍了匈牙利算法的基本思想,基本步骤,以及它的改进方法.在匈牙利算法的基础上,本文还介绍了两种更简便实用的寻找独立零元素的方法——最小零元素消耗法和对角线法.

关键词:指派问题;匈牙利解法;最小零元素消耗法;对角线法 0 引言

在现实生活中经常会遇到把几个任务分派给几个不同的对象去完成,由于每个对象的条件不同,完成任务的效率和效益亦不同.指派问题的目标就是如何分派使所消耗的总资源最少（或总效益最优）,如给工人分派工作,给车辆分配道路,给工人分配机床等等,同时许多网络问题（如旅行问题,任务分配问题,运输问题等）,都可以演化成指派问题来解决.在现实生活中,指派问题是十分常见的问题,而匈牙利解法是解决指派问题的一种非常简单有效的方法.本文主要介绍匈牙利解法的基本原理及思想,解题步骤,不足与改进,以使匈牙利法更能有效地解决指派问题.

1 指派问题及其数学模型

指派问题是指由m项任务,需要n个人来承担,每人只能承担一项任务,且每项任务只能有一人来承担,由于各人的专长不同,各人完成的任务不同,导致其效率也各不相同.因此,就产生怎样科学地指派任务,才能使完成各项任务所消耗的总资源最少（或总成本最低等）,由于m,n不同,指派问题可分为以下三种情况:

1

洛阳师范学院本科毕业论文

第一、当m?n时,即为每人指派一项任务.

第二、当m?n时,即任务数〉人数,这时可虚设(m?n)个人构成m?m的 效率矩阵,并且这(m?n)个人在执行这m项任务时的效率应该是效率最高. 第三、当m?n时,即配置人数〉任务数,这时应虚设(n?m)项任务,并且这n个人在执行这(n?m)项任务时的成本最低.

通过虚设任务或人,指派问题的效率矩阵都可以转化成方阵.匈牙利解法要求指派问题最小化,其数学模型为

设用cij?0(i,j?1,2,?,n)表示指派第i个人去完成第j项任务时所用的时间,定义决策变量

?1xij???0表示第i个人完成第j项任务, 表示不指派第i个人完成第j项任务.

则问题可转化为0-1线性规划问题:

nnij minZ???ci?1j?1

?n??xij?1,?i?1?n s?t ??xij?1,?j?1?x?0或1,ij??j?1,2,?,n,i?1,2,?,n, i,j?1,2,?,n.如果指派问题要求的是最大化问题如maxF,则可以转化为最小化问题,一般方法是:取M?maxcij(i,j?1,2?n),令bij?M?cij(i,j?1,2?,n),则

nnijminf???bi?1j?1,有F?nM?f,从而求maxF.

2 指派问题的解法——匈牙利解法

“匈牙利解法”最早是由匈牙利数学家D.Konig用来求矩阵中0元素的一种方法,由此他证明了“矩阵中独立0元素的最大个数等于能覆盖所有0元素的最少直线数”.1955年由W.W.Knhu在求解著名的指派问题时引用了这一结论,并对具体解法做了改进,仍称为匈牙利解法.

2

洛阳师范学院本科毕业论文

2.1 匈牙利解法的基本原理和解题思想

从根本上讲,求指派问题的最优解就是要在n阶方阵中找到n个这样的元素,它们分布在不同行不同列上,并且这些元素之和为最小,而要使这些元素之和为最小,就要使其中的每一个元素尽可能的小——最好这些元素都是其所在行所在列上的最小元素.

而指派问题的最优解又具有这样的性质（定理1）:若从系数矩阵(cij)的每行（列）各元素中分别减去该行（列）的最小元素,得到的新矩阵(bij),那么以(bij)为系数矩阵求得的最优解与用(cij)求得最优解相同.

由于新矩阵(bij)中每行每列都有最小元“0”,因此,求原指派问题的最优解转化为在(bij)中指出n个分布在不同行不同列上的“0”元素（简称为独立0元素）,而根据考尼格（Konig）证明的定理（定理2）:矩阵中独立元素的0最多个数等于能覆盖所有零元素的最少直线数,利用这一定理,就可以通过寻找“能覆盖所有零元素的最少直线数”来确定(bij)中独立元0素的具体数量.若(bij)中独立0元素的个数少于矩阵的阶数n,就要继续对矩阵(bij)进行化简,直到找到n个独立0元素为止,这就是匈牙利解法的基本原理和解题思想. 2.2 匈牙利解法的解题步骤

第一步:变换效益矩阵,使新矩阵中的每行每列至少有一个0.

（1）行变换:找出每行最小元素,再从该行各元素中减去这个最小元素. （2）列变换:从所得新矩阵中找出每列中的最小元素,再从该列各元素中减去这个最小元素.

第二步:进行试指派,以寻找最优解. （1）逐行检查

从第一行开始,如果该行只有一个零元素,就对这个零元素打上括号,划去与打括号零元素同在一列的其他零元素,如果该行没有零元素,或有两个或多个零元素（已划去的不计在内）,则转下行.

打括号的意义可理解为该项任务已分配给某人.如果该行只有一个0,说明只能有唯一分配.划掉同列括号零元素可理解为该任务已分配,此后不再考虑分配给

3

洛阳师范学院本科毕业论文

他人.当该行有两个或更多的零元素时,不计括号内的,其理由是至少有两个分配方案,为使以后分配时具有一定的灵活性,故暂不分配.

（2）逐列检查

在行检查的基础上,由第一列开始检查,如果该列只有一个零元素,就对这个零元素打括号,再划去与打括号零元素同行的其它零元素.若该列没有零元素或有两个以上零元素,则转下一列.

（3）重复（1）、（2）两步后,可能出现以下三种情况:

① 每行都有一个零元素标出括号,显然打括号的零元素必然位于不同行不同列,因此得到最优解.

② 每行每列都有两个或两个以上的零,这表示对这个人可以分配不同任务中的任意一个.这时可以从所剩零元素最少的行开始,比较这行各零元素所在列中元素的个数,选择零元素少的那列这个零元素打括号,划掉同行同列的其他它零元素,然后重复前面的步骤,直到所有0都作了标记.

③ 矩阵中所有零都作了标记,但标有(0)的元素个数少于m个,则转下步. 第三步:做最少的直线覆盖所有零元素,以确定该系数矩阵中能找到最多的独立0元素.

· 对没有（）的行打√;

· 对打√的行上所有含0元素的列打√; · 再对打√的列上有（）的行打√; · 重复上两步,直到过程结束;

· 对没有打√的行划横线,对所有打√的列划垂线.

这就得到了能覆盖矩阵中所有0元素的最少直线数.

第四步:非最优阵的变换——零元素的移动.

（1）在没有被直线覆盖的所有元素中,找出最小元素; （2）所有未被直线覆盖的元素都减去这个最小元素; （3）覆盖线十字交叉处的元素都加上这个最小元素; （4）只有一条直线覆盖的元素的值保持不变.

第五步:回到第二步,反复进行,直到矩阵中每行每列都有一个打（）的0元素为止,即找到最优解.

4

洛阳师范学院本科毕业论文

2.3 匈牙利算法的一点注记

（1）匈牙利算法第一步变换效益矩阵使每行每列都出现零元素,一般方法是先行变换,再列变换,但先列变换再行变换最优解不变.

（2）有些时候先行后列变换后不能得到最优解,但先列后行变换时却能直接找到最优解,从而减少了计算步骤,使计算简明.如下所示:

先行变换,再列变换得

?2?15B???13??4104141591416137??(0)??811??B???211???9??08(0)31125(0)45??4? 0??5?只找到三个独立0元素,不是最优解.那么先列变换,后行变换得

?2?15B???13??4104141591416137??0??138??B???711???9??(0)6(0)69(0)5320??1? (0)??0?每行每列都有“(0)”,得到最优解. 3 匈牙利法的不足与改进 3.1 不足和改进（一）

以上是匈牙利法的常规解题方法,虽然能有效地解决指派问题,但是其解题过程中还存在以下两点不足:

第一、在匈牙利算法的第二步中用“试指派”的方法寻找独立0元素,道理简单,也能很快找到独立0元素,但对于一个n阶方阵,这些独立0元素在矩阵中可能有n种排列方式,这样在矩阵中标出来的独立0元素排列很乱,没有规律.另外,对于某些矩阵0元素排列的比较有规律,本可以用别的更简单的方法寻找独立0元素,而用这种“一般性”的方法比较麻烦.

第二、在匈牙利算法的第三步“做最少的直线覆盖所有0元素”过程中,一会儿针行,一会儿针对列,一会儿对没有（）的打√,一会儿又对有（）的打√,一会对没有打√号的（行）划线,一会又对打√号的（列）划线,这样变来变去令人晕头转向,稍不注意就会出错,特别是对于这种画法每一步的意图以及内在原理,大多数人难以理解,具体步骤很难记住,难以掌握,这就影响了这一理论在实际工作

5

本文来源：https://www.bwwdw.com/article/tqfv.html