学生面试问题

论文导读：本文主要讨论的是优化分配问题，利用排列组合知识建立模型、搜索求解得到分配方案。
关键词：优化分配

 

1 问题重述

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

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

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

Y3. 两个考生的“面试组”中有两位或三位老师相同的情形尽量的少；

Y4. 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。

请回答如下问题：

问题一：设考生数N已知，在满足Y2条件下，说明聘请老师数M至少分别应为多大，才能做到任两位学生的“面试组”都没有两位以及三位面试老师相同的情形。（相同人数为0－1）

问题二：请根据Y1～Y4的要求建立学生与面试老师之间合理的分配模型，并就N＝379，M＝24的情形给出具体的分配方案（每位老师面试哪些学生）及该方案满足Y1～Y4这些要求的情况。论文参考网。

问题三：假设面试老师中理科与文科的老师各占一半，并且要求每位学生接受两位文科与两位理科老师的面试，请在此假设下分别回答问题一与问题二。

2 符号说明

表1 变量含义一览表

变量	定义
	参加面试的学生人数
	参与面试的老师人数
	0－1变量，当等于1时表示第个学生被第个老师面试
	不同考生的面试组成员相同的人数
	0－1变量，当其值为1时表示第位老师都面试了第个同学
	任意两个考生的面试组成员中有两个相同的人数
	任意两个考生的面试组成员中有三个相同的人数
	任意两个老师面试同一个学生的人数
	表示第位老师面试学生的个数
	不同考生的面试组成员相同的人数
	任意两个考生的面试组成员中有两个相同的人数

3 问题一的求解

3.1 没有两位相同的情况

任两位考生的“面试组”成员没有两位老师相同，也就是说只有一位相同或全都不同，易知有一位相同老师的情况对应的老师总数M比全不相同的老师总数要少，所以这里在安排学生老师的对应方案时，要尽量使任两组都有一位老师相同，这样才能保证老师的数目最小。

首先，根据贪婪算法给出学生数目（N）为1～14时对应的老师数目（M），如下表所示：

表2 学生―老师对应情况

通过对表格中数据的分析可知：

一个老师M也可以对应多个学生N，学生数目为N时，至少需要老师M位，只需在M对应的多个学生数目中找出最大的一个N。即通过M来寻找N，也就是在N确定时得到M。

对M而言，任意选出4人组合成一个面试组的数目为：，在这些组合中调出两组进行比较，共有种，现进行如下分析，当两组进行比较时，如果有大于1个相同的老师，则认为此时对应的为0，如果有1个或全不相同则认为相应的为1。

这样就可以计算出所有满足任意两个面试组没有两个相同的组合数目；即学生数目：

【说明】式中N为考生人数，M为面试老师人数。

3.2 没有三位相同的情况

同一个M可对应多个考生，但 是考生数目N的大小不同。M一定时对应的考生数目中最大学生数为N1，当N1＝N时，对应的M即为所求。

4 问题二的求解

4.1 对四项要求的量化分析

4.1.1 Y1的要求

每位学生的面试组成员为4名，所以：

两个老师面试数目尽量相同：

4.1.2 Y2的要求

0－1变量，不同学生的面试组中有相同老师则，否则

由此就可以将任意两个不同学生的面试组中含有相同老师的个数得到，如下：

面试不同考生的“面试组”成员不能完全相同，于是：

4.1.3 Y3的要求

使这两方面的数目尽量少，在相同成员不同数目的组合时进行加权处理，根据对题目公平性的理解，当面试组中相同成员数目小时更为公平，所以令有两个成员的相同的项权值为0.4,三个成员相同的项权值为0.6。

4.1.4 Y4的要求

首先统计出任意两位老师面试同一位学生的数量，利用如下公式：

 1/3    1 2 3 下一页 尾页