《匹配理论及其应用第二组(共33页).docx》由会员分享，可在线阅读，更多相关《匹配理论及其应用第二组(共33页).docx（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上论文编号图论课程专题论文论文题目： 匹配理论及其应用 专 业：数学与应用数学班 级：2014级数学与应用数学组 长：姓名学号成绩 2017年 12月 10日论文评价指标与鉴定意见论文题目匹配理论及其应用完成人专业及班级2014级数学与应用数学指标论文评价（对表格中的各栏，用“”表示意见）优良中差论文选题基础理论与专门知识语言的表达水平创新性学术价值应用价值总体评价A（86100分）B（7085分）C（6069分）D（059分）鉴定意见评阅人签名：成绩评阅人职 称专 业论文题目匹配理论及其应用专业年级2014级数学与应用数学组长吴娜电话QQ号完成人分工情况完成度（%）吴
2、娜分析题目，选择框架21%高思雨查询资料，有关匹配的理论15%宋美玲论文的背景和方法的查找总结16%张珂查找资料，论文改动，整理资料16%杨敏蝶组织语言，编辑文字16%马华组织语言，排版格式15%匹配理论及其应用摘 要 匹配理论在理论化学、组合优化等研究领域中得到非常重要的应用。因此，得到了很多研究学者的关注并且产生了许多重要的理论结果。本文首先介绍了匹配的相关理论,然后对匹配理论进行应用，主要将匹配理论用于排课问题以及工件排序问题。对于排课问题，本文设计了基于匹配理论的排课方法，我们先根据教学的要求构造了排课模型图，接着用匹配理论对课时进行安排，使得每一学时，每位老师最多为一个班上课，每个班
3、至多接受一个老师授课。对于工件排序问题，因为工件排序问题可转化为双竞赛图与偶图，所以我们通过Kuhn-Munkres算法求出了工件排序问题的最优解。关键词 匹配，排课问题，工件排序问题，Kuhn-Munkres算法ABSTRACTMatching theory in theoretical chemistry, combinatorial optimization and other research in the field of application is very important. Therefore, a lot of researchers concerned and prod
4、uced many important theoretical results. Firstly, matching theory , and then applying the matching theory, mainly matching theory to course scheduling problems, and job scheduling problem. For timetabling problem, we designed a course dispatching method based on matching theory, we start teaching co
5、urse scheduling model is constructed, then match the arrangement of class theories, making each school, each teacher for at most one class, each class up to accept a teacher. For job scheduling problem, job scheduling problem can be transformed into a double with bipartite graphs of tournaments, so
6、according to Kuhn-Munkres algorithm we will get a job scheduling problem of optimal solutions.Key Words:Matching,The timetabling problem,Job scheduling problem, Kuhn-Munkres algorithm目录专心-专注-专业1绪论一直以来图论倍受人们关注，图论中的匹配理论在很多领域得到了应用，我们对排课问题和工件排序问题的背景和研究意义进行了了解，并且阐述了国内外对匹配的研究，以及对排课问题和工件排序问题存在的问题进行了分析。此外，大
7、学生就业难已经成为中国一个十分突出的问题，因而利用匹配理论的知识对大学生就业市场的研究具有重大的意义。匹配是图论的一个重要内容。匹配理论很好的描述了市场中双向选择的情形，解释了一个市场能稳定存在的根源，并为我们对各种市场进行设计建立合理的市场机制提供了可行的选择。1.1选题背景随着近年来我国高校不断扩招，学生人数不断增加，但是与之相配的学校的各种基础资源设施并没有跟上。例如老师、教室、多媒体资源等等。所以，高校排课成为新一轮的难题。传统人工排课是基于学生人数少，教室也不多的情况下，对老师等各种资源的合理分配。虽然传统人力排课能在一定程度上解决这个难题，但随着学生人数的增加，新课程内容的添加，老
8、师人数相对较少，人工排课势必要耗费大量的时间与精力。显然，在如今讲求高效率的社会体系中，无论哪一方，都不愿意因排课这件小事而耗费大量时间与精力。所以，怎样合理优化老师、学生、教室、多媒体等各种资源就成了高校每年新学期开始面临的“当务之急”。目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并非如此。“毕业即失业”已经成为普遍现象。在工件加工的过程中，有加工时间、加工顺序、加工价值等因素的限制，在大规模使用机器制造的背景下，需要利
9、用一些处理机,机器或资源,最优地完成一批给定的任务或作业。排序问题有深刻的实际背景和广阔的应用前景。被广泛应用于计算机系统，运输调度，生产管理等领域。1.2研究的意义1.2.1排课问题研究的意义本文通过对匹配理论的发展过程、国内外发展现状、研究的思路与方法以及应用匹配理论解决排课问题的事例进行一个相对比较完整的综述，为我国的研究匹配理论的学者提供一些参考。另外，高校的教务管理中，排课工作非常复杂且手工操作要花费大量精力，不仅效率低，而且教学资源也很难被充分利用。将匹配理论与高校排课结合起来，设计一种相对稳定的匹配机制，优化高校排课，增加排课的效率和匹配的稳定性。1.2.2工件排序问题研究的意义
10、我国的生产企业工件排序效率未能合理优化的问题，这不仅影响企业效益，还会造成资源浪费，影响整个行业的发展。对于这种情况，有必要对工件排序进行分析研究，将匹配理论与工件排序问题结合起来，设计一种相对稳定的匹配机制，优化工件排序，增加工件排序的效率和匹配的稳定性，进而促进整合行业的发展。1.2.3就业问题研究的意义目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并非如此，“毕业即失业”已经成为普遍现象。将匹配理论应用到就业问题中，解
11、决就业困难的匹配问题，既丰富了对就业问题的研究，也扩大了匹配理论的应用范畴。1.3国内外研究综述匹配理论的研究和发展已有悠久的历史，在这发展的过程中匹配理论逐步发展成为运筹学中重要的一部分，与此同时，它也是图论的核心内容。在实际生活中，许多问题都与匹配理论有着紧密的联系，在这种情况下，许多国内外学者对匹配理论进行了研究并且将匹配理论应用于实际问题中。1.3.2国外研究情况在1891年匹配理论开始发展，丹麦人Petersen首先对正则图中的完美匹配进行了研究：证明了任意一个3-正则连通图，如果没有两条以上割边，则此图就有完美匹配。1915年匈牙利人konig对二部图中的完美匹配进行了研究。194
12、7年，Tutte 对普通图中的完美匹配进行研究，得出了判别一个图G是否存在完美匹配的充要条件：一个图G有完美匹配当且仅当对任意,不等式，其中表示图中顶点数为奇数的连通片的个数。1935年，P.Hall对二部图中的匹配问题进行研究，并且得到了Hall定理：设图G是一个二部图,两顶点集分别为X、Y，其存在一个浸润X(即包含X的全部顶点)的匹配的充要条件是：Y中与X的任意子集 S相邻的顶点数不小于S中的顶点数。1942年，Rado 将Hall定理推广到欧氏向量空间中相异代表系独立系统，首次将匹配和拟阵联系起来。在此之后匹配理论得到了迅速的发展：1964年Gallai提出了依赖最大匹配的图的规范分解理
13、论、1972年Lovasz定义了图的双临界性、1980 年Plunner 定义了K-可扩图的概念、1989年Cameron定义了导出匹配的概念、1998年原晋江首次提出了关于导出匹配可扩图的概念等。随着计算机的发展，有关匹配问题的算法不断被提出。1955年Kuhn及1956年Hall首先提出了寻找二部图的完美匹配的线性规划算法。同年，Ford和Fulkerson发表了关于网络流理论的著作。之后，网络流理论也开始应用于二部图的匹配问题（不赋权和赋权的），并且得到较好的结果。1.3.2国内研究情况相对于国外对匹配理论的研究，国内对这方面的相关研究是比较少的，其大部分的研究是结合了中国的一些相关实例
14、。例如文胜运用双边匹配理论阐述中国信贷市场二元结构目标客户信贷市场和非目标客户信贷市场；聂海峰总结GS算法，得到了新的中国高考录取机制，假设在得知高考分数得情况下报考录取的制度只有唯一一个纳什均衡结果,并且均衡是帕累托有效和公平的，这个机制是基于信息是完全的情况下进行说明的。张成进一步研究了应届毕业生劳动力市场匹配模型，根据我国应届毕业生劳动力市场存在的问题，结合双边匹配理论对我国劳动力市场进行研究、剖析，构建了随机非中心化单次录取机制模型，得出了市场的不稳定性和其他的相关结论，诠释了市场上出现这种现象的原因。张振华和汪定伟构建了关于电子中介的多目标匹配模型，基于电子中介处理多属性商品交易，得
15、到了双方的满意度函数，利用最大化双方满意度作为排序清单，构建多个买家和卖家多目标匹配平台，得出求解单目标的优先贪婪算法。赵希男等专家对人与组织匹配测试方法提出新的观点，与人员与组织匹配的纵向匹配指标、横向匹配指标以及截面匹配指标的测试模型相结合，得出相对应的匹配结果。1.4研究的思路与方法对于排课问题，我们设计了基于匹配理论的排课方法，我们先根据教学的要求构造了排课模型图，然后用匹配理论对课时进行安排，使得每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课。对于工件排序问题，因为工件排序问题可转化为双竞赛图与偶图，所以我们通过Kuhn-Munkres算法求出了工件排序问题的最优解。
16、对于就业问题，可以直接转换为匹配问题，利用匈牙利算法求最优解。2基础理论在进行应用前，首先对匹配的基础知识进行整理，然后介绍了排课问题以及工件排序问题的相关知识。2.1匹配理论定义1：是图的边子集，且中任意两边在中不相邻，则称是中的一个匹配或称对儿集；中的每条边的两个端点称为在中相配；中每边的端点称为被许配；中每个顶点皆被许配时，称为的一个完备匹配；中边数最多的匹配称为的最大匹配。定义2：设是图的一个匹配, 中的一条轨上，u与v未被许配，但上的边交替地不在中出现与在出现，则称为的可增广轨。定理1：（Berge，195）是图中的一个最大匹配当且仅当中无可增广轨。 定理2：（Hall，1935）设
17、是二分图，顶集的二分图划分为与，即，中无邻顶对，中亦然；存在把中顶皆许配的匹配的充要条件是,其中是中每个顶的邻顶组成的所谓的邻集。推论1：次正则2分图有完美匹配。定理3：（Knig，1931）若是二分图，则其最大匹配的边数为。定理4：（Tutte，1947）图有完美匹配的当且仅当对，其中是中的奇数个顶的连通片的个数。为解决此类匹配问题，1965年匈牙利数学家埃德蒙兹（Edmonds）基于Berge定理和Hall定理进行了改进设计了一种命名为“匈牙利算法”的有效算法，既能判定一个二部图中完美匹配是否存在，又能在存在时求出一个完美匹配。其算法思想：从图的任何匹配开始，（1）若饱和，则是的完美匹配；
18、（2）若不饱和，在中选择一个不饱和点x。若存在以x为起点的增广轨P，则由Berge定理知不是最大匹配，且是比更大的匹配。用替代重复上述过程；若中不存在以x为起点的增广轨，则可找到与由交错路相连的顶点集合，而满足（见Hall定理的证明）。由Hall定理，不存在完美匹配。算法步骤：step0.任取图的一个匹配。 step1.若饱和，则停止，是的完美匹配。 否则，取中一个不饱和点x，记。step2.若，则停止，无完美匹配。（因),否则取。step3.若y是饱和的，设，转step2（此时仍保持)。否则，取增广轨，令，转step1。2.2排课问题的理论本校有位教师和个班级，老师为班每日授课学时，试安排一
19、个授课表，使学校上课的时间最少。令，顶与之间有条边相连，形成一个有重边的二分图。每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课，于是我们的问题就是求。又，可见若没有授课多于节的老师，也没有上课多于节的班级，则可编出一个至多节课的时间表；如果只有指定的几间教室可用，全校一天最少只排几节课？设共计门功课，编成每天节课的课表，每节课平均开门功课，至少要间教室，为了分析这一问题，我们为之建立引理和定理。引理1：与是图的无公共边的匹配，且，则存在无公共边的匹配与，使得，定理1：是二分图，则内存在个无公共边的匹配，使得，且对，.2.3工件排序问题的理论Kuhn-Munkres算法1.从任意
20、可行的定点标号开始，确定等子图,并且在中选取匹配M。若M饱和X，则M是完备匹配，得知M是最优匹配，算法停止，否则转入第2步。2.匈牙利算法终止于使。计算l,确定新的可行顶点标号l,并以l替代,以替代转入第1步。Kuhn-Munkres算法可以用来求中的最小权完备匹配。它基于下列结果。2.4就业问题理论构造一个二分图，,是的二分图的顶划分，其中，仅当可以胜任学科时，在顶与之间连一条边，如此构成一个应聘图，接下来利用匈牙利算法求得该二分图的最大匹配。3问题分析为了很好得解决排课问题以及工件排序问题，我们首先需要对排课问题和工件排序问题中所存在的问题进行分析，这样可以使我们更好得将匹配论文运用到排课
21、问题以及工件排序问题当中去。3.1排课问题分析排课问题其实也就是时间表问题,排课问题的解决是各所高校教务管理工作中劳动量大，复杂度高且需要耗费大量时间的一项重要工作。排课问题涉及到许多因素,其中有:上课班级、老师、授课时间等。由于排课文图中存在种种困难,现在大部分的院校还只能凭经验手工进行排课,在信息处理自动化不断发展的现代,显得极不协调。各大高校的教务管理中，排课的工作非常复杂，一般情况下是通过手工的方式，这样操作起来需要花费大量的精力，并且效率低下，教学资源很难得到充分的利用。因此，这是一个急需解决但这又是一个非常棘手的问题。由于各所高校课程和教学单位众多并且相互交叉，而老师和教室又十分短
22、缺，很难使用手工的办法制定出高效、准确、合理的课程表来。另外教学管理的信息化不能只建立在手工方式上，信息技术的成熟和理论研究为我们提供了用计算机进行自动排课的重要方法，因此用计算机编排出一套准确、高效、实用的课程表程序已经成为了可能。3.2工件排序问题分析在工件排序的问题中，如何使得加工的效率最高,一直是一个十分重要但又十分困难的问题。特别是当问题的规模达到很大的时候,现在各种算法计算就十分困难,而且有的甚至还无法得到合理的解决方案。3.3就业匹配问题分析大学生就业具有一定的特殊性，大学生就业现状的研究主要集中在三个方面：对大学生就业的整体形势的分析；关于大学生择业观的研究；关于大学生就业过程
23、中劳动力市场分隔、性别歧视、社会资本，以及其它歧视现象等的研究。各种类型的歧视和不可竞争性因素对大学生就业的影响非常突出。我国对大学生就业问题的研究主体之间还没有一个明确的分工。我们要再系统和科学的进一步地深入研究。4匹配理论的应用在上述的理论基础下，我们设计了基于匹配理论的排课方法，我们先根据教学的要求构造了排课模型图，然后用匹配理论对课时进行安排，使得每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课。对于工件排序问题，因为工件排序问题可转化为双竞赛图与偶图，所以我们通过Kuhn-Munkres算法求出了工件排序问题的最优解。4.1匹配理论在排课问题中的应用4.1.1符号约定本
24、院有10位老师和6个班级,老师为班每日授课学时。令，顶与之间有条边相连，形成一个有重边的二分图G。每一课时，每位老师最多为一个班上课，每个班至多接受一个老师授课。4.1.2构造关联矩阵排课表的时候需要明确教学的要求。教学要求会表达老师、课程、班级以及授课时间之间的关联关系，这关联关系可以使用关联矩阵进行量化，并用计算机进行存贮和处理。假定有十位老师和六个班级,教学要求所对应的关联矩阵可用下面的矩阵表示,其中,xi表示老师,yj表示班级,pij表示老师xi需要给班级yj上课的课时。 y1y2y3y4y5y6x1x2x3x4x5x6x7x8x9x1011 0 0 0 0 0 0 1 0 00001
25、4.1.3将关联距阵表示成图关联距阵可表示成一个图G,如图1所示。由图1可知：图G是一个以为顶点集，以下面授课关系为边集的偶图。图1 关联矩阵表示图4.1.4用匹配理论分配课时在这篇论文中，我们把一种颜色对应一个课时,也就是把k个课时的分配方案转换成图G的k边着色方案,每一次分配授课时间段其实就是边着色过程,这样就既可以保证在一张有k个课时的课表中,某一个老师所上的各个班级的课不在同一个学时中,同时还可以保证每一个班级所要上的不同老师的课也不在同一个学时中。如果这么做,假设教室的数量足够的情况下,我们就可以保证班级、老师以及课程等要素不会发生矛盾。图2就是图1的一种正常的着色方案。图2 着色方
26、案图图2中黑色对应课时1,红色对应课时2,黄色对应课时3,绿色对应课时4，紫色和粉色对应课时5。从图2中可以看出(以老师x2为例),老师x2在课时1要给班级y6上课，在课时2要给班级y1上课,在课时5要给班级y2上课。同样的，其余老师的授课情况同样可以从图2中看出。4.2匹配理论在工件排序问题中的应用有一台机床需要加工n种不同的零件(i=1,2,n).每加工完一种零件后，需要将机床加以改动后才能用来加工另一个零部件。假定加工完后，在加工前机床改动时间为。我们需要安排加工顺序使整台机床所耗费的总时间最短。我们给出如下例子，有6种零件需要被加工，改动机床所耗费的时间(单位为分)有如下的矩阵：T=t
27、ij=250为了找到好的加工顺序，我们构造了加权简单有向图（D，T），其中VD=J1，J2，J3，J4，J5，J6,且权为，这样可以得到如下的加权有向图（D，T）。W=200图3 加权有向图假设最好的加工顺序已安排好，它对应D中具有最小权的Hamilton有向路，设为。考虑对应于D的伴随二部图G，如图4所示，其中权。注意，由于D无环，所以这样的2部图G不含边，于是，D中任何Hamiton路P就对应于中一个完备匹配M,并且与P有相等的权。图4 D的伴随二部图G接下来，我们利用Kuhn-Munkres算法求出使整台机床所耗费的总时间最短的匹配来。考虑二部图加权图，其中加权矩阵W为想要求中最小权完备
28、匹配，只要求中最大权完备匹配，其中下面的矩阵就是。平凡标号和等子图如图5所示。图5 等子图有完备匹配，如图中的粗线所示：。是中的最小权完备匹配，且权为5，它对应D中的Hamilton有向路是。于是，按的顺序加工零件，改动机床的总耗时是5分钟，所以是最好的。4.3匹配理论在大学生就业市场中的应用某单位因业务扩大需要招聘五位各部门的经理。已知有五位毕业生去应聘该单位，并且知道这五位毕业生做这五项工作的利润矩阵为：求如何分配，可以使得该公司获利最大？分析此题考虑了利润的信息，属于求最优匹配的情形，基本思想是按一定的办法修改标号，使得和：不断下降，直到给出问题的解为止。标号的唯一要求是：，2，。解 (
29、1)给初始标号：如图10所示。 图10(2)在标号下得：.(3)用匈牙利算法求(图11)的最大匹配。匹配的边用实线给出。 图11(4)未饱和，.所以，.所以.（5）.（6）重新标号：，.(7)在新的标号下，增加了一条边，减少一条边，如图12所示。 图12(8)在新的标号下，存在，已饱和，.由于，存在 ，而且非饱和，故存在一条可增广道路：.作得图(5.2.4).图13(9)已饱和，是最优匹配。5结束语在这篇文章中，我们分析了排课问题以及工件排序问题的研究背景以及研究意义，还给出了国内外的研究现状。再对排序问题以及工件排序问题所存在的问题进行了分析，最后本文给出了解决的方案。对于排课问题，本文设计
30、了基于匹配理论的排课方法，我们先根据教学的要求构造了排课模型图，接着用匹配理论对课时进行安排，使得每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课。对于工件排序问题，因为工件排序问题可转化为双竞赛图与偶图，所以我们通过Kuhn-Munkres算法求出了工件排序问题的最优解。参考文献1Peterson.Die theorie der regularen graphenJ.Acta Math.1891,15:193-220.2Konig.line sysrem ang determinatsJ.Math.Termesz. Eet.1915,33:221-229.3P.Hall.On
31、representatives of subsetsJ.London Math.Soc.1935,10:26-30. 4Rado.A Theorem on independence relationsJ.Quart.Marh.Oxford.1942,13:83-89. 5K.Cameron.Induced matchingJ.Discrete Appl.Math.1989,24:72-102. 6J.J.Yuan.Induced matching extengable graphsJ.Graph Theory.1998, 28:203-213. 7Kuhn.The Hungarian meth
32、od for the assignment problemJ.Naval Res.Logist.Quart.1955,2: 83-97. 8P.Hall.An algorithm for distinct representativesM.Amer. Math:Mon-thly,1956,716-717. 9L.R.Ford,D.R.Fulkerson.A simple algorithm for finding maximalnetwork flows and application to the Hitchcock problemJ.Canad.Math.1957,9:210-218. 1
33、0Galil.Efficient algorithms for finding maximum matching in graphJ.ACM Computing Surveys.1986,18:23-38.11J.Hopcroft,R.Karp.An algorithm for maximum matching in bipartite graphsJ.SIAM Computing.1973,2:225-231. 12文胜.双边匹配理论及在中国银行信贷市场中的运用D.武汉:华中科技大学,2006.13聂海峰.高考录取机制的博弈分析J.经济学(季刊),2007,6(3):899-915.14张成
34、.中国大学生劳动力市场的微观研究J.经济研究导刊,2009,(21):110-111. 15张振华,汪定伟.电子中介中的交易匹配研究J.控制与决策,2005,20(8):917-920.16赵希男,温馨,贾建锋.组织中人岗匹配的测算模型及应用J.工业工程与管理2008,13(2):112-117.17王树禾.图论M.科学出版社:北京,2004. 67-91答 谢首先感谢西北民族大学给我提供了学习和深造的机会以及良好的学习环境，然后感谢学院的领导和老师们,他们给予了我们全方面的关心和照顾。本论文是在西北民族大学数学与计算机科学学院李老师的悉心指导下完成的。李老师作为一名优秀的、经验丰富的教师，具有丰富的知识和经验，在整个论文写作过程中，对我们进行了耐心的指导和帮助，提出严格要求，引导我不断开阔思路，为我们答疑解惑，鼓励我们大胆创新，使我们在这一段宝贵的时光中，既增长了知识、开阔了视野、锻炼了心态，又培养了良好的钻研精神，在此，我们小组向我们的指导老师李琼老师表示最诚挚的谢意。在论文即将完成之际，我们的心情无法平静，从开始选题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我们小组无言的帮助，在这里请接受我们诚挚的谢意。最后我们小组还要深深谢谢培养我们长大含辛茹苦的父母，谢谢你们。