数学建模学生面试问题(值得看).doc

单目标和多目标规划模型求解学生面式问题摘要随着高校自主招生规模的扩大，学生面试的公平性成为人们关注的焦点。本文通过建立单目标和多目标规划模型，利用MATLAB软件和搜索算法，进行了有关招生面试问题的研究。对于问题一，为表示面试学生和老师之间的相应关系，引入01变量，建立以老师数M最小为目标的01规划模型。利用搜索算法，求解出考生数N确定的情况下，满足其他约束条件的最小M值。问题二中，将Y1、Y3、Y4看成基本约束条件下的目标函数，Y2作为约束条件，建立多目标规划模型。运用MATLAB软件对模型进行求解，得到满足约束条件的近似最优分配方案。问题三，增加每位学生的面试组中各有两位文理科老师的约束条件，假设前M/2个老师为文科老师，通过限制第i位学生“面试组”中前M/2个老师的个数来保证每位学生的文科和理科面试老师人数相等。在新的约束条件下，分别对问题一、二进行重新求解，得到聘请老师数M以及老师和学生之间的面试分配方案的最优解。最后，在问题一、二、三分析求解的基础上，本文对考生与面试老师之间分配的均匀性和面试的公平性进行了讨论，认为两者是对立统一的矛盾统一体。为兼顾分配均匀和面试公平，本文讨论了其他影响因素，并提出了六条切实可行的建议。另外，考虑将面试老师职称因素引入问题分析，建立新的模型。关键词：公平 师生匹配均匀 分配方案1 问题重述高校自主招生是高考改革中的一项新生事物，2006年，全国具有自主招生资格的高校已由最初的22所增加到53所。学生面试的公平性越来越引起人们和社会的高度重视。某高校拟在全面衡量考生的高中学习成绩及综合表现后再采用专家面试的方式决定录取与否。该校在今年自主招生中，经过初选合格进入面试的考生有N人，拟聘请老师M人。每位学生要分别接受4位老师的单独面试。为了保证面试工作的公平性，组织者提出如下要求：Y1：每位老师面试的学生数量应尽量均衡；Y2：面试不同考生的“面试组”成员不能完全相同；Y3：两个考生的“面试组”中有两位或三位老师相同的情形尽量的少；Y4：被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。需要解决如下问题：问题一：设考生数N已知，在满足Y2条件下，说明聘请老师数M至少分别应为多大，才能做到任意两位学生的“面试组”都没有两位以及三位面试老师相同的情形。问题二：请根据Y1Y4的要求建立学生与面试老师之间合理的分配模型，并就N379，M24的情形给出具体的分配方案（每位老师面试哪些学生）及该方案满足Y1Y4这些要求的情况。问题三：假设面试老师中理科与文科的老师各占一半，并且要求每位学生接受两位文科与两位理科老师的面试，请在此假设下分别回答问题一与问题二。问题四：请讨论考生与面试老师之间分配的均匀性和面试公平性的关系。为了保证面试的公平性，除了组织者提出的要求外，你们认为还有哪些重要因素需要考虑，试给出新的分配方案或建议。2 基本假设1、每位考生分别接受“面试组”几位老师的单独面试，小组面试结束前彼此完全独立；2、“面试组”老师的专业不同，提问的问题、提问的方式及评分习惯会有差异；3、面试部门的分配方案实施没有困难；4、考生和老师绝对服从组织者的统一安排；5、文科和理科老师各占一半时，第1到第M/2个老师为文科老师，第M/21到第M个老师为理科老师；6、正副教授在文理科老师中平均分配。3 符号说明N：需要面试的学生个数；M：需要聘请的老师个数；n：任意两位老师面试的两个学生集合中最多可能出现的相同学生人数：4 模型的建立和求解4.1 问题一4.1.1 问题分析设考生数N已知，在满足Y2条件下，说明聘请老师数M至少分别应为多大，才能做到任意两位学生的“面试组”都没有两位以及三位面试老师相同的情形。要解决这个问题，关键是怎样表示出面试的学生和老师之间的对应关系，为了表示这种对应关系，我们引入下面的01变量：在此基础上就可以根据不同的约束条件，以老师数M最小为目标建立01规划模型来求解。4.1.2 01规划模型的建立模型一：没有两位面试老师相同的规划模型根据对问题一的分析可知，可以建立下面的01规划模型：考生数N已知，满足Y2、以及任意两位学生的“面试组”都没有两位相同老师的条件下，聘请老师M最小为模型目标。约束条件： 每位学生的面试老师有四个，对于第i个学生来说表示面试老师的个数，需要满足。 任意两个学生的“面试组”都没有两位面试老师相同。如果第i和第k个学生都被第j个老师面试，那么和的值均为1， 则；如果第i个学生被第j个老师面试，而第k个学生不被第j个老师面试，那么取值为1 ，取值为0，则。同样，如果第i个学生不被第j个老师面试，而第k个学生被第j个老师面试，也有。没有两位面试老师相同，也就是只能有1或者0位老师相同，最多只能有一组和全取1。所以对于任意两个学生来说，必须满足：。 不同考生的“面试组”成员不能完全相同。当任意两个学生没有两位相同面试老师的时候，考生“面试组”的成员肯定不完全相同。该约束条件没有约束条件2强，所以只需满足约束条件2即可。 ，即我们定义的01变量。由此可以得到，在考生数N已知的情况下，任意两位学生都没有两位相同的面试老师的01规划模型如下：目标函数：约束条件： 模型二：没有三位面试老师相同的规划模型根据对问题一的分析，建立01规划模型。考生数N已知，满足Y2、以及任意两位学生的“面试组”都没有三位相同老师的条件下，聘请老师M最小为模型目标。约束条件： 每位学生的面试老师有四个，对于第i个学生来说表示面试老师的个数，需要满足。 任意两个学生的“面试组”都没有三位面试老师相同。没有三位面试老师相同，即可能存在2位、1位或者0位老师相同的情况。当2位老师相同时，；如果只有1位或者0位老师相同，的取值肯定更大。所以，没有三位面试老师相同，应该满足的条件。 不同考生的“面试组”成员不能完全相同。当任意两个学生没有三位相同面试老师的时候，考生“面试组”的成员肯定不完全相同。该约束条件没有约束条件2强，所以满足约束条件2即可。 ，即我们定义的01变量。在考生数N已知的情况下，任意两位学生都没有三位相同的面试老师的01规划模型如下：目标函数：约束条件： 4.1.3 模型的求解与分析按照搜索算法，通过MATLAB程序（见附录三、四），可以计算出M确定的情况下N的取值，根据运算结果可以反推出N确定时M的取值。部分具体N值对应的M见表1、表2：表1：没有两个老师相同时学生人数N和老师个数M的关系N12345678910M47910101112121213N11121314151617202124M14151616161717181920N26303335374245485055M21222324252627282930表2：没有三个老师相同时学生人数N和老师个数M的关系N123456781418M4667777889N1826395577105140148164189M10111213141517181920N221263315378442518606707819945M21222324252627282930由表1、表2结果可以知道：当老师人数M增加时，能够面试的学生数N，不是简单的成比例增加，而是按照一定的规律呈几何级数形式增加。随着老师数M的增加，每增加一个老师而增加的面试学生数越来越大，类似边际递增的现象。比如模型二中，M=17时，增加一个老师可以增加面试8个学生；M=29时，增加一个老师就可以增加面试126个学生。对于任意两学生都没有三位面试老师相同的情况，没有三位老师相同，说明可能存在2个、1个或者0个老师相同的情况，约束强度较模型一弱，相同学生数N对应的M值要小于模型一中的对应取值。由于算法中不能确定剔除含有两个或两个以上（三个或三个以上）相同元素的组合对中的某一个，会对后面的选取产生什么影响，因此也就不能保证选择剔除其中某一组合得到的最终结果会比保留该组合而剔除另一个所得到的最终结果好，所以只能给出近似最优解。4.2 问题二4.2.1 问题分析 问题二要求根据Y1Y4的要求建立学生与面试老师之间合理的分配模型，并就N379，M24的情形给出具体的分配方案（每位老师面试哪些学生）使得该方案尽量满足Y1Y4要求。与问题一相似，可以引入01变量来表示学生与老师之间的面试关系，根据Y1Y4的要求建立规划模型。由于要求比较多，问题二的模型与问题一有以下不同：考生数N379，老师数M24；2、同时满足Y1Y4的约束条件：在四个约束条件下求解最佳分配方案，涉及老师和学生双方面的约束，已经不能用简单的单目标规划模型来解决。所以，可以考虑建立基于同一组约束条件的多目标规划模型。运用多目标规划模型，不仅可以从多目标层次给出解决规划方案的优化问题，而且可以提供出具体的分配方案。4.2.2 多目标规划模型的建立模型三：最佳分配方案模型问题二中，可以将Y1、Y3、Y4看成基本约束条件下的目标函数，Y2作为约束条件，建立多目标规划模型。对于Y1，要满足每位老师面试的学生数量尽量均衡，即每位老师实际面试的学生数与每位老师平均面试的学生数之差的平方和最小。为第j位老师面试的学生总数，为每位老师平均面试的学生个数， Y1可以表示为：对于Y3，两个考生的“面试组”中有两位或三位老师相同的情况尽量的少。对于任意两个学生，分别表示第i和第k个学生是否被第j个老师面试，若说明第i和第k个学生有一个相同的面试老师，若说明他们有一个不同的面试老师。可以知道，只要越大，两个考生“面试组”中有两位或者三位老师相同的情形就会越少，Y3就可以表示为： 对于Y4，被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。这同Y3的思路一样，只是把两个学生之间的比较换为两个老师之间的比较。对于任意两位老师，取1或取0分别表示第j和第个老师是否面试第i个学生，当时第j和第个老师都面试第i个学生，当时他们不都面试第i个学生。对于第j和第个老师，的值越大，任意两个老师面试的两个学生集合中出现相同学生的人数越少。Y4就可以表示为： 对于上述目标函数，他们需要满足Y2约束条件： 每位学生的面试老师有四个，即。 不同考生的“面试组”成员不能完全相同。可能包含3个、2个、1个或者0个老师相同的情况，一定满足：，。 即我们定义的01变量。根据上述分析，建立N379，M24时，满足约束条件Y1Y4的学生与面试老师之间合理分配的模型如下：目标函数： 约束条件： 4.2.3 算法实现 求解多目标规划问题的基本思想是将多目标规划问题转换为单目标规划，具体的方法有很多，本文主要采用分层序列法的思想。即：将多个目标依次排序，先求出第一个目标的最优解，依次在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。由于涉及到01规划和过多的变量及约束，所以用LINGO不能直接求解。我们仍然选用搜索算法，对模型进行求解。具体算法步骤如下：Step1：用搜索算法生成24个老师可能组成的 个“面试组”。Step2：剔除其中不符合约束条件的组合。具体算法是对由Step1中得到的所有组合进行两两比较，找出含有三个或三个以上相同元素的组合对，从中剔除一个，使得在剩下的组合中的任意两个组合都不会含有三个或三个以上相同元素。Step3：判断剔除后的组合个数是否与N379相近，如果相近，则检验这些组合是否较好满足约束条件，并能使规划目标较为优化。Step4：找出每位老师所面试学生的集合，集合中的元素个数即为相应老师所面试学生的个数，由此可以判断各位老师面试的学生数量是否较为平均。Step5：根据每位老师所面试学生的集合，判断任意两位老师面试的两个学生集合中出现相同元素的个数是否较少。4.2.4 模型求解和分析由于算法是通过求出没有三位相同老师的组合，然后检验是否满足约束条件，使目标函数较为优化，所以Y2、Y3被很好满足，只需检验是否满足Y1、Y4。如果能较好满足，则求出的分配组合即为近似最优解。通过MATLAB求解（见附录五），没有三个老师相同的情况下，24个老师最多可以有378个组合。此时，每位老师面试的学生数都是63，非常均衡；同时可以看出，任意两个老师所面试的两个学生集合中重复的元素较少，较好满足Y4。在中选出不同于该378个组合的任意一个组合，添加到分配方案中。由于最多只有两个老师相同的组合只有378，因此添加任意一个组合，都会和这378组中的至少一个组合有三个相同元素。又由于378个组合中，每位老师面试的学生数都是63，所以加入任意一个组合对Y1、Y3、Y4都会产生相同影响。因此，任意加入一个组合，都可以得到问题二的一个近似最优解（具体方案见附录一）。在这个分配方案中，每位老师面试的学生个数相当均衡，符合Y1的要求。具体数据见表3：表3：每位老师面试的学生个数第M位老师12345678面试学生数N6464646364636363第M位老师910111213141516面试学生数N6363636363636363第M位老师1718192021222324面试学生数N6363636363636363任意两位老师面试的两个学生集合中出现相同学生的人数尽量少，只需使每个老师和其他老师相比，面试学生集合中最多相同学生个数n尽量小。分配方案得到的n值较小，基本满足Y4的要求。具体数据见表4：表4：每位老师面试学生集合中最多的相同个数第M位老师12345678n1212121112111111第M位老师910111213141516n711111111111111第M位老师1718192021222324n711111111111111同样可以得到，两个考生的“面试组”中有两位老师相同的情况总共有343组，有三位老师相同的情况有303组，基本满足Y2、Y3。由上述分析可知，所求的分配方案是问题二的近似最优解。4.3 问题34.3.1 问题分析 问题三假设面试老师中理科与文科老师各占一半，并且每位学生要接受两位文科与两位理科老师的面试。在此假设基础上，分别回答问题一和问题二。可以按照问题一、二的思路，将所有老师分为文科和理科两个部分，分别从两个部分中选取2位老师，组成一个学生的“面试组”，建立新的规划模型，进行求解。在这个问题里我们要解决三个子问题：子问题1：考生数N已知，满足Y2、每位学生的面试老师文理科各两个、以及任意两学生都没有两位面试老师相同的约束条件下，最小老师数M；子问题2：考生数N已知，满足Y2、每位学生的面试老师文理科各两个、以及任意两学生都没有三位面试老师相同的约束条件下，最小老师数M；子问题3：N379，M24时，满足Y1Y4、以及每位学生的面试老师文理科各两个的约束条件下，学生与老师之间的合理分配方案。4.3.2 问题三的模型建立整体的分析思路和问题一、二相同，多了文科和理科老师的限制。对于文理老师的平均分配，可以通过定义老师的编号顺序来解决。如聘请的老师数为M（M为偶数），设第1到第M/2个老师为文科老师，第M/2+1到第M个老师为理科老师，在此基础上就可以通过限制“面试组”中前M/2个老师中的个数来保证同一学生文科和理科面试老师人数相等。4.3.3 算法实现问题三中，模型四和模型五的算法同模型一、二大致相同，只需再加入文理科老师的限制。具体算法步骤如下：Step1：用搜索算法生成M个老师可能组成的个“面试组”。Step2：找出个“面试组”中同时满足下列条件的所有组合：组合中第2个元素小于等于M/2，组合中第3个元素大于M/2。Step3：剔除其中不符合约束条件的组合。具体算法是对由Step1中得到的所有组合进行两两比较，找出含有两个或两个以上（三个或三个以上）相同元素的组合对，从中剔除一个，使得在剩下的组合中的任意两个组合都不会含有两个或两个以上（三个或三个以上）相同元素。Step4：由Stept2得到M个老师可以面试的学生数N，循环操作，可以得到确定学生数N对应的最小老师数M。4.3.4 模型求解和分析子问题1、2：按照搜索算法，通过MATLAB程序（见附录六、七），可以计算出M确定的情况下N的取值，根据运算结果可以反推出N确定时M的取值。部分具体N值对应的M见表5、表6：表5：没有两个老师相同时学生人数N和老师个数M的关系N123456910M48101010121214N1316202531354148M1618202224262830表6：没有三个老师相同时学生人数N和老师个数M的关系N15163363112120M481012141618N153211300408553735M202224262830由表3、表4结果可以知道：当老师人数M增加时，能够面试的学生数N，不是简单的成比例增加，而是按照一定的规律呈几何级数形式增加。随着老师数M的增加，每增加一个老师而增加的面试学生数越来越大。如表4中，M=10时，增加二个老师可以增加面试17个学生；M=28时，增加二个老师就可以增加面试182个学生。对于任意两学生都没有三位面试老师相同的情况，没有三位老师相同，说明可能存在2个、1个或者0个老师相同的情况，约束强度较模型一弱，相同学生数N对应的M值要小于模型一中的对应取值。子问题3：根据模型三的分析，用搜索算法（见附录八）可以得到近似最优解。没有三个老师相同的情况下，24个老师最多可以有300个组合。此时，有三个老师面试的学生数都是75，非常均衡；同时可以看出，任意两个老师所面试的两个学生集合中重复的元素较少，较好满足Y4。根据加入组合后，新的分配方案仍能很好满足均衡条件这一要求，用MATLAB程序在中选出79个新的组合，使得24个老师能够面试379个学生。检验新的分配方案，发现仍能较好解决子问题3（具体分配方案见附录二）。在这个分配方案中，每位老师面试的学生个数相当均衡，符合Y1的要求。具体数据见表7：表7：每位老师面试的学生个数第M位老师12345678面试学生数N6463636363636363第M位老师910111213141516面试学生数N6363636463646363第M位老师1718192021222324面试学生数N6362636365636363任意两位老师面试的两个学生集合中出现相同学生的人数尽量少，只需使每个老师和其他老师相比，面试学生集合中最多相同学生个数n尽量小。分配方案得到的n值较小，基本满足Y4的要求。具体数据见表8：表8：每位老师面试学生集合中最多的相同个数第M位老师12345678M位老师910111213141516n61081218161815第M位老师1718192021222324n1514161517151617同样可以得到，两个考生的“面试组”中有两位老师相同的情况总共有269组，有三位老师相同的情况有2组，基本满足Y2、Y3。由上述分析可知，所求的分配方案是子问题3的近似最优解。4. 4 问题44.1.1考生与面试老师分配的均匀性与面试公平性的关系：面试是主观性很强的评价工作。如何保证面试的公平性是众多考生和家长关注的问题，也是本题想加以解决的核心。面试老师的专业不同，方向有差异，年龄跨度可能也比较大，他们所提问问题的内容、方式及对问题的看法，甚至对同一考生回答的评价都会迥然不同以致得出完全背离的结果。为了减少由于考生与面试老师分配的不均匀所导致的不公，组织者给出了四个要求：Y1、每位老师面试的学生数量应尽量均衡；Y2、面试不同考生的“面试组”成员不能完全相同；Y3、两个考生的“面试组”中有两位或三位老师相同的情形尽量的少；Y4、被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。根据组织者提出的要求及我们对问题的求解显示，多目标规划问题的各个优化目标之间本身可能就存在一定矛盾，从而不能保证分配均匀和面试公平同时达到最优。以问题二为例，每位老师面试的学生数量几乎完全相同，且仅有2个组合具有三个相同的元素，但同时，被任意两位老师面试的两个学生集合中出现相同学生的人数却有12个之多，可见，多目标规划中，Y1,Y2,Y4三者的优化目标之间本身就可能存在矛盾。这一说法在问题三中再次得到证明，问题三得到的结果中, 每位老师面试的学生数量还是几乎完全相同，但由于加入了文理科老师必须都有两个的约束，具有三个相同元素的组合达到了303个之多，而且被任意两位老师面试的两个学生集合中出现相同学生的人数多达18个。也就是说，考生与面试教师之间分配的越均匀，专业差异越体现，看问题视角就越不同，评分结果越无可比性，相应地会越不公平。所以，考生与面试老师分配的均匀性与面试公平性的关系是对立统一的矛盾统一体。增加均匀是想要体现公平，但在增加了均匀的同时，差异又在放大，公平反而在缩小。4. 4.2 考虑新因素情况下的分配方案和建议在考虑新因素的情况下，可以建立新的模型，给出新的分配方案或建议。面试公平性的影响因素很多，其中包括很多主观和无法控制的因素。这里，我们引入面试老师的职称因素。假设参加面试的老师职称包括正教授和副教授两个级别，且正副教授在男女老师中平均分配，就可以按照问题三中的思路，通过限制“面试组”中老师的顺序来保证文理科和正副教授的均衡。在问题三中，讨论了聘请的老师数为M的情况下，设第1到第M/2个老师为文科老师，第M/2+1到第M个老师为理科老师，可以加强假设条件：设文科老师中第1到第M/4（不可整除时，对M/4取整）个老师为正教授，第M/41到第M/2个老师为副教授；理科老师中第M/21到第3M/4个老师为正教授，第3M/41到第M个老师为副教授。这样，就可以通过限制“面试组”中各个部分中老师的个数来保证面试同一学生的老师中正副教授数相等。这个约束条件可以表示为： 在该约束条件下，可以对问题一、二、三中的模型重新进行求解，模型形式和算法不变。5 模型评价和改进5.1 模型评价5.1.1 模型优点l 本文所建规划模型简单易懂，符合实际；l 在规划的基础上，采用搜索算法全局寻优，可以简化模型求解过程，解决LINGO软件不能实现的问题。l 运用搜索算法，可以直接给出学生和老师之间具体的分配方案，方便可行。l 在增加新因素的情况下，可以建立新的规划模型进行求解。5.1.2 模型缺点l 多目标规划模型涉及变量和约束过多，搜索算法只求出近似最优解。l 由于时间与篇幅限制，本文没有进行误差分析。5.2 模型改进搜索算法虽然可以很好的给出求解结果，但始终不是最优解，如何将求解结果尽可能的优化，是本文模型改进的重点。6 附录附录一：问题二的具体分配方案1234125612781291012111212131412151612171812192012212212232413571368139111310121313151314161317191318201321231322241458146714912141011141316141415141720141819142124142223159131510141511151512161517211518221519231520241691416101316111616121516172216182116192416202317915171016171113171214171723171824171921172022189161810151811141812131817241818231819221820212358236723912231011231316231415231720231819232124232223245724682491124101224131524141624171924182024212324222425914251013251116251215251722251821251924252023269132610142611152612162617212618222619232620242791627101527111427121327172427182327192227202128915281016281113281214281723281824281921282022345634783491034111234131434151634171834192034212234232435915351016351113351214351723351824351921352022369163610153611143612133617243618233619223620213791337101437111537121637172137182237192337202438914381013381116381215381722381821381924382023459164510154511144512134517244518234519224520214691546101646111346121446172346182446192146202247914471013471116471215471722471821471924472023489134810144811154812164817214818224819234820245678569105611125613145615165617185619205621225623245791157101257131557141657171957182057212357222458912581011581316581415581720581819582124582223679126710116713166714156717206718196721246722236891168101268131568141668171968182068212368222478910781112781314781516781718781920782122782324910111291013149101516910171891019209102122910232491113159111416911171991118209112123911222491213169121415912172091218199122124912222391317219131822913192391320249141722914182191419249142023915172391518249151921915202291617249161823916192291620211011131610111415101117201011181910112124101122231012131510121416101217191012182010122123101222241013172210131821101319241013202310141721101418221014192310142024101517241015182310151922101520211016172310161824101619211016202211121314111215161112171811121920111221221112232411131723111318241113192111132022111417241114182311141922111420211115172111151822111519231115202411161722111618211116192411162023121317241213182312131922121320211214172312141824121419211214202212151722121518211215192412152023121617211216182212161923121620241314151613141718131419201314212213142324131517191315182013152123131522241316172013161819131621241316222314151720141518191415212414152223141617191416182014162123141622241516171815161920151621221516232417181920171821221718232417192123171922241720212417202223181921241819222318202123182022241920212219202324212223241235附录二：问题三的分配方案1213171213151213141215191215161217181219201221221223241313151314181314161317191318201321231322241413161414151415231417201418191421241422231513141513171514181515191516201613181614171615201616191618241713181713191714201715171716181813201814151814191815181816171913211914221915231916241918241101322110142211014211101524110162311113191111323111142411115211111622112131