匹配理论及其应用第二组

论文编号《图论》课程

专题论文论文题目:匹配理论及其应用论文题目:匹配理论及其应用专业：数学与应用数学班级：2014级数学与应用数学组长:姓名学号成绩2017年12月10日

论文评价指标与鉴定意见论文题目匹配理论及其应用完成人专业及班级2014级数学与应用数学指标论文评价（对表格中的各栏，用表示意见）优良中差论文选题基础理论与专门知识语言的表达水平创新性学术价值应用价值总体评价A（86—100分）B（70—85分）C（60—69分）D（0—59分）鉴定意见评阅人签名：成绩评阅人职称专业

论文题目匹配理论及其应用专业年级2014级数学与应用数学组长吴娜电话QQt完成人分工情况完成度（%吴娜分析题目，选择框架21%[Mi思雨查询资料，有关匹配的理论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-MunkresalgorithmTOC\o"1-5"\h\z1绪论1选题背景1研究的意义2国内外研究综述3研究的思路与方法52基础理论6匹配理论6排课问题的理论8工件排序问题的理论93问题分析9排课问题分析9工件排序问题分析104匹配理论的应用10匹配理论在排课问题中的应用11匹配理论在工件排序问题中的应用135结束语16参考文献20答谢221绪论一直以来图论倍受人们关注，图论中的匹配理论在很多领域得到了应用，我们对排课问题和工件排序问题的背景和研究意义进行了了解，并且阐述了国内外对匹配的研究，以及对排课问题和工件排序问题存在的问题进行了分析。止匕外，大学生就业难已经成为中国一个十分突出的问题，因而利用匹配理论的知识对大学生就业市场的研究具有重大的意义。匹配是图论的一个重要内容。匹配理论很好的描述了市场中双向选择的情形，解释了一个市场能稳定存在的根源，并为我们对各种市场进行设计建立合理的市场机制提供了可行的选择。选题背景随着近年来我国高校不断扩招，学生人数不断增加，但是与之相配的学校的各种基础资源设施并没有跟上。例如老师、教室、多媒体资源等等。所以，高校排课成为新一轮的难题。传统人工排课是基于学生人数少，教室也不多的情况下，对老师等各种资源的合理分配。虽然传统人力排课能在一定程度上解决这个难题，但随着学生人数的增加，新课程内容的添加，老师人数相对较少，人工排课势必要耗费大量的时间与精力。显然，在如今讲求高效率的社会体系中，无论哪一方，都不愿意因排课这件小事而耗费大量时间与精力。所以，怎样合理优化老师、学生、教室、多媒体等各种资源就成了高校每年新学期开始面临的“当务之急”。

目前，大学生就业难已经成为中国一个十分突出的问题中国经目前，大学生就业难已经成为中国一个十分突出的问题中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并非如此。“毕业即失业”已经成为普遍现象。在工件加工的过程中，有加工时间、加工顺序、加工价值等因素的限制，在大规模使用机器制造的背景下，需要利用一些处理机，机器或资源，最优地完成一批给定的任务或作业。排序问题有深刻的实际背景和广阔的应用前景。被广泛应用于计算机系统，运输调度，生产管理等领域。研究的意义排课问题研究的意义本文通过对匹配理论的发展过程、国内外发展现状、研究的思路与方法以及应用匹配理论解决排课问题的事例进行一个相对比较完整的综述，为我国的研究匹配理论的学者提供一些参考。另外，高校的教务管理中，排课工作非常复杂且手工操作要花费大量精力，不仅效率低，而且教学资源也很难被充分利用。将匹配理论与高校排课结合起来，设计一种相对稳定的匹配机制，优化高校排课，增加排课的效率和匹配的稳定性。工件排序问题研究的意义我国的生产企业工件排序效率未能合理优化的问题，这不仅影响企业效益，还会造成资源浪费，影响整个行业的发展。对于这种情况，有必要对工件排序进行分析研究，将匹配理论与工件排序问题结合起来，设计一种相对稳定的匹配机制，优化工件排序，增加工件排序的效率和匹配的稳定性，进而促进整合行业的发展。就业问题研究的意义目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并非如此，“毕业即失业”已经成为普遍现象。将匹配理论应用到就业问题中，解决就业困难的匹配问题，既丰富了对就业问题的研究，也扩大了匹配理论的应用范畴。国内外研究综述匹配理论的研究和发展已有悠久的历史，在这发展的过程中匹配理论逐步发展成为运筹学中重要的一部分，与此同时，它也是图论的核心内容。在实际生活中，许多问题都与匹配理论有着紧密的联系，在这种情况下，许多国内外学者对匹配理论进行了研究并且将匹配理论应用于实际问题中。国外研究情况在1891年匹配理论开始发展，丹麦人Petersen首先对正则图中的完美匹配川进行了研究：证明了任意一个3-正则连通图，如果没有两条以上割边，则此图就有完美匹配。1915年匈牙利人konig对二部图中的完美匹配⑵进行了研究。1947年，Tutte对普通图中的完美匹配进行研究，得出了判别一个图G是否存在完美匹配的充要条件：一个图G有完美匹配当且仅当对任意SGV(G),不等式O(G.S闫耳，其中O(G—S)表示图G—S中顶点数为奇数的连通片的个数。1935年,P.Hall对二部图中的匹配问题进行研究，并且得到了Hall定理［3］:设图G是一个二部图，两顶点集分别为X、Y,其存在一个浸润X(即包含X的全部顶点)的匹配的充要条件是：Y中与X的任意子集S相邻的顶点数不小于S中的顶点数。1942年，Rado将Hall定理推广到欧氏向量空间中相异代表系独立系统网，首次将匹配和拟阵联系起来。在此之后匹配理论得到了迅速的发展：1964年Gallai提出了依赖最大匹配的图的规范分解理论、1972年Lovasz定义了图的双临界性、1980年Plunner定义了K-可扩图的概念、1989年Cameron5］定义了导出匹配的概念、1998年原晋江［6］首次提出了关于导出匹配可扩图的概念等。随着计算机的发展，有关匹配问题的算法不断被提出。1955年Kuhn［7］及1956年Hall［8］首先提出了寻找二部图的完美匹配的线性规划算法。同年，Ford和Fulkerson［9］发表了关于网络流理论的著作。之后，网络流理论也开始应用于二部图的匹配问题(不赋权和赋权的)［10］［11］,并且得到较好的结果。国内研究情况相对于国外对匹配理论的研究，国内对这方面的相关研究是比较少的，具大部分的研究是结合了中国的一些相关实例。例如文胜［12］运用双边匹配理论阐述中国信贷市场二元结构一一目标客户信贷市场和非目标客户信贷市场；聂海峰［13］总结GS算法，得到了新的中国高考录取机制，假设在得知高考分数得情况下报考录取的制度只有唯一一个纳什均衡结果，并且均衡是帕累托有效和公平的，这个机制是基于信息是完全的情况下进行说明的。张成［14］进一步研究了应届毕业生劳动力市场匹配模型，根据我国应届毕业生劳动力市场存在的问题，结合双边匹配理论对我国劳动力市场进行研究、剖析，构建了随机非中心化单次录取机制模型，得出了市场的不稳定性和其他的相关结论，诠释了市场上出现这种现象的原因。张振华和汪定伟［15］构建了关于电子中介的多目标匹配模型，基于电子中介处理多属性商品交易，得到了双方的满意度函数，利用最大化双方满意度作为排序清单，构建多个买家和卖家多目标匹配平台，得出求解单目标的优先贪婪算法。赵希男等［16］专家对人与组织匹配测试方法提出新的观点，与人员与组织匹配的纵向匹配指标、横向匹配指标以及截面匹配指标的测试模型相结合，得出相对应的匹配结果。研究的思路与方法对于排课问题，我们设计了基于匹配理论的排课方法，我们先根据教学的要求构造了排课模型图，然后用匹配理论对课时进行安排，使得每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课。对于工件排序问题，因为工件排序问题可转化为双竞赛图与偶图，所以我们通过Kuhn-Munkres算法求出了工件排序问题的最优解。对于就业问题，可以直接转换为匹配问题，利用匈牙利算法求最优解。2基础理论在进行应用前，首先对匹配的基础知识进行整理，然后介绍了排课问题以及工件排序问题的相关知识。匹配理论定义1：M是图G的边子集，且M中任意两边在G中不相邻，则称M是G中的一个匹配或称对儿集；M中的每条边的两个端点称为在M中相配；M中每边的端点称为被M许配；G中每个顶点皆被M许配时，称M为G的一个完备匹配；G中边数最多的匹配称为G的最大匹配。定义2：设M是图G的一个匹配，G中的一条轨P(u,v)上，u与V未被M许配，但P(u,v)上的边交替地不在M中出现与在M出现，则称P(u,v)为M的可增广轨。定理1:(Berge,195)M是图g中的一个最大匹配当且仅当G中无M可增广轨。定理2:(Hall,1935)设G是二分图，顶集的二分图划分为X与Y,即V(G)=X=Y,XCY=0,X中无邻顶对，Y中亦然；存在把X中顶皆许配的匹配的充要条件是VS^X,|N(S)|>|S,其中N(S)是S中每个顶的邻顶组成的所谓S的邻集。推论1:k(k>0)次正则2分图有完美匹配。定理3:(K0nig,1931)若G是二分图，则其最大匹配的边数为P(G),(P(G)是G的覆盖数)。定理4:(Tutte,1947)图G有完美匹配的当且仅当对VScV(G),o(G-S)<|S,其中o(G—S)是G-S中的奇数个顶的连通片的个数。为解决此类匹配问题，1965年匈牙利数学家埃德蒙兹(EdmondS基于Berge定理和Hall定理进行了改进设计了一种命名为“匈牙利算法”的有效算法，既能判定一个二部图中完美匹配是否存在，又能在存在时求出一个完美匹配。其算法思想：从图G的任何匹配M开始，(1)若M饱和X,则M是G的完美匹配；(2)若M不饱和X,在X中选择一个M不饱和点X。若存在以x为起点的M增广轨P,则由Berge定理知M不是最大匹配，且M'=M$E(P)是比M更大的匹配。用M'替代M重复上述过程；若G中不存在以X为起点的M增广轨，则可找到与X由M交错路相连的顶点集合A,而s=acx满足|N(S)|<S(见Hall定理的证明)。由Hall定理，G不存在完美匹配。算法步骤：step0.任取图G的一个匹配M。Step1.若M饱和X,则停止，M是G的完美匹配。否则，取X中一个M不饱和点X,记S=~｝万=0。step2.若N(S)=T,则停止，G无完美匹配。(因N(S)|=Th|s|-1<|s|),否则取yWN(S)Tostep3,若y是M饱和的，设yzwM^S=S"x},T=T={y},转step2(此时仍保持T=S-1)o否则，取M增广轨P(x,y),令M'=MeER),转stepl。排课问题的理论本校有m位教师Xi,X2,...,Xm和n个班级%)2，...»,Xi老师为yj班每日授课Pj学时，试安排一个授课表，使学校上课的时间最少。令X={xi,X2,...,Xm),Y={yi,y2,...,yn),顶Xi与yj之间有Pj条边相连,形成一个有重边的二分图G。每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课，于是我们的问题就是求x1(G)o又■Z‛(G)=A(G),可见若没有授课多于P节的老师，也没有上课多于P节的班级，则可编出一个至多P节课的时间表；如果只有指定的几间教室可用，全校一天最少只排几节课？设共计l门功课，编成每天P节课的课表，每节课平均开,门功P课，至少要间教室，为了分析这一问题，我们为之建立引理和定p理。引理1：M与N是图G的无公共边的匹配，且|m|a|n|,则存在无公共边的匹配M'与N’,使得|M'|=|M|-1，|N'|=|N|+1，M'uN'=M=N定理1：G是二分图，AEp,则G内存在P个无公共边的匹配M1,M2,...,Mp,使得PE(G)=^Mi,且对1与Mp,；(G)；(G)[、^]H|Mi|M{q}.工件排序问题的理论Kuhn-Munkres算法.从任意可行的定点标号l开始，确定l等子图Gl,并且在Gl中选取匹配M若M饱和X,则M是完备匹配，得知M是最优匹配，算法停止，否则转入第2步。.匈牙利算法终止于SuX,TuY使Ng（S）=T。计算？??确定新的t可行顶点标号？域以准代l,以G替代Gl转入第1步。Kuhn-Munkres算法可以用来求（心皿切）中的最小权完备匹配。它基于下列结果。2.4就业问题理论构造一个二分图g,V（E）=XJy，X，丫是G的二分图的顶划分，其中，X={xxxxx}Y-{vvvvv}，仅当x可以胜任学科v时，在顶x与X-■%,X2，%,X4,%.,Y-.y1,%,y3,y4,y5xiyjxi、，之间连一条边，如此构成一个应聘图G,接下来利用匈牙利算法求得该二分yj图的最大匹配。3问题分析为了很好得解决排课问题以及工件排序问题，我们首先需要对排课问题和工件排序问题中所存在的问题进行分析，这样可以使我们更好得将匹配论文运用到排课问题以及工件排序问题当中去。排课问题分析排课问题其实也就是时间表问题，排课问题的解决是各所高校教务管理工作中劳动量大，复杂度高且需要耗费大量时间的一项重要工作。排课问题涉及到许多因素，其中有：上课班级、老师、授课时间等。由于排课文图中存在种种困难，现在大部分的院校还只能凭经验手工进行排课，在信息处理自动化不断发展的现代，显得极不协调。各大高校的教务管理中，排课的工作非常复杂，一般情况下是通过手工的方式，这样操作起来需要花费大量的精力，并且效率低下，教学资源很难得到充分的利用。因此，这是一个急需解决但这又是一个非常棘手的问题。由于各所高校课程和教学单位众多并且相互交叉，而老师和教室又十分短缺，很难使用手工的办法制定出高效、准确、合理的课程表来。另外教学管理的信息化不能只建立在手工方式上，信息技术的成熟和理论研究为我们提供了用计算机进行自动排课的重要方法，因此用计算机编排出一套准确、高效、实用的课程表程序已经成为了可能。工件排序问题分析在工件排序的问题中，如何使得加工的效率最高，一直是一个十分重要但又十分困难的问题。特别是当问题的规模达到很大的时候现在各种算法计算就十分困难，而且有的甚至还无法得到合理的解决方案。就业匹配问题分析大学生就业具有一定的特殊性，大学生就业现状的研究主要集中在三个方面：①对大学生就业的整体形势的分析；②关于大学生择业观的研究；③关于大学生就业过程中劳动力市场分隔、性别歧视、社会资本，以及其它歧视现象等的研究。各种类型的歧视和不可竞争性因素对大学生就业的影响非常突出。我国对大学生就业问题的研究主体之间还没有一个明确的分工。我们要再系统和科学的进一步地深入研究。4匹配理论的应用在上述的理论基础下，我们设计了基于匹配理论的排课方法，我们先根据教学的要求构造了排课模型图，然后用匹配理论对课时进行安排，使得每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课。对于工件排序问题，因为工件排序问题可转化为双竞赛图与偶图，所以我们通过Kuhn-Munkres算法求出了工件排序问题的最优解。匹配理论在排课问题中的应用符号约定本院有10位老师Xi,x2,...,xio和6个班级乂,..』,为老师为yj班每日授课Pij学时。令X={x1,X2,...,Xm},Y="1,丫2,...,丫口）,顶X与％之间有Pij条边相连，形成一个有重边的二分图Q每一课时，每位老师最多为一个班上课，每个班至多接受一个老师授课。构造关联矩阵排课表的时候需要明确教学的要求。教学要求会表达老师、课程、班级以及授课时间之间的关联关系，这关联关系可以使用关联矩阵进行量化，并用计算机进行存贮和处理。假定有十位老师和六个班级，教学要求所对应的关联矩阵可用下面的矩阵表示，其中，？漆示老师，？?表示班级，？??表示老师？襦要给班级？?±课的课时。??？？？？？？？？？？TOC\o"1-5"\h\z？？110000？？110011？？110000？？110000？？000010？？000010？？002100？？000100？？001200？%000001将关联距阵表示成图关联距阵可表示成一个图G,如图1所示。由图1可知:图G是一个以x={x1,X2,...,X0k>y={y1,y2,..,y6）为顶点集，以下面授课关系为边集的偶图。Pj-灰丫1,、丫2,*2%/2丫2*2丫5,“丫643丫1木3丫2,羽丫1,儿丫2*5丫5,小丫5*7丫3*7丫4,4丫4*9丫3木9丫4,40丫6.'图1关联矩阵表示图用匹配理论分配课时在这篇论文中，我们把一种颜色对应一个课时,也就是把k个课时的分配方案转换成图G的k边着色方案，每一次分配授课时间段其实就是边着色过程，这样就既可以保证在一张有k个课时的课表中，某一个老师所上的各个班级的课不在同一个学时中，同时还可以保证每一个班级所要上的不同老师的课也不在同一个学时中。如果这么做,假设教室的数量足够的情况下，我们就可以保证班级、老师以及课程等要素不会发生矛盾。图2就是图1的一种正常的着色方案。图2着色方案图图2中黑色对应课时1,红色对应课时2,黄色对应课时3,绿色对应课时4,紫色和粉色对应课时5。从图2中可以看出(以老师乂2为例)，老师x2在课时1要给班级y6上课，在课时2要给班级y1上课，在课时5要给班级y2上课。同样的，其余老师的授课情况同样可以从图2中看出。匹配理论在工件排序问题中的应用有一台机床需要加工n种不同的零件J(i=1,2,,,n).每加工完一种零件后，需要将机床加以改动后才能用来加工另一个零部件。假定加工完Ji后，在加工Ji前机床改动时间为我们需要安排加工顺序使整台机床所耗费的总时间最短。我们给出如下例子，有6种零件需要被加工，改动机床所耗费的时间t式单位为分)有如下的矩阵:T=?????T=?????=012114534210123250123440123450542310为了找到好的加工顺序,我们构造了加权简单有向图(为了找到好的加工顺序,我们构造了加权简单有向图(D,??),其中V其中VD=??,??挈，？？璃召,(Ji,J)wE(D)utj<tji,且权为tj,这样可以得到如下的加权有向图(D,??)TOC\o"1-5"\h\z000001101232_200120-100012130000002010图3图3加权有向图假设最好的加工顺序已安排好，它对应D中具有最小权的Hamilton有向路，设为P*。考虑对应于D的伴随二部图G,如图4所示，其中权6(A，aJ=tj。注意，由于D无环，所以这样的2部图G不含边Aai,i=1,2，…,6.于是,D中任何Hamiton(Ji,Jj)路P就对应于G-{A©}中一个完备匹配M,并且与P有相等的权。

图4D的伴随二部图G接下来，我们利用Kuhn-Munkres图4D的伴随二部图G接下来，我们利用Kuhn-Munkres算法求出使整台机床所耗费的总时间最短的匹配来。考虑二部图加权图（K6,6g）,其中加权矩阵W553421151232125W=T+5I=

14想要求（（,6f）中最小权完备匹配，只要求（K6,6©'）中最大权完备匹配，其中下面的矩阵就是W'=5J-W。平凡标号l和l等子图G如图5所示。4210004-11324014011000

图5等子图Gi_｛与a｝有完备匹配，如图中的粗线所示:*M—{Ala6>A2a3>A3a4>A4a5,A5a1}°W'（M*）=4*5=20。M*是G-｛2但｝中的最小权完备匹配，且权为5,它对应D中的Hamilton有向路是（（』,"/』/）。于是，按11111J2》J3》J4》J5》J1,J6的顺序加工零件，改动机床的总耗时是5分钟，所以是最好的。匹配理论在大学生就业市场中的应用某单位因业务扩大需要招聘五位各部门的经理。已知有五位毕业生去应聘该单位，并且知道这五位毕业生做这五项工作的利润矩阵为:一5440一5440■3746347063364305314005求如何分配，可以使得该公司获利最大?分析此题考虑了利润的信息，属于求最优匹配的情形，基本思想是按一定的办法修改标号l,使得和:

n

n

z

i=11xi1yj不断下降，直到给出问题的解为止。标号l的唯一要求是:TOC\o"1-5"\h\zl(K)+1(yj)至cji,j=12解(1)给初始标号:lx1=maxGj=max5,7,7,6,3=7,lx2=maxc2j=max(4,4,0,4,4)=4,lx3=maxc3j=max4,6,6,3,0=6,lx4=maxc4j=max0,3,3,0,0=3,lx5=maxc5j=max3,4,3,5,5=5,ly1)=ly2)=ly3)=ly4)=l丫5)=。如图10所示⑺(4)(6)⑶(5)yi(0)V2(0)V3(0)y4(0)V5(0)图10(2)在标号l下得:E=\%丫2,乂1丫3,乂2丫1*2丫2*2丫4,乂2丫5*3丫2*3丫3,乂4丫2,乂4丫3*5丫4,%丫5：(3)用匈牙利算法求(图11)的最大匹配。匹配的边用实线给出lxly⑺X1-.yi(0)(4)X2-y2(0)4Jr—产\、i-1"、产、［»k-f(6)X3•―—iV3(0)⑶X4『-］、y4(0)(5)X5一一一二y5(0)图11⑷人未饱和，vi~a'v2~0.：lVi二V2,y3IVV2,y3，x3M.所以Vi=氏必}又2='}MM产V2,y2^P?(Vi)V2,(y2?产M所以Vi-汽4，%,%：，"2=句3，丫2),：1ViV-V2

