您好,欢迎来到爱站旅游。
搜索
您的当前位置:首页面试问题论文.doc

面试问题论文.doc

来源:爱站旅游
承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。

我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。

我们参赛选择的题号是(从A/B/C/D中选择一项填写): E 我们的参赛报名号为(如果赛区设置报名号的话):

所属学院(请填写完整的全名): 自动化学院 参赛队员 (打印并签名) :1. 祁冰露

2. 刘健滨

3. 李玉杰

日期:2009 年 8 月 21 日

评阅编号(教师评阅时填写):

学生面试中的教师分组问题探讨

摘要

本文研究了在保证面试工作公平性的情况下,使用计算机搜索、逐步修正等方法,解决了在N一定的条件下,所需教师数量的最小值M,并建立0-1整数规划模型和多目标优化模型,应用贪婪法求解模型给出具体的分组情况,最后对模型进行了评价并提出改进方法。

问题一:要解决在给定条件下,求出应聘教师最小值问题。只要求出教师M与面试学生N的关系表达式即可。文中针对题目要求及目标建立了单目标规划模型。为了确定M和N 的关系,我们将教师任意四人分成一组,共有C4M种不同组合,各组排列按照第一个老师>第二个老师>第三个老师>第四个老师的优先顺序进行升序或降序排列,再利用计算机从这组排列中进行搜索比较,如果两组中相同的老师数超过我们规定的最大值,则将后面的一组删除,如此循环下去,直到搜索结束。另外,不断改变M(最小取4)的值,即可求出对应的最大面试学生数N。但是,教师编码排序规则的不同,会直接影响输出值N,所以,文中设计四种教师编码排序规则,分别编程求解出四组不同的数据,根据四组数据对不满足条件的点进行修正,得到最优数据组。最后,分别对最优数据组进行高斯函数和多项式拟和,选择一种误差较小的拟和方案。最后得到满足“没有两个教师相同”和“没有三个教师相同”要求下M与N的关系表达式分别为:

N23.63e((M38.472)20.5M417.82)232.65.701e((M4.72)4.186M1552)125.78.876e((M15.552)11.28

。 N23.69e10.95e5.91e问题二:要求在满足一定条件下,建立学生与面试老师直接合理的分配模型,给出具体分配方案,并对方案进行合理性分析。文中建立了教师与学生组合分配的多目标规划模型。求解模型时,通过设置约束(面试组)的优先级别,确定优化目标,并利用贪婪算法对模型求解,最后给出M与N的“面试组”方案(详见附表1)。

问题三:要做的是在新加条件(面试老师文理各半;每位学生接受两位文科和两位理科教师的面试)下,解决问题一和问题二。本问在问题一模型的基础上,对约束条件稍加修改,得到新的0-1整数规划模型。解决问题二,也是在问题二的结论上进行修改。将问题进一步简化,即从已分配好的“面试组”中挑选出满足新条件的组合(两奇两偶),对余下组合,重新分配,这样就大大减少了计算量。

最后,本文在面试公平性的条件下给出题目以外的合理建议,并对模型进行了客观评价。

[关键字] 计算机搜索;数值拟合;0-1整数规划;贪婪法.

1

M45.492)46.38

一. 问题的重述

自国家教育局实施高校自主招生以来,各地高校陆续采用自主招生的

模式进行录取新生。自主招生还处于探索阶段,很多方面还不够完善,正在进一步发展。考生通过考试等综合素质的考核后,还要经过教师面试,决定是否录取,这样就会出现考生与面试老师之间分配的均匀性和面试公平性问题。

某高校采用通过专家面试的方式进行自主招生, 经过初选合格进入面试的考生有N人,拟聘请老师M人进行面试。每位学生要分别接收“面试组”每位老师的单独面试,每个面试组由4名老师组成,各位老师对考生进行提问并根据学生回答问题的情况给予评分。为了保证面试工作的公平性,组织者提出如下要求:

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

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

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

Y4:任意两位老师面试的两个学生集合出现相同学生的人数尽量的少。 本文要解决下面四个问题:

问题一:设考生数N已知,要求在满足条件二的情况下,说明聘请老师数M至少分别应为多大,才能做到任两位学生的“面试组”都没有两位以及三位面试老师相同的情形。

问题二:根据条件一至条件四的要求建立学生与面试老师直接合理的分配模型,并就N=379,M=24的情形给出每位老师面试学生名单的具体分配方案,并分析该方案满足条件一至条件四的情况

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

问题四:讨论考生与面试老师之间分配的均匀性和面试公平性的关系。为了保证面试的公平性,除了组织者提出的要求外,还有哪些因素需要考虑进来,并给出新的分配方案或建议。

二. 模型的假设

1.

2. 3. 4.

假设每位学生分别单独接受四位老师的面试; 假设面试时老师之间是进行互不影响; 假设每位考生只有一次面试的机会;

4假设假设考生的人数为N,老师的人数为M,NCM; 5. 假设所有老师和学生都严格遵守分配方案; 6. 假设假设每个老师对待每个学生都是公正的。

三. 符号说明

符号 M N

含义 表示参加面试的老师人数 表示参加面试的学生人数 2

备注

xij Wj 为0-1变量,当xij=1时表示第j个老师面试第i个学生时, 表示被第j个老师面试的学生的个数 为0-1变量,当qi,j,k1时,表示第i个和第j个学生都被第k个老师面试 为0-1变量,当pi,j,k1时,表示老师j、k面模型一 问题二 问题二 问题二 问题四 问题四 问题四 问题四 问题四 问题一 问题一 问题三 问题三 qi,j,k pi,j,k Qij 试都学生i 学生i和j的面试组中含有相同老师的个数 老师j、k面试相同学生的个数 为0-1变量,当Tij1时,表示学生i和j的面试Pjk Tij Hij F总 F1 F2 w1 w2 e1 e2 A B 组中含有相同老师的个数分别为2 为0-1变量,当Hij1时,表示学生i和j的面试组中含有相同老师的个数分别为3 考生面试的总成绩 考生面试的理科成绩 考生面试的文科成绩 考生理科成绩占的权重 考生文科成绩占的权重 非线性拟和结果平均误差 非线性拟和结果平均误差 全部为奇数的编码组合 全部为偶数的编码组合 四. 问题分析

4.1问题题干的分析

面试在自主招生中扮演着越来越重要的角色,考生面试的成绩不容忽

视。因此如何确定面试专家的分配方案,使录取工作真正公平合理的进行,是各大高校积极考虑的问题。

本文要解决的是在公平、均衡的情况下对面试老师进行合理分配。这是一个优化问题,所以我们考虑到用目标规划模型来解决问题一和问题二,问题三可以根据问题一二稍加修改即可以解决。规划模型中的目标函数和约束条件,我们可以根据将题目中的约束条件、变量和求解目标转化为数学表达式,这样就构成了目标规划模型。最后要做的是求解模型,可以考虑用遗传算法、极大极小法、理想点法等进行模型求解。 4.2问题一的分析

问题一要求的是在学生数N已知,且满足面试不同考生的“面试组”

3

成员不能完全相同的情况下,计算聘请老师数M至少分别应为多大,才能做到任两位学生的“面试组”都没有两位以及三位面试老师相同的情形。问题一相对较简单,是一个单目标规划问题。只要把题目要求的决策变量和约束条件转化成数学表达式,就可以得到目标规划模型的约束条件和目标函数。由于教师数M、学生数N均未知,因此无法求出最少教师数目或最多学生数目。因此考虑应用枚举法(取部分数据),列出M值求出对应的最优学生数N,此步应用计算机编程实现。最后对所得数据进行函数拟合,即可得到面试学生数N与所需最少教师M的函数表达式。 4.3问题二的分析

问题二与问题一类似,只是多出了条件Y1和Y4,是一个多目标最优化问题。条件Y1(每位老师面试的学生数量应尽量均衡)作为模型二的约束条件;条件Y4(任意两位老师面试的两个学生集合出现相同学生的人数尽量的少)让求的是尽量最优问题,因此可以作为目标函数。我们可以在模型一的基础上,增加一个约束条件,增加一个目标,这样就建立一个新的多目标优化模型。

