1 问题重述

1 问题重述

高校自主招生是高考改革中的一项新生事务，现在仍处于探索阶段。学生面试问题理所当然的成为高校自主招生中考察考生综合素质的重要环节之一。现有某高校拟在全面衡量考生的高中学习成绩及综合表现后再采用专家面试的方式决定录取与否。该校在今年自主招生中，经过初选合格进入面试的考生有N 人，拟聘请老师M 人。其中每位学生需要分别接受4位老师（简称该学生的“面试组”）的单独面试。在面试时，各位老师独立地对考生提问并根据其回答问题的情况给出评分。由于这是一项主观性很强的评价工作，老师的专业可能不同，他们的提问内容、提问方式以及评分习惯也会有较大差异，因此面试同一位考生的“面试组” 的具体组成不同会对录取结果产生一定影响。同时为了保证面试工作的公平性，要求：

Y1. 每位老师面试的学生数量应尽量均衡；

Y2. 面试不同考生的“面试组”成员不能完全相同；

Y3. 两个考生的“面试组”中有两位或三位老师相同的情形尽量的少； Y4. 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。 需要解决如下问题：

问题1：当考生人数N 已知时，在满足条件：两位学生的“面试组”都没有两位以及三位面试老师相同的情形时，该校至少要聘请的老师数M 。

问题2：在满足条件Y2的要求下，当学生数N =379，聘请的教师数M =24时，建立学生与教师之间合理的分配模型，并给出具体的分配方案。

问题3：假设当面试老师中理科与文科的老师各占一半，而每位学生都分别要接受两位文科与两位理科老师面试的情况下重新分析问题1与问题2。

问题4：在解决以上问题的基础上，针对考生与面试老师之间分配的均匀性和面试公平性的关系，同时也是为了保证面试的公平性，提出一些合理化的意见及建议。

2 问题分析

高考自主招生考试是通过笔试成绩和面试成绩两方面的综合评定鉴定学生的录取情况的。因此面试的成绩不容忽视。确定合理的面试老师分配方案，保证使录取工作达到真正的公平合理。针对这个问题提出了一些公平性准则（Y1-- Y4）, 最终目的是合理分配老师。这是一个优化问题，所以我们用目标规划模型来解决这个问题。由于牵扯到很多个量的确定（M 个老师，N 个学生，分配方案的0-1矩阵是N ⨯M 阶的），考虑到选取一定有M

3模型假设

4.1假设考生人数N 有一个上限G 。

4.2分配方案一旦确定，都可以招聘到任何需要的老师，招聘不到的情况忽略不计。 4.3设对每位招聘来的老师都要给他安排面试工作，即∑x ij =0的情况是不存在的。

i =1N

4 问题1模型建立、求解及结果分析

5.1 问题1的模型分析：

在Y 2的前提下，参加面试的人数N 已知，要计算出满足任两位学生“面试组”都没有两位及三位面试老师相同的情况下符合情况的M 的最小值，只需将涉及到的条件转换成数学表达式作为目标规划的约束条件。

5.1.1由此可将条件Y 1~Y 4的条件转换成数学表达式:

Y 1：每位老师面试的学生数量应尽量均衡。即要取得min a i -a j ，i , j =1, 2 M . Y 2：面试不同考生的“面试组” 成员不能完全相同。即必须满足B i ≠B j ，

i , j =1, 2 N .

Y 3:要求两个考生的“面试组”中有两位或三位老师相同的情形尽量少。我们理解

的尽量少是在学生人数给定的前提下，先考虑任两个“面试组”中只有一个相同老师的情形，如果该情形能够面试完所有的学生，则不再考虑两组中有两个相同老师的情况；否则，就要继续考虑。只有当两组中有两个相同老师也不能满足面试人数时，才会考虑有三个相同老师。 那么第二个目标规划为：min αC 1+βC 2, ，正如上述的分析，要求三个相同的情况尽可能少，所以β〉α。

