单目标和多目标规划模型求解学生面式问题摘要
随着高校自主招生规模的扩大，学生面试的公平性成为人们关注的焦点。本文通过建立单目标和多目标规划模型，利用MATLAB软件和搜索算法，进行了有关招生面试问题的研究。
对于问题一，为表示面试学生和老师之间的相应关系，引入0－1变量
x，
ij 建立以老师数M最小为目标的0－1规划模型。利用搜索算法，求解出考生数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至少分别应为多大，才能做到任意两位学生的“面试组”都没有两位以及三位面试老师相同的情形。
问题二：请根据Y1～Y4的要求建立学生与面试老师之间合理的分配模型，并就N＝379，M＝24的情形给出具体的分配方案（每位老师面试哪些学生）
及该方案满足Y1～Y4这些要求的情况。
问题三：假设面试老师中理科与文科的老师各占一半，并且要求每位学生接受两位文科与两位理科老师的面试，请在此假设下分别回答问题一与问题二。问题四：请讨论考生与面试老师之间分配的均匀性和面试公平性的关系。为了保证面试的公平性，除了组织者提出的要求外，你们认为还有哪些重要因素需要考虑，试给出新的分配方案或建议。
2 基本假设
1、每位考生分别接受“面试组”几位老师的单独面试，小组面试结束前彼此完全独立；
2、“面试组”老师的专业不同，提问的问题、提问的方式及评分习惯会有差异；
3、面试部门的分配方案实施没有困难；
4、考生和老师绝对服从组织者的统一安排；
5、文科和理科老师各占一半时，第1到第M/2个老师为文科老师，第M/2＋1到第M个老师为理科老师；
6、正副教授在文理科老师中平均分配。
3 符号说明
N：需要面试的学生个数；
M：需要聘请的老师个数；
n ：任意两位老师面试的两个学生集合中最多可能出现的相同学生人数 ij x ：ij 1,i j = 1,2,...,,1,2,..., x i N j M ⎧==⎨⎩第个学生被第个老师面试
0,第i 个学生没有被第j 个老师面试
4 模型的建立和求解
4.1 问题一 4.1.1 问题分析
设考生数N 已知，在满足Y2条件下，说明聘请老师数M 至少分别应为多大，才能做到任意两位学生的“面试组”都没有两位以及三位面试老师相同的情形。
要解决这个问题，关键是怎样表示出面试的学生和老师之间的对应关系，为了表示这种对应关系，我们引入下面的0－1变量：
ij 1,i j x = 1,2,...,,1,2,..., i N j M ⎧==⎨⎩第个学生被第个老师面试0,第i 个学生没有被第j 个老师面试
在此基础上就可以根据不同的约束条件，以老师数M 最小为目标建立0－1规划模型来求解。
4.1.2 0－1规划模型的建立
模型一：没有两位面试老师相同的规划模型
根据对问题一的分析可知，可以建立下面的0－1规划模型：
考生数N 已知，满足Y2、以及任意两位学生的“面试组”都没有两位相同
老师的条件下，聘请老师M 最小为模型目标。
约束条件：
○1 每位学生的面试老师有四个，对于第i 个学生来说1M
ij j x =∑表示面试老师的
个数，需要满足1
4M
ij j x ==∑。
○2 任意两个学生的“面试组”都没有两位面试老师相同。如果第i 和第k 个学生都被第j 个老师面试，那么ij x 和kj x 的值均为1， 则0ij kj x x -=；如果第i 个学生被第j 个老师面试，而第k 个学生不被第j 个老师面试，那么ij x 取值为1 ，
kj x 取值为0，则1ij kj x x -=。同样，如果第i 个学生不被第j 个老师面试，而第k
个学生被第j 个老师面试，也有1ij kj x x -=。没有两位面试老师相同，也就是只能有1或者0位老师相同，最多只能有一组ij x 和kj x 全取1。所以对于任意两个学生来说，1
M ij kj j x x =-∑必须满足：1
6M
ij kj j x x =-≥∑(,1,2,...,,)i k N i k =≠。
○3 不同考生的“面试组”成员不能完全相同。当任意两个学生没有两位相同面试老师的时候，考生“面试组”的成员肯定不完全相同。该约束条件没有约束条件2强，所以只需满足约束条件2即可。
○4 0 1ij x =或，即我们定义的0－1变量。
由此可以得到，在考生数N 已知的情况下，任意两位学生都没有两位相同的面试老师的0－1规划模型如下：
目标函数：min M