我们把“面试组”分为四类,分别为:没有一个教师相同的情形;有一个教师相同;有两个教师相同;有三个教师相同,且优先级逐次降低。求解模型时,我们采用贪婪法思想编程,按照四种“面试组”的优先级顺序,分别从C4M中教师组合中,搜索出面试学生数目的“面试组”。至此,对M=24,N=379进行合理公平的分配基本完成。 4.4问题三的分析

问题三和问题二相比,增加了新的约束条件“文理科教师各占一半”和“每位学生分别接受两位文科两位理科教师的面试”。我们假设1、3……M1的编码代表文科教师,2、4、6……M的编码代表理科教师(M为偶数的前提下)。

新的条件下解决问题一:只是在模型中加入“文理科教师各占一半”和“每位学生分别接受两位文科两位理科教师的面试”的约束条件,其余做法和模型一完全相同。

新条件下解决问题二:将问题转化成数学语言,就是我们所求出的所有378的教师组合中,必须含有两个奇数和两个偶数。本问可以直接在模型二结果的基础上求解。第一步,挑选出不符合“两奇、两偶”的组合;第二步,将不符合条件的组合相互之间重新安排分配组合,这样就组成378组“最多有两个教师相同”的分配方案;第三步,第379位同学的“面试组”可以从24位教师中任选4位,这样就会出现5为同学的“面试组”有“三个教师相同”的情形。最后对新的分配方案进行条件Y1~Y4的合理性分析。

4.5问题四的分析

借鉴问题1~3的求解过程及结果,针对面试面试均匀性与公平性的关系,给出几点可行建议,以避免出现面试过程不公平现象的产生。

五. 模型的建立和求解

4

5.1 问题1模型的建立及其求解

本问题解决的是满足一定约束条件要求,计算在给出一定的学生人数下,所需要教师的最少人数。我们把这个实际问题抽象为目标规划模型的数学问题来求解。

根据实际情况分析,一般面试学生的个数要远大于教师的个数。因为教师人数较少,容易进行分组(即按照约束条件将教师每四人分成一组),满足约束条件的情况下,所能组合的最大组数目即可面试学生的最大人数。因此,我们改变优化变量,当教师数目M一定的情况下最多可面试的学生个数,即求max N。

5.1.2没有两位老师相同的情形 5.1.2.1模型1.1的建立

(1)设xij代表第j个老师面试第i学生,xij0表示第j个老师不面试第i个学生,xij1表示第j个老师面试第i个学生,用数学语言表达即:

1,第j个老师面试第i个学生(xij为0—1变量)。 xij0,第j个老师不面试第i个学生(2)每个学生只能接受四名老师面试,转化成数学表达式为:

xk1Mik4M(i1,2,N,。)

(3)任意两位学生的“面试组”不能有两个老师相同的情形,转化为如下数学表达式:xikxjk1k1k表示第k个老(ij;i,j1,2,,N,其中)师,xik、xjk是0—1变量。

通过以上3步的模型准备,针对“没有两个老师相同的情形”可建立

如下单目标规划模型1.1:

maxN(1)M(2)xikxjk1(ij;i,j1,2,,N)k1M st.xik4(i1,2,,N)(3)k1xik,xjk0或1(是0-1变量)(4)5.1.2.2模型1.1的求解

由于M是未知数,所以没有办法使用优化算法求出具体的N值,这里我们采用数值模拟的方法,通过列举一定的M值,求出相应的最优的N值,然后通过曲线拟合的方法求出M和N的近似表达式,从而求出考生数为N时,至少需要聘请的老师数M。

列举M值,求相应的最优的N值,针对此模型我们设计了寻优算法,此步可以通过Matlab编程实现,程序的算法由以下步骤实现:

4Step1:首先对M位教师每四人一组进行组合,求出所有组合项为CM,

把所有项按递增方式排列成序列S0;

5

Stsp2:从S0第一项开始,逐次扫描后面所有项,如果后面项同第一项有两个或超过数字相同的就将其删除,这样形成了一个新的序列S1;

Step3:从S1的第二项开始,逐次扫描后面所有项,如果后面项同第二项有两个或超过两个数字相同的就将其删除,这样形成了一个新的序列S2,然后从S2的第三项开始,逐次扫描后面所有项,如果后面项同第三项有超过两个数字相同的就将其删除,这样形成了一个新的序列S3,依次类推,直到搜索完成。

注:考虑到问题二有让求解24位教师的面试分配情况,在此,我们只列举出4——24位教师,所能面试的最大学生数。将24位教师分别编号为1、2、3………24;学生分别编号为1、2、3………N。

通过Matlab软件编程实现(见附录程序1),所得数据如表1:

表1 不能有两个教师相同的情况 5 6 7 8 9 10 11 12 13 14 教师(M) 4 1 1 2 2 3 3 6 9 13 11 学生(N) 1 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 13 15 17 20 21 24 26 30 33 35 从表1得到的数据看,当教师从13位增加到14时,所能面试的学生的最大人数不增加,反而变小了(本文将这种数称为“特殊数”)。这说明算法陷入局部最优,即不能按照表1数据进行教师数M与学生数N的数值拟和,局部最优拟和出的结果会产生很大的残差,致使拟和结果误差较大。因此我们将表1数据进行修正,即将14个教师所能面试的最大学生数改为13个教师所能面试的学生数13。

我们知道,当教师编号按照不同规则排序,列举出的M值对应的最大N会不同。所以,本文为得到最优结果或使计算结果逼近最优值,利用Matlab编程分别求出教师编号按照不同规则排序情况下,一定数量教师M对应能面试的最多学生数N值。然后对每组数据都按照上述方法进行修正,最后可以得到一组最优值,即每一个M值,对应能得到真实的最大N值。

四种教师编码排序规则如下:

C1:第一个老师编号递增,第二个老师编号递增 ,第三个老师编号递增,第四个老师编号递增;

C2:第一个老师编号递增,第二个老师编号递增 ,第三个老师编号递增,第四个老师编号递减;

C3:第一个老师编号递增,第二个老师编号递增 ,第三个老师编号递减,第四个老师编号递减;

C4:第一个老师编号递增,第二个老师编号递减 ,第三个老师编号递减,第四个老师编号递减;

通过Matlab软件编程(见附录程序1),得到四组数据分别如下: 按C1规则: 教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 1 2 2 3 3 6 9 13 11 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 13 15 17 20 21 24 26 30 33 35 按C2规则:

6

教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 1 2 2 3 3 6 9 13 12 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 12 16 17 20 22 23 29 30 35 38 按C3规则: 教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 1 2 2 3 3 6 9 13 13 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 14 16 18 20 23 25 27 30 31 36 按C4规则: 教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 1 2 2 3 3 6 9 13 13 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 13 14 14 15 15 20 23 25 25 25 将以上四个表格中的“特殊点”M对应的N值,全部修正为第M-1个数对应的N值,最后得到一组修正后的最优结果见下表: 教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 1 2 2 3 3 6 9 13 13 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 14 16 18 20 23 25 29 30 35 38 分析上表得到对应的学生数与所需老师的最少数量的数据如下表2: 表2 “没有两个老师相同”已知N对应的最小M表 M 4 7 9 11 12 13 14 15 16 N 1 2 3 6 9 13 13 14 16 M 17 18 19 20 21 22 23 24 N 18 20 23 25 29 30 35 38 表2中显示,24位教师可以面试的最多学生数为38人;而未修正前的表1显示24位教师能面试学生的最大人数为35人。由此可见,修正后的数据更逼近最优解或者即为最优解。

针对表2数据,为了用Matlab编程,进行曲线拟合,为了拟合结果更加准确,我们采用两种方式拟合。

1) 高斯函数拟和

用Matlab编程,采用高斯函数逼近,拟合所得图形如下图1所示:

