招聘中的面试时间问题论文.docx
《招聘中的面试时间问题论文.docx》由会员分享，可在线阅读，更多相关《招聘中的面试时间问题论文.docx（17页珍藏版）》请在冰点文库上搜索。
招聘中的面试时间问题论文
保证书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则,我们完全明白在竞赛开始后不能以任何方式与队外的任何人（包括指导教师）讨论竞赛题的求解问题,抄袭别人的成果也是违反竞赛规则的,如被发现将会受到严肃处置。
我们也知道如果引用别人的成果或其他公开的资料（包括网上查到的资料）必须按照规定的参考文献的表述方式在正文和参考文献中明确列出。
为了确保竞赛的公正、公平性,我们保证严格遵守竞赛规则。
参赛报名号：
参赛队员（签名）
招聘中的面试时间问题
摘要：
面试问题普遍出现于公司招聘事务中，而随着求职者的增多，公司不得不考虑人数和时间的问题。
因此为了合理安排和使用时间，建立各种与问题相对应的解决方案是必要的。
本文从时间，人数以及顺序的角度，并根据求最优值的方法建立了基本的线性方程模型。
在建立模型以及模型求解中，我们借助Lingo8.0语言编程得出了四名同学分别按可以插队和不可以插队时的最优方案：
即按丁、甲、乙、丙的顺序进行面试，秘书、主管、经理三人才能最早离开公司。
为了形象表达出顺序问题我们绘制出了顺序图，以及另外一个相关的表格。
最后本文列出了Lingo8.0中的源代码和解决问题的全过程。
一．问题重述：
招聘中的面试时间问题（B）
有4名同学到一家公司参加三个阶段的面试：
公司派出公司秘书、部门主管和经理三人对这4名学生进行面试，公司要求每个同学必须首先找到公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：
分钟）：
秘书初试
主管复试
经理面试
同学甲
13
15
20
同学乙
10
20
18
同学丙
20
16
10
同学丁
8
10
15
秘书、部门主管和经理三人约定他们完成面试后一起去另外的地点参加会议。
假定在早晨8：
30开始面试，在以下两种情况下，问他们最早何时能离开公司？
并且为公司安排出对每个同学的具体面试时间表。
（1）面试不允许插队（即在任何一个阶段4名同学的顺序是一样的）。
（2）面试不分先后次序（即在任何一个阶段4名同学的顺序可以不一样的）。
二．基本假设
1假设每个队员的面试都是理论值，无误差
2假设会议准时开始
3假设一个队员完成了一个阶段面试，下一个等待这个阶段面试的队员就开始面试，且时间间隔为0
4最后面试结束时间即为公司三人离开公司时间
5四位同学都必须完成三个阶段的面试
三．符号约定
1．A:
第一个面试的求职者
2．B：
第二个面试的求职者
3．C:
第三个面试的求职者
4．D：
第四个面试的求职者
5．记ABCD分别为求职者i=1,2,3,4;
6.记秘书初试、主管复试、经理面试为j＝1,2,3;
7.记学生甲乙丙丁分别为p=1,2,3,4。
8.tij：
第i个求职者开始第j阶段的时刻
9.cij第i个求职者第j阶段面试的时间
10.引入0-1变量yip，若第i个求职者就是第p个学生，那么yip＝1，否则yip＝0。
11.引入0－1变量w（i,k,j）表示在第j＝1，2，3个阶段如果面试者i先于面试者k,则w（i,k,j）=1,否则w（i,k,j）＝0
四．解题分析
（1）这个优化问题的目标是使4个人总的面试时间最短。
要做的决策是4个人的面试顺序问题。
任意两个求职者之间，考官等候求职者的时间与求职者等候求职者的时间之和最短。
我们按ABCD的顺序进行面试，并且画出时序图（如图1）。
由图可知，这场面试的总时间可以折算成：
D的第三次面试的开始时刻t43加上第三阶段面试的时间c43。
由图
（1）可看出，t12可由t11＋c11得出，t13可由t12＋c12得出，同理我们可以得到t21，t22，t23的递推关系，最终我们可以推出t43＋c43。
（2）我们按指派问题建立A、B、C、D与甲、乙、丙、丁的关系，引入0－1变量yip：
若第i个求职者就是第p个学生，那么yip＝1，否则yip＝0。
因此建立图2的关系。
因此甲、乙、丙、丁的顺序问题就归结为A、B、C、D到底是哪个求职者。
图1
甲
乙
丙
丁
A
y11
y12
y13
y14
B
y21
y22
y23
y24
C
y31
y32
y33
y34
D
y41
y42
y43
y44
图2
五．模型构建
（1）通过以上分析秘书、主管、经理最早离开公司即是求
Min＝t43＋c43
（1）
对A的约束
t11＝0
（2）
t12＝t11＋c11（3）
t13＝t12＋c12（4）
对B的约束
t21＝t11＋c11（5）
t22=max{t21+c21,t12+c12}（6）
t23=max{t22+c22,t13+c13}（7）
对C的约束
t31＝t21+c21（8）
t32=max{t31+c31,t22+c22}（9）
t33=max{t32+c32,t23+c23}（10）
对D的约束
t41=t31+c31（11）
t42=max{t41+c41,t32+c32}（12）
t44=max{t42+c42,t33+c33}（13）
A、B、C、D与甲、乙、丙、丁建立如下关系
y11+y12+y13+y14=1;（14）y21+y22+y23+y24=1;（15）y31+y32+y33+y34=1;（16）y41+y42+y43+y44=1;（17）
y11+y21+y31+y41=1;（18）y12+y22+y32+y42=1;（19）y13+y23+y33+y43=1;（20）y14+y24+y34+y44=1;（21）
cij（i=1,2,3;j=1,2,3,4）的取值我们就可以确定
c11>13*y11+10*y12+20*y13+8*y14;（22）c12>15*y11+20*y12+16*y13+10*y14;（23）c13>20*y11+16*y12+10*y13+15*y14;（24）
c21>13*y21+10*y22+20*y23+8*y24;（25）c22>15*y21+20*y22+16*y23+10*y24;（26）c23>20*y21+16*y22+10*y23+15*y24;（27）
c31>13*y31+10*y32+20*y33+8*y34;（28）c32>15*y31+20*y32+16*y33+10*y34;（29）c33>20*y31+16*y32+10*y33+15*y34;（30）
c41>13*y41+10*y42+20*y43+8*y44;（31）c42>15*y41+20*y42+16*y43+10*y44;（32）c43>20*y41+16*y42+10*y43+15*y44;（33）
把（6）t22＝max{t21+c21,t12+c12}改为
t22>t21+c21
t22>t12+c12
依次把（7）（9）（10）（12）（13）改为如上形式
再加上
@gin（y11）;@gin（y12）;@gin（y13）;@gin（y14）;@gin（y21）;@gin（y22）;@gin（y23）;@gin（y24）;@gin（y31）;@gin（y32）;@gin（y33）;@gin（y34）;@gin（y41）;@gin（y42）;@gin（y43）;@gin（y44）;end
我们把修改了的代码（附录1）输入lingo8.0中。
结果为：
Globaloptimalsolutionfoundatiteration:
36
Objectivevalue:
84.00000
VariableValueReducedCost
T4374.000000.000000
C4310.000000.000000
T110.0000000.000000
T128.0000000.000000
C118.0000000.000000
T1318.000000.000000
C1210.000000.000000
T218.0000000.000000
T2221.000000.000000
C2113.000000.000000
T2336.000000.000000
C2215.000000.000000
C1318.000000.000000
T3121.000000.000000
T3236.000000.000000
C3115.000000.000000
T3356.000000.000000
C3220.000000.000000
C2320.000000.000000
T4136.000000.000000
T4256.000000.000000
C4120.000000.000000
C4218.000000.000000
C3318.000000.000000
Y110.00000013.00000
Y120.00000010.00000
Y130.00000020.00000
Y141.0000008.000000
Y211.00000028.00000
Y220.00000030.00000
Y230.00000036.00000
Y240.00000018.00000
Y310.00000035.00000
Y321.00000038.00000
Y330.00000026.00000
Y340.00000025.00000
Y410.00000020.00000
Y420.00000018.00000
Y431.00000010.00000
Y440.00000015.00000
（1）的结果分析
通过y11到y44的值，我们可以由y14＝1得第一个求职者为丁，由y21＝1得第二个求职者为甲，由y32＝1得第三个人为乙，由y43＝1得第四个求职者为丙。
所以在不插队的条件下，按照丁－>甲－>乙－>丙的顺序面试，所用的时间最短。
因此我们可以得出最短时间为84分钟，因此秘书、主管、经理最早离开的时间为9：
54，
我们还能得到变量值的直方图（附录2）
（2）现在我们考虑第二个问题即可以插队的时候，面试所用最短时间的顺序。
对每个面试者的上一个面试阶段必定在下一个面试阶段之前于是有约束t（i,j）+c（i,j）<=t（i,j+1）i=1,2,3,4;j=1,2,3
引入0－1变量w（i,k,j）表示在j=1,2,3阶段如果面试者i先于面试者k,则w（i,k,j）=0否则w（i,k,j）＝1
对于第j个阶段而言面试者间的先后面试顺序满足
t（i,j）+c（t,j）-t（k,j）<=M*w（i,k,j）
t（k,j）+c（k,j）-t（i,j）<=M*（1-w（i,k,j））
M为足够大的数，我们选取M＝200
所求的时间最短问题就是目标函数Min＝tt
t（i,3）+c（i,3）<=tti＝1，2，3，4
用lingo8.0表示出来见附录（3）
运算结果如下：
Objectivevalue:
84.00000
VariableValueReducedCost
NP4.0000000.000000
NS3.0000000.000000
TT84.000000.000000
C（P1,S1）13.000000.000000
C（P1,S2）15.000000.000000
C（P1,S3）20.000000.000000
C（P2,S1）10.000000.000000
C（P2,S2）20.000000.000000
C（P2,S3）18.000000.000000
C（P3,S1）20.000000.000000
C（P3,S2）16.000000.000000
C（P3,S3）10.000000.000000
C（P4,S1）8.0000000.000000
C（P4,S2）10.000000.000000
C（P4,S3）15.000000.000000
T（P1,S1）8.0000000.000000
T（P1,S2）21.000000.000000
T（P1,S3）36.000000.000000
T（P2,S1）21.000000.000000
T（P2,S2）36.000000.000000
T（P2,S3）56.000000.000000
T（P3,S1）38.000000.000000
T（P3,S2）58.000000.000000
T（P3,S3）74.000000.000000
T（P4,S1）0.0000001.000000
T（P4,S2）8.0000000.000000
T（P4,S3）21.000000.000000
W（P1,P2,S1）0.0000000.000000
W（P1,P2,S2）0.000000-200.0000
W（P1,P2,S3）0.0000000.000000
W（P1,P3,S1）0.0000000.000000
W（P1,P3,S2）0.0000000.000000
W（P1,P3,S3）0.0000000.000000
W（P1,P4,S1）1.000000200.0000
W（P1,P4,S2）1.0000000.000000
W（P1,P4,S3）1.0000000.000000
W（P2,P3,S1）0.0000000.000000
W（P2,P3,S2）0.0000000.000000
W（P2,P3,S3）0.000000-200.0000
W（P2,P4,S1）1.0000000.000000
W（P2,P4,S2）1.0000000.000000
W（P2,P4,S3）1.0000000.000000
W（P3,P4,S1）1.0000000.000000
W（P3,P4,S2）1.0000000.000000
W（P3,P4,S3）1.0000000.000000
（2）的结果分析
最短时间为84分钟
由y（i,k,j）的值得阶段1W（P1,P2,S1）0.000000；
W（P1,P3,S1）0.000000；W（P1,P4,S1）1.000000
W（P2,P3,S1）0.000000W（P2,P4,S1）1.000000
W（P3,P4,S1）1.000000
P1先于p3；p4先于p1；p2先于p3；p4先于p2，即阶段1的顺序为
丁－>甲->乙->丙
同理可得阶段2的顺序为
丁－>甲->乙->丙
同理可得阶段3的顺序为
丁－>甲->乙->丙
可得面试不分次序与分次序得最优解一样。
六．模型的优劣分析
本问题是一个排列排序问题。
对于阶段数不小于3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如20）的情况是无法求解的。
因此人们找到了很多近似算法。
这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是多于学生数的平方。
因此，当学生数稍多一点儿规划模型的规模经很大，求解会花费很长时间。
而整数变量比较多时lingo求解速度会减慢。
此外，lingo的免费试用版对整数变量的个数的限制更加严格。
七．模型推广
这种模型可以应用于某工厂用n种原料经过s个阶段生产出不同的产品，并且是一种原料生产必须经过第一个阶段，然后经过第二个阶段直到第s个阶段才能生产出一种产品，并且一种原料在第k个阶段生产的时候，其他原料不能进行第k个阶段的生产。
原料i在j阶段生产的时间为c（i,j）i=1到n，j＝1到s。
问如何安排这n种原料的生产顺序?
使这n种产品在最短的时间内生产出来。
Lingo代码见附录（4）
参考文献
[1]．洪毅林建良等，数学模型，高等教育出版社，2004－05－1
[2].万宝成.LINGO8.0 for windows软件及应用（编译），2005－6－3
[3].作者未知,[数学建模]数学建模论文－人员面试问题,
2005－6－3
[4].刘京城、吕小苏、邓尚俊，学习数学建模有感
（2），
[5].作者未知.2005西南科技大学数学建模比赛培训材料
（一）
附录1：
min=t43+c43;
t11=0;
t12=t11+c11;
t13=t12+c12;
t21=t11+c11;
t22>t21+c21;
t22>t12+c12;
t23>t22+c22;
t23>t13+c13;
t31=t21+c21;
t32>t31+c31;
t32>t22+c22;
t33>t32+c32;
t33>t23+c23;
t41=t31+c31;
t42>t41+c41;
t42>t32+c32;
t43>t42+c42;
t43>t33+c33;
y11+y12+y13+y14=1;
y21+y22+y23+y24=1;
y31+y32+y33+y34=1;
y41+y42+y43+y44=1;
y11+y21+y31+y41=1;
y12+y22+y32+y42=1;
y13+y23+y33+y43=1;
y14+y24+y34+y44=1;
c11>13*y11+10*y12+20*y13+8*y14;
c12>15*y11+20*y12+16*y13+10*y14;
c13>20*y11+18*y12+10*y13+15*y14;
c21>13*y21+10*y22+20*y23+8*y24;
c22>15*y21+20*y22+16*y23+10*y24;
c23>20*y21+18*y22+10*y23+15*y24;
c31>13*y31+10*y32+20*y33+8*y34;
c32>15*y31+20*y32+16*y33+10*y34;
c33>20*y31+18*y32+10*y33+15*y34;
c41>13*y41+10*y42+20*y43+8*y44;
c42>15*y41+20*y42+16*y43+10*y44;
c43>20*y41+18*y42+10*y43+15*y44;
@bin（y11）;@bin（y12）;@bin（y13）;@bin（y14）;
@bin（y21）;@bin（y22）;@bin（y23）;@bin（y24）;
@bin（y31）;@bin（y32）;@bin（y33）;@bin（y34）;
@bin（y41）;@bin（y42）;@bin（y43）;@bin（y44）;
end
附录2
附录3
!
面试不分先后次序;
model:
sets:
persons;!
面试成员集;
stages;!
面试阶段集;
ps（persons,stages）:
c,t;
rt（persons,persons,stages）|&1#LT#&2:
w;
endsets
data:
persons=p1..p4;
stages=s1..s3;
c=
131520
102018
201610
81015;
enddata
np=@size（persons）;!
求职者人数;
ns=@size（stages）;!
阶段数;
!
每个求职者面试时间先后次序的约束;
@for（ps（I,J）|J#LT#ns:
t（i,j）+c（i,j）<=t（i,j+1）
）;
@for（rt（I,K,j）:
@for（stages（j）:
t（I,j）+c（I,j）-t（K,j）<=200*w（I,K,j）;
t（K,j）+c（K,j）-t（I,j）<=200*（1-w（I,K,j））;
）
）;!
在阶段j中求职者间满足的约束；
!
目标函数;
min=tt;
@for（persons（I）:
t（I,3）+c（I,3）<=tt
）;
@for（rt:
@bin（w））;!
定义0－1变量w（i，k,j）；
end
附录4
model:
sets:
material;
stages;!
阶段集;
ps（material,stages）:
c,t;
rt（material,material）|&1#LT#&2:
w;
endsets
data:
material=m1..mn;
stages=s1..ss;
c=
!
第i种原料在第j阶段生产所花费的时间矩阵
enddata
np=@size（material）;
ns=@size（stages）;!
阶段数;
@for（ps（I,J）|J#LT#ns:
t（i,j）+c（i,j）<=t（i,j+1）
）;
@for（rt（I,K）:
@for（stages（j）:
t（I,j）+c（I,j）-t（K,j）<=M*w（I,K）;
t（K,j）+c（K,j）-t（I,j）<=M*（1-w（I,K））;
）
）;
!
目标函数;
min=tt;
@for（material（I）:
t（I,s）+c（I,s）<=tt
）;
@for（rt:
@bin（w））;!
定义0－1变量w（i，k）；
end
升级会员 