研究生录取中的最佳匹配问题.DOC

1、1研究生录取中的最佳匹配问题褚瑞 晏小波 张雄明国防科技大学摘 要：本文将考生录取问题转化为图论中一个特定约束条件下双向二部图的最大权匹配问题。对于问题一，采用搜索法直接得到最优解，运算复杂度为 O(MN)。对于问题二，考虑是否满足稳定匹配条件的两种情况，采用 Kuhn-Munkras 算法和改进的 Kuhn-Munkras算法分别求得最大满意度的解和极大满意度的解，前者的算法复杂度仅为 O(Nlog2N)。对于问题三，分两步解决。首先给出一种选优录取 10 个考生的方法，在此基础上提出了一种最大平衡策略，求出一组约束条件下的极大解。对于问题四，首先在充分考虑考生志愿和专业平衡的条件下，给出了

2、 5 名导师和 10 名考生的选择策略，然后在此基础上采用虚拟导师节点的方法，转化为问题二中的情况进行求解。最后，我们分析上述各种策略的弊端，提出了虚拟节点的方法，有效消除了上述弊端，并将模型统一到问题二的情况中。本文的最终模型可扩展性好，算法复杂度低，较好的解决了本文提出的所有问题。问题的重述某学校系计划招收 10 名计划内考生，依照有关规定由初试上线的前 15 名考生参加复试，专家组由 8 位专家组成。在复试过程中，要求每位专家对每个参加复试考生的以上个方面都给出一个等级评分，从高到低共分为 A,B,C,D 四个等级，并将其填入面试表内。所有参加复试考生的初试成绩、各位专家对考生的个方面专

3、长的评分如表（）表（8）所示。该系现有 10 名导师拟招收考生，分为四个研究方向。导师的研究方向、专业学术水平（发表论文数、论文检索数、编(译) 著作数、科研项目数） ，以及对考生的期望要求见表(9)。在这里导师和考生的基本情况都是公开的。要解决的问题是：(1) 首先，请你综合考虑考生的初试成绩、复试成绩等因素，帮助主管部门确定 10 名考生的录取名单。然后，要求被录取的 10 名考生与 10 名导师之间做双向选择，即考生可根据自己的专业发展意愿（依次申报个专业志愿，如表(10)所示） 、导师的基本情况和导师对考生的期望要求来选择导师；导师根据考生所报专业志愿、专家组对考生专长的评价和自己对考

4、生的期望要求等来选择考生。请你给出一种 10 名考生和导师之间的最佳双向选择方案（并不要求一名导师只带一名考生） ，使师生双方的满意度最大。(2) 根据上面已录取的 10 名考生的专业志愿，如果每一位导师只能带一名考生，请你给出一种 10 名导师与 10 名考生双向选择的最佳方案，使得师生双方尽量都满意。(3) 如果由十位导师根据初试的成绩及专家组的面试评价和他们自己对考生的要求条件录取考生，那么，10 名考生的新录取方案是什么？为简化问题，假设没有申报专业志愿，请你给出这 10 名考生各申报一名导师的策略和导师各选择一名考生的策略。相互选中的即为确定；对于剩下的导师和考生，再按上述办法进行双

5、向选择，直至确定出每一名导师带一名考生的方案，使师生都尽量满意。(4) 学校在确定考生导师的过程中，要充分考虑考生的申报志愿情况。为此，学校要求根据 10 名导师和 15 名考生的综合情况选择 5 名导师招收考生，再让这 5 名导师在 15 名考生中择优录取 10 名考生。请你给出一种导师和考生的选择（录取）方案，以及每一名导师带名考生的双向选择最佳策略。(5) 请你设计一种更能体现“双向选择”的考生录取方案，提供给主管部门参考，并2说明你的方案的优越性。 模型的假设1 考生和导师都是诚实的，在按策略选定录取方案时不会撒谎。2 考生填报的志愿要尽量满足，专业不对口将大大降低考生和导师的满意度。

6、符号系统T, S: S 表示所有导师组成的集合，T 表示所有考生组成的集合。N，M：分别表示系统中考生和导师的个数，N=|S|，M=|T|。Ai (Ai1， Ai2， Ai3， Ai4， Ai5)：考生 i 的复试成绩中的 5 项指标的成绩的归一化值向量。Bi：考生 i 的复试综合成绩的归一化值。：考生 i 的初试成绩的综合归一化值。i：考生对导师的满意度矩阵， 表示当考生 i 被导师 j 录取时，考生 i 的MNjiW,ji,满意度。：导师对考生满意度的矩阵。 表示当考生 i 被导师 j 录取时，导师 j 的ji, ji,满意度。：与考生 i 是否报了导师 j 的专业这一因素相关的系数，取值