Y 4：被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。即，

min C ij 。

5.1.2 引进分配变量x ij 后的符号表示变化：

i 个学生⎧1第j 个老师面试第

其中x ij =⎨，i =1, 2, N ，j =1, 2, M 。

0第j 个老师没有面试第i 个学生⎩由此可知， ∑x ij =4，∑x ij =a i 。 （1）

j =1

i =1

M N

Y 1转换成 min ∑x ij -∑x kj ，j =1, 2, M 。 （2）

i =1

k =1

N N

因此任意两个学生i , j ，（i , j =1, 2, N ）选择k 老师的情况有三种，即全选，全

⎧1选法不相同

不选，其中一个选，即 x ik -x jk =⎨ （3）

⎩0选法相同那么，Y 2转化成 x ik -x jk >0.

考虑到要求面试老师没有两个相同的情况，那么最多只有一个选择相同，由（3）：

i ≠k =1j =1

∑∑x

N M

ij

-x kj ≥6

5.2建立模型：（满足不同情况的两个模型）

通过上述的建模准备工作，针对问题1可以建立两个单目标的规划模型：模型1.1（对任意两个学生的“面试组”中面试老师没有两个相同的模型）和模型1.2（对任意两个学生的“面试组”中面试老师没有三个相同的模型）。

min M =

4N

∑x

i =1

N

ij

⎧M

⎪∑x ij =4, i =1, 2, , N ⎪j =1⎪N

⎪∑x ij =a i >0 模型1.1 i =1⎪⎪

⎨x ik -x jk >0, i , j =1, 2, , N , k =1, 2, , M ⎪N M ⎪x ij -x kj ≥6∑⎪i ∑≠k =1j =1⎪

⎪x ij =0或1，i =1, 2, , N , j =1, 2, , M ⎪⎩

考虑到要求面试老师中没有三个相同的情况，那么最多只有两个选择相同，根据上述（3）

所示，将模型1.1中的最后一个约束条件改为：

min M =

4N

i ≠k =1j =1

∑∑x

N M

ij

-x kj ≥4，建立模型1.2.

∑x

i =1

M

ij

⎧M

⎪∑x ij =4, i =1, 2 , N ⎪j =1⎪N

模型1.2 s . t ⎪∑x ij =a i , j =1, 2 , M

⎪i =1⎪

⎨x ik -x jk >0, i , j =1, 2 , N , k =1, 2, , M ⎪N M ⎪x ij -x kj ≥4⎪∑∑i =1j =1⎪

⎪x ij =0或1，i =1, 2, , N , j =1, 2, , M ⎪⎩

5.3 问题1模型求解： 5.3.1方法：

针对问题1建立的目标规划模型1. 1, 1. 2同时也是一个0-1整数规划模型，涉及

的内容比较复杂通过常规的方法是不好求解的，因此我们提出了近似求解方法，即引用隐枚举法找到了变量x ij 取值0、1的最优组合，从而得到了较优的分配方案，取定一些特殊的N 值，例如N =6，7，8，9„24, 通过模型1.1和模型1.2利用此方法算出较优的M 值，计算的结果如表2所示。为了寻找出M 和N 之间的关系，我们将这些组数据进行拟合得到了M 和N 的函数关系。

5.3.2 拟合数据

对于有两个老师相同的情况，首先将得到的表格中的6-24的十九组数据进行拟合，程序见附录一的1.1。其中参加面试学生数N 看成是自变量x ，应聘的老师数M 看成变量y 。拟合图象如图1所示。

为了使残差相对较小，而且从图象上直观的看拟合的效果好一些，因此选取三次函数做为最后结果。

y (1) =P 4(1) +P 3(1) x +P 2(1) x 2+P 1(1) x 3

(4)

P 1

(1) (1) (1) (1)

=2. 7049e -007=-0. 00026336=0. 10592

P 2

P 3

P 4=7. 1768