7

图1 “没有两个老师相同”情形下拟合图

通过运行结果得到的参数,列出教师数M和面试最大面试学生数N的函数表达式:

N23.63e5.701e8.876e (1) 2) 多项式拟和

直接用polyfit函数对数据进行5次拟合时,所得图形如下图2:

(M38.472)20.5(M4.72)4.186(M15.552)11.28

图2 “没有两个老师相同”情形下拟合图

得到的函数表达式为:

f(x)0.00048x0.01807x20.30479x32.74139x42.25378x5 (2)

5.1.2.3结果和误差分析

根据公式(1)求出M拟合值,并与原始值做比较,结果见下表3:

表3 非线性拟和误差分析表 原始数 4 7 9 11 12 13 15 16 拟合数 4.91 6.63 8.40 11.58 11.51 13.62 14.44 15.97 误差 0.91 0.37 0.6 0.58 0.49 0.62 0.56 0.03 原始数 17 18 19 20 21 22 23 24 拟合数 17.19 18.09 19.11 19.74 误差 0.19 0.09 0.11 0.26

8

求出表3中误差值的平均误差e10.2508。

根据公式(2)求出M拟合值,并与原始值做比较,结果见下表4:

表4 线性拟和误差分析表 原始数 4 7 9 11 12 13 15 16 拟合数 4.71 6.65 8.18 11.05 12.53 114.08 14.51 15.47 误差 0.71 0.35 0.82 0.05 0.53 1.08 0.49 0.53 原始数 17 18 19 20 21 22 23 24 拟合数 16. 17.68 19.32 20.26 21.52 21.71 22.58 24.20 误差 0.46 0.32 0.32 0.26 0.52 0.29 0.42 0.20 求出表4中误差值的平均误差e20.3063。 由此得出,第一种线型拟合的得出的结果误差要小,拟合的值更接近真实值,所以采用第一种方案。即M一定时,可面试的最大学生人数N与M的关系表达式为:

N23.63e5.701e8.876e (3) 5.1.3没有三位老师相同的情形

任两位学生的“面试组”都没有三位面试老师相同的情形,设计模型步骤和算法基本与模型.1.1(见5.1.2)相同。只有上文5.1.2中第三小点:任意两位学生的“面试组”不能有三位老师相同的情形,更改为如下数学

(M38.472)20.5(M4.72)4.186(M15.552)11.28表达式:xikxjk2k1Mk表示第k个老师,xik、(ij;i,j1,2,,N,其中)xjk是0—1变量。

同理可建立单目标规划模型1.2:

maxN

M(ij;i,j1,2,,N)xikxjk2k1Mst.xik4(i1,2,,N)

k1xik,xjk0或1(是0-1变量)设计寻优算法,利用Matlab编程(程序及运行结果见附录程序2),运行结果所得数据如表5:

表5 不能有三个教师相同的情况 5 6 7 8 9 10 11 12 13 14 教师(M) 4 1 3 7 14 14 18 26 39 55 77 学生(N) 1 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 105 140 140 148 1 1 221 263 315 378 同理5.1.2,针对“不能有三个教师相同的情形”,我们也不能直接使用表2中一次得出的数据拟合。因为,所得数据没有对不合理的数进行修正,也使结果陷入局部最优,最终导致拟和结果与实际相差太大的后果。

根据“没有两个教师相同的情形”中的四个教师编码规则,使用Matlab编程计算出如下四组结果:

按C1规则:

9

教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 3 7 14 14 18 26 39 55 77 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 105 140 140 148 1 1 221 263 315 378 按C2规则: 教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 3 7 14 15 21 30 39 55 71 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 95 140 140 163 195 229 272 324 376 424 按C3规则: 教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 3 7 14 14 18 30 39 55 77 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 105 140 140 148 177 1 244 295 328 378 按C4规则: 教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 3 7 14 14 20 29 40 72 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 96 140 138 163 190 220 257 296 331 384 将以上四个表格中的“特殊点”M对应的N值,全部修正为第M-1个数对应的N值,最后得到一组修正后的最优结果见下表: 教师(M) 4 5 6 7 8 9 10 11 12 13 14 学生(N) 1 1 3 7 14 15 21 30 40 55 77 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 105 140 140 163 195 229 272 324 376 424 分析上表得到对应的学生数与所需老师的最少数量的数据如下表6: 表6 “没有三个老师相同”已知N对应的最小M表 M 4 6 7 8 9 10 11 12 13 14 N 1 3 7 14 15 21 30 40 55 77 M 15 16 17 18 19 20 21 22 23 24 N 105 140 140 163 195 229 272 324 376 424 对比表6和表5:表3显示,24位教师可以面试的最多学生数为424人;而未修正前的表2显示24位教师能面试学生的最大人数为378人。教师人数越大时,所能面试的学生最大学生人数相差越大。因此,修正后的数据拟和出的数值表达式更能真实的反映教师数M和可面试的最大学生数N的关系。

5.1.2已经证明,采用高斯函数拟合,比采用多项式拟合得出的结果更准确,因此,对“没有三个教师相同的情形”,我们直接采用高斯函数进行拟合。通过对表4中的数据进行数据拟和,拟合所得图形如下图3所示:

10

图3 “没有三个老师相同”情形下的拟合图

由图3也可以看到,曲线拟合效果比较好,基本上所有的点都在曲线的附近浮动。对应的M与N的表达式为:

N23.69e(M417.82)232.6

10.95e(M1552)125.75.91e(M45.492)46.38 (4)

5.2问题二模型的建立及求解

本问题是要求根据Y1~Y4的要求,建立学生与面试老师直接合理的分配模型。相当于在问题一的基础上增加了约束和目标,因此问题二要解决的是一个多目标规划问题。

首先对题目给出的四个要求进行量化分析,转化为多目标规划的四个约束条件;再将问题2的目标转化为数学表达式,得到目标函数,最后进行规划分配得到到一个多目标规划求最优的模型2。 5.2.1贪婪法思想简介

贪心方法是一种改进了的分级处理方法。它首先根据题意,选取一种量度标准。然后按这种量度标准对这n个输入排序,并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法。

由上述定义知,选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。

本问中也建立的优先级标准,详细见5.2.4程序算法编写步骤。 5.2.2将题目要求量化处理

1、对于Y1的要求:要使每位老师面试的学生数量应尽量均衡

1,第j个老师面试第i个学生设xij,其中i=(1,2,…,N), j=

0,第j个老师不面试第i个学生(1,2,…,M)

则第j个老师面试学生的个数为:

11

Wjxiji1N(i1,2,,N;j1,2,M)

要使老师面试的学生数量应尽量均衡,由于有N个学生和M个老师,

4N则平均每个老师面试学生的个数为W,代入N379,M24, 求得

MW63.1667,我们可以假设WiWj1

2、对于Y2的要求:面试不同考生的“面试组”成员不能完全相同

通过分析可以求出任意两位学生被同一个老师面试为: xikxjk(ij且i,j1,2,,N;k1,2,,M),

qi,j,k式中,xik,xjk均为0—1变量,所以:

1,第i和第j个学生都被第k个老师面试 qi,j,k0,第i和第j个学生不都被第k个老师面试由此得到任意两个学生i和j的面试组中含有相同老师的个数为Qij,

Qijqi,j,kk1M(ij且i,j1,2,N;k1,2,M)

由于面试不同考生的“面试组”成员不能完全相同,则:

Qij4

3、对于Y3的要求: 两个考生的“面试组”中有两位或三位老师相同的情形尽量的少

通过分析得到:

1,Qij2Tij,ij且i,j1,2,N

0,其它1,Qij3Hij,ij且i,j1,2,N

0,其它式中Tij和Hij分别表示任意两个学生i和j的面试组中含有相同老师的个数分别为2和3的情况。

要使这两种情况数目尽量少,应当对含有相同老师的不同组合进行加权处理,由题目公平性的理解,当面试组中含有相同老师的数目越小是,更显公平性,所以,就是先考虑使两个老师相同的数目少,在考虑三个老师相同的数目少。用数学语言表示为求:

