研究生录取问题.ppt

研究生录取问题摘 要：本文将研究生录取问题和跟导师之间的双向选择问题.分别转化成层次分析问题和线性规划中的0-1 规划问题。首先利用层次分析法对进入复试的学生进行差额录取，再在所有可能的师生配对方案中找出使得总体满意度最大的一种方案，作为师生间的最佳配对方案，达到双向选择的目的。对于满意度量化中各种权值的具体赋值，我们利用层次分析中权值矩阵的一致性检验法则进行了检验计算，使得每个最终配对方案的可信度达到最大。在比较各个方案的总体满意度大小的基础上，我们提出了更能体现双向选择的录取方案。关键词：集对分析、层次分析法、0-1 规划、双向选择某学校系计划招收 10 名计划内研究生，依照有关规定由初试上线的前15名学生参加复试，专家组由8 位专家组成。在复试过程中，要求每位专家对每个参加复试学生的以上个方面都给出一个等级评分，从高到低共分为A,B,C,D四个等级，并将其填入面试表内。所有参加复试学生的初试成绩、各位专家对学生的个方面专长的评分。问题提出该系现有10 名导师拟招收研究生，分为四个研究方向。导师的研究方向、专业学术水平（发表论文数、论文检索数、编（译）著作数、科研项目数），以及对学生的期望要求。在这里导师和学生的基本情况都是公开的。要解决的问题是：(1)首先，请你综合考虑学生的初试成绩、复试成绩等因素，帮助主管部门确定10 名研究生的录取名单。然后，要求被录取的10 名研究生与10 名导师之间做双向选择，即学生可根据自己的专业发展意愿（依次申报个专业志愿）、导师的基本情况和导师对学生的期望要求来选择导师；导师根据学生所报专业志愿、专家组对学生专长的评价和自己对学生的期望要求等来选择学生。请你给出一种10 名研究生和导师之间的最佳双向选择方案（并不要求一名导师只带一名研究生），使师生双方的满意度最大。(2)根据上面已录取的10 名研究生的专业志愿，如果每一位导师只能带一名研究生，请你给出一种10 名导师与10 名研究生双向选择的最佳方案，使得师生双方尽量都满意。(3)如果由十位导师根据初试的成绩及专家组的面试评价和他们自己对学生的要求条件录取研究生，那么，10 名研究生的新录取方案是什么？为简化问题，假设没有申报专业志愿，请你给出这10 名研究生各申报一名导师的策略和导师各选择一名研究生的策略。相互选中的即为确定；对于剩下的导师和学生，再按上述办法进行双向选择，直至确定出每一名导师带一名研究生的方案，使师生都尽量满意。(4)学校在确定研究生导师的过程中，要充分考虑学生的申报志愿情况。为此，学校要求根据10 名导师和15 名学生的综合情况选择5 名导师招收研究生，再让这5 名导师在15 名学生中择优录取10 名研究生。请你给出一种导师和研究生的选择（录取）方案，以及每一名导师带名研究生的双向选择最佳策略。(5)请你设计一种更能体现“双向选择”的研究生录取方案，提供给主管部门参考，并说明你的方案的优越性。二 模型的假设1 学生在衡量自己与导师期望要求之间的差异时，用的是专家组对自己的评分表据，而不是自我评价的数值。2 在量化学生对导师的满意度时，学生把导师是否与自己的专业一致看得最重要，在量化导师对学生的满意度时，导师把自己对学生的期望要求看得最重要。3 不考虑两个或多个导师带一个学生的情况。三符号说明CI:一致性度量指标Ci:层次分析法中的第i 个因素C:正互反矩阵 max:正互反矩阵的最大特征值Q:模型中第三层每个方案对第二层中每个因素的权向量构成的矩阵CR:一致性比率Q:归一化权向量S:双向选择的满意度目标矩阵Sij:学生i与导师j之间双向选择的满意度Mij:学生i 与导师j 专业匹配满意度gij:学生i 对导师j 水平的满意度rij:学生i与导师j期望要求匹配满意度Wmij:学生i 与导师j 专业匹配满意度加权系数Wgij:生i 对导师j 水平的满意度加权系数Wrij:学生i与导师j期望要求匹配满意度加权系数A,B,C,D 专家对学生的面试评分等级u 联系度a 同一度b 差异度n 差异度系数c 对立度m 对立度系数A:在学生某项成绩评分中持A 意见的专家占总专家的百分比B:在学生某项成绩评分中持B 意见的专家占总专家的百分比C在学生某项成绩评分中持B 意见的专家占总专家的百分比D在学生某项成绩评分中持B 意见的专家占总专家的百分比四模型的分析与建立研究生录取问题和公司人力资源配置问题非常类似，都是通过双向选择更好地优化组织的人员结构，提高组织的整体效能。但由于在实际操作中尚缺乏科学，可行的方法，往往达不到理想的效果。我们知道，组织是一个多因素，多层次的人造系统，是由许多相互作用相互依存的要素组成的有机整体，要使它形成一个合理、有效的结构，必须将人员配置的方法建立在对构成组织的相关要素进行综合、系统分析和客观评价的基础上。考虑到组织的人员结构是不同素质、不同能力的人在组织内各岗位上的分布状态。我们建模的思路是，以提高组织的整体效能（师生双方总的满意度）为目标，通过对学生、导师进行定量测评和综合分析，建立一个系统优化模型，以此寻求学生和导师之间的最佳对应，实现招生调剂的优化。以下就方法和模型的建立分步阐述：（一）、用层次分析法对候选研究生进行测评排名。（1）层次分析法介绍：层次分析法是一种定性与定量相结合的、系统化、层次化的分析方法，它用来帮助我们处理决策问题。特别是考虑的因素较多的决策问题，而且各个因素的重要性、影响力、或者优先程度难以量化的时候，层次分析法为我们提供了一种科学的决策方法。层次分析法的基本思路与人对一个复杂的决策问题的思维、判断过程大体上是一致的。现在便用层次分析法模型来对15 名学生的成绩做排序。设最上层为目标层，即最后的排名；中间层为准则层，有初试成绩、复试中表现出来的灵活性、创造性、知识面、表达力、外语等6 个准则；最下层为方案层，有15 名学生供选择。各层联系用相连的直线表示。（如下图）通过相互比较确定各准则对于目标的权重，及各方案对于每一准则的权重。这些权重在人的思维过程中通常是定性的，而在层次分析法中则要给出得到权重的定量方法。考虑到待选学生6 个评测因素中，初试成绩与复试中表现出来的灵活性、创造性、知识面、表达力、外语等5 个准则相比并不太重要，因此我们现在主要对这5 个因素分配合理的权重，而权重的计算一般用Saaty 提出的AHP 法。（2）、具体计算权重的AHP 法。AHP 法是将各要素配对比较，根据各要素的相对重要程度进行判断，再根据计算成对比较矩阵的特征值获得权重向量Wk。Step1.构造成对比较矩阵假设比较某一层k个因素C1，C 2，Cik，C k 对上一层因素o的影响，每次两个因素Ci和C j，用Cij表示Ci和C j对o的影响之比，全部比较结果构成成对比较矩阵C，也叫正互反矩阵。C=(Cij)k*k Cij 0,Cij=1/C jiStep2.计算该矩阵的权重通过解正互反矩阵的特征值，可求得相应的特征向量，经归一化后即为权重向量Qk=q1k,q2k,.,qkk ，其中的qik就是Ci对o的相对权重。Step3.一致性检验为了度量判断的可靠程度，可计算此时的一致性度量指标CI，CI 越小，说明权重的可靠性越高。当CR 10的为虚拟的导师点，所以与这些导师相配对的学生即为没有配对的学生，也就是被淘汰的学生。第二步：用新的规划方程进行新的逐步配对要求10 名学生各选一位导师，10 位导师再各选一名学生，这样，我们用改变约束的满意度方程，先是允许多个学生对一个导师，再允许多个导师对一个学生，这样我们考察2 组数据，如果有一名学生选中一位导师，同时这位导师也选了这名学生，这样，这对学生和老师配对成功。我们将剩下的学生与导师再分别作上面多对一的线性规划，结果中如果继续有配对的学生和老师，我们便将他们也配对组合，将其余的继续做多对一线性规划，直到再没有配对的老师和学生。这时，我们就将这些导师和学生用一对一的线性规划满意度方程，求出他们之间的最佳配对，结合上面所保留的所有配对，便得出本问结果。步骤 第一步 第二步 第三步学生i 1 2 3 7 4 8 9 12 5 15导师j 4 6 3 9 10 5 1 7 8表6：通过导师学生单向意愿的结合而得到的配对结果。问题4：选择5 名导师重新录取并配对10 名学生（一带二）第一步：为了充分考虑学生的志愿申报情况，我们可以利用前面得到的学生对导师的满意度权值，对每一个导师的权值求和，先挑选出每个专业的第一名，保证每个专业至少有一名导师，还剩下一个名额，只需在剩下6 个导师中取权值最大者即可，导师的挑选结果如下表：专业(1)(2)(3)(4)导师j 1 2 3 4 5 6 7 8 9 10得分 1140 1096 1210 1097 997 1233 1075 1059 1151 1072选取 表 7、通过题4 中提出的所有判别因素得到的选取导师的结果。代表被选中其中得分为对每个导师所有学生对他的满意度求和所得的值第二步：在确定了5 名导师后，由于要求每名招两名学生，为了利用我前面做过的模型，我们把每个导师看成两个点，然后再与15 个学生进行匹配，就可得到结果。规划方程为：将选取导师的满意度矩阵进行调整，把不参加录取的导师数据用参加录取导师数据替代。也即用第1、3、4、6、9 列的数据分别取代2、5、7、8、10 列的数据。通过解上面线形规划的问题，便可以得出xij=1时i,j的值，输出结果如下：专业(1)(2)(3)(4)导师序号 1 3 4 6 9学生序号 3 15 9 14 1 8 2 12 4 7表8：5 位导师每个导师可以招收2 个学生的结果。如表，一位导师带2 个研究生，没有导师与其配对的学生即为被淘汰的学生。和前面几问中的结果比较，其中5 号6 号入选的原因是他们所报考的专业方向的导师已经招收了满额的比他们还要优秀的学生所以他们即使绝对成绩较好，但在专业志愿的作用下，他们被淘汰。问题5：模型的进一步思考和对录取方案的改进为了更加体现双向选择的要求，我们作如下假设：1、在面试的时候专家的组成需要来自每个专业方向2、每个导师在招收学生的时候，学生数目不能超过同一专业中导师招收学生平均数的50,用四舍五入取学生的个数，在实际招生中还可以假如每个导师招生数的上限，如每位导师最多只能带5 个学生。3、在挑选招收的10 个学生的时候还是使用第三问中的前部分采用的方法，4、对这10 位导师和10 名学生用问题一中的方法，不需要一一配对的匹配，不过其中加入了导师招生不能超过同专业平均招生数的50这样一个约束条件。在此基础上，我们提出更加合理的录取方案如下：第一步：用问题3 种我们采用的选取10 名入围学生的方法，在这里同样选取入围的10 名学生，结果如下:学生i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15导师j 4 7 1 9 6 11 10 5 2 15 12 8 13 14 3录取 表9：15 名学生中选取的10 名学生这里导师和学生的配对并不是最终双向选择的结果，只是为了淘汰5 名学生第二步：现在我们用这入围10 名学生和10 位导师做双向选择（1 位导师可以选择多个学生，与问题一中的情况类似），目标函数及约束条件列为:是限制入围的每个学生只能选择十名导师中的一名,但没有限制不同学生选择同一个导师。结果如下表：编号 1 2 3 4 5 6 7 8 9 10学生i 1 2 3 4 5 7 8 9 12 15导师j 4 6 3 9 6 9 4 3 6 3表10：自由双向选择的配对结果第三步：从上表看出导师 3 带了3 个学生，导师4 带了2 个学生，导师6 带了3 个学生，导师9 带了2 个学生。拿导师3 的情况为例，导师3 的专业方向是1，这个专业中有3 名导师，总共招收了3 名学生，这样平均每个导师招收1 个学生，用我们先前假设的可以超出50%的原则，这样导师3 可以招收1.5 个学生，四舍五入后可以招收2 个学生，这样在专业1 招收的3 名学生中与导师3 配对满意度最低的3 号学生需要调剂，调剂时考虑3 号学生对导师1 的满意度是除了对导师3之外最高的，这样我们便把学生3 调剂给导师1。用同样的方法分析学生5 也需要调剂，调剂给导师7。最终配对结果如下：编号 1 2 3 4 5 6 7 8 9 10学生i 1 2 3 4 5 7 8 9 12 15导师j 4 6 1 9 7 9 4 3 6 3表11：问题五最终配对结果为了比较本方案和前面四个方案的优越性，我们将各方案所得总满意度列出如下表：问题序号 第一个 第二个 第三个 第四个 第五个对应的总满意度值 740.02 677.35 754.56 848.27 850.49表11 不同的约束下的总满意值表比较五种情况的满意度值,不难发现：第五问中我们得到的总满意度值最大，所以，第五题我们采用的方法是最能体现双向选择的。这是由于我们在处理”双向选择”的问题时,把双向选择的要求体现在了权向量的确定中,而权向量的确定原则是层次分析法,显然我们对层次分析法的底层限制越是详细,越能更好的体现”双向选择”的要求。为此我们提出了对每个导师最终招收的学生人数占导师所在专业总数的比例限制，这是很符合实际的。我们不难想象：不管是先确定学生数，还是先确定导师数，然后再求最优，都不如把两步一起考虑，更能体现双向选择性。实际的模拟结果也是如此。比较表二和表八，我们看到表八中不再出现表二中的那种一个导师带4 个学生的情况，结果应该更合理些。但是到底需要多大的比例最佳，是一个值得深入的问题。六 模型优缺点分析优点：对于题目中的“体现双向选择”的要求，我们巧妙地借助层次分析法计算验证各类因素间的加权量值，得到老师学生之间双向选择的满意度Sij，进一步利用0-1 规划模型进行配对方案的求解，使得师生双方总满意度达到最大值，符合题目的要求，而且模型简单，只须借助Linda 软件就能求解；缺点:在题目求解中我们多次采取了加权平均的方法，尽管加权的权重都是参照经典的模型方法计算得到的，而且符合精度要求,但仍然有一定的主观因素，因此可能有与实际有所出入的地方。参考文献1谢政.戴丽.国防科技大学出版社2梅志红.金炜东.一种基于决策者满意度的多属性决策方法 3谢政.网络算法与复杂性理论国防科大出版社4姜启源.数学建模.高等教育出版社5李卫星.人力资源优化配置的双向选择模型湖北经济学院