数学建模y04研究生录取中的最佳匹配问题D题

D题--一等奖1研究生录取中的最佳匹配问题摘要：本文将考生录取问题转化为图论中一个特定约束条件下双向二部图的最大权匹配问题。对于问题一，采用搜索法直接得到最优解，运算复杂度为O(MN)。对于问题二，考虑是否满足稳定匹配条件的两种情况，采用Kuhn-Munkras算法和改进的Kuhn-Munkras算法分别求得最大满意度的解和极大满意度的解，前者的算法复杂度仅为O(Nlog2N)。对于问题三，分两步解决。首先给出一种选优录取10个考生的方法，在此基础上提出了一种最大平衡策略，求出一组约束条件下的极大解。对于问题四，首先在充分考虑考生志愿和专业平衡的条件下，给出了5名导师和10名考生的选择策略，然后在此基础上采用虚拟导师节点的方法，转化为问题二中的情况进行求解。最后，我们分析上述各种策略的弊端，提出了虚拟节点的方法，有效消除了上述弊端，并将模型统一到问题二的情况中。本文的最终模型可扩展性好，算法复杂度低，较好的解决了本文提出的所有问题。问题的重述某学校Ｍ系计划招收10名计划内考生，依照有关规定由初试上线的前15名考生参加复试，专家组由8位专家组成。在复试过程中，要求每位专家对每个参加复试考生的以上５个方面都给出一个等级评分，从高到低共分为A,B,C,D四个等级，并将其填入面试表内。所有参加复试考生的初试成绩、各位专家对考生的５个方面专长的评分如表（１）～表（8）所示。该系现有10名导师拟招收考生，分为四个研究方向。导师的研究方向、专业学术水平（发表论文数、论文检索数、编(译)著作数、科研项目数），以及对考生的期望要求见表(9)。在这里导师和考生的基本情况都是公开的。要解决的问题是：(1)首先，请你综合考虑考生的初试成绩、复试成绩等因素，帮助主管部门确定10名考生的录取名单。然后，要求被录取的10名考生与10名导师之间做双向选择，即考生可根据自己的专业发展意愿（依次申报２个专业志愿，如表(10)所示）、导师的基本情况和导师对考生的期望要求来选择导师；导师根据考生所报专业志愿、专家组对考生专长的评价和自己对考生的期望要求等来选择考生。请你给出一种10名考生和导师之间的最佳双向选择方案（并不要求一名导师只带一名考生），使师生双方的满意度最大。(2)根据上面已录取的10名考生的专业志愿，如果每一位导师只能带一名考生，请你给出一种10名导师与10名考生双向选择的最佳方案，使得师生双方尽量都满意。(3)如果由十位导师根据初试的成绩及专家组的面试评价和他们自己对考生的要求条件录取考生，那么，10名考生的新录取方案是什么？为简化问题，假设没有申报专业志愿，请你给出这10名考生各申报一名导师的策略和导师各选择一名考生的策略。相互选中的即为确定；对于剩下的导师和考生，再按上述办法进行双向选择，直至确定出每一名导师带一名考生的方案，使师生都尽量满意。(4)学校在确定考生导师的过程中，要充分考虑考生的申报志愿情况。为此，学校要求根据10名导师和15名考生的综合情况选择5名导师招收考生，再让这5名导师在15名考生中择优录取10名考生。请你给出一种导师和考生的选择（录取）方案，以及每一名导师带２名考生的双向选择最佳策略。(5)请你设计一种更能体现“双向选择”的考生录取方案，提供给主管部门参考，并说明你的方案的优越性。模型的假设D题--一等奖21．考生和导师都是诚实的，在按策略选定录取方案时不会撒谎。2．考生填报的志愿要尽量满足，专业不对口将大大降低考生和导师的满意度。符号系统T,S:S表示所有导师组成的集合，T表示所有考生组成的集合。N，M：分别表示系统中考生和导师的个数，N=|S|，M=|T|。Ai＝(Ai1，Ai2，Ai3，Ai4，Ai5)：考生i的复试成绩中的5项指标的成绩的归一化值向量。Bi：考生i的复试综合成绩的归一化值。iγ：考生i的初试成绩的综合归一化值。MNjiW×=][,ω：考生对导师的满意度矩阵，ji,ω表示当考生i被导师j录取时，考生i的满意度。MNjiW×′=′][,ω：导师对考生满意度的矩阵。ji,ω表示当考生i被导师j录取时，导师j的满意度。jia,：与考生i是否报了导师j的专业这一因素相关的系数，取值0～1之间。lj,λ：导师j的学术水平在指标l)4,3,2,1(=l上的归一化值。bj：导师j的学术水平综合值。lji,β：考生i与导师j在复试指标l上的专长期望匹配度的归一化值。ci,j：考生i与导师j总的专长期望匹配度的归一化值。sgn(x)：sgn(x)表示变量x的符号，定义如下：⎩⎨⎧≤−=0,10,1)sgn(xxx)(xfloor：x向下取整函数；问题的分析1.将考生录取转化为二分图的匹配问题本文需要解决的问题是在特定的约束条件下，导师和考生之间建立一种匹配关系（即：考生被某个导师录取），使得导师和考生双方的总满意度最大。可以把导师集合T和考生集合S看成某个二部图顶点集的两个子集，连接S与T的边表征了某考生对某导师可能的申报关系，该边上的权表征了申报该导师使得该考生所能获取的满意度；连接T到S的边表征了导师对考生可能的录取关系，其上的权表征了录取该考生使得该导师所能获取的满意度。该二部图具有以下特点：①它的边是双向的。这种双向的边是成对出现的，即：对于每个考生，如果存在他对某个导师的申报可能，就必然存在该导师对此考生的录取可能；反之亦然。②它的边是带权的。D题--一等奖3③本文的目标是在某种特定约束下，构造一种考生到导师的匹配使得在该匹配下考生和导师双方的总体满意度最大。这样我们就将本文的所有问题映射到了图论中特定约束条件下双向二部图的最大权匹配问题。下图为一个简单的双向二部图的最大权匹配问题。图1一个双向带权二部图的实例图1中考生集合S={A,B,C,D}，导师集合T={1,2,3,4}，图1表中列出上述左图二部图上任意双向边上的正反两向的权值。现实中类似的双向带权二部图的实例还有婚姻匹配问题[1,3,4,6]，任务分配问题[2,5]等。总体满意度可以表示为考生的总体满意度和导师的总体满意度的线性组合，因此可以将二部图中的双向边转化为单向边，同时将边上的权修正为正向权值与反向权值的线性组合，则双向二部图的总体满意度最大问题就可以转化为对应的无向二部图中的最大权匹配问题了。2．不稳定匹配方案的概念与满意度的关系正如婚姻匹配问题中可能存在不稳定的匹配方案一样，通过上述方法解出的匹配方案也可能存在不稳定的匹配对。对于婚姻匹配问题而言，一个不稳定的匹配对(x,y)指的是一对不稳定的男x女y，他们没有结合，但是x喜欢y的程度胜过他喜欢目前的配偶，并且y喜欢x的程度也胜过她目前配偶；同样的，对于一种匹配方案而言，如果存在这么一对男女，这个系统就称为不稳定，其所以不稳定是因为x和y最有可能放弃目前配偶，双双私奔，造成社会不安。同样的，对于一种强调“双向选择”的匹配系统而言，不稳定匹配对的出现可能会造成匹配方案的崩溃。对考生录取问题而言，一个不稳定匹配对的例子如图2：TutorsStudent1234A0，02，30，04，5B4，20，00，00，0C0，03，14，55，3D3，60，00，02，4D题-张雄明，晏小波，褚瑞-一等奖4图2一个不稳定匹配对的实例,边上的权用二元组表示。如（1,2）表示，从左到右的权为1，从右到左的权为2如图2所示，假设（S1,T1）、（S2,T2）为二部图最大权匹配的两条边，但S1对T1的满意度为1，S1对T2的满意度为2；而T2对S1的满意度为2，T2对S2的满意度为1，这样，相对于T1,S1更倾向于选T2做导师，T2也更倾向于选S1做考生，这样的匹配对（S1,T1）和（S2,T2）就是一对不稳定匹配对。含有不稳定匹配对的匹配方案也称之为不稳定的。模型的建立在建立模型之前，我们需要先对已有数据进行处理，从中构造出下列信息：1．各个考生的复试成绩指标及复试成绩归一化值。考生i的复试成绩向量Ai＝(Ai1,Ai2,Ai3,Ai4,Ai5)与考生的复试成绩的5项指标有关，对于某项指标i，他的分数取所有专家打分的平均(更一般的情况为所有专家打分的凸线性组合)，则他的复试成绩∑==515.0jjiiAB。2．考生对导师的满意度的矩阵W＝MNji×][,ω和导师对考生满意度的矩阵W’=MNji×′][,ω。考生信息包含以下3个方面：初试成绩、复试成绩（与5项指标相关）以及填报专业（包括其所申报的第一志愿和第二志愿）。导师信息包含以下3个方面：所属的专业、学术水平状况（与4项指标相关）以及对考生的标准。考生i对导师j的满意度ji,ω与以下因素有关：(1)专业匹配度考生i与导师j的专业匹配度用jia,表示，应满足两个特征：①如果考生i和导师j专业不对口(也即导师j所在的专业不属于考生i所申报的两个专业志愿中)，则考生i就对该导师的满意度应该为0，即：jia,＝0，如果考生i的第一志愿是j的专业，就令jia,＝1；②如(1,2)(2,2)(1,1)121ST2D题-张雄明，晏小波，褚瑞-一等奖5果考生i的第二志愿是导师j的专业，则jia,取值是一个介于0～1之间的可调值h(其具体值将在问题的求解部分定义)。(2)导师的学术水平(导师j在学术上的造诣，由导师j的学术水平指标决定)。导师j的学术水平有4个指标，其归一化值分别为lj,λ)4,3,2,1(=l。则导师j的学术水平可表述为：4,143,132,121,11jjjjjkkkkbλλλλ+++=(∑==4111llk，1lk0,l=1,2,3,4)其中因子1ik(4,,32,,1=i)用以衡量导师学术水平的第i个指标在考生心目中的重要性。(3)专长期望匹配度（考生i与导师j对考生专长期望要求的匹配度）。考生i如果与导师j的对考生的专长期望要求匹配的越好，他就对导师j越满意。复试成绩有5个指标，用归一化值lji,β(5}4,,32,,{1∈l)描述导师j对考生i的满意度，也表现为考生i对导师j的满意度。以lji,β为例，它具有以下特性：①它与考生i在指标l上的值xi相关的，当考生i在指标l上达到门限gi,j时满意度为Q0。当考生i在指标l上值为0时满意度为也为0。②lji,β的值恒小于1。一种满足上述条件的lji,β的函数形式为ijixgQljie,0)1ln(,1−−=β，如下图所示。图3lji,β函数的曲线示意图则考生i与导师j总体专长期望要求的匹配度可表示为：525424323222121,,,,,,jijijijijikkkkkcjiβββββ++++=(1512=∑=llk，12lk0,l=1,2,3,4）其中2ik(5}4,,32,,{1∈i)是指关于复试中的第i个指标在考生和导师心目中的重要性0期望门限gi,j1指标大小指标满意度达到门限时的满意度Q0D题-张雄明，晏小波，褚瑞-一等奖6因子。考察上述三个因素，用因素分析法进行分析。按照假设1，当考生i的专业与导师j不对口时，他们之间不存在满意与否的问题，即jia,＝0时，0,=jiω；而不考察考生i志愿的情况下，考生i对导师j的满意度应该为jijcb,5.05.0+，即jia,＝1时，jijjicb,,5.05.0+=ω，因此ji,ω应表示为jia,与jijcb,5.05.0+的乘积比较合理，于是我们取)5.05.0(,,,jijjijicba+=ω。再考察导师j对考生i的满意度ji,'ω，它与以下因素有关：（1）专业匹配度（考生i是否报了导师j的专业）这个比例系数跟考生是一样的，仍为jia,。（2）考生i的综合成绩我们已将考生复试成绩的各项指标归一化，则考生的i的复试成绩∑==jijiAB512.0（认为复试时考查的各项专长同等重要），i的初试成绩的归一化值为iγ，则考生i的综合成绩为iiB5.05.0+γ(不同的学校对初、复试的意义轻重看法可能不一致，为简洁计，本文认为它们在总成绩中的权重是相同的)。（3）专长期望匹配度（考生i与导师j对考生专长期望要求的匹配度）。对于教师，可以认为这个因素也是跟考生一样的：525424323222121,,,,,,jijijijiji