minZ1TijHiji1ji1i1ji1N1NN1N()

4、对于Y4的要求: 任意两位老师面试的两个学生集合出现相同学生的人数尽量的少

设pxijxik表示任意两个老师j、k面试学生i的情况,由于xij和xik为0—1变量,则:

1,j,k两个老师都面试学生i pi,j,k0,j,k两个老师不都面试学生i所以,任意两个老师j、k都面试学生相同的个数为:

12

Pjkpi,j,k

i1n根据题目意思,所以有:

minZ2M1k1jk1PMjk

5.2.3模型2的建立

根据5.2.1模型准备,以任意两个学生的面试组中有两个老师或三个老师相同的情况尽量少、任意两个老师面试学生的集合出现相同学生尽量少为目标,在满足约束条件下,可以建立整数规划模型如下:

minZ1TijHij

i1ji1i1ji1N1NN1Nmins..tZ2M1k1jk1PMjk

WiWj1xj1Mij4

Qij4Wjxiji1Nxij为01变量模型解释:

1) 目标1:表示两个考生的“面试组”中有两位或三位老师相同的情

形尽量的少;

2) 目标2:表示任意两位老师面试的两个学生集合出现相同学生的人

数尽量的少;

3) 约束1:表示每位老师面试的学生数量应尽量的均衡; 4) 约束2:每位学生只能接受四位教师的面试;

5) 约束3:表示面试不同考生的“面试组”成员不能完全相同; 6) 约束4:代表第j个教师面试学生的总数;

7) 约束5:代表第j个教师面试第i个学生的0-1变量。 5.2.4 求解当N=379,M=24的分配方案 1、设计算法

针对本问,我们设计了如下寻优标准:

把“面试组”分为四类,分别为:没有一个教师相同的情形;有一个教师相同;有两个教师相同;有三个教师相同,且优先级逐次降低。求解模型时,我们采用贪婪法思想编程,按照四种“面试组”的优先级顺序,分别从C4M中教师组合中,搜索出面试学生数目的“面试组”。至此,对M=24,N=379进行合理公平的分配基本完成。

程序算法步骤如下:

4Step1:首先对M位教师每四人一组进行组合,求出所有组合项为CM,把所有项按递增方式排列成序列S0;

13

Step2:从S0第一项即:1、2、3、4开始,逐次扫描后面所有项,如果后面项同第一项没有一个相同,将其选出来作为第二项,继续扫描找出与第二像没有一个相同的项,依次类推直至最后一组。然后将找出的所有项剔除,这样形成了一个新的序列S1,如果赛选出的所有项数目之和n<379,转入Step3;

Step3:从S1的第一项开始,逐次扫描后面所有项,如果后面项同第二项有一个数字相同的就将其选出,继续扫描后面的项,方法同Step2。直到找出所有的项,将第二次找出的所有项剔除,这样形成了一个新的序列S2,如果前两次赛选出的所有项之和n<379,转向Step4;

Step4:然后从S2的第一项开始,逐次扫描后面所有项,如果后面项同第三项有两个数字相同的就将其选出,这样形成了一个新的序列S3,依次类推,直到赛选出的所有项之和n>=379,搜索完成。

Step5:根据约束条件进行面试教师分配。

将N=379,M=24代入模型2,经过编程(程序见附录程序3)计算24位教师的合理分配方案。 2、分配方案

通过以上步骤和算法,得到在任意两学生“面试组”最多有两位教师相同的分组共有378组,具体见表7:

表7 分配表 学生教师序号 学生教师序号 序号 序号 1 16 1 2 3 4 1 3 13 15 2 17 1 2 5 6 1 3 14 16 3 18 1 2 7 8 1 3 17 19 4 19 1 2 9 10 1 3 18 20 5 20 1 2 11 12 1 3 21 23 6 21 1 2 13 14 1 3 22 24 7 22 1 2 15 16 1 4 5 8 8 1 2 17 18 9 1 2 19 20 …….. ……... ……. ……. ……. 10 1 2 21 22 11 1 2 23 24 12 375 1 3 5 7 18 20 22 24 13 376 1 3 6 8 19 20 21 22 14 377 1 3 9 11 19 20 23 24 15 378 1 3 10 12 21 22 23 24 注:由于表格太大,表5只有部分数据,其它数据详见附表1。 分析表5可知,按照上述方法分组,24位老师最多可面试378位学生,如不考虑第3位学生,每位教师面试的学生认数n=378*4/24=63。而题目要求是有379位学生,24位教师。因此,我们要考虑从已分好的378组中任取4位教师另组一个“面试组”。在此,我们选的是编号为21、22、23、24的教师,这样就会出现4位教师面试为学生。对应的教师面试的学生名单为(见下表8),下图2更能形象清楚的看到每位教师所面试的学生名单。

表8 教师面试学生名单

14

面试学生名单(学生编号) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 55 56 57 58 59 60 61 62 63 1 2 3 4 5 6 7 8 9 10 11 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 2 81 82 83 84 85 86 87 88 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 1 12 13 14 15 16 17 18 19 20 21 65 66 67 68 69 70 71 72 73 116 117 118 119 120 3 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 1 155 156 157 „„ „„„ „„ „„„ „„ „„„ 10 21 31 37 44 55 62 73 83 88 97 106 115 124 133 140 147 1 1 173 178 187 197 206 214 222 230 237 244 251 257 22 259 262 269 272 279 285 286 291 296 301 306 311 314 317 320 326 331 332 337 343 348 352 356 360 363 366 369 371 373 375 376 378 379 11 20 31 38 47 52 61 73 82 91 98 105 112 125 130 139 148 157 163 170 181 188 23 198 205 214 222 229 238 245 250 257 260 265 266 271 279 284 2 292 295 298 307 308 313 318 323 325 328 335 338 344 347 352 356 359 3 367 368 371 373 374 377 378 379 11 21 30 39 46 53 60 72 83 90 99 104 113 125 131 138 149 156 162 171 180 1 198 206 213 221 230 238 245 251 24 256 261 2 267 270 278 285 288 293 294 299 307 309 312 319 322 324 329 334 339 344 348 351 355 360 3 367 369 370 372 375 377 378 379 5.2.4满足条件Y1~Y4的分析 1、满足条件Y1

15

教师编号 1

每位教师面试的学生个数见下图4:

图4 每位教师面试的学生个数

由图4可以看到,只有4位教师面试位学生,其余20位教师均面试63位学生,很好的满足条件Y1:每位老师面试的学生数量应尽量均衡。 2、满足条件Y2

首先,模型求解过程中已经把“面试组”有超过两个的情况删除了,余下的“面试组”均满足不超过两个教师相同的要求。

4

其次,24位教师任意四个分成一组,共可以分成CM=10626组,即如果不考虑面试组教师存在完全相同的情况,24位教师就可以面试10626位学生,而题目中只有379位学生参加面试,数量远远小于10626。可以找到379个组满足“面试组”成员不能完全相同的要求。

综上所述,该分配方案可以很好的满足Y2。 3、满足条件Y3

因为文中设计的算法是按照“零个教师相同”、“一个教师相同”、“两个教师相同”、“三个教师相同”优先级顺序逐次递减的规则,从所有教师的全排列C4M中,逐步挑选出符合条件的“面试组”,最后我们得到只有5

5个“面试组”出现“三个教师相同的情形”,所占比例为4100%1.31%,

CM很好的满足条件Y3. 4、满足条件Y4

根据以上分配方案,得到每位教师面试学生名单的立方图,见图4:

16

图5 每个教师面试的学生名单

从图5侧面看,任意两条线重复的部分不是很多,而是成斜梯形逐渐上升。说明,每一位教师与其他任何一位教师所面试的学生集合出现相同的学生数目很少。

经过统计得出,两个老师面试的学生名单中,相同的学生数最大为11,只占总人数的2.9%(11/279),占每个老师面试学生数的17.46(11/63)。

