2572.学生面试问题.doc

题 目 学生面试问题摘 要：本文主要讨论的是优化分配问题，在充分理解问题的基础上，利用排列组合、计算机搜索等知识对各问进行分析，建立模型求解得到所需结果，并对结果的合理性做出验证。对于第一问，首先利用贪婪算法给出不同情况下（有两位老师相同及有三位老师相同）不同学生数目N对应的老师数量M，在对应数据中可以发现有多组N对应的是同一M，通过逆向思维我们利用固定的M确定最大的N，反过来此N对应的M就是最小的老师数量。采用不完全归纳的方法给出了不同情况下M和N的对应关系，并对其进行了证明。对于第二问，在充分理解4项要求的基础上，将其分别转化为约束条件和目标函数。经过分析，以两个考生的“面试组”中有两位或三位老师相同的情形尽量的少、 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少为目标，在满足Y1、Y2等条件的约束下，建立双目标整数规划模型。利用计算机搜索求解，得到具体的分配方案详见模型的求解（6.3.2），并对得到的方案进行分析，给出满足Y1Y4要求的情况，详见6.4的结果分析。对于第三问，在新加条件“考生面试组成员中文理老师各占一半”的约束下，经过分析得到与原要求的根本区别在于：将原来一个考生的面试组成员为4人的约束细化为有两位文科老师、两位理科老师。在原模型目标函数不变的情况下，针对新加约束，建立整数规划模型，进行求解，得到新的分配方案并对方案满足4项要求的情况做出了具体分析，详见7.3。对于第四问，在所得数据的基础上，通过对题目的理解，讨论了考生与面试老师之间分配的均匀性和面试公平性的关系。针对公平性原则，提出了其他一些需要考虑的重要因素。关键词： 贪婪算法 穷举法 计算搜索 排列组合 1 问题重述高校自主招生是高考改革中的一项新生事物，现在仍处于探索阶段。某高校拟在全面衡量考生的高中学习成绩及综合表现后再采用专家面试的方式决定录取与否。该校在今年自主招生中，经过初选合格进入面试的考生有N人，拟聘请老师M人。每位学生要分别接受4位老师（简称该学生的“面试组”）的单独面试。面试时，各位老师独立地对考生提问并根据其回答问题的情况给出评分。由于这是一项主观性很强的评价工作，老师的专业可能不同，他们的提问内容、提问方式以及评分习惯也会有较大差异，因此面试同一位考生的“面试组”的具体组成不同会对录取结果产生一定影响。为了保证面试工作的公平性，组织者提出如下要求：Y1. 每位老师面试的学生数量应尽量均衡；Y2. 面试不同考生的“面试组”成员不能完全相同；Y3. 两个考生的“面试组”中有两位或三位老师相同的情形尽量的少；Y4. 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。请回答如下问题：问题一：设考生数N已知，在满足Y2条件下，说明聘请老师数M至少分别应为多大，才能做到任两位学生的“面试组”都没有两位以及三位面试老师相同的情形。（相同人数为01）问题二：请根据Y1Y4的要求建立学生与面试老师之间合理的分配模型，并就N379，M24的情形给出具体的分配方案（每位老师面试哪些学生）及该方案满足Y1Y4这些要求的情况。问题三：假设面试老师中理科与文科的老师各占一半，并且要求每位学生接受两位文科与两位理科老师的面试，请在此假设下分别回答问题一与问题二。问题四：请讨论考生与面试老师之间分配的均匀性和面试公平性的关系。为了保证面试的公平性，除了组织者提出的要求外，你们认为还有哪些重要因素需要考虑，试给出新的分配方案或建议。2 问题分析针对问题一，通过贪婪算法可以确定不同学生数量N对应的不同老师数量M，从所得数据中可以发现有多组N对应的M是相同的，也就是一个M可以对应几个N，但其中必有一个最大值，此时最大的N对应的老师数量M也就是我们要找的当N固定时最小的老师数量。利用此结论可通过不完全归纳的方法得到任两个考生“面试组”成员中有两个及三个相同时的老师数量。针对问题二，通过对题目所给四项要求合理的分析，可以知道Y1（老师面试学生数量尽量均衡）、Y2（任意两考生面试组成员不能完全相同）可作为约束，Y3（两个考生的“面试组”中有两位或三位老师相同的情形尽量的少）、Y4 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少分别作为一、二级目标，建立双目标整数规划模型，利用计算机搜索求解得到各分配方案，根据题目的4项要求对所得结果进行分析。针对问题三，此问即在原要求的基础上新加条件“每位学生的面试组中有两位文科老师和两位理科老师”，仔细分析，只是将原约束中每位学生的面试组成员为4人变成理科两人、文科两人，其目标不变仍然是以Y3、Y4为目标，建立双目标01整数规划模型进行求解得到新加条件下的分配方案。针对问题四，通过对题目的理解，结合求解出的已知数据，对考生面试老师分配的均匀性和公平性的关系给出讨论，根据题目所述的公平性原则，提出了几点需要考虑的重要因素。3 模型假设1 面试老师没有特殊要求。2 考生无文理分别。3 每位考生只面试一次。4 符号说明表1 变量含义一览表变量定义参加面试的学生人数参与面试的老师人数01变量，当等于1时表示第个学生被第个老师面试不同考生的面试组成员相同的人数01变量，当其值为1时表示第位老师都面试了第个同学任意两个考生的面试组成员中有两个相同的人数任意两个考生的面试组成员中有三个相同的人数任意两个老师面试同一个学生的人数表示第位老师面试学生的个数不同考生的面试组成员相同的人数任意两个考生的面试组成员中有两个相同的人数5 问题一的求解5.1 没有两位相同的情况任两位考生的“面试组”成员没有两位老师相同，也就是说只有一位相同或全都不同，容易想象有一位相同老师的情况对应的老师总数M比全不相同的老师总数要少，所以这里在安排学生老师的对应方案时，要尽量使任两组都有一位老师相同，这样才能保证老师的数目最小。首先，根据贪婪算法给出学生数目（N）为114时对应的老师数目（M），如下表所示：表2 学生老师对应情况学生数目（N）老师数目（M）14273941051061171281291210131113121313131414通过对表格中数据的分析可以看出，有多个不同学生数目对应的老师数目是相同的，反过来，同一个老师M也可能对应多个学生N，但其中必有一个较大的值。这样要找学生数目为N时，最小的老师数目M，只需在M对应的多个学生数目为N的数据中找出最大的一个N，此时的M是N固定时最小的老师数量。利用此逆向思维的方法我们可以通过M来寻找最大N，也就是在N确定时得到了一个最小的M。首先对M而言，从中任意选出4人组合成一个面试组的数目为：，在这些组合中调出两组进行比较，共能抽出种，现进行如下分析，当两组进行比较时，如果有大于1个相同的老师，则认为此时对应的为0，如果有1个或全不相同则认为相应的为1。这样就可以计算出所有满足任意两个面试组没有两个相同的组合数目为：【说明】式中N为考生人数，M为面试老师人数。将上表格中数据带入检验，得到公式满足如上数据，根据此式，给出一个N，就有一个最小的M与之项对应。5.2 没有三位相同的情况任两位考生的“面试组”成员没有三位老师相同，也就是说只有两位相同、一位相同或全都不同，容易想象有两位相同老师的情况对应的老师总数M比全不相同和有一位相同老师的总数要少，所以这里在安排学生老师的对应方案时，要尽量使任两组都有两位位老师相同，这样就能保证老师的数目最小。当学生的数目由1逐渐增加时可以通过排列组合的知识得到相应的老师数目，如下所示：表3 考生老师的对应情况学生数目（N）老师数目（M）142636475767778898108118128138从表中数据可以看出，N取不同值时可能对应同一个M，换位思考，同一个M可对应多个考生，但是N的大小不同。通过逆向思维，当N1确定时，要确定最少的老师数目M1，也就是要找到M1一定时对应的考生数目中最大学生数N2，当N1N2时，对应的M1就是要求的最小值。所以我们进行如下分析可得。5.2.1 mod()1老师数目位M，从中任选4个组成不同的面试组，满足要求Y2，共能组成面试组的数量为，为了满足条件任两个学生对应的面试组中没有三位面试老师相同。一个面试组的成员为4人，将M1个人按每组4人进行分组，对结果进行向下取整得到个组，乘以四加1，然后利用除以此值向下取整得到所需要的值。【说明】式中表示从M中任选4人，表示对向下取整。此时给定一个N必有一个M与之相对应。5.2.2 mod()2 如上式的分析，在面试老师人数对4取余为2时，得到固定老师数目为M对应最大的数目为N，如下式，此式的调控因子为0。5.2.3 mod()3 通过M对4取余为3的讨论，经过化简得到面试老师数目固定为M时对应的最大学生数目N：其中：当是奇数时，；当是偶数时，；以上均为调控因子。5.2.4 mod()0 将M对4 取余的情况经过分析化简，得到M对应学生数量N的表达式为：6 问题二的求解6.1 对四项要求的量化分析6.1.1 Y1的要求为了方便对题目的理解，在进行量化之前首先对学生和老师进行编号，号码分别为1N，1M。共有N个学生，M位老师，平均每位老师面试的学生个数为：（本题所给数据计算的结果为63.17），每位老师面试的学生数目尽量相同，也就是各位老师偏离平均面试个数的幅度尽量小。在确定老师面试学生数目尽量相同时利用表示，每位老师面视学生的个数为: 【符号说明】表示第位老师面试学生的个数。 通过题目已知，每位学生的面试组成员为4名，所以：为了对数目尽量相同进行约束，我们规定任意两个老师面试学生的个数之差在一定的范围之内，将最大差值定义在1。所以 上式就可以确保任意两位老师面试学生的数目尽量相同。6.1.2 Y2的要求 通过分析可以求出任意两位学生面试时的面试组中相同的老师人数。利用公式可得到: 【符号说明】、均为01变量，等于1时表示被第j个老师面试，当等于2时，表示第两位学生都被第个老师面试。定义01变量表示不同学生的面试组中有相同老师，含义如下： 由此就可以将任意两个不同学生的面试组中含有相同老师的个数得到，如下： 【符号说明】表示不同考生面试组成员相同的个数。为了满足Y2的要求，即面试不同考生的“面试组”成员不能完全相同，于是得到下式： 6.1.3 Y3的要求 利用Y2的分析，可以将不同考生面试组相同成员的数目表示出来，如下所示;【符号说明】分别表示面试组中相同成员数位2，3的情况。要使这两方面的数目尽量下，需要在相同成员不同数目的组合时要进行加权处理，根据对题目公平性的理解，当面试组中相同成员数目小时更为公平，所以令有两个成员的相同的项权值为0.4,三个成员相同的项权值为0.6，也就是尽量使两个相同的数目少，然后在考虑三个成员相同的方面。所以得到下式： 6.1.4 Y4的要求首先统计出任意两位老师面试同一位学生的数量，利用如下公式：【符号说明】当2时表示第位老师都面试了第个同学，等于其他值时不表示上述含义。、均为01变量，等于1时分别表示被第位老师面试。为了更好的说明表示以上情况，特引入了01变量，其含义如下：即当时，表示第位老师都面试了第个同学。将第位老师都面试同一学生的数量进行累加得到： 表示第两位老师都面试同一个学生的个数。根据题目的意思，所以： 6.2 模型的建立根据上述分析，以两个考生的“面试组”中有两位或三位老师相同的情形尽量的少、 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少为目标，在满足Y1、Y2等条件的约束下，建立整数规划模型如下： 【模型说明】(1) 目标一，使两个考生面试组中两位或三位老师相同的情形尽量少。分别为的函数（详见6.1.3），具体含义见符号说明。(2) 目标二，被任意两位老师面试的学生稽核中出现相同学生人数尽量少。有关的得出详见6.1.4。(3) 约束一，每位老师面试的学生数量应尽量平衡。(4) 约束二，面试不同考生的“面试组”成员不能完全相同。是通过得到的，具体含义及推理详见6.1.2。(5) 约束三，每位学生面试时老师的人数为4。(6) 约束四，每位老师面试学生的人数。【符号声明】表4 参数说明 变量 含义任意两个考生的面试组成员中有两个相同的人数任意两个考生的面试组成员中有三个相同的人数任意两个老师面试同一个学生的人数表示第位老师面试学生的个数不同考生的面试组成员相同的人数01变量，当其值为1时表示第个学生被第个老师面试6.3 模型的求解 题目给出了学生数量，面试老师的数量为，将此数据带入上述模型进行编程求解即可得到分配方案。编程算法和分配方案如下。6.3.1 编程算法Step1:判断。每4位老师组成一个面试组，当位老师面试位考生的时候，只要满足条件，就可以满足组织者提出的要求（面试不同考生的“面试组”成员不能完全相同）。在满足上述必要的条件下，对老师以及考生进行编号处理，将老师编号按一定的规律每4人一组生成组合矩阵，然后对组合矩阵进行搜索求解。Step2:组合矩阵的生成。步骤一中对老师进行了编号，在此，每一个号码代替一位老师生成“面试组”矩阵。在生成的每组组合数中，第一个数最小为1，最大为；最后一个数最小为4，最大为。第个组合数的排列顺序为，其中，。按照上述组合规则对所有数据进行排序组合，每一个组合组成矩阵的行，组合的个数组成矩阵的行数。Step3:换位法全排列。由于矩阵排列顺序的不同对最后搜索结果有一定的影响，为了得到全局最优解，应对组合矩阵进行全排列，然后对每一种情况进行搜索求解。为了好说明，进行图示表示： 其中有4个数，每个数代表一个组合，按照上述规律，从最底行，每次将其和上一行进行对换，每对换一次按一定的约束条件进行组合筛选。将所有结果进行比较选取最优解。Step4:搜索。在搜索过程中运用了搜索比较置0法。以任意两位考生的面试组没有两位老师相同的情形为例。从第一行开始，依次和其下面的每一行进行比较，用作为每一行的比较相同计数累加器，当累加数大于等于2时，将比较行进行清零处理。最后将没有被清零的组数统计出，得到的就是位老师在一定条件下所能组成的组数。Step5:搜索结果处理。通过上面步骤一到四得到全局所有结果，选取其中最优解，当 为定值时，得到的最大值。Step6:题目要求要求两个考生的“面试组”中有两位或三位老师相同的情形尽量少；任意两位老师面试的考生集合的交集数尽量少以尽量保持其公平性。在上述条件约束下，就要对结果进行分析，选取较优的方案。6.3.2 分配方案通过上诉方法的计算得到具体分配方案，表5 分配方案老师编号考生编号1 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162632 12345678910116465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141153 11213141516171819202164656667686970717273116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157231120313847526173829198105112125130139148157163170181188198205214222229238245250257260265266271279284289292295298307308313318323325328335338344347352356359364367368371373374377378 379241121303946536072839099104113125131138149156162171180189198206213221230238245251256261264267270278285288293294299307309312319322324329334339344348351355360364367369370372375377378 379具体数据详见附录一。下面给出的每位老师对应的考生编号，如下所示：6.4 满足情况6.4.1 Y1要求由上述分配方案中可以看出每位老师面试63或64位考生，很好的满足了Y1（每位老师面试的学生数量应尽量均衡）。6.4.2 Y2要求有位老师共可以组成成员完全不同的面试组个，远大于题中要求的个考生，因此可以满足Y2（面试不同考生的“面试组”成员不能完全相同）。6.4.3 Y3要求(1) 两位老师相同表6 两位老师相同的情况现将方案中任意两考生面试组中有两位相同的情况。表 两个考生的面试组中有两位老师相同的数据统计 606044444444444444456060444444444444444460604444444444444444444444444444444444444444444444444444444445444444444444444544444460604444444444444444606044444444444444444444444444444444444444444444444444444444454444444444444445444444606044444444444444454444444445444444444444444544444444444444444444444444444444444444444444444544444444444444454444444444444444444444444444444444444460444444444444444544444444444444444444444444444444444444444444444444444444444444444444444444444445606060454444446060454445456060454445454544454545444545444544444445444460604444444460604444444444444444444444444544444445444444606044444445454444444544444444444444444444444544444445444444444444444444444460444444454444444444444444444444444444444444444445606060616161616060606060616142 上表中数据依次为1379号考生分别与其他多少个考生在面试组中有两位老师相同的情况的统计数据（共379个数据）。(2) 三位老师相同现给出方案中任意两考生面试组中有三位相同的情况表7 面试组中有三位老师相同的情况 两个考生的面试组中有三位老师相同 考生编号245266270367379重叠数11114上表为有三位老师相同的情况统计结果，379号考生分别与245、266、270、367号考生的面试组中有三位老师相同的情况出现，上述两表说明求得的分配方案满足Y3的情况。从统计分配方案中可以看出：一个考生与其他4460位考生的面试组中有两位老师相同，仅有4对考生的面试组中出现三位老师相同的情况，能够较为合理的满足Y3（两个考生的“面试组”中有两位或三位老师相同的情形尽量的少）。6.4.4 Y4要求根据分配方案，任意两位老师面试的两个学生集合中出现相同学生的人数情况如下： 表8 任意两老师面试学生集合相同学生的情况老师编号任意两位老师面试考生的交集数（0表示和自己比较）1 01111111111111177777777777777772 11011111111111177777777777777773 11110111111111177777777777777774 11111101111111177777777777777775 11111111011111177777777777777776 11111111110111177777777777777777 11111111111101177777777777777778 11111111111111077777777777777779 777777770111111111111117777777710 777777771101111111111117777777711 777777771111011111111117777777712 777777771111110111111117777777713 777777771111111101111117777777714 777777771111111111011117777777715 777777771111111111110117777777716 777777771111111111111107777777717 777777777777777701111111111111118 777777777777777711011111111111119 777777777777777711110111111111120 777777777777777711111101111111121 777777777777777711111111011111122 777777777777777711111111110111123 777777777777777711111111111101124 7777777777777777111111111111110上表中数据为在求得分配方案中124位老师分别与其他老师面试的两个学生集合中出现相同学生的人数统计。从统计分配方案中任意两位老师面试考生的交集数可以看出：任意两个老师面试的两个考生集合中出现出现相同考生的人数为7或11,能够较好的满足Y4（被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少）7 问题三的求解7.1 在新加条件下对问题一的求解7.1.1 没有两位相同的情况 从文科老师个人中选取2位，得到种组合，从个理科老师中选取2位，同样得到种组合，将这两种组合联合得到各种面试组共有个，从中任选两种组合进行进行比较，将满足条件的组合系数记为1，不满足条件的组合记为0，将所有组合进行累加，得到全部满足条件的数量，公式如下：【其中】，给定一定的数目N，就有最小的M与之对应。7.1.2 没有三位相同的情况类似于上一问的分析，从文理两个科目中各选取两位老师组合成一个面试组，共有个方式，这些组中任选两组进行比较，令得到组合数位个，当两个组合中有大于2个老师相同时组合系数0，当小于等于2个时组合系数1，所以可得到下式：【其中】，给定一定的数目N，就有最小的M与之对应。7.2 在新加条件下对问题二的求解7.2.1 对新加条件的分析新加条件与原文的不同之处在于添加了文理科老师在每位学生的面试组中各占一半的条件。其他条件基本不变，通过分析可知，对于任意一个学生被4各老师面试的条件可以细化成被2名文科和2名理科老师同时面试。这里我们将文理老师分为两组，一组是文科老师，编号为1，一组是理科老师，编号是，学生编号仍然是1。在原6.2模型的基础上增加将约束三即表达式(5)进行替换成新加约束，如下： 第一个式子表示第个学生被两位文科老师面试，后一个式子表示第个学生同时被两个理科老师面试。7.2.2 模型的建立根据上述分析，在新加条件下，仍然以两个考生的“面试组”中有两位或三位老师相同的情形尽量的少、 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少为目标，在满足新加条件和原Y1、Y2等条件的约束下，建立整数规划模型如下所示： 【模型说明】(1) 目标一，使两个考生面试组中两位或三位老师相同的情形尽量少。分别为的函数（详见6.1.3），具体含义见符号说明。(2) 目标二，被任意两位老师面试的学生集合中出现相同学生人数尽量少。有关的得出详见6.1.4。(3) 约束一，每位老师面试的学生数量应尽量平衡。(4) 约束二，面试不同考生的“面试组”成员不能完全相同。是通过得到的，具体含义及推理详见6.1.2。(5) 约束三，每位学生同时被两位文科和两位理科老师面试。(6) 约束四，每位老师面试学生的人数。【符号声明】表9 参数说明 变量 含义任意两个考生的面试组成员中有两个相同的人数任意两个考生的面试组成员中有三个相同的人数任意两个老师面试同一个学生的人数表示第位老师面试学生的个数不同考生的面试组成员相同的人数01变量，当其值为1时表示第个学生被第个老师面试7.2.3 模型的求解(1) 编程算法面试老师中文科和理科老师各占一半，每位学生接受两位文科与两位理科老师的面试。此算法和上述算法大体相同，只是在组合矩阵的生成上存在着不同。Step1:判断。由于将老师分成了两部分，最后可形成的无重复组合数列将大大降低。有 位老师，其中文理科老师各占一半，分别为。当满足，就可以满足条件二（）。Step2:组合矩阵的生成。每位学生面试时对应着两位文科与两位理科老师，为了好处理，在组合时，将前两个数作为文科老师的编号，其范围，后两个数作为理科老师的编号，范围。组合数列中，。按照上述组合规则对所有数据进行排序组合，每一个组合组成矩阵的行，组合的个数组成矩阵的行数。Step3: 经过上面两个步骤进行组合后，由于矩阵排列顺序的不同对最后搜索结果有一定的影响，为了得到全局最优解，应对组合矩阵进行全排列，然后对每一种情况进行搜索求解。为了好说明，进行图示表示： 其中有4个数，每个数代表一个组合，按照上述规律，从最底行，每次将其和上一行进行对换，每对换一次按一定的约束条件进行组合筛选。将所有结果进行比较选取最优解。Step4:搜索。在搜索过程中运用了搜索比较置0法。以任意两位考生的面试组没有两位老师相同的情形为例。从第一行开始，依次和其下面的每一行进行比较，用作为每一行的比较相同计数累加器，当累加数大于等于2时，将比较行进行清零处理。最后将没有被清零的组数统计出，得到的就是位老师在一定条件下所能组成的组数。Step5:搜索结果处理。通过上面步骤一到四得到全局所有结果，选取其中最优解，当 为定值时，得到的最大值。Step6:题目要求要求两个考生的“面试组”中有两位或三位老师相同的情形尽量少；任意两位老师面试的考生集合的交集数尽量少以尽量保持其公平性。在上述条件约束下，就要对结果进行分析，选取较优的方案。(2) 分配方案通过编程求解得到所有学生老师的分配方案如下：表10 分配方案老师编号考生编号11 2 34 5 6 7 89 1011 12 1314 15 1617 18 19202122232425 26 27 28 293031 32 3334 35 36 37 38 39 40 4142 43 4445 46 4748 49 5051 52 53 54 5556 57 58 337 338 340 341 342 343 345346349350353356360361 36236636737037137437537737821 2 3 4 5 6 5960 61 6263 64 65 66 67 68 69 7071 72 73 74 75 76 77 7879 80 81 82 83 84 858687 88 89 90 91 9293 94 95 96 97 9899 100 101 102 103 104105 106107108109110338339344347348349351352354355357358 35936336436536836937237337637937 8 9 10 11596061626364111112113114115116117118 119120121122123124125126127128129130131132133134135 136137138139140141142143144145146147148149150151152 15315415515615734735135536236537522511172128364145525864697579849199 106 108115126129137141145149156162173176180187192194203 210211219224227233236246250254258263271275279287290 294298307314319324330334349366374375 2361628374446515663758592102104107116121 137142144150155167173179188191195204209213217223229 234238245249252259265272276286295297308313319324329 335363370373377379 2461727384348535564748694101103109116136 143148152154172183189190197204210216221230235246247 251260266272274280283291293301308314330336362363370 373377379