《毕业设计（论文）模糊指派问题的解法研究及应用.docx》由会员分享，可在线阅读，更多相关《毕业设计（论文）模糊指派问题的解法研究及应用.docx（31页珍藏版）》请在金锄头文库上搜索。
1、摘 要 相对于指派问题来说，传统的算法最主要的是匈牙利算法，匈牙利法可以为我们解决大多数指派问题，但是，也存在一些较为特殊的模糊指派问题无法用匈牙利法算出，本文就此进行分析探讨。 从传统指派问题的解法出发，分析研究了匈牙利法的步骤与其所存在的问题，从中得到了许多有实用指导意义的指派原则。按照所知指派问题的特点从而进行了扩展研究，并且结合从研究中导出的指派原则，按照模糊数学原理的到了模糊效率矩阵。从模糊化求解的过程中受到启发，将求解传统指派问题所运用到的匈牙利法进行了研究分析、改进、进而推广，讨论了模糊指派问题的求解方法，我们通过分析对其进行完善，提出了一种新的指派问题的解法，引入直觉模糊集这个
2、概念，从而将直觉模糊矩阵转化为得分矩阵，把得分矩阵看作指派问题的效益矩阵，然后用匈牙利法得出最优解，在将直觉模糊矩阵转化为得分矩阵部分，综合考虑了集中方法，然后进行对比分析，得出一种较为合理的方法，也即修正得分函数。再通过实例分析，进行验证其可行性和正确性。关键词：模糊指派问题；匈牙利法；效益矩阵；直觉模糊集 AbstractCompared with the traditional assignment problem, the algorithm is the most important Hungarian algorithm, we can solve most of the Hung
3、arian method of assignment problem, but there are some special fuzzy assignment problem can not be calculated based on the analysis of Hungary, conducted to explore. Starting from the solution of the traditional assignment problem, this paper analyzes and studies the steps of Hungarian law and the p
4、roblems existing in it, and obtains a lot of practical guiding principles. According to the characteristics of the known assignment problem, the extended research is carried out, and according to the assignment principle derived from the study, the fuzzy efficiency matrix is formulated according to
5、the principle of fuzzy mathematics. Inspired by the process of fuzzy solution in the Hungarian method to solve the traditional assignment problem is applied to analysis, improvement, and promotion, this paper discussed the method for solving fuzzy assignment problem, we analyze to perfect it, puts f
6、orward a solution for the new assignment problem, introducing the concept of intuition fuzzy sets, intuitionistic fuzzy matrix into the score matrix, the score matrix as the benefit matrix assignment problem, and then use the Hungarian method of optimal solution in the intuitionistic fuzzy matrix in
7、to the score matrix part, integrating the centralized method, then carries on the contrast analysis, obtained a more rational approach, i.e. corrected score function. Then, the feasibility and correctness of the method are verified by an example. Key words：Fuzzy assignment problem;Hungarian method;
8、Benefit matrix; Intuition fuzzy sets目 录摘 要IAbstractII目 录III第一章 绪 论1 1.1 研究背景及意义11.2 本文的研究内容11.2.1 研究的重点11.2.2 存在的问题21.3 本文的组织结构2第二章 模糊指派问题42.1 模糊指派问题42.2 模糊效率矩阵42.3 本章小结5第三章 指派问题的数学模型和“匈牙利法”63.1 模糊指派问题的数学模型63.2 匈牙利解法过程及其问题6 3.1.1 匈牙利法的计算步骤63.1.2 匈牙利法存在的问题73.1.3 “匈牙利法”的改进93.3 最优指派原则103.4 直觉模糊集的概念10第四
9、章 实例应用对比解析13 4.1 应用举例134.2 模糊效率矩阵实例求解144.3 求解具有直觉模糊信息的任务指派问题的实例14第五章 总结17参考文献18致谢19附录20IV第一章 绪 论1.1 研究背景及意义 在企业生产管理工作和我们日常的生活中，总会面临如何对人员进行分配、对机床进行指派加工任务等等问题，由于每个人的能力有所不同，所以他们完成任务的效率（或者完成任务所需的时间、所需要的费用）都不相同，因此产生了我们该如何分配人员，如何分配机床加工任务，才能使得我们的效率最高，所需要的时间和费用最少的等指派问题。每个任务都会有其所需时间、费用，所需要的达到的效率指标，想要得到其最确切的最
10、合理的结果，必须等到最后任务完成之后。因此我们在分析研究指派问题的时候，例如反映一个人、一张机床完成任务时的效率、费用或者时间等等参数应该看作一个估计值，这个估计值会带有人的主观判断，尤其是那些在没有经历过类似的情况下，此时的模糊数就能够较好地表示这种带有主观判断的估计值。 模糊指派问题是一种较为特殊的整数规划问题，在许许多多应用领域中经常会碰到，匈牙利法现在是指派问题的最常用解法，而指派问题在当今这个发展极为迅速、一切都要以效率为主的社会中使用的极为广泛1。在竞争中寻求生存，在竞争中寻求发展是当今世界的一个很重要的话题，优化改进匈牙利法的计算对于当今社会的发展也有着非常重大的意义。我们通过对
11、匈牙利法的改进，从而往匈牙利法中引入了最小元素。使匈牙利法不在受到传统的束缚，不再是0元素，更进而简化了它的运算量，最后我们也通过大量的实例论证了这种方法的有效性和可行性。1.2 本文的研究内容1.2.1 研究的重点 从传统指派问题的解法出发，分析研究了匈牙利法的步骤与其所存在的问题，从中得到了许多有实用指导意义的指派原则。按照所知指派问题的特点从而进行了扩展研究，并且结合从研究中导出的指派原则，按照模糊数学原理的到了模糊效率矩阵。从模糊化求解的过程中受到启发：在我们的到最优解的情况下，我们还需要让其拥有丰富的管理指导意义，让两者并存，才能体现出定量化处理的意义。 将求解传统指派问题所运用到的
12、匈牙利法进行了研究分析、改进、进而推广，讨论了模糊指派问题的求解方法，并且结合实际例子进行了讨论说明。“匈牙利法”的分配算法，是目前被公认为解决分配问题最有效的算法2，又对匈牙利法进行了讨论，得出求解两模糊数差值的模糊方程的定义，基于对此定义的研究将传统的指派问题的匈牙利法进行了推广。 1.2.2 存在的问题 但是在大量数据试验过程中发现“匈牙利法”在处理一些特殊数据时无法从有效算法不收敛中找出最优解。通过研究找到了“匈牙利法”存在问题的原因并对“匈牙利法”进行了完善，改进了算法功能使之能解决任何的分配问题。 在各种已经发表的有关“匈牙利法”的教材、专著和研究成果中。通常在求解中、小型分配问题
13、时，效能矩阵的阶数一般来说不会超过20，所以很难发现“匈牙利法”中所存在的问题。 许多与分配有关的运输、调配问题都是用“匈牙利法”处理的，在大多数情况下这个算法是收敛的，能够得到最优解，但是当处理一些较为特殊的数据时，算法会不收敛，没有办法得到最优解。当矩阵的阶数越来越大，那么其分配问题存在不收敛的情况就会越来越多。1.3 本文的组织结构 第一章，本文的绪论部分，主要介绍本课题的研究背景意义、研究现状以及本篇文章的主要内容及组织结构. 第二章，介绍了模糊指派问题 第三章，讲解了模糊指派问题的解法，以匈牙利方法为主。又对“匈牙利法”进行了分析研究，再进而改进，得到更加完善的“匈牙利法”。 第四章
14、，通过实例来证明改进后的算法的有效性和可行性 第五章，进行总结第二章 模糊指派问题2.1 模糊指派问题从更为现实的角度来看，许多现实指派问题的具体、精确的效率矩阵(费用矩阵)往往很难得出或者无法得出，往往人们只有模糊和定性的认识。例如下面这个例子中这个指派问题的背景是：有一份中文指导书需要翻译成英、俄、德、法、日语，现有甲、乙、丙、丁、戊五人都具备上述的5种语言的翻译能力，但是每个人的专长、效率都不相同，反应在中就会得出每个人完成上述任务的具体时间(费用)5。但实际上我们很难确切知道某人将某份说明书翻译成某种语言所需要的时间，通常只能定性的知道，比方戊的英语最佳，丁的法语和德语很好，甲的俄语比
15、英语好，乙的日语比丙的日语好，丙的工作效率相对于来说较低，这5小我遍及德语程度都相对于较高档等的环境。也就是说精确、定量的效率矩阵在现实中是难以得到的，即使能够得到其付出的过程也是不经济的，所以相对于现实的管理问题来说，通过建立模糊效率矩阵将指派问题扩展为更贴近实际的模糊指派问题，再运用我们前面所探讨的最优指派原则来解决该问题无疑是个十分有意义的工作。因此，扩展后得到的模糊指派问题可以表述为：每项任务需分配给一个工作者来完成，每个工作者完成每项任务的效率情况反应在效率矩阵中，这个就是模糊隶属度数值，要求按照将每项任务的性质和难度与各个工作者的工作效率与工作能力相结合，综合权衡考虑后，使得每项任务在各个工作者之间得到一个最为合理的分配，使得指派决策能得到一个非常满意的高效率的结果。2.2 模糊效率矩阵 此处考虑要运用AHP原理6来给出指派问题的模糊效率矩阵。 AHP采取单一准则下被测度因素的两两比较判断得出的判断矩阵，而且用解判断矩阵的特征根和特征向量来给出