因此,以上分配方案能够比较好的满足Y4,使任意两教师面试的学生集合出现相同的学生人数尽可能的少。 5.3问题三模型的建立及求解

本问题和前面两问相比,增加了“文理科教师各占一半”和“每位学生分别接受两位文科两位理科教师的面试”的条件,我们在问中称之为“第二条件”。其余的条件和以上分析完全一样(详见5.1和5.2)。 5.3.1对问题一模型及结果的修改

针对“没有两位面试教师相同的情形”,条件改变后,5.1.2中的第2个条件变化为:

xxikk1lM2M2Mil4(k代表文科教师;l代表理科教师i1,2,,N)

因此,得到单目标规划模型为: maxNMxikxjk1(ij;i,j1,2,,N)k1MM2 st.xikxil4(k代表文科教师;l代表理科教师i1,2,,N)Mk1l12xik,xjk0或1(是0-1变量)下面对模型结果进行分析:

设计寻优算法,利用Matlab编程(程序及运行结果见附录程序4),分

17

别求出在问题一中C1~C4规则下的四组数据分别为:

按C1规则: 5 6 7 8 9 10 11 12 13 14 教师(M) 4 1 1 2 2 3 5 6 9 9 10 学生(N) 1 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 12 14 16 16 19 21 23 25 28 29 按C2规则: 5 6 7 8 9 10 11 12 13 14 教师(M) 4 1 1 2 2 3 5 6 9 9 9 学生(N) 1 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 12 14 16 16 19 23 24 26 29 33 按C3规则: 5 6 7 8 9 10 11 12 13 14 教师(M) 4 1 1 2 2 3 5 6 9 9 9 学生(N) 1 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 11 13 14 16 19 20 24 26 29 32 按C1规则: 5 6 7 8 9 10 11 12 13 14 教师(M) 4 1 1 2 2 3 5 6 9 9 10 学生(N) 1 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 12 14 16 17 19 21 23 26 29 33 对以上四个表逐步修正,得到最优的数据见下表9: 表9 新条件下“没有两个老师相同的情形” 5 6 7 8 9 10 11 12 13 14 教师(M) 4 1 1 2 2 3 5 6 9 9 10 学生(N) 1 教师(M) 15 16 17 18 19 20 21 22 23 24 学生(N) 12 14 16 17 19 21 23 26 29 33 根据表9 可得出得到对应的学生数与所需老师的最少数量的数据如下表10所示:

表10 “没有两个老师相同”已知N对应的最小M表 M 4 7 9 11 12 13 14 15 16 N 1 2 3 6 9 13 13 14 16 M 17 18 19 20 21 22 23 24 N 18 20 23 25 29 30 35 38 对表10数据进行函数拟合,得到图形如下图6所示: 18

图6 新条件下“没有两位老师相同”拟和图

对应的教师数M和面试学生数N的数值表达式:

(N32.142)17.44(N28.162)1.531(N11.652)9.53(N3.7712)2.443

M23.98e0.7179e8.825e3.863e(5) 因此,如果面试学生数N一定,在任两位学生的“面试组”都没有两位学生相同的情形下,根据上式即可求出所需应聘教师M的最小值。

同理,针对“没有三位面试教师相同的情形”, 设计寻优算法,利用上述方法可求解出M与N的关系表达式。 5.3.2对问题二模型及结果的修改

修改之后,问题二增加了“文理科教师各占一半”和“每位学生必须分别接受两个文科和两个理科教师的面试”。这样,上文5.2.2中约束条件

xj1M2k1Mij4就要发生变化,根据要求该约束可表达为:

xiklMM12xil4(k代表文科教师;l代表理科教师i1,2,,N)

0-1

规划模型:

因此,模型二可更改为如下双目标

minminZ1TijHij

i1ji1MN1NN1Ni1ji1Z2M1k1jk1Pjk

19

WiWj1MM2xikxil4(k代表文科教师;l代表理科教师i1,2,,N)Mk1l12 s..tQij4NWjxiji1xij为01变量5.3.3新条件下对N=379,M=24重新设计分配方案

假设1、3……M1的编码代表文科教师,2、4、6……M的编码代表理科教师(M为偶数的前提下)。

新条件:“每位学生必须接受两位文科、两位理科教师的面试”。将问题转化成数学语言,就是我们求解出的所有379组教师组合中,必须满足“含有两个奇数和两个偶数”的条件。本问可以直接在模型二结果的基础上进行挑选、重组。

Step1:从问题2的结论378中组合中,挑选出不符合“两奇、两偶”的组合;

Step2:将不符合条件(挑选剩余的)的组合相互之间重新分配,这样就组成378组“最多有两个教师相同”的分配方案;

Step3:第379位同学的“面试组”可以从24位教师中任选4位,这样就会出现5为同学的“面试组”有“三个教师相同”的情形。最后对新的分配方案进行条件Y1~Y4的合理性分析。

针对Step1,通过编程(见附录程序4)选出300个符合“两奇两偶”的组合,剩余78组不符合条件,我们将这78组单独列出,其中A代表全奇数组合,B代表全偶数组合,详见下表11:

表11 不满足新条件的78种组合 教师编码组合A 教师编码组合B 1 3 5 7 2 4 6 8 1 3 9 11 2 4 10 12 1 3 13 15 2 4 14 16 1 3 17 19 2 4 18 20 1 3 21 23 2 4 22 24 1 5 9 13 2 6 10 14 1 5 11 15 2 6 12 16 1 5 17 21 2 6 18 22 1 5 19 23 2 6 20 24 1 7 9 15 2 8 10 16 1 7 11 13 2 8 12 14 1 7 17 23 2 8 18 24 1 7 19 21 2 8 20 22 3 5 9 15 4 6 10 16 20

…… …… 13 13 17 …… …… …… …… …… …… …… …… …… …… …… …… …… …… 15 17 19 14 16 18 20 15 21 23 14 16 22 24 19 21 23 18 20 22 24 分析表11中的数据,可以很清楚看到,表中的78种组合只有两种情况:“四奇”和“四偶”,并没出现“一奇三偶”和“一偶三奇”的组合。这给我们解题提供很大的方便,为方便组合,我们将奇、偶组合按升序排列。只需要将表中奇数组A与相对应的偶数组B交换两个数字即可。

这种组合会有很多种,我们选择A中的前两个数与B中的中间两个数组合在一起,这样不会出现和满足条件的300组有“四个教师都相同的情形”。原因是,B中第二个数刚好与A中第二个数相差1。例如:我们选1、3、4、6为一组,对比其余300组数发现和1、3组合的所有数最小从5开始,所以300组中就不会出现与1、3、4、6完全相同的组合,会出现这种现象的原因是,在挑选378组两两比较的过程中(和前一项有两个或超过两个相同数字的组合就从总组合中剔除),删除了与3最接近的1、3、4、X组合。因此,只要分组时选择与A中第二个数相差为1的编码,就不会出现有“四个教师都相同的面试组”。依次按照上述方法组合余下77组,得到满足条件的78个组合如下表11所示:

表12 不满足新条件的78种组合 教师编码组合 教师编码组合 1 3 4 6 2 5 7 8 1 3 4 10 2 9 11 12 1 3 4 14 2 13 15 16 1 3 4 18 2 17 19 20 1 3 4 22 2 21 23 24 1 5 6 10 2 9 13 14 1 5 6 12 2 11 15 16 1 5 6 18 2 17 21 22 1 5 6 20 2 19 23 24 1 7 8 10 2 9 15 16 1 7 8 12 2 11 13 14 1 7 8 18 2 17 23 24 1 7 8 20 2 19 21 22 3 5 6 10 4 9 15 16 …… …… …… …… …… …… …… …… …… …… …… …… …… …… …… …… 15 16 18 14 17 19 20 15 16 22 14 21 23 24 19 20 22 18 21 23 24 这样就得到378种满足题目要求的组合。同问题二一样,第379位学生按照要求“面试组成员不能完全相同”,选择四位教师即可。最终的24位教师面试学生名单见附表2。

