学生面试问题
摘要
本文研究的学生面试问题，是在给定学生数量的前提下，按照每名学生的面试组由四名老师组成，且各个学生的面试组两两不完全相同的要求，研究需要的老师数量，并求出面试分组方案。为了保证面试的公平性，组织者还提出了四条要求，需要考虑除Y2外使其它三条要求尽量满足的分配方案。
第一问是已知学生数量为N，求任意两个面试组最多只有一名老师相同的最小老师数量，我们将此问题转化成一个0-1规划模型，并设计了优化搜索方法，通过MATLAB编程实现了最少M的近似解。
在第二问的解决中，首先对Y1-Y4四个要求进行了分析，并分别建立了相应的量化指标，在此基础上，建立了一个多目标规划模型。针对学生数较多，模型求解运算量大的问题，特别设计了优化算法，减少了搜索中的运算量。同时，通过讨论均衡与公平性的含义，以分目标为基础，建立了综合评价目标，以此为指引，使搜索算法更具有针对性。计算结果表明，分配方案满足Y1-Y4的情况是非常好的。
第二问中还运用组合数学中区组设计的理论，论证了N=379、M=24时不存在完全满足均衡和公平要求的理想分配方案。
第三问中，将老师组分成文、理两类，首先修改了问题一中的相应模型和算法，给出了求解结果。在第二问中提出了启发式－混合交叉算法，从模拟结果看，分配方案比原第二问中的方案要差些，但总体上在各个指标上满足的情况也是较好的。
第四问首先分析了均匀性与面试公平性的关系，并提出了公平率的评价指标。为了解决学生与面试老师有特殊关系，及个别老师打分过于苛刻或宽松的问题，本文提出了规避的解决方法。
关键词：多目标规划算法评价指标
1.问题重述
某高校采用专家面试的方式进行自主招生录取工作。经过初选合格进入面试的考生有N人，拟聘请老师M人进行面试。每位学生要分别接受“面试组”的每一位老师的单独面试。每个面试组由4名老师组成。各位老师独立地对考生提问并根据其回答问题的情况给出评分。
为了保证面试工作的公平性，组织者提出如下要求：
Y1：每位老师面试的学生数量应尽量均衡；
Y2：面试不同考生的“面试组”成员不能完全相同；
Y3：两个考生的“面试组”中有两位或三位老师相同的情形尽量的少；
Y4：任意两位老师面试的两个学生集合中出现相同学生的人数尽量少。
请回答如下问题：
问题一：设考生数N已知，要求在满足条件二的情况下，说明聘请老师数M至少分别应为多大，才能做到任两位学生的“面试组”都没有两位以及三位面试老师相同的情形。
问题二：请根据条件一至条件四的要求建立学生与面试老师之间合理的分配模型，并就N＝379，M＝24的情形给出每位老师面试学生名单的具体分配方案，并分析该方案满足条件一至条件四的情况。
问题三：假设面试老师中理科与文科的老师各占一半，并且要求每位学生接受两位文科与两位理科老师的面试，请在此假设下分别回答问题一与问题二。
问题四：请讨论考生与面试老师之间分配的均匀性和面试公平性的关系。为了保证面试的公平性，除了组织者提出的要求外，你们认为还有哪些重要因素需要考虑，试给出新的分配方案或建议。
2.模型假设
根据题意，可以进行如下假设：
1．所有参加面试的考生在建模中不作区分，认为是完全一样的；
2．所有面试老师也认为是没有差别，完全一样的；
3．只考虑面试分组，不考虑时间安排。
4．制定分派方案时，只考虑尽量使老师交叉混合，而不考虑学生的主观要求。
3.符号约定
M        老师总数
N        学生总数
N2        遇到两位老师相同情况的学生人数
N3        遇到三位老师相同情况的学生人数
N敏        敏感学生的人数
N亏        吃亏学生的人数
N幸        幸运学生的人数
        第个学生如果分配给第位老师面试则此值为1，否则为0
        第位老师面试的学生人数
Imax        单独一位老师面试学生人数的最大值
R        评价每位老师面试人数均匀性的指标
T        两位老师共同面试人数的最大值的最小值
        公平率
所有老师之间相同的学生个数的均值
所有老师之间相同的学生个数的方差
4.模型建立和分析
4.1问题一
4.1.1分析与建模
    无论是最多只有一位老师相同还是两位老师相同，该问题的解决都可以看成满足一定的约束要求，使得在给定的学生数下，寻求最少的聘请老师数。因此，我们把问题抽象为一个规划模型来寻优。
（1）最多只有一位老师重复的情况
设，取值为1时表示第个学生分配给第位老师面试，取值为0时表示第个学生不分配给第位老师面试，满足问题要求的约束首先是每个学生面试组的成员数为4，并且使得任意两个学生的面试组最多只有一名老师重复。目标是使聘请老师数M最小，即
（4.1）
针对该模型，我们设计了寻优算法，采用Matlab编程实现。该算法的流程图如图1所示。
图1 寻优算法流程图
表1列出了部分数值，图2是该数值的可视化。
表1  任两位学生的“面试组”都没有两位老师相同时最少的老师数
学生人数
最少老师
人数
学生人数
最少老师
人数
学生人数
最少老师
人数
学生人数
最少老师
人数
1
4
6
11
16~17
16
24~27
20
2
7
7~9
12
18~19
17
28~30
21
3
9
10~13
13
20
18
31~32
22
4~5
10
14~15
15
21~23
19
33
23
图2任两位学生的“面试组”都没有两位老师相同时最少的老师数
（2）最多只有两位老师重复的情况
同（1）中的含义相同，（4.1）式中第一个约束仍然不变，只是使得任意两个学生的面试组最多只有两名老师重复。
（4.2）
表2列出了部分数值，图3是数值的可视化。
表2  任两位学生的“面试组”都没有三位老师相同时最少的老师数
学生人数
最少老师
人数
学生人数
最少老师
人数
学生人数
最少老师
人数
学生人数
最少老师
人数
1
4
20~26
11
141~143
17
310~358
23
2~3
6
27~41
12
144~165
18
359~404
24
4~7
7
42~55
13
166~195
19
8~14
8
面试名单
56~75
14
196~229
20
15~18
9
76~105
15
230~263
21
19
10
106~140
16
264~309
22
图3 任两位学生的“面试组”都没有三位老师相同时最少的老师数
4.1.2 结果分析
从图2、图3可以看出，随着学生人数增加，最少面试老师数是增多的；而且随着老师数增多，学生人数的变化率是加快的，这种趋势是比较符合直观经验的。但在图3数据中也发现
有个别不满足这种情况的点。对于原因还未到，有可能是算法精度的问题。并且每个最少面试老师数上，都有一个学生数的“持续期”。