数学建模y04研究生录取问题D题.doc

D 题-二等奖全国首届部分高校研究生数模竞赛题 目(D 题)研究生录取问题摘要：本文将研究生录取问题和跟导师之间的双向选择问题 分别转化成层次分析问题和线性规划中的 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一致性比率Qk归一化权向量0-1 规 划 模 型S双向选择的满意度目标矩阵Sij学生i 与导师 j 之间双向选择的满意度mij学生i 与导师 j 专业匹配满意度g ij学生i 对导师 j 水平的满意度rij学生i 与导师 j 期望要求匹配满意度Wmij学生i 与导师 j 专业匹配满意度加权系数Wgij学生i 对导师 j 水平的满意度加权系数Wrij学生i 与导师 j 期望要求匹配满意度加权系数A, B, C, D专家对学生的面试评分等级D 题-邓斌，李廷伟，王刚-二等奖集 对 分 析 模 型u联系度a同一度b差异度n差异度系数c对立度m对立度系数 A在学生某项成绩评分中持 A 意见的专家占总专家的百分比B在学生某项成绩评分中持 B 意见的专家占总专家的百分比C在学生某项成绩评分中持 C 意见的专家占总专家的百分比 D在学生某项成绩评分中持 D 意见的专家占总专家的百分比四 模型的分析与建立研究生录取问题和公司人力资源配置问题非常类似，都是通过双向选择更好 地优化组织的人员结构，提高组织的整体效能。但由于在实际操作中尚缺乏科学， 可行的方法，往往达不到理想的效果。我们知道，组织是一个多因素，多层次的 人造系统，是由许多相互作用相互依存的要素组成的有机整体，要使它形成一个 合理、有效的结构，必须将人员配置的方法建立在对构成组织的相关要素进行综 合、系统分析和客观评价的基础上。考虑到组织的人员结构是不同素质、不同能力的人在组织内各岗位上的分布 状态。我们建模的思路是，以提高组织的整体效能（师生双方总的满意度）为目 标，通过对学生、导师进行定量测评和综合分析，建立一个系统优化模型，以此 寻求学生和导师之间的最佳对应，实现招生调剂的优化。以下就方法和模型的建立分步阐述：（一）、用层次分析法对候选研究生进行测评排名。（1）层次分析法介绍： 层次分析法是一种定性与定量相结合的、系统化、层次化的分析方法，它用来帮助我们处理决策问题。特别是考虑的因素较多的决策问题，而且各个因素的 重要性、影响力、或者优先程度难以量化的时候，层次分析法为我们提供了一种 科学的决策方法。层次分析法的基本思路与人对一个复杂的决策问题的思维、判断过程大体上 是一致的。现在便用层次分析法模型来对 15 名学生的成绩做排序。设最上层为 目标层，即最后的排名；中间层为准则层，有初试成绩、复试中表现出来的灵活 性、创造性、知识面、表达力、外语等 6 个准则；最下层为方案层，有 15 名学生供选择。各层联系用相连的直线表示。（如下图）图 1：学生综合排名的层次结构通过相互比较确定各准则对于目标的权重，及各方案对于每一准则的权重。 这些权重在人的思维过程中通常是定性的，而在层次分析法中则要给出得到权重 的定量方法。考虑到待选学生 6 个评测因素中，初试成绩与复试中表现出来的灵活性、创 造性、知识面、表达力、外语等 5 个准则相比并不太重要，因此我们现在主要对 这 5 个因素分配合理的权重，而权重的计算一般用 Saaty 提出的 AHP 法。（2）、具体计算权重的 AHP 法。AHP 法是将各要素配对比较，根据各要素的相对重要程度进行判断，再根据 计算成对比较矩阵的特征值获得权重向量Wk 。Step1. 构造成对比较矩阵k假设比较某一层 k 个因素 C1 , C 2 , C3 , , Ci, C k 对上一层因素 o 的影响，每次两个因素 Ci 和 C j ，用 Cij 表示 Ci 和 C j 对 o 的影响之比，全部比较结果构成成对比较矩阵 C ，也叫正互反矩阵。C = (Cij ) k *kCij 0, Cij = 1 / C jiStep2. 计算该矩阵的权重通过解正互反矩阵的特征值，可求得相应的特征向量，经归一化后即为权重向量 Q = q , q,., q ，其中的 q 就是C 对 o 的相对权重。k1k2kkkikiStep3. 一致性检验为了度量判断的可靠程度，可计算此时的一致性度量指标 CI ： kCI = maxk 1其中 max 表示矩阵 C 的最大特征值， CI 越小，说明权重的可靠性越高。当 CR = CI b, c, d=0.25ak + 0.35bk + 0.25ck + 0.15d k , b a, c, dsk 0.15ak + 0.25bk + 0.35ck + 0.25d k , c a, b, d0.1ak+ 0.2bk+ 0.3ck+ 0.4d k, d a, b, c由此 sk 便可估算出每个学生在复试中各项素质的档次情况表。有了这张表后，我们把相对分 A 、B 、C 、D 量化为具体的数字，对应法则是 A = 95 、B = 85、C = 75 、D = 65,将之与初试成绩进行加权求和，从而按照分数从高到低取前十名即可。8 位专家对学生评价汇总如下：初试灵活性创造性知识面表达力外语成绩总评学生 1416ABABA87.087500学生 2410ABABA87.215000学生 3405BABBB82.727500学生 4397BBBBB82.105000学生 5392ABBBB83.335000学生 6389BBBBC81.267500学生 7385ABBCC80.142500学生 8382BBACB82.292500学生 9380ABABB83.072500学生 10378CBBCC77.395000学生 11377CBBAB79.615000学生 12372ABBBB84.460000学生 13360BBBBB81.095000学生 14358CBABB80.660000学生 15356ABBBB83.647500表 1:只考虑初试成绩和面试成绩两项因素的加权成绩总评。对学生总评成绩排序，得录取结果：名次12345678学生编号2112155938成绩87.287.184.583.683.383.182.782.3名次9101112131415学生编号46131471110成绩82.181.381.180.780.119.677.4表 2：学生通过成绩总评后的排序。后五个被淘汰第二步：利用层次分析法检验修正各因素间的加权系数考虑 10 名学生已经定下来了，在这个条件下，先求出学生对导师的满意度Wij ，其中根据题意，这个满意度取决于三个方面。一为学生 i 与导师 j 专业匹配 满意度 mij ；二为学生 i 对导师 j 水平的满意度 g ij ，这项理解为学生通过导师发文、检索、著书、课题等素质的加权，权值根据一致性检验修正定为1，1.5，3.5，4三为学生 i 与导师 j 期望要求匹配满意度 rij ，这项理解为用学生复试时 5 项 素质的档次去和老师在这个方面的要求进行比较，高出一档加 1 分、两档加 3分、三档加 6 分，低一档减 1 分、两档减 3 分、三档减 6 分，最后加权求和得到rij 。在这 5 项之间的权值选取上，我们选取的初始权值由 10 个导师对该项素质 的平均期望要求得到，为 0.89，0.9，0.9，0.84，0.87经过一致性检验修正，得到最终权值为：0.213，0.205，0.187，0.203，0.192 可以看出基本上是求平均，略有差异学生对老师的满意度按下式计算：SST ij= Wm ij m ij+ Wg ij g ij+ Wr ij rij我们直接选取Wmij = 0.6 ,Wg ij = 0.3 ,Wrij = 0.1 ,这么选取的原因是由于Wmij = 0.6 ,Wg ij = 0.3 ,Wrij = 0.1 能通过一致性检验事实上， 0.3 0.6 = 0.6满足正互反矩阵的一致性必要条件。0.10.30.1用同样的方法计算 10 位导师对 10 名学生的满意度W ji ，根据题意，这个满意度同样也取决于三个方面。一为导师 j 对学生 i 专业意愿满意度 m ji ，二是专 家组对学生专长的评价，即学生自身在面试中的综合表现 g ji ，三是导师 j 对学 生i 期望要求满意度 r ji 。导师对学生的满意度按下式计算：SST ij= Wmji m ji+ Wgji g ji+ Wr ji r ji权值的分配计算与上面类似。最终计算出来的双向选择的满意度表如下：导师1 导师2 导师3 导师4 导师 5导师6 导师 7导师8 导师9 导师 10学生152.7149.3657.0036.0029.7175.0065.1463.5039.8634.29学生235.2131.8639.5071.0064.7157.5047.6446.0039.8634.29学生335.2131.8639.5036.0029.7175.0065.1463.5057.3651.79学生470.2166.8674.5053.5047.2140.0030.1428.5039.8634.29学生535.2131.8639.5053.5047.2175.0065.1463.5039.8634.29学生670.2166.8674.5036.0029.7157.5047.6446.0039.8634.29学生770.2166.8674.5053.5047.2140.0030.1428.5039.8634.29学生835.2131.8639.5071.0064.7140.0030.1428.5057.3651.79学生935.2131.8639.5036.0029.7157.5047.6446.0074.8669.29学生1035.2131.8639.5036.0029.7175.0065.1463.5057.3651.79.第三步：列出规划方程求解要求给出 10 位导师和 10 名学生中的最佳双向选择，要求满意度最大， 目标函数及约束条件列为:10 10max S ij xijs.ti =1j =110 xij = 1j =1i = 1,2, 10 xij = 0orxij = 1, foralli, j10其中,约束条件 xij = 1j =1i = 1,2,10 的作用是限制一名学生只能选择十名导师中的一名,但没有限制不同学生选择同一个导师。结果如下表：编号12345678910学生 i211215593846导师 j6463633496表 3:导师学生不用一一配对的组合结果。一个导师可以招多个学生，那每个学生都去选择自己最满意的导师，这样总 体满意度也会达到最高。开始用初试成绩排在前面的 7 号和 10 号，由于面试中 专家对他们的评分不高，所以在综合考察了这些指标后，他们被淘汰。问题 2：录取后的 10 名学生与导师配对（一个导师只能带一名 学生）问题 2 和问题 1 基本相同，区别就在于问题 1 中老师和学生配对的时候没有 强调必须一一配对，而问题 2 提出了这个要求，我们只要修改一下最后满意度函 数的约束条件即可得解。满意度方程如下：10 10max S ij xiji =1j =1s.t10 xij = 1j =1i = 1,2, 1010 xij = 1i =1j = 1,2, 10 x = 0orx = 1, foralli, jijij通过解这个线形规划的问题，便可以得出 xij =1 时 i, j 的值，从而便知导师与学生的配对关系。编号12345678910学生 i211215593846导师 j85736214109表 4:在先确定十名录取名单后,要求 10 名导师和 10 名学生间一一对应的结果。这里一个导师只能有一个学生，那么结果是一一对应的，而且满足总体满意 度最大。问题 3：重新录取 10 名学生并与导师配对（一个导师只能带一 名学生）第一步：用新的规划方程进行重新录取在问题 1 第一步的基础上进行一定的变化。题目要求用学生初试、复试的成 绩和导师对学生的要求这 3 个大的因素去考虑从 15 名学生中录取 10 名。因此我们直接用 15 名学生的成绩和 10 位导师对学生的期望要求作为满意度 Sij 的组成。 用线性规划的一一匹配，就会有 5 名学生没有机会和导师配对，这样我们就淘汰这 5 名学生。15 10max S ij xij配对方程为： s.ti =1j =110 xij = 1j =1i = 1,2, 1515xij = 1i =1j = 1,2, 10 xij = 0orxij= 1, foralli, j通过解这个线形规划的问题，便可以得出 xij =1 时 i, j 的值，输出结果如下：学生 i123456789101112131415导师 j471961110521512813143选择表 5:用题三方法选择学生的情况。其中导师中 j 10 的为虚拟的导师点，所以与这些导师相配对的学生即为没 有配对的学生，也就是被淘汰的学生。第二步：用新的规划方程进行新的逐步配对要求 10 名学生各选一位导师，10 位导师再各选一名学生，这样，我们用改 变约束的满意度方程，先是允许多个学生对一个导师，再允许多个导师对一个学 生，这样我们考察 2 组数据，如果有一名学生选中一位导师，同时这位导师也选 了这名学生，这样，这对学生和老师配对成功。我们将剩下的学生与导师再分别 作上面多对一的线性规划，结果中如果继续有配对的学生和老师，我们便将他们 也配对组合，将其余的继续做多对一线性规划，直到再没有配对的老师和学生。 这时，我们就将这些导师和学生用一对一的线性规划满意度方程，求出他们之间 的最佳配对，结合上面所保留的所有配对，便得出本问结果。步骤第一步第二步第三步学生i123748912515导师j46391051782表 6：通过导师学生单向意愿的结合而得到的配对结果。问题 4：选择 5 名导师重新录取并配对 10 名学生（一带二）第一步： 为了充分考虑学生的志愿申报情况，我们可以利用前面得到的学生对导师的满意度权值，对每一个导师的权值求和，先挑选出每个专业的第一名，保证每个 专业至少有一名导师，还剩下一个名额，只需在剩下 6 个导师中取权值最大者即 可，导师的挑选结果如下表：专业(1)(2)(3)(4)导师 j12345678910得分114010961210109799712331075105911511072选取表 7、通过题 4 中提出的所有判别因素得到的选取导师的结果。代表被选中其中得分为对每个导师所有学生对他的满意度求和所得的值 第二步：在确定了 5 名导师后，由于要求每名招两名学生，为了利用我前面做过的模型， 我们把每个导师看成两个点，然后再与 15 个学生进行匹配，就可得到结果。规 划方程为：15 10max S ij xiji =1j =1s.t10 xij = 1j =1i = 1,2, 1515xij = 1i =1j = 1,2, 10 x = 0orx = 1, foralli, jijij将选取导师的满意度矩阵进行调整，把不参加录取的导师数据用参加录取导师数据替代。也即用第 1、3、4、6、9 列的数据分别取代 2、5、7、8、10 列的数据。通过解上面线形规划的问题，便可以得出 xij =1 时 i, j 的值，输出结果如下：专业(1)(2)(3)(4)导师序号13469学生序号3159141821247表 8：5 位导师每个导师可以招收 2 个学生的结果如表，一位导师带 2 个研究生，没有导师与其配对的学生即为被淘汰的学生。 和前面几问中的结果比较，其中5号6 号入选的原因是他们所报考的专业方向的 导师已经招收了满额的比他们还要优秀的学生，所以他们即使绝对成绩较好，但 在专业志愿的作用下，他们被淘汰。问题 5：模型的进一步思考和对录取方案的改进为了更加体现双向选择的要求，我们作如下假设 ：1、在面试的时候专家的组成需要来自每个专业方向2、每个导师在招收学生的时候，学生数目不能超过同一专业中导师招收学 生平均数的 50,用四舍五入取学生的个数，在实际招生中还可以假如每个导师 招生数的上限，如每位导师最多只能带 5 个学生。3、在挑选招收的 10 个学生的时候还是使用第三问中的前部分采用的方法， 即用 10 位导师和 15 名学生做一一匹配，这样便可得到招收的 10 个学生。4、对这 10 位导师和 10 名学生用问题一中的方法，不需要一一配对的匹配， 不过其中加入了导师招生不能超过同专业平均招生数的 50这样一个约束条 件。在此基础上，我们提出更加合理的录取方案如下： 第一步：用问题 3 种我们采用的选取 10 名入围学生的方法，在这里同样选取入围的10 名学生，结果如下:学生 i123456789101112131415导师 j471961110521512813143录取表 9：15 名学生中选取的 10 名学生这里导师和学生的配对并不是最终双向选择的结果，只是为了淘汰 5 名学生第二步：现在我们用这入围 10 名学生和 10 位导师做双向选择（1 位导师可以选择多 个学生，与问题一中的情况类似），目标函数及约束条件列为:15 10max Sij xijs.ti=1j =110 xij = 1j =1i = 1,2,3,4,5,7,8,9,12,15xij = 0orxij= 1, foralli, j10其中,约束条件 xij = 1j =1i = 1,2, ,3,4,5,7,8,9,12,15 的作用是限制入围的每个学生只能选择十名导师中的一名,但没有限制不同学生选择同一个导师。结果如下表：编号12345678910学生 i123457891215导师 j4639694363表 10：自由双向选择的配对结果第三步：从上表看出导师 3 带了 3 个学生，导师 4 带了 2 个学生，导师 6 带了 3 个学 生，导师 9 带了 2 个学生。拿导师 3 的情况为例，导师 3 的专业方向是 1，这个 专业中有 3 名导师，总共招收了 3 名学生，这样平均每个导师招收 1 个学生，用 我们先前假设的可以超出 50%的原则，这样导师 3 可以招收 1.5 个学生，四舍五 入后可以招收 2 个学生，这样在专业 1 招收的 3 名学生中与导