21

13 13 17

5.3.4根据以上分配方案,针对条件Y1~Y3进行合理性分析

1、Y1:每位老师面试学生数量尽量均衡

由于此方案是按照问题二进行改进得到,只是对每位教师面试的学生名单进行了调整,面试学生数量并没有减少。因此,同问题二一样满足Y1(详见5.2.4)。

2、Y2:面试不同考生的“面试组”成员不能完全相同

首先,模型求解过程中已经把“面试组”有超过两个的情况删除了,余下的“面试组”均满足不超过两个教师相同的要求。

4

其次,24位教师任意四个分成一组,共可以分成CM=10626组,即如果不考虑面试组教师存在完全相同的情况,24位教师就可以面试10626位学生,而题目中只有379位学生参加面试,数量远远小于10626。可以找到379个组满足“面试组”成员不能完全相同的要求。

综上,分配方案满足Y2.

3、Y3:两个考生的面试组中有两位或三位老师相同的情形尽量的少 因为问题二是按照“面试组”优先级顺序进行选择分组的,而问题三又是在问题二结论的基础上,只是对一些组合稍加修改,因此问题三的分配方案也是满足Y3的。

4、Y4:任意两老师面试的两个学生集合出现相同学生的人数尽量少 分析同5.2.4。 5.1 问题四公平性讨论及建议

5.4.1“均匀性”和“公平性”的关系的讨论

在科学的评价中,分配面试老师和考生时,需要评估的“均匀性”和“公平性”。为了得到尽量可靠的参考标准,评分的老师应是比较专业的,从而评出的分数即使也有评分老师的主观因素,但也是相对比较客观的。

对于此题的理解,老师分配的越均匀,对于学生来说就越公平。因为所有面试老师的背景、研究领域、提问方式、出题上的内容难度都各不相同,因而他们对考生的作答方式、答案满意度要求和评分标准都有很大不同。若面试老师分配得不均匀,如某一组老师的要求特别严格,而另一组老师的要求特别宽松,会导致两个能力接的近学生获得的评价会由巨大差别。因此要做让各个学生尽量公平,应注重老师分配均匀性的考虑。题中组织者的提出的4个要求都对此有明确体现。如:每位老师面试的学生数量应尽量均衡;两个考生的“面试组”中有两位或三位老师相同的情形尽量的少等等。 5.4.2给出的建议

针对5.4.1“均匀性”和“公平性”讨论的进一步考虑,有以下的改进方案:

1、老师在对学生打分时是根据题目的难易程度而定的,难度越大,相对考生所得的分数应越高

2、为了让学生尽量能够正常发挥、心理情绪波动尽量小,老师提问应尽量先易后难,(尽量避免学生因为前一难题回答的不理想而影响后面相对简单题目的正常作答)

3、所有老师的学术水平尽量接近,这样能尽量使得所有老师出题的难度差异相对小,所有学生回答的问题难度也就波动不大,更显公平性。

22

4、合理搭配面试员的知识结构,文理比例适当。

5、在统计最终得分时,对文科学生和理科学生回答文理问题的分数按一定的权重进行统计总分数(若针对招生为理科学生,理科问题所占的分数与文科问题的分数占的权重比可以设为w1:w2,其中w1>0, w2>0,且。 w1>w2;若针对招生为文科学生,反之亦然)

例如:某个理科学生回答理科问题的分数F1为90分,回答文科问题分数F2为70分,若该招生的专业为理科专业,则理科问题所占的分数与文科问题的分数占的权重比可以设为0.7:0.3,则改学生的实际得分为:

F总w1F1w2F20.7900.30

84(分)而不是单纯的求算术平均:

1F总(F1F2) 2=80(分)这样通过权重的调整,则理科特长的学生更具有竞争力,更有利于该高校对录取文理科学生的针对性。

6、面试老师和学生的编号最好在面试前临时抽签决定,以避免有学生在面试前贿赂老师或者面试老师和某个学生有亲属关系而引起的不公平。

六. 模型评价与改进

本文研究了在保证面试工作公平性的情况下,使用计算机搜索、逐步

修正以及排列组合等方法,解决了在N一定的条件下,所需教师数量的最小值M,并建立0-1整数规划模型和多目标优化规划模型,应用贪婪法求解模型给出具体的分组情况。

优点:

1. 本文将实际问题转化为数学问题,结构清晰,层次分明,数学表达

式涵盖了题目中所有的约束条件和目标;

2. 问题一,为得到最优值,我们计算得出多种规则下的数据,逐一对

数据进行修正,使结果逼近最优解;

3. 使用数值拟合方法,增加本文计算的可操作性;

4. 问题三,为减少计算量,将问题进一步简化,即从已分配好的“面

试组”中挑选出满足新条件的组合,对余下组合,重新分配,这样就大大减少了计算量;

然而,美中不足的是,数值计算方法对于很简单的模型,都可能会有很大的运算量。例如,从C4M中组合中太哦选满足要求的组合,都需要运行上万次。

可以考虑用字典序列、组合数学与遗传算法相结合的算法思想,对模型进一步优化,使结果更优,同时减少运算量。

23

七. 考文献

[1]张志涌,MATLAB教程[M].北京:北京航空航天大学,2001.

[2]盛聚,概率论与数理统计[M].北京:高等教育出版社,2001. [3]张宜华,精通MATLAB5[M].北京:清华大学出版社,1999.

[4]陈理荣,数学建模导论[M].北京:北京邮电大学出版社,1999. [5]解可新,最优化算法[M].天津:天津大学出版社,1997. [6]谢胜智,运筹学[M].成都:西南财经大学出版设,1999.

[7]赵静,数学建模与数学实验[M].北京:高等教育出版社,第2版. [8]程理民,运筹学模型与方法教程[M].北京: 清华大学出版社, 2004. [9]李永、冯勇, 多目标决策中目标权重的分析法 [J].甘肃工业大学学

报,2003,5(8):23—30.

[10]陈媛,攀治平,综合性面试中的面试官分组方法[J].系统工

程,2008,26(1):96-101.

八.附录

8.1附表

1、附表1 问题二的379组分配方案

学生编号 分组(教师编号) 学生编号 分组(教师编号) 学生编号 分组(教师编号) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 5 7 9 11 13 15 17 19 21 23 4 4 4 4 4 6 10 14 18 22 4 6 8 10 12 14 16 18 20 22 24 6 10 14 18 22 8 12 16 20 24 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 24

6 6 6 10 12 18 20 9 10 11 12 17 18 19 20 8 8 8 8 10 12 12 18 20 16 14 24 22 16 15 14 13 24 23 22 21 10 12 18 20 14 16 253 2 255 256 257 258 259 260 261 262 263 2 265 266 267 268 269 270 271 272 273 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 12 12 12 12 12 13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16 14 17 18 21 22 14 14 18 20 17 18 19 20 16 16 18 20 17 18 19 20 15 20 19 24 23 18 20 22 24 22 21 24 23 18 20 24 22 24 23 22 21

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 55 56 57 58 59 60 61 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 5 6 9 10 13 14 17 18 21 22 6 6 6 6 10 12 18 20 9 10 11 12 17 18 19 20 8 8 8 8 10 12 18 20 9 10 11 12 17 18 8 7 12 11 16 15 20 19 24 23 10 12 18 20 14 16 22 24 14 13 16 15 22 21 24 23 10 12 18 20 16 14 24 22 16 15 14 13 24 23 148 149 150 151 152 153 1 155 156 157 158 159 160 161 162 163 1 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 7 7 8 8 8 8 8 8 8 8 5 5 5 5 5 5 5 5 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 14 14 16 16 22 22 25

