浅析指派问题的匈牙利解法成稿
更新时间:2023-11-17 01:06:01 阅读量: 教育文库 文档下载
洛阳师范学院本科毕业论文
浅析指派问题的匈牙利解法
胡小芹
数学科学学院 数学与应用数学 学号: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
正在阅读:
浅析指派问题的匈牙利解法成稿11-17
食品经营者(食品销售类)制度07-19
新格林耐特配置命令04-18
参观黄埔军校心得体会作文3篇06-18
第八届地球小博士地理科技大赛高中组试题及答案 - 图文04-25
大学生志愿者暑期社会实践个人心得体会范文03-24
我是一朵云作文600字07-15
超星尔雅《大学生心理健康教育》题库06-08
matlab实验报告10-28
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 匈牙利
- 解法
- 指派
- 浅析
- 问题
- 成稿
- (完整版)离子膜法烧碱工艺 毕业论文
- 滚筒反力式加载制动检验台操作规程
- 秋季滋补季--各种滋补粥、汤的做法大全
- 统计学试题(一)及其答案
- 南京市江宁区城乡总体规划(2010-2030)
- 预测与决策是管理学的两个重要研究范畴
- (部编版)八年级《道德与法治》下册第四课 公民义务 测试题
- 2015年山东艺术学院艺术史论专业招生考试真题
- 科粤版化学九上 2.1《空气的成分》同步练习学习精品
- 脊椎动物中鱼纲的总结
- 2019年云南楚雄州学前教育特岗教师招聘刷题卷七
- 数字图像处理冈萨雷斯第三版课后答案
- 人权与国家主权
- 湖北省职业教育科学研究申报书 - 图文
- 模拟电子技术及应用 习题解答
- 体育中心击剑馆2014年终工作总结报告
- 新闻宣传中心工作认识
- 其他食品(龟苓膏类)生产许可证审查细则
- 高等教育心理学考试纲要
- 用友时空KSOA结转算法说明佳易