匹配理论及其应用第二组

《图论》课程专题论文论文题目：匹配理论及其应用专业：数学与应用数学班级：2014级数学与应用数学组长：2017年12月10日论文编号姓名学号成绩论文评价指标与鉴定意见论文题目匹配理论及其应用完成人专业及班级2014级数学与应用数学指标论文评价（对表格中的各栏，用“√”表示意见）优良中差论文选题基础理论与专门知识语言的表达水平创新性学术价值应用价值总体评价A（86—100分）B（70—85分）C（60—69分）D（0—59分）鉴定意见评阅人签名：成绩评阅人职称专业论文题目匹配理论及其应用专业年级2014级数学与应用数学组长吴娜电话QQ号完成人分工情况完成度（%）吴娜分析题目，选择框架21%高思雨查询资料，有关匹配的理论15%宋美玲论文的背景和方法的查找总结16%张珂查找资料，论文改动，整理资料16%杨敏蝶组织语言，编辑文字16%马华组织语言，排版格式15%匹配理论及其应用摘要匹配理论在理论化学、组合优化等研究领域中得到非常重要的应用。因此，得到了很多研究学者的关注并且产生了许多重要的理论结果。本文首先介绍了匹配的相关理论,然后对匹配理论进行应用，主要将匹配理论用于排课问题以及工件排序问题。对于排课问题，本文设计了基于匹配理论的排课方法，我们先根据教学的要求构造了排课模型图，接着用匹配理论对课时进行安排，使得每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课。对于工件排序问题，因为工件排序问题可转化为双竞赛图与偶图，所以我们通过Kuhn-Munkres算法求出了工件排序问题的最优解。关键词匹配，排课问题，工件排序问题，Kuhn-Munkres算法ABSTRACTMatchingtheoryintheoreticalchemistry,combinatorialoptimizationandotherresearchinthefieldofapplicationisveryimportant.Therefore,alotofresearchersconcernedandproducedmanyimportanttheoreticalresults.Firstly,matchingtheory,andthenapplyingthematchingtheory,mainlymatchingtheorytocourseschedulingproblems,andjobschedulingproblem.Fortimetablingproblem,wedesignedacoursedispatchingmethodbasedonmatchingtheory,westartteachingcourseschedulingmodelisconstructed,thenmatchthearrangementofclasstheories,makingeachschool,eachteacherforatmostoneclass,eachclassuptoacceptateacher.Forjobschedulingproblem,jobschedulingproblemcanbetransformedintoadoublewithbipartitegraphsoftournaments,soaccordingtoKuhn-Munkresalgorithmwewillgetajobschedulingproblemofoptimalsolutions.KeyWords:Matching,Thetimetablingproblem,Jobschedulingproblem,Kuhn-Munkresalgorithm目录1绪论...................................................11.1选题背景..........................................11.2研究的意义........................................21.3国内外研究综述.....................................31.4研究的思路与方法...................................52基础理论...............................................62.1匹配理论..........................................62.2排课问题的理论.....................................82.3工件排序问题的理论.................................93问题分析...............................................93.1排课问题分析.......................................93.2工件排序问题分析..................................104匹配理论的应用........................................104.1匹配理论在排课问题中的应用........................114.2匹配理论在工件排序问题中的应用....................135结束语................................................16参考文献................................................20答谢..............................................2211绪论一直以来图论倍受人们关注，图论中的匹配理论在很多领域得到了应用，我们对排课问题和工件排序问题的背景和研究意义进行了了解，并且阐述了国内外对匹配的研究，以及对排课问题和工件排序问题存在的问题进行了分析。此外，大学生就业难已经成为中国一个十分突出的问题，因而利用匹配理论的知识对大学生就业市场的研究具有重大的意义。匹配是图论的一个重要内容。匹配理论很好的描述了市场中双向选择的情形，解释了一个市场能稳定存在的根源，并为我们对各种市场进行设计建立合理的市场机制提供了可行的选择。1.1选题背景随着近年来我国高校不断扩招，学生人数不断增加，但是与之相配的学校的各种基础资源设施并没有跟上。例如老师、教室、多媒体资源等等。所以，高校排课成为新一轮的难题。传统人工排课是基于学生人数少，教室也不多的情况下，对老师等各种资源的合理分配。虽然传统人力排课能在一定程度上解决这个难题，但随着学生人数的增加，新课程内容的添加，老师人数相对较少，人工排课势必要耗费大量的时间与精力。显然，在如今讲求高效率的社会体系中，无论哪一方，都不愿意因排课这件小事而耗费大量时间与精力。所以，怎样合理优化老师、学生、教室、多媒体等各种资源就成了高校每年新学期开始面临的“当务之急”。2目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并非如此。“毕业即失业”已经成为普遍现象。在工件加工的过程中，有加工时间、加工顺序、加工价值等因素的限制，在大规模使用机器制造的背景下，需要利用一些处理机,机器或资源,最优地完成一批给定的任务或作业。排序问题有深刻的实际背景和广阔的应用前景。被广泛应用于计算机系统，运输调度，生产管理等领域。1.2研究的意义1.2.1排课问题研究的意义本文通过对匹配理论的发展过程、国内外发展现状、研究的思路与方法以及应用匹配理论解决排课问题的事例进行一个相对比较完整的综述，为我国的研究匹配理论的学者提供一些参考。另外，高校的教务管理中，排课工作非常复杂且手工操作要花费大量精力，不仅效率低，而且教学资源也很难被充分利用。将匹配理论与高校排课结合起来，设计一种相对稳定的匹配机制，优化高校排课，增加排课的效率和匹配的稳定性。1.2.2工件排序问题研究的意义我国的生产企业工件排序效率未能合理优化的问题，这不仅影响企业效益，还会造成资源浪费，影响整个行业的发展。对于这种情况，3有必要对工件排序进行分析研究，将匹配理论与工件排序问题结合起来，设计一种相对稳定的匹配机制，优化工件排序，增加工件排序的效率和匹配的稳定性，进而促进整合行业的发展。1.2.3就业问题研究的意义目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并非如此，“毕业即失业”已经成为普遍现象。将匹配理论应用到就业问题中，解决就业困难的匹配问题，既丰富了对就业问题的研究，也扩大了匹配理论的应用范畴。1.3国内外研究综述匹配理论的研究和发展已有悠久的历史，在这发展的过程中匹配理论逐步发展成为运筹学中重要的一部分，与此同时，它也是图论的核心内容。在实际生活中，许多问题都与匹配理论有着紧密的联系，在这种情况下，许多国内外学者对匹配理论进行了研究并且将匹配理论应用于实际问题中。1.3.2国外研究情况在1891年匹配理论开始发展，丹麦人Petersen首先对正则图中的完美匹配[1]进行了研究：证明了任意一个3-正则连通图，如果没有两条以上割边，则此图就有完美匹配。1915年匈牙利人konig对二部图中的完美匹配[2]进行了研究。1947年，Tutte对普通图中的完美4匹配进行研究，得出了判别一个图G是否存在完美匹配的充要条件：一个图G有完美匹配当且仅当对任意SVG,不等式OGSS，其中OGS表示图GS中顶点数为奇数的连通片的个数。1935年，P.Hall对二部图中的匹配问题进行研究，并且得到了Hall定理[3]：设图G是一个二部图,两顶点集分别为X、Y，其存在一个浸润X(即包含X的全部顶点)的匹配的充要条件是：Y中与X的任意子集S相邻的顶点数不小于S中的顶点数。1942年，Rado将Hall定理推广到欧氏向量空间中相异代表系独立系统[4]，首次将匹配和拟阵联系起来。在此之后匹配理论得到了迅速的发展：1964年Gallai提出了依赖最大匹配的图的规范分解理论、1972年Lovasz定义了图的双临界性、1980年Plunner定义了K-可扩图的概念、1989年Cameron[5]定义了导出匹配的概念、1998年原晋江[6]首次提出了关于导出匹配可扩图的概念等。随着计算机的发展，有关匹配问题的算法不断被提出。1955年Kuhn[7]及1956年Hall[8]首先提出了寻找二部图的完美匹配的线性规划算法。同年，Ford和Fulkerson[9]发表了关于网络流理论的著作。之后，网络流理论也开始应用于二部图的匹配问题（不赋权和赋权的）[10][11]，并且得到较好的结果。1.3.2国内研究情况相对于国外对匹配理论的研究，国内对这方面的相关研究是比较少的，其大部分的研究是结合了中国的一些相关实例。例如文胜[12]运用双边匹配理论阐述中国信贷市场二元结构——目标客户信贷市场5和非目标客户信贷市场；聂海峰[13]总结GS算法，得到了新的中国高考录取机制，假设在得知高考分数得情况下报考录取的制度只有唯一一个纳什均衡结果,并且均衡是帕累托有效和公平的，这个机制是基于信息是完全的情况下进行说明的。张成[14]进一步研究了应届毕业生劳动力市场匹配模型，根据我国应届毕业生劳动力市场存在的问题，结合双边匹配理论对我国劳动力市场进行研究、剖析，构建了随机非中心化单次录取机制模型，得出了市场的不稳定性和其他的相关结论，诠释了市场上出现这种现象的原因。张振华和汪定伟[15]构建了关于电子中介的多目标匹配模型，基于电子中介处理多属性商品交易，得到