18 20 9 10 11 12 17 18 19 20 9 10 11 12 17 18 19 20 9 11 17 19 9 10 11 12 17 18 19 20 9 11 17 19 9 11 9 11 17 19 22 24 14 13 16 15 22 21 24 23 16 15 14 13 24 23 22 21 15 13 23 21 14 13 16 15 22 21 24 23 13 15 21 23 13 13 15 15 21 21 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 2 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 13 13 13 13 14 14 15 15 15 15 16 16 16 20 22 22 24 24 24 12 12 12 12 12 12 13 13 13 13 14 14 13 14 17 18 21 22 13 17 21 17 18 19 20 17 19 17 18 19 20 13 17 19 17 17 19 17 19 21 13 15 17 19 21 23 14 14 18 20 17 18 16 15 20 19 24 23 15 19 23 22 21 24 23 21 23 24 23 22 21 15 23 21 19 21 21 23 23 23 14 16 18 20 22 24 18 20 24 22 24 23

62 63 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 90 91 92 93 94 95 96 97 98 99 100 101 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

8 8 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 19 20 5 6 9 10 13 14 17 18 21 22 5 9 13 17 21 9 10 11 12 17 18 19 20 9 11 17 19 9 10 11 12 17 18 19 20 5 9 11 22 21 8 7 12 11 16 15 20 19 24 23 7 11 15 19 23 14 13 16 15 22 21 24 23 13 15 21 23 16 15 14 13 24 23 22 21 7 15 13 188 1 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 24 24 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 7 7 7 7 7 7 7 7 8 8 8 8 12 26

17 19 7 9 11 13 15 17 19 21 23 8 8 8 8 10 14 18 22 9 10 13 14 17 18 21 22 9 10 13 14 17 18 21 22 9 13 17 21 9 23 23 8 10 12 14 16 18 20 22 24 10 14 18 22 12 16 20 24 12 11 16 15 20 19 24 23 12 11 16 15 20 19 24 23 11 15 19 23 11 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 15 15 15 15 16 16 16 16 13 13 13 13 14 14 15 15 15 15 16 16 22 22 24 24 14 14 14 14 14 15 15 15 15 16 16 16 16 15 19 20 16 16 18 20 17 18 19 20 17 18 19 20 17 19 17 18 19 20 17 19 17 19 17 19 15 17 19 21 23 16 16 18 22 17 18 21 22 17 22 21 18 20 22 24 22 21 24 23 24 23 22 21 23 21 22 21 24 23 21 23 21 21 23 23 16 18 20 22 24 18 22 20 24 20 19 24 23 20

102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3

8 8 12 14 14 16 16 16 20 22 22 24 24 24 4 4 4 4 4 4 4 4 4 4 5 17 19 9 9 11 9 11 13 17 17 19 17 19 21 5 7 9 11 13 15 17 19 21 23 6 23 21 11 13 13 15 15 15 19 21 21 23 23 23 6 8 10 12 14 16 18 20 22 24 10 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 6 6 6 7 7 7 7 7 7 7 7 9 9 9 9 9 9 9 9 9 9 9 9 9 9 16 20 24 8 8 8 8 8 8 8 8 10 10 10 10 10 10 10 11 11 11 11 11 11 12 13 17 21 9 11 13 15 17 19 21 23 11 13 15 17 19 21 23 12 12 12 14 18 22 13 15 19 23 10 12 14 16 18 20 22 24 12 14 16 18 20 22 24 14 18 22 16 20 24 16 3 355 356 357 358 359 360 361 362 363 3 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 14 14 14 14 14 14 14 15 15 15 15 17 17 17 17 17 17 17 18 18 18 18 19 19 21 21 15 15 15 16 16 20 24 16 16 16 16 18 18 18 19 19 20 20 19 19 20 24 20 20 22 22 18 21 22 17 21 17 21 17 19 21 23 19 21 23 20 22 21 22 21 22 21 21 21 23 23 23 19 24 23 19 23 19 23 18 20 22 24 20 22 24 22 24 24 23 24 23 23 23 22 24 24 24 2、问题三新条件下的教师面试学生名单

A B C D E F G H I J K L M N O P Q R S T U V W X 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 12 13 14 15 16 17 18 19 20 1 12 13 14 15 16 22 23 24 25 2 22 32 33 34 35 36 37 38 39 2 12 17 23 32 33 34 35 40 41 3 23 48 49 50 51 52 53 55 3 17 22 48 49 50 51 56 57 58 4 24 40 56 66 75 79 87 91 100 4 13 18 25 32 36 41 48 52 57 5 25 42 58 67 75 81 88 93 101 5 18 24 33 37 43 49 53 59 66 6 26 41 59 68 76 80 87 94 101 6 14 19 27 36 40 53 58 69 79 7 27 43 57 69 76 82 88 92 100 7 19 26 37 42 52 56 68 81 91 8 28 44 60 70 77 83 95 102 8 15 20 29 34 38 45 50 61 9 29 46 62 71 77 85 90 97 103 9 20 28 35 39 47 51 55 63 70 10 30 45 63 72 78 84 98 103 10 16 21 31 38 44 55 62 73 83 11 31 47 61 73 78 86 90 96 102 11 21 30 39 46 60 72 85 95 27

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 11 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 90 91 92 93 94 95 96 97 98 99 1021 65 66 67 68 69 70 71 72 73 26 27 28 29 30 31 74 75 76 77 78 74 79 80 81 82 83 84 85 86 99 42 43 44 45 46 47 65 87 88 90 65 74 91 92 93 94 95 96 97 98 99 59 60 61 62 63 99 104 105 107 67 80 92 104 106 82 94 105 93 107 107 110 71 84 96 110 112 86 98 111 97 113 113 106 105 108 108 111 112 111 114 114 108 104 109 106 109 109 113 114 110 115 112 115 115 118 118 119 119 120 120 121 121 122 122 123 123 124 124 125 125 134 126 136 127 137 131 135 130 138 128 140 129 141 133 139 132 150 130 152 131 151 136 153 134 1 132 156 133 155 140 157 138 158 135 160 137 161 146 159 147 162 139 1 141 165 148 163 149 100 166 142 167 143 167 150 166 152 168 144 169 145 169 1 168 156 101 170 146 172 147 171 160 173 158 174 148 176 149 175 1 177 162 102 178 151 179 153 178 170 179 172 180 155 181 157 180 174 181 176 103 182 159 183 161 182 182 184 184 186 163 187 165 186 186 188 188 116 116 116 116 117 117 184 171 185 173 183 183 185 185 188 175 1 177 187 187 1 1 117 117 126 126 142 142 191 191 192 192 193 193 194 194 195 195 196 196 197 197 198 198 118 118 127 127 143 143 207 199 208 203 209 200 210 204 211 201 212 205 213 202 214 206 119 119 128 128 144 144 215 203 216 207 217 204 218 209 219 205 220 211 221 206 222 213 120 120 129 129 145 145 223 208 223 215 224 210 224 217 225 212 225 219 226 214 226 221 121 121 130 134 146 150 227 216 227 227 228 218 228 228 229 220 229 229 230 222 230 230 122 122 131 135 147 151 231 231 232 232 233 233 234 234 235 235 236 236 237 237 238 238 123 123 132 136 148 152 239 239 239 239 240 240 241 241 242 242 243 243 244 244 245 245 124 124 133 137 149 153 240 240 246 246 252 246 253 249 2 247 255 250 256 248 257 251 125 125 158 138 170 1 241 241 247 247 258 249 266 252 262 250 2 2 263 251 265 256 126 158 159 139 171 155 242 242 248 248 259 253 267 266 270 255 272 259 273 257 271 261 127 159 160 140 172 156 243 243 249 252 260 258 268 267 276 258 277 261 278 260 279 2 128 160 161 141 173 157 244 244 250 253 261 259 269 270 281 260 281 265 282 262 282 268 129 161 162 166 174 178 245 245 251 2 274 262 275 271 283 263 285 267 284 269 286 270 130 162 163 167 175 179 246 274 274 255 280 263 280 272 287 266 288 269 287 272 288 278 131 163 1 168 176 180 247 275 275 256 283 2 2 273 2 268 291 273 292 279 290 285 132 1 165 169 177 181 248 276 276 257 284 265 290 274 294 271 295 276 295 283 294 2 133 165 190 190 190 190 249 277 277 280 285 275 291 293 296 277 296 286 297 291 299 299 134 166 191 191 199 199 250 278 278 281 286 287 292 294 297 284 298 292 298 297 300 300 135 167 192 192 200 200 251 279 279 282 293 288 293 295 299 290 300 296 301 298 301 301 136 168 193 193 201 201 252 280 302 302 302 302 303 303 304 304 305 305 306 306 307 307 137 169 194 194 202 202 253 281 303 303 308 308 316 316 312 308 314 309 315 311 313 310 138 170 195 195 203 207 2 282 304 304 309 309 317 317 320 310 322 311 321 314 323 312 139 171 196 196 204 208 255 283 305 305 310 312 318 320 324 313 326 315 327 318 325 319 140 172 197 197 205 209 256 284 306 306 311 313 319 321 328 316 329 317 329 320 328 322 141 173 198 198 206 210 257 285 307 307 324 314 330 322 330 318 332 319 331 326 333 324 48 49 0 10142 174 199 215 215 211 258 286 308 324 325 315 331 323 334 321 335 323 334 330 335 332 143 175 200 216 216 212 259 287 309 325 326 328 332 334 336 325 337 327 336 336 338 338 28

