最优指派问题算法及其应用+源程序
时间:2018-05-11 11:45 来源:毕业论文 作者:毕业论文 点击:次
| 摘要在生产运营管理中有时会遇到这样的问题：有 项任务要完成，恰好有 个人可以去完成其中每一项任务，由于每项任务的性质和个人专长不同，因此各项任务由不同的人完成的效率有所不同。在这种状况下如何分配任务使每人完成一项且仅完成一项，使完成所有 项任务的总效率最高或者如何安排人员使得总费用最少？若考虑每个职工对工作的效率（如熟练程度等），怎样安排会使总效率达到最大？此类问题就被称为指派问题。本文先对指派问题进行陈述，引出对实际问题的求解。通过匈牙利算法实现指派问题的解决办法，对匈牙利算法进行改进及分析，最后通过 编译程序来解决实际应用问题。22713 毕业论文关键词： 指派问题；分配；匈牙利算法；生产运营管理 ABSTRACT Sometimes we meet such kind of questions during production and operation management that there is a project need be to done, as it happens, there is a person who can do one of those tasks about the project, because of the feature of work and specialty of personnel are different,work efficiency dealing with tasks of different people varies.Under this circumstance, in order to get highest overall efficiency or spend lowest overall cost, how to assign one and only one task to each person reasonably? And how can we maximize overall efficiency if we take every staff’s work efficiency (such as skill level etc.) into account? This kind of problem is called assignment problem.This paper describes assignment problem at first and then explains how to get solution for the problem. Solution has been found by Hungary algorithm, after improving and analyzing Hungary algorithm, at last, compiling routine has been used to solve practical problems. Key words: assignment problem; assign; Hungary algorithm; production and operation management 目录 摘要 1 ABSTRACT 1 第一章 绪论 3 1.1 课题的目的及意义 3 1.2 国内外研究现状与发展趋势[15] 3 1.3 基本概念及符号说明 4 1.3.1 基本概念 4 1.3.2 符号说明 5 1.4 用到的定理 6 第二章 指派问题的描述 6 2.1 指派问题的一般形式 6 2.2 指派问题数学模型的建立 7 第三章 匈牙利算法 8 3.1 匈牙利算法的实现步骤[1] 8 3.3 匈牙利算法实现指派问题 9 第四章 模型拓展 11 4.1 目标函数极大化的指派问题 11 4.2 非标准指派问题 12 4.3 拓展模型实例分析 12 第五章 算法的改进 17 5.1 对角线法 17 5.1.1对角线法的原理 18 5.1.2 对角线法的具体方法 18 5.1.3 实例分析 19 5.2 隶属矩阵法 21 5.2.1 隶属矩阵法的原理 21 5.2.2 隶属矩阵额具体算法 21 5.2.3 实例分析 21 第优尔章 MATLAB程序实现 23 6.1 程序调用 23 6.2 程序截图 24 致谢 27 参考文献 28 附录 29 第一章 绪论 1.1 课题的目的及意义 图论是应用数学的一个重要分支，它涉及的内容非常广泛，并且在许多领域有十分广泛的应用。指派问题在图论中的应用非常广泛，比如在生产运营管理中有时会遇到这样的问题：有 项任务要完成，恰好有 个人可以去完成其中每一项任务，由于每项任务的性质和个人专长不同，因此各项任务由不同的人完成的效率有所不同。在这种状况下如何分配任务使每人完成一项且仅完成一项，使完成所有 项任务的总效率最高。又比如某公司指派 个人去做 件事，各人做不同的一件事，如何安排人员使得总费用最少？若考虑每个职工对工作的效率（如熟练程度等），怎样安排会使总效率达到最大？这些都是一个企业经营管理员必须考虑的问题，而此类问题的解法常有的有线性规划法和匈牙利法。匈牙利法相对来说比线性规划法简单一些，运算速度快一些，但仍不理想。随着科技的发达，现在人们对原有的方法提出了质疑，在原有的基础上进行了改进及其实现，所以该问题的研究现实意义非常突出。 (责任编辑：qin) |