.-Vi72=、”“%),.=现{l(xi户比)—cJumyVhXi)+l(yj)—q}=1

xiiVi1n，3,4yj%ivjm4,5(6)重新标号：1Xi=7-1=6,1X3=6-1=5,1X4=1-1=01y2=01=1,1y3=01=1⑺在新的标号1下，E1增加了一条边乂也，减少一条边用丫2,如图12所示。(6)xi(6)xi(4)X2⑸x:,一＞一7V3⑴J_rOn、(2)X4y4(0)(5)X5-----=y5(0)图12⑹在新的标号1下，存在y4W「1(M)V2,丫4已饱和，Vi=&,x3,xi,x5},丫2="3)2，}.由于「9产V2,存在y5三「MV-2,而且y5非饱和，故存在一条可增广道路P：P=G4y3x3y2xiy4x5y5\作M-M@E(P)得图(5.2.4).x5■V5图13(9)x已饱和，刈4,%丫2,%小，%丫5是最优匹配。w="-32C43C55^64635-245结束语在这篇文章中，我们分析了排课问题以及工件排序问题的研究背景以及研究意义，还给出了国内外的研究现状。再对排序问题以及工件排序问题所存在的问题进行了分析，最后本文给出了解决的方案。对于排课问题，本文设计了基于匹配理论的排课方法，我们先根据教学的要求构造了排课模型图，接着用匹配理论对课时进行安排，使得每一学时，每位老师最多为一个班上课，每个班至多接受一个老师授课。对于工件排序问题，因为工件排序问题可转化为双竞赛图与偶图，所以我们通过Kuhn-Munkres算法求出了工件排序问题的最优解。参考文献[1]Peterson.Dietheoriederregularengraphen[J].ActaMath.1891,15:193-220.[2]Konig.linesysremangdeterminats[J].Math.Termesz.Eet.1915,33:221-229.[3]P.Hall.Onrepresentativesofsubsets[J].LondonMath.Soc.1935,10:26-30.[4]Rado.ATheoremonindependencerelations[J].Quart.Marh.Oxford.1942,13:83-89.[5]K.Cameron.Inducedmatching[J].DiscreteAppl.Math.1989,24:72-102.[