7、 01 之间。jia,：导师 j 的学术水平在指标 l 上的归一化值。lj,)4,321(bj：导师 j 的学术水平综合值。：考生 i 与导师 j 在复试指标 l 上的专长期望匹配度的归一化值。lji,ci ,j：考生 i 与导师 j 总的专长期望匹配度的归一化值。sgn(x)： sgn(x)表示变量 x 的符号，定义如下： 0,1)sgn(xx：x 向下取整函数 ；)(flor问题的分析1. 将考生录取转化为二分图的匹配问题 本文需要解决的问题是在特定的约束条件下，导师和考生之间建立一种匹配关系（即：考生被某个导师录取） ，使得导师和考生双方的总满意度最大。可以把导师集合 T 和考生集合 S

8、 看成某个二部图顶点集的两个子集，连接 S 与 T 的边表征了某考生对某导师可能的申报关系，该边上的权表征了申报该导师使得该考生所能获取的满意度；连接 T 到 S 的边表征了导师对考生可能的录取关系，其上的权表征了录取该考生使得该导师所能获取的满3意度。该二部图具有以下特点： 它的边是双向的。这种双向的边是成对出现的，即：对于每个考生，如果存在他对某个导师的申报可能，就必然存在该导师对此考生的录取可能；反之亦然。 它的边是带权的。 本文的目标是在某种特定约束下，构造一种考生到导师的匹配使得在该匹配下考生和导师双方的总体满意度最大。这样我们就将本文的所有问题映射到了图论中特定约束条件下双向二部图

9、的最大权匹配问题。下图为一个简单的双向二部图的最大权匹配问题。图 1 一个双向带权二部图的实例图 1 中考生集合 S=A, B, C, D，导师集合 T=1, 2, 3, 4，图 1 表中列出上述左图二部图上任意双向边上的正反两向的权值。现实中类似的双向带权二部图的实例还有婚姻匹配问题 1, 3, 4, 6，任务分配问题 2, 5等。总体满意度可以表示为考生的总体满意度和导师的总体满意度的线性组合，因此可以将二部图中的双向边转化为单向边，同时将边上的权修正为正向权值与反向权值的线性组合，则双向二部图的总体满意度最大问题就可以转化为对应的无向二部图中的最大权匹配问题了。2不稳定匹配方案的概念与满

10、意度的关系正如婚姻匹配问题中可能存在不稳定的匹配方案一样，通过上述方法解出的匹配方案也可能存在不稳定的匹配对。对于婚姻匹配问题而言，一个不稳定的匹配对(x, y)指的是一对不稳定的男 x 女 y，他们没有结合，但是 x 喜欢 y 的程度胜过他喜欢目前的配偶，并且 y喜欢 x 的程度也胜过她目前配偶；同样的，对于一种匹配方案而言，如果存在这么一对男女，这个系统就称为不稳定，其所以不稳定是因为 x 和 y 最有可能放弃目前配偶，双双私奔，造成社会不安。同样的，对于一种强调“双向选择”的匹配系统而言，不稳定匹配对的出现可能会造成匹配方案的崩溃。对考生录取问题而言，一个不稳定匹配对的例子如图 2：Tu

11、torsStudent1 2 3 4A 0，0 2，3 0，0 4，5B 4，2 0，0 0，0 0，0C 0，0 3，1 4，5 5，3D 3，6 0，0 0，0 2，44(1, 2)(2, 2)(1, 1)121S T2图 2 一个不稳定匹配对的实例, 边上的权用二元组表示。如（1, 2）表示，从左到右的权为 1，从右到左的权为 2如图 2 所示，假设（S 1, T1） 、 （S 2, T2）为二部图最大权匹配的两条边，但 S1 对 T1 的满意度为 1，S 1 对 T2 的满意度为 2；而 T2 对 S1 的满意度为 2，T 2 对 S2 的满意度为 1，这样，相对于 T1, S1 更倾

12、向于选 T2 做导师，T 2 也更倾向于选 S1 做考生，这样的匹配对（S 1, T1）和（S 2, T2）就是一对不稳定匹配对。含有不稳定匹配对的匹配方案也称之为不稳定的。模型的建立在建立模型之前，我们需要先对已有数据进行处理，从中构造出下列信息：1各个考生的复试成绩指标及复试成绩归一化值。考生 i 的复试成绩向量 Ai(A i1, Ai2, Ai3, Ai4, Ai5)与考生的复试成绩的 5 项指标有关，对于某项指标 i，他的分数取所有专家打分的平均 (更一般的情况为所有专家打分的凸线性组合)，则他的复试成绩 。51.0jjiiB2考生对导师的满意度的矩阵 W 和导师对考生满意度的矩阵 W

13、=MNji,。MNji,考生信息包含以下 3 个方面：初试成绩、复试成绩（与 5 项指标相关）以及填报专业（包括其所申报的第一志愿和第二志愿） 。导师信息包含以下 3 个方面：所属的专业、学术水平状况（与 4 项指标相关）以及对考生的标准。考生 i 对导师 j 的满意度 与以下因素有关：ji,(1) 专业匹配度考生 i 与导师 j 的专业匹配度用 表示，应满足两个特征： 如果考生 i 和导师 j 专jia,业不对口( 也即导师 j 所在的专业不属于考生 i 所申报的两个专业志愿中)，则考生 i 就对该导师的满意度应该为 0，即： 0，如果考生 i 的第一志愿是 j 的专业，就令ji,51； 如

14、果考生 i 的第二志愿是导师 j 的专业，则 取值是一个介于 01 之间的可jia, jia,调值 h(其具体值将在问题的求解部分定义 )。(2) 导师的学术水平(导师 j 在学术上的造诣，由导师 j 的学术水平指标决定)。导师 j 的学术水平有 4 个指标，其归一化值分别为 。则导师 j 的学lj,)4,321(术水平可表述为：( ， 0, l=1, 2, 3 ,4)4,13,12,1,1 jjjjj kkb1l1lk其中因子 ( )用以衡量导师学术水平的第 个指标在考生心目中的重要i , i性。(3) 专长期望匹配度（考生 i 与导师 j 对考生专长期望要求的匹配度） 。考生 i 如果与导

15、师 j 的对考生的专长期望要求匹配的越好，他就对导师 j 越满意。复试成绩有 5 个指标，用归一化值 ( )描述导师 j 对考生 i 的满意度，也表现lji,54,32,1为考生 i 对导师 j 的满意度。以 为例，它具有以下特性：lji, 它与考生 i 在指标 l 上的值 xi 相关的，当考生 i 在指标 l 上达到门限 gi,j 时满意度为 Q0。当考生 i 在指标 l 上值为 0 时满意度为也为 0。 的值恒小于 1。lji,一种满足上述条件的 的函数形式为 ，如下图所示。lji,ijixgQljie,0)1ln(,0 期望门限 gi,j1指标大小指标满意度图 3 函数的曲线示意图lji

16、,则考生 i 与导师 j 总体专长期望要求的匹配度可表示为：( ，1 0, l=1, 2, 3, 4）524232212, , jijijijiji kkkcji 12l 2lk其中 ( )是指关于复试中的第 个指标在考生和导师心目中的重要性2i 54,达到门限时的满意度 Q06因子。考察上述三个因素，用因素分析法进行分析。按照假设 1，当考生 i 的专业与导师 j 不对口时，他们之间不存在满意与否的问题，即 0 时， ；而不考察考生 i 志愿jia, 0,ji的情况下，考生 i 对导师 j 的满意度应该为 ，即 1 时，jijcb,5.jia,，因此 应表示为 与 的乘积比较合理，于是我们j

17、ijji cb, 5.0.ji,ji, jij,取 。)(, jijjijia再考察导师 j 对考生 i 的满意度 ，它与以下因素有关：ji,（1）专业匹配度（考生 i 是否报了导师 j 的专业）这个比例系数跟考生是一样的，仍为 。jia,（2）考生 i 的综合成绩我们已将考生复试成绩的各项指标归一化，则考生的 i 的复试成绩（认为复试时考查的各项专长同等重要） ，i 的初试成绩的归一化值为 ，jiiAB51.0 i则考生 i 的综合成绩为 (不同的学校对初、复试的意义轻重看法可能不一致，iiB5.0.为简洁计，本文认为它们在总成绩中的权重是相同的)。（3）专长期望匹配度（考生 i 与导师 j

18、 对考生专长期望要求的匹配度） 。对于教师，可以认为这个因素也是跟考生一样的： 524232212, , jijijijiji kkkcji 归纳起来得： 。.0).5.0( , jiiijiji cBa在构造出满意度矩阵 和 之后，我们就可以对模型进行建模了。W问题一：我们按照各个考生的综合成绩 排序(为了方便计，假设初试，面试的重要iiB5.0.性是一样的)，取出前 10 个成绩最好的考生加入录取名单。用 表示我们最终求得的结果，其中：MNjixX, 录 取没 有 被 导 师考 生 录 取被 导 师考 生 jixji,01,我们的目标是，考生和导师的总体满意度最大，为了公平起见，我们认为导

19、师和考生的满意度同等重要。目标函数就可表示为： max10,10,NiMj jijiNiMjji xx7约束 1：一个考生只能被一个导师录取。即 。1,0;10, NixMjji 约束 2： 取值约束：jix, ,;,1,Mjixji 因此问题一可看成一个 01 整型规划问题： ma10,01,NiMjjiNiMjji xx 1,0;1,01.,10, jNixtsjiMjji 其中：M 10，N 10在实际求解中，因为每个考生只能报一个导师，因此只需要对每一个考生 i 搜索 j 使得 j 满足： = ，并令 1， ，则考生 i 与导jiji,ma,10kiikjix, )(,jlli师 j

20、构成的匹配对使得由考生 i 发出的边正好使双方的总体满意度最大。这样得到的 X 就可以使得目标函数 在满足约束条件下达到最大值。01,10,NiMjjiNiMjjix问题二：目标函数还是(1)式不变，但增加每个导师只能招收一名考生的约束。即： 1,0,10, jxNij 稳定匹配约束：如果 ，则不存在 使得21,jiji且 1,0,21Mji，该条件等价于下式：221121 , jijijiji 且故,)sgn()sgn( 21, 22121211 jixx jijijijijiji 问题二可化为如下规划问题 ma10,10,NiMjjiNiMjji xx 1,0;1,01 )(, 2)sgn

21、()sgn(,1,0,1., 2121 ,0,21 MjNix jxjxitsji iijijijijiNjiMjji 可 选 约 束其中：M N 10实际求解中，我们是采用 Kuhn-Munkras 算法（若带稳定约束条件，则采用改进的Kuhn-Munkras 算法）求解，Kuhn-Munkras 算法的计算复杂度仅为 O(Nlog2N)。问题三：首先按照问题一选中的 10 个考生的初始成绩、复试成绩和导师们对考生的要求，求出导师们对每一个考生 i 的总满意度8（因为不考虑填报志愿因素，因此 ） ，然后排序，10,Mjji 1),10,(, ,jiaji令取出前 10 个考生进入系统，进行录

22、取方案的求解。因为考生没有申报专业，故 及 。jijji cb, 5.0.jiiiji cB, 5.0)2.5.( 充分考虑导师和考生双方的公平性，设计最大平衡策略如下：（1）导师 j（ ）的策略：每次选择一个考生 i 满足下式：T。|, jijijijii （2）考生 i（ ）的策略：每次选择一个导师 j 满足下式：S。| , jijijijij （3）对于每一个互相选中的 i1, j1，则将 ， ，),(1jiM1iS。1jT（4）如果 ，则退出，否则转到（1） 。Sor定理 1：每轮循环中上述步骤（3）中至少有一对考生、导师二元组（i 1，j 1）可以互相选中。证明：考虑（i 1, j1

23、） ，则按照最大平衡策|),( , jijijijiji 略（1） （2）两步，导师 j1 选的考生必然是 i1，而 i1 选的导师也必然是 j1。故至少 i1 、j 1 互相选中。因此上述策略必定会终止。问题四：在筛选老师和考生的过程中除了要看各导师及考生的水平等因素，还要注意权衡各专业方向招生人数，否则可能出现某个方向的导师全部不招生的恶劣情况。第一步：要从 10 个导师中选出 5 个导师，筛选方法如下：（1）循环处理每个考生的志愿情况，将其第一志愿所在专业的报考数目加 1，将其第二志愿所在专业的报考数目增加一个大于 0、小于 1 的较小常数值 h。得到各类专业的总报考量 (i1, 2,

24、3, 4)。C（2）采用 Hamilton 议席分配策略 7，按照各专业的报考量 (i1, 2, 3, 4)，将 5 个导C师名额分配到各个专业。专业 i 的报考比例为 ，则将 位导师名41/iip)ipqflor额指派到的专业 i (其中 q 为可用的导师总名额 )；如果指派完成后还有未分配的导师名额，则将各专业按 的小数部分升序排序，然后依次将剩余名额依次分配给各个专业。ip9（3）具体某个专业 中，则按照所有考生对该导师的总体满意度 排序，选取前l 10,Nij名导师，容许他们招收考生。lD本策略充分考虑了各专业的招生平衡。第二步：5 名导师从 15 名考生中选择 10 名考生的策略如下

25、：（1）令已录取考生的集合为 。Set（2）对每一专业 ，构造该专业可选考生集合 所有申报了该专业的考生。l lSet（3）循环处理每一专业 ， ，按照已选导师对该考生的总满意度tell排序，选取前 个考生，并将这 个考生加入集合 。40,jjilD2lD2Set（4）最后所得的集合 即为最终的录取考生集合，集合元素个数为 10 个。Set这种选择策略认为，专业匹配对于考生而言是一个最重要的指标，如果不能满足，会大大降低考生的满意度。第三步：找到一个 5 个导师对 10 个考生的最佳加权匹配。因为每个导师必须带两个考生，所以将每个导师产生一个虚拟节点（如：导师 0 和导师 5 是同一个导师，导

26、师 1 和导师 6 是同一个导师，一次类推，导师 4 和导师 9 是同一个导师） ，他们与考生之间的满意度信息是从原来的 5 个导师到考生的加权连线中复制得到的。这样就将问题四的第三步转化为了问题二，可以完全运用问题二的模型对 5 个导师到 10 个考生之间的最大加权匹配求解。问题五：为了更好地体现“双向选择”的观点，在设计考生录取方案时，我们考虑下列原则：1. 考虑“双向选择”的稳定匹配问题。最后的双向选择方案最好是稳定的匹配，这样不至于会出现所谓的不稳定匹配对，可能使制订的配对方案遭到破坏。2. 录取考生问题中，考生的满意度及导师的满意度重要性可能不同，有些学校可能更看重导师的满意度，也有

27、的学校更看重考生的满意度，因此问题二的模型中考生的满意度及导师的满意度中的比例因子的可以根据实际情况设置，如认为导师的满意度占总体满意度的 70%，考生的满意度占总体满意度的 30%。3. 为了更好地体现考生与导师之间的“双向选择”性, 直接让导师与考生进行配对，这样，整个录取、配对工作在一个整体步骤内完成，而不需将录取作为一个单独的步骤。该做法等同于导师直接参与了录取工作，导师的选择面更宽，录取灵活性更大。在问题三中，有可能出现这样的情况，对于某个考生，有导师最想招收他，他也最想报该导师，然而由于他在筛选过程中的评分太低，过早的退出了系统，可能使得后续的匹配工作不是最佳。对于考生 i 而言，

28、存在被录取与落榜两种状态，于是其约束调整为：，其中10,Mjjix1,0Nj10对导师的约束为：，其中10,Nijx1,0Mi否 则录 取被 导 师当 考 生，jiji,目标函数修正为： 10,10,)(maxNiMjjiNiMjji xkxk其中 k 为权重因子，用以衡量导师对考生及考生对导师的满意度的相对重要性。在问题二的求解中，要求导师和考生的数目相等；但是考虑实际情况，导师和考生的数目不一定相等，下面考虑更一般情况，即当 时问题的处理。 当 NM 时，可以增加位虚拟 位导师（虚拟结点） ，虚拟导师对所有考生的N满意度均为 0，反之亦然；在匹配方案中，当考生对应的导师为虚拟导师时，该考生即落榜； 当 NM, 增加 位虚拟考生，任意虚拟考生对导师的满意度为 0，反之亦然；M这样，很多 的问题都可以通过构造虚拟节点的方式转化为问题二求解。模型的求解与结果分析在上一节中，我们采用统一的模型，在不同的约束条件下，对原题中的五个问题设计了合理的求解方案。下面我们将分别使用上述各求解方案，对于原题中给定的全部数据，使用计算机进行模拟和求解，并给出结果和分析。