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

D 题- -一等奖 研究生录取中的最佳匹配问题 摘 要：本文将考生录取问题转化为图论中一个特定约束条件下双向二部图的最大权 匹配问题。对于问题一，采用有哪些信誉好的足球投注网站法直接得到最优解，运算复杂度为 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) 请你设计一种更能体现“双向选择”的考生录取方案，提供给主管部门参考，并说 明你的方案的优越性。 模型的假设 1 D 题- -一等奖 1．考生和导师都是诚实的，在按策略选定录取方案时不会撒谎。 2 ．考生填报的志愿要尽量满足，专业不对口将大大降低考生和导师的满意度。 符号系统 T, S: S 表示所有导师组成的集合，T 表示所有考生组成的集合。 N ，M ：分别表示系统中考生和导师的个数，N=|S| ，M=|T| 。 1 2 3 4 5 Ai ＝(Ai ，Ai ，Ai ，Ai ，Ai ) ：考生i 的复试成绩中的 5 项指标的成绩的归一化值向量。 Bi ：考生i 的复试综合成绩的归一化值。 γi ：考生 i 的初试成绩的综合归一化值。 W [ω ] ：