1 1050 2 1051 3 1052 4 1053 5 10 6 1055 7 1056 8 1057 9 1158 0 1159 1 1160 2 1161 3 1162 4 1163 5 157 1 214 230 238 238 273 301 323 339 352 360 3 3 371 375 377 377 378 378 378 378 379 379 379 379 156 188 213 229 237 237 272 300 322 338 351 359 363 363 370 374 376 376 376 376 377 377 155 187 212 228 236 236 271 299 321 337 350 358 362 362 369 373 373 374 375 373 375 375 1 186 211 227 235 235 270 298 320 336 349 357 361 361 368 372 372 371 374 371 374 372 153 185 210 226 234 234 269 297 319 335 348 356 356 358 367 367 369 370 372 369 373 370 152 184 209 225 233 233 268 296 318 334 347 355 355 357 366 366 368 368 370 368 371 369 151 183 208 224 232 232 267 295 317 333 346 3 3 352 365 365 365 365 366 366 367 367 150 182 207 223 231 231 266 294 316 332 345 353 353 351 361 361 362 362 363 363 3 3 149 181 206 222 222 226 265 293 315 331 344 344 348 350 359 3 359 359 360 356 360 360 148 180 205 221 221 225 2 292 314 330 343 343 347 349 357 350 357 353 358 352 358 355 147 179 204 220 220 224 263 291 313 329 342 342 346 346 353 347 3 349 355 348 356 351 146 178 203 219 219 223 262 290 312 328 341 341 345 345 349 345 350 347 351 346 352 348 145 177 202 218 218 214 261 2 311 327 340 340 340 340 341 341 342 342 343 343 344 344 144 176 201 217 217 213 260 288 310 326 327 329 333 335 338 331 339 333 337 337 339 339 8.2源程序及结果

程序1:没有两个老师相同的情况下的一种方案的程序: clear

q=input('请输入任两个学生有最多有几个老师相同:'); l=1;

for p=4:24 M=1:p;

x=1; %组合数最开始设置为1 a=1;

29

for i=1:p; %第一个老师编号递增 for j=(i+1):p; %第二个老师编号递增 for m=p:-1:j+1; %第三个老师编号递减 for n=p:-1:m+1; %第四个老师编号递减 N(x,1)=M(i); N(x,2)=M(j); N(x,3)=M(m); N(x,4)=M(n); x=x+1; end end

end end y=x-1;

for i=1:y-1; %比较次数 j=i+1;

while(jif(N(i,m)==N(j,1)||N(i,m)==N(j,2)||N(i,m)==N(j,3)||N(i,m)==N(j,4))

f(1,m)=1;

else

f(1,m)=0; end end

if(sum(f(1,:))>q) N(j,:)=[]; y=y-1; j=j-1; end

j=j+1; end end

c(1,l)=p;

c(2,l)=y; %p个老师能面试的最大学生数 l=l+1; end

c %最后数据

30

请输入任两个学生有最多有几个老师相同:1

c =

Columns 1 through 17

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 1 2 2 3 3 6 9 13 13 14 16 18 20 23 25

Columns 18 through 21 21 22 23 24 27 30 31 36 程序2:

没有三个老师相同的情况下的一种方案的程序: clear

q=input('请输入任两个学生有最多有几个老师相同:'); l=1;

for p=4:24 M=1:p;

x=1; %组合数最开始设置为1 a=1;

for i=1:p; %第一个老师编号递增 for j=(i+1):p; %第二个老师编号递增 for m=(j+1):p; %第三个老师编号递增 for n=p:-1:(m+1); %第四个老师编号递减 N(x,1)=M(i); N(x,2)=M(j); N(x,3)=M(m); N(x,4)=M(n); x=x+1; end end end end y=x-1;

for i=1:y-1; %比较次数 j=i+1;

while(jif(N(i,m)==N(j,1)||N(i,m)==N(j,2)||N(i,m)==N(j,3)||N(i,m)==N(j,4))

f(1,m)=1;

31

else

f(1,m)=0; end end

if(sum(f(1,:))>q) N(j,:)=[]; y=y-1; j=j-1; end j=j+1; end

end

c(1,l)=p;

c(2,l)=y; %p个老师能面试的最大学生数 l=l+1; end

c %最后数据

请输入任两个学生有最多有几个老师相同:2 c =

Columns 1 through 17

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 3 7 14 15 21 30 39 55 71 95 140 140 163 195 229

Columns 18 through 21 21 22 23 24 272 324 376 424 程序3: clear q=2; p=24; M=1:p;

x=1; %组合数最开始设置为1 for i=1:p;

for j=(i+1):p; for m=(j+1):p; for n=(m+1):p; N(x,1)=M(i); N(x,2)=M(j); N(x,3)=M(m); N(x,4)=M(n); x=x+1;

32

end end end end y=x-1;

for i=1:y-1; %比较次数 j=i+1;

while(jif(N(i,m)==N(j,1)||N(i,m)==N(j,2)||N(i,m)==N(j,3)||N(i,m)==N(j,4))

f(1,m)=1; else

f(1,m)=0; end end

if(sum(f(1,:))>q) N(j,:)=[]; y=y-1; j=j-1; end j=j+1; end end

for j=1:24; k=1;

for i=1:y;

if(N(i,1)==j||N(i,2)==j||N(i,3)==j||N(i,4)==j) a(k,j)=i; k=k+1; end end end

程序4: clear q=2; p=24; M=1:p; k=1;

x=1; %组合数最开始设置为1

for i=1:p; %老师的号数:单表示文科,双表示理科 for j=(i+1):p; for m=(j+1):p; for n=(m+1):p;

33

N(x,1)=M(i); N(x,2)=M(j); N(x,3)=M(m); N(x,4)=M(n); x=x+1; end end end end y=x-1;

for i=1:y-1; %比较次数 j=i+1;

while(jif(N(i,m)==N(j,1)||N(i,m)==N(j,2)||N(i,m)==N(j,3)||N(i,m)==N(j,4))

f(1,m)=1; else

f(1,m)=0; end end

if(sum(f(1,:))>q) N(j,:)=[]; y=y-1; j=j-1; end j=j+1; end end i=1;

while(iif(mod(N(i,1),2)+mod(N(i,2),2)+mod(N(i,3),2)+mod(N(i,4),2)==2)

b(k,:)=N(i,:); k=k+1;

N(i,:)=[]; i=i-1; end i=i+1; end

y=378;

for j=1:24; k=1;

34

for i=1:y;

if(N(i,1)==j||N(i,2)==j||N(i,3)==j||N(i,4)==j) a(k,j)=i; k=k+1; end end end a

35

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- azee.cn 版权所有 赣ICP备2024042794号-5

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务