从图1中看出在M =16, 17处的拟合效果不好，那么分段进行考虑。在M =16处

函数关系如下：

y 2=P 4(2) +P 3(2) x +P 2(2) x 2+P 1(2) x 3P 1(2) =9. 5192e -006P 2(2) =-0. 0026579P 3(2) =0. 26167P 4(2) =5. 4428

(5)

对后面第16-30组数据实现三次多项式拟合，可得到：函数关系和图3如下所示： y 3=P 4(3) +P 3(3) x +P 2(3) x 2+P 1(3) x 4, 其中(6)

P 1(3) =4. 2883e -008P 2(3) =-8. 6435e -005P 3(3) =0. 064984P 4(3) =9. 8379

利用第三列数据（最多只有一个老师相同的情况）实现对第6－24组数据的拟合，这时二次多项式拟合的效果较好。如图4所示。

图4

函数关系式如下：

y 4=P 3(4) +P 2(4) x +P 1(4) x 2

P P

(4) 1(4) 2

=-0. 0085046=0. 77452

(7)

P 3(4) =6. 1494

综上所述，问题1的结果是：

任意两个学生面试组中没有三位老师相同的情形：

⎧P 4(2) +P 3(2) N +P 2(2) N 2+P 1(2) N 3, N ∈[6, 140]M =⎨(3) （8） (3) (3) 2(3) 4

]⎩P 4+P 3N +P 2N +P 1N N ∈[140, 2000

任意两个学生面试组中没有两位老师相同的情形：

(4) 2

M =P 3(4) +P 2(4) N +P 1N （9）

5.4. 结果分析：

利用回归分析法得到四个拟合函数的残差表（表3）

5问题2模型建立、求解及结果分析

6.1问题2的分析：

问题2要求我们在问题1的基础上，考虑满足Y1-Y4的条件下建立学生与面试老师之间合理的分配模型并对M=24,N=379的情况给出具体的分配方案。

这里要比问题1多考虑三个条件Y1,Y3,Y4。每位老师面试的学生数量应尽量均衡和被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。这就在建立的模型1.1的基础上增加了更多的目标和约束条件，因此可以将模型一进行改进，得到一个多目标，多个约束条件的目标规划问题。根据这个模型确立所考虑的情况，可以对N =379, M =24的具体情况利用隐枚举和割平面的方法找到一个分配的最佳方案。 6.2建立模型:

因此，由上述的三个目标（Y 1, Y 3, Y 4）和一个约束（Y 2）可以得到一个多目标规划模型。（模型2.1）

min ∑X ij -∑X kj i , k =1, 2, M

j =1

j =1

N

N

min (αC 1+βC 2) (β α)min A i A j =a ij

M

⎧ ⎪∑x ij =4, i =1, 2 N 模型2.1 ⎪j =1N ⎪⎪x ≤N s . t ⎨∑ij

⎪i =1

⎪x ik -x jk >0 k =1, 2 M 且i , j =1, 2, N ⎪⎪⎩x ij =0或1

6.3建立模型：

在模型2.1的基础上将多目标规划模型转化为单目标规划模型2.2。

，

min [P 1(Y 1)+P 2(Y 2)+P 3(Y 3)]

⎧M

⎪∑x ij =4, i =1, 2 N ⎪j =1N

⎪ 模型2.2 ⎪x ≤N

s . t ⎨∑ij

⎪i =1

⎪x ik -x jk >0 k =1, 2 M 且i , j =1, 2, N ⎪⎪⎩x ij =0或1

6.5结果分析：

对于我们给出的表4的N =379, M =24的具体分配方案是基本符合条件Y1-Y4 6.5.1 对条件Y 1而言：

24个老师中，前20个老师都面试63次，只有后四个老师面试64次，这就符合了第一个条件保证每位老师面试的学生数量尽量均衡的要求。 6.5.2 对条件Y 2而言：

在建立四位数组时就已经把三个和四个相同的情况删除了，因此这一点是完全符合条件要求的。 6.5.3 对条件Y 3而言： 如果任意两个学生的“面试组”中只有一位老师不同，那么24位老师只能给35位学生面试。所以我们就在让有两个老师相同的情况下保证有三个老师相同的情况尽可能的少，根据6.5.1的分析，说明这个结果也符合这个条件。 6.5.2 对条件Y 4而言：

根据生成四位数组的方法可知这一点也是基本满足的。 因此，给出的具体的分配方案是比较合理的分配方案。

6 问题3的模型建立与求解

6.1问题3分析：

在上面两问的基础上，又要考虑到文理分科的情况:理科与文科的老师各占一半，故我们假设面试老师总数为偶数；同时还要求每位学生接受两位文科和两位理科老师的面试，所以我们假设奇数为文科老师，偶数为理科老师。也就是将所有老师按编号分为奇数组和偶数组两组，面试组中的编号排列要符合两奇两偶的情况。面试学生时，只需分别从两组中任取两位老师组合即可。

对于问题1，我们需要在模型1.1的基础上加上老师编号要符合两奇两偶的条件，将其转化为数学表达式，即

∑(-1)

j =1

M

j -1

x ij =0

6.2模型建立和求解：（分别考虑问题1和问题2的情况） 7.2.1重新考虑问题1：

对于模型1.1，任意两个学生的“面试组”中面试老师没有两个相同的单目标

规划模型改为：

min M =

4N

∑x

i =1

N

ij

⎧M

⎪∑x ij =4, i =1, 2, , N ⎪j =1⎪N

⎪∑x ij =a i >0⎪i =1 模型3.1 ⎪x -x >0, i , j =1, 2, , N , k =1, 2, , M

jk ⎪ik

⎨N M ⎪x ij -x kj ≥6∑⎪i ∑≠k =1j =1⎪

⎪x ij =0或1，i =1, 2, , N , j =1, 2, , M ⎪M

⎪(-1) j -1x =0∑ij ⎪j =1⎩

对于模型1.2，对任意两个学生的“面试组”中面试老师没有三个相同的模型

相应的改为：

min M =

4N

∑x

i =1

M

ij

⎧M

⎪∑x ij =4, i =1, 2 , N ⎪j =1⎪N

⎪∑x ij =a i , j =1, 2 , M ⎪i =1 模型3.2 ⎪x -x >0, i , j =1, 2 , N , k =1, 2, , M

jk ⎪ik

⎨N M ⎪x ij -x kj ≥4⎪∑∑i =1j =1⎪

⎪x ij =0或1，i =1, 2, , N , j =1, 2, , M ⎪M

⎪(-1) j -1x =0∑ij ⎪j =1⎩

这两个单目标规划模型只是在问题一的基础上多加了一个约束条件，我们仍然可以

用解决问题一的方法来解决该问题，这里就不再赘述了。 6.2.2重新考虑问题2： 对于问题2，我们同样需在原来解决问题方案的基础上，再加上老师编号要符合两奇两偶的条件。经过统计，379组面试组里共有39组全奇数组，39组全偶数组。也就是说有39个学生的面试组中全是文科老师，而那39个学生的面试组中则全是理科老师，这就不符合题目中的要求。此时，我们需要将其调整为两奇两偶的形式。

考虑到这两组分别是全奇全偶的情况，我们就将这39组全奇数组与39组全偶数组两两重组，以得到两奇两偶的形式。这时，我们发现任两个面试组中三个老师相同的情

况增加了许多；经过计算共有308对两两出现三个老师相同，具体分配方案见表4。

由于该模型考虑问题时，优先满足任两个面试组中只有一个老师相同的情况；在面试不够学生的时候，才考虑有两个老师相同的情况；同理，当两个老师相同的组合也不够时，才考虑三个老师相同的情况。所以，我们有理由认为该方案完全适合组织者提出的那四个要求。

11