面试顺序问题

一、摘要

本文立足现实生活中面试排序问题的特点，站在面试者的角度，要求整个面试过程中使用时间最短，即所有面试者能最早离开公司，分析问题。首先，本文的问题概述如下：有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。已知每个同学在各个阶段面试所需时间（详见附录三）。

各同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最早何时能离开公司。针对这一问题，由于面试人数较少，运算量不大，故可以运用枚举法将所有面试的情况列举出来。根据题目可知，共有4名同学参加面试，不难得出，4名同学面试顺序的所有情况共有24种，然后计算出所有情况下的面试结束时间，根据比较，可以得出题目要求下的最优结果，枚举法虽然解题效率相对要低，但是考虑的情况较为全面，得出的结果是可靠的。

根据以上我们提到的枚举法解决该问题，可能做了很多的无用功，浪费了宝贵的时间，效率低下。为此我们可以进行优化，对于枚举法产生的弊端，我们可以运用0-1整数规划方法进行优化，根据题意建立较为优化的模型，建立相应的目标函数和约束条件，并且对目标函数进行进一步的改善，能够提高解题的效率，简化解决问题的过程，最后将我们的模型在lingo中求解，得出结果与枚举法相一致，即4名同学面试完成的最短时间是84分钟，并且给出面试时间最短排序（丁-甲-乙-丙），为公司面试安排提供具有一定指导意义的建议。

关键词：面试问题 枚举法 0-1整数线性规划

1

二、问题重述

题目给出有4名同学到一家公司参加三个阶段的面试，公司要求每位同学都必须首先找到公司秘书初试，然后到主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一阶段，4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同。

表 1

同学甲 同学乙 同学丙 同学丁

秘书初试 13 10 20 8 主观面试 15 20 16 10 经理面试 20 18 10 15 根据题意这四名同学约定他们全部面试完成后一起离开公司，现在时间是早晨8:00，本题需要我们给出一种最合理的排序方案，使得他们最早能够离开公司。

三、问题分析与基本假设

在社会工作和生活中，面试顺序问题十分常见。题目中的面试流程分为三个阶段，每一位面试官同时期只能面试一位同学，下一名同学面试之前需要等待上一位该阶段面试结束，由于4名同学在任何一阶段的顺序是一样的，公司在安排面试顺序的时候只需要考虑一次，使得总面试时间最短。由于数据较少运用枚举法可以得出真正正确的解。

同时，这也是一个整数线性规划问题，针对本题，联系实际，可引入0-1变量，对目标函数进行优化求解。在进行数据分析时，不可能通过几个简单的假设就建立出一个完美的数学模型，这就需要对现有数据进行一个筛选，并在此基础上建立出简易的数学模型。因此，我们假设如下： （1）假设早晨时间8:00为0时刻。

（2）假设上一位同学面试结束后，下一位同学立刻开始该阶段面试，且时间间

2

隔为0。

（3）假设整个面试过程中任何一位面试官都连续工作。 （4）假设面试过程中没有任何同学退出。 （5）假设同学和面试官都在早晨八点准时到场。

（6）各位同学和各位面试官没有事先约定好面试顺序，整个过程公平公正

四、基本符号说明

枚举法符号说明：

tij表示第i个人在第j轮面试结束的时间 xij表示第i个人在第j轮面试所经历的时间

Tk表示每个面试顺序中每个面试者每轮面试结束时间矩阵

Time表示各个同学完成各阶段面试的时刻

Time1.finaltime为每个面试顺序所对应的离开时间

最优化方法符号说明：

Xij表示第i个人面试第j阶段所用的时间；

Tij表示第i个人面试第j阶段的开始时间；

T表示4个人面试完成的总时间；

Mik表示第k个人是否排在第i个人之前，Mik =1，表示第k个人排在第i个人之

前，否则，Mik=0

i=1,2,3,4; k=1,2,3,4; j=1,2,3

五、模型建立与求解

（一）枚举法 1.模型概述

设第i个人在第j轮面试结束的时间为tij，所经历的时间为xij， 每个面试顺序中每个面试者每轮面试结束时间设为矩阵Tk（0k24，24A4，则第4）一个人在第一轮结束的时间为tijxij，tijxijmaxti-1j，tij-1，则t43为最终结束时间。首先根据排列组合原理，可知所有面试顺序排列共有A4424种。

3

确定每一种排序的面试结束时间为枚举对象，则每个矩阵中最后一行最后一列的时间即最早离开时间。

根据题意编制模型如下：

xijTimeij1xijTimeijTimei1jxijxmaxTimei1j,Timeij1iji1,j1i1,2j4

j1,2i32i3,2j4利用MATLAB求解结果，得出每一种顺序下每位面试者结束时间矩阵（去掉了第一行第一列的固定时间）。 2.模型求解与算法流程图

为了使过程更加显而易见，我们制作了简易的算法流程图，其想法是全排列出每一种面试排序方法，然后建立计算公式分别计算每个面试者的结束时间。

图 1

根据此思路我们用MATLAB编写了相应程序得出

4

8101581833最优解X5131520102018201610，此顺序的面试者结束时间矩阵为Time5213656315674517284

3.模型的优点

（1）结合了企业面试时的要求和特点，一一列举所有可能，得到的结果肯定是正确的。

（2）算法直观，容易理解，易于证明其正确性。 （3）模型稳定，结果贴近实际。 5.模型的缺点和改进

由于枚举法穷举了所有可能，运算量比较大，解题效率低下，如果枚举范围太大，在时间上就难以承受， 所以我们可以在以下方面进行改进：

（1）减少状态总数（即减少枚举变量和枚举变量的值域），如采用隐枚举法可以设定条件减持。 （2）减少重复计算。

（3）将原问题化为更小的问题，比如考虑等待时间最小即结束时间最少的算法实现。

（二）优化模型 1.模型建立

由于已知同学数量和阶段面试时间，只考虑固定一种顺序的情形，记Xij表示第i个同学面试第j阶段所用的时间，Tij表示第i个同学面试第j阶段的开始时间。引入0-1变量Mik，Mik表示第k个人是否排在第i个同学之前，Mik=1，表示第k个人排在第i个同学之前，否则，Mik=0。(i1,2,3,4;j1,2，3,4)

1，第k个人排在第i个同学之前Mik

0，第k个人排在第i个同学之后则Xi3为第i个同学面试第3阶段所用时间,Ti3为第i个同学面试第3阶段的开始时间，要求四人完成面试后同时离开则可知Max(Xi3Ti3)表示四人完成面试后的结束时间，设为为目标函数TMax(Xi3Ti3)。

5

这样T越小则离开时间越早，于是对0-1整数线性规划模型进行改善，改写为

MinTMax(Xi3Ti3)

同时根据面试中的四人必须同时离开，可以建立约束

X13T13TXTT2323



XTT3333X43T43T

此外，结合原题

（1）每个人必须面试完上一轮才能开始下一轮面试

XijTijXij1(i1,2,3,4;j1,2)

（2）每个阶段j只能面试一个人:用0-1变量Mik表示第k个人是否排在第i个人之前，即第k个人排在第i个人之前，Mik=1；否则，Mik=0。 若Mik=0，k排在i后面

XijTijXkj0(i,k1,2,3,4;j1,2,3;ik) XkjTkjXijT(i,k1,2,3,4;j1,2,3;ik)

若Mik=1，则k排在i前面

XijTijXkjT(i,k1,2,3,4;j1,2,3;ik) XkjTkjXij0(i,k1,2,3,4;j1,2,3;ik)

综上所述，可得

XijTijXkjTMik(i,k1,2,3,4;j1,2,3;ik) XkjTkjXijTMik(i,k1,2,3,4;j1,2,3;ik)

加上之前的一个约束，综上，最终得出一个0-1整数线性规划模型

MinTMax(Xi3Ti3)

s.t.

XijTijXkjTMik，(i,k1,2,3,4;j1,2,3;ik)

6

XkjTkjXijTMik，(i,k1,2,3,4;j1,2,3;ik)

X13T13TX23T23TX33T33TX43T43T

1，第k个人排在第i个同学之前Mik

0，第k个人排在第i个同学之后2.模型求解

该题是一个0-1整数线性规划问题，直接利用lingo编程求解。计算结果见图2和附录二。

图 2

根据结果，能使四人最早同时离开的面试排序用时84分钟，同时计算并汇总出各同学面试时间和开始时间如下表2。

表 2

甲（秘书初试） 甲（主管初试） 甲（经理面试） 乙（秘书初试） 乙（主管初试） 乙（经理面试） 丙（秘书初试） 各阶段开始时间 8 21 36 36 36 56 36 7

各阶段使用时间 13 15 20 10 20 18 20 各阶段结束时间 21 36 36 36 56 74 56

丙（主管初试） 丙（经理面试） 丁（秘书初试） 丁（主管初试） 丁（经理面试） 56 74 0 8 21 16 10 8 10 15 72 84 8 18 36 各同学各阶段面试时间及排序9080706050403020100各阶段使用时间各阶段开始时间 图 3

图4显示了每位同学在各阶段面试时间长短的排序，可以看出甲的主管面试、乙的秘书面试、丁的经理面试，还有甲的经理面试、乙的主管面试、丙的秘书初试，都分别是同时结束的。

表 3

Variable M(S1,S2) M(S1,S3) M(S1,S4) M(S2,S3) M(S2,S4) M(S3,S4) Value 0.000000 0.000000 1.000000 0.000000 1.000000 1.000000

又根据表5的0-1变量运算结果可知最优面试排序为丁、甲、乙、丙，显然计算结果与枚举法模型结果相一致，确定正确。 （三）结果分析

通过枚举法和规划方法，最终可以确定，公司应该安排四位同学按照丁、甲、乙、丙这样的顺序进行面试可以达到用时最短时间的效果，即84分钟，早晨9:24面试结束.枚举结果如下。

8

表 4

完成面试所序号 1 2 3 4 5 6 7 8 9 10 11 12 面试顺序 用时间 丁丙乙甲 丁丙甲乙 丁乙丙甲 丁乙甲丙 丁甲乙丙 丁甲丙乙 丙丁乙甲 丙丁甲乙 丙乙丁甲 丙乙甲丁 丙甲乙丁 丙甲丁乙 102 97 89 86 84 95 104 99 109 109 104 104 13 14 15 16 17 18 19 20 21 22 23 24 乙丙丁甲 乙丙甲丁 乙丁丙甲 乙丁甲丙 乙甲丁丙 乙甲丙丁 甲丙乙丁 甲丙丁乙 甲乙丙丁 甲乙丁丙 甲丁乙丙 甲丁丙乙 序号 面试顺序 完成面试所用时间 93 96 93 93 93 93 102 97 91 91 91 95

如此一来同学可以完成共同离开的心愿，且公司可以以最高效率工作。但是连续工作可能会导致面试官疲惫，公司可以适当在面试过程中添加休息时间，比如在56分钟时进行休息，此时刚好第一、二位同学丁和甲三轮面试结束，乙第二轮面试结束，丙第二轮面试尚未开始，所有人可以共同休息调整状态。

图 4

图2为所有排序方法的结束用时计算结果，可以看出各种顺序的用时差别相当大，当面试人数更多的时候，这一差距会更加显著，所以企业合理安排面试顺序的具有重要现实意义。

9

六、模型评价与改进

本文首先通过枚举法列举出24种排序方案，并计算出每一种排序方式的所用时间，虽然计算量较大，但程序较为容易实现，其正确性也较容易证明。但是可以运用隐枚举法进行改进，提高解题效率。

其次，构建了面试排队决策的优化模型，通过目标函数，从而建立成了一个线性规划模型，求地了所有同学排序情况下，被排在最后的一个同学面试完时所用总时间T（也即排序后，从第一个同学参加第一阶段面试时开始计时，到最后一个同学面试完最后一阶段的这段时间）中最小的一个，然后，又建立了一个0-1变量表示其约束条件，并使用LINGO软件求解，所得结果具有一定的正确性和指导意义。但是，本文只讨论了四个同学面试三个阶段的合理排序方法，而没有讨论更多同学面试更多的阶段的合理排序的解决方案，从而使得面试总时间最短。在实际应用中还存在许多更复杂但是类似相关的情形，此时，若还用本文中的解决方案未必是合理的。因此，对更多同学面试更多的阶段的合理排序的解决方案是进一步应该研究和改进的方向。

七、参考文献

[1] 姜启源，谢金星，叶俊.数学模型（3版）.北京：高等教育出版社，2003. [2] 徐玖平，胡知能.运筹学-数据·决策.北京：科学出版社，2006.

[3] 茆诗松，程依明，濮晓龙.概率论与数理统计（第二版）.北京:高等教育出版社，2002

[4] 赵静，但琦，数学建模与数学实验.北京:高等教育出版社，2003. [5] Frank R.Giordano，Maurice D.Weir，William P.Fox(美).数学建模.叶其孝，姜启源等译.北京：机械工业出版社，2005

[6] 宋兆基等.MATLABA在科学计算中的应用.北京：清华大学出版社。2005.

10

八、附录

附录一： MATLAB程序：

student(1).shijian=[13 15 20]; student(2).shijian=[10 20 18]; student(3).shijian=[20 16 10]; student(4).shijian=[8 10 15]; student

T=pailie(4,student) 结构体T for i=1:24 for i=1:24

string = [sprintf('X%d', i) ' = T(i).rearray;' ]; eval(string); end end

%将所有面试顺序所对应的面试时间保存为矩阵

%求到所有面试顺序所对应的面试时间存到

%将各学生面试时间存到结构体

附录1（pailie.m的内容)：function [T] = pailie( k,S) %k为进行全排列的个数 A=1:k; Q=perms(A);

%对A进行全排列得到的数组

%得到Q的大小

[m,n]=size(Q); for i=1:m a=Q(i,1); b=Q(i,2); c=Q(i,3); d=Q(i,4);

T(i).rearray=[S(a).shijian;S(b).shijian;S(c).shijian;S(d).shijian]; end

11

%将全排列得到的面试者面试时间存到T结构体

end for k=1:24

string = [sprintf('Time%d(1,1)', k) sprintf(' = X%d(1,1);',k) ]; eval(string); 结束时间

string = [sprintf('Time%d(1,2)', k) sprintf(' = X%d(1,1)',k) sprintf('+X%d(1,2);',k) ]; eval(string); 结束时间

string = [sprintf('Time%d(1,3)', k) sprintf(' = X%d(1,1)',k) sprintf('+X%d(1,2)',k) sprintf('+X%d(1,3);',k) ]; eval(string); 结束时间

string = [sprintf('Time%d(2,1)', k) sprintf(' = X%d(1,1)',k) sprintf('+X%d(2,1);',k) ]; eval(string); 结束时间

string = [sprintf('Time%d(3,1)', k) sprintf( ' = X%d(1,1)',k) sprintf('+X%d(2,1)',k) sprintf('+X%d(3,1);',k) ]; eval(string); 结束时间

string = [sprintf('Time%d(4,1)', k) sprintf(' = X%d(1,1)',k) sprintf('+X%d(2,1)',k) sprintf('+X%d(4,1);',k) ]; eval(string); 结束时间 end for k=1:24 for i=2:4

12

%对每一个面试顺序中第一个面试者中秘书初始

%对每一个面试顺序中第一个面试者中主管复试

%对每一个面试顺序中第一个面试者中经理面试

%对每一个面试顺序中第二个面试者中秘书初始

%对每一个面试顺序中第二个面试者中秘书初始

sprintf('+X%d(3,1)',k)

%对每一个面试顺序中第二个面试者中秘书初始

for j=2:3

formatSpec='Time%d(i,j)=X%d(i,j)+max(Time%d(i-1,j),Time%d(i,j-1));'; str=sprintf(formatSpec,k,k,k,k); eval(str);% 个结束时间 end end end

则每个矩阵中最后一行最后一列的时间即最早离开时间 for i=1:24

time(i).final=T(i).rearray(4,3); end

>> for i=1:24

format='Time(i).finaltime=Time%d(4,3);'; str1=sprintf(format,i); eval(str1); end 体

bar([Time.finaltime]) 运行结果：

其余数值结果冗长，故不予表述。

%把最终离开时刻做成一张柱状图

%把24种面试顺序最终离开跌时刻输出为一个结构

%把每个面试顺序中每个面试者每轮面试剩下4

13

1201008060402000510152025

附录二： lingo程序： model: sets:

students; !学生集三阶段面试模型; phases; !阶段集;

sp(students,phases):t,x;

ss(students,students)|&1 #LT# &2:m; end sets data:

students=s1..s4; phases=p1..p3; t= 13 15 20 10 20 18 20 16 10

14

8 10 15; end data

ns=@size(students); !学生数; np=@size(phases); !阶段数; !单个学生面试时间先后次序的约束; @for(sp(i,j)|j #LT# np: x(i,j)+t(i,j)<=x(i,j+1) );

!学生间的面试先后次序保持不变的约束; @for(ss(i,k): @for(phases(j):

x(i,j)+t(i,j)-x(k,j)<=200*m(i,k); x(k,j)+t(k,j)-x(i,j)<=200*(1-m(i,k)); ) );

!目标函数; min=TMAX;

@for(students(i): x(i,3)+t(i,3)<=TMAX );

!把Y定义0-1变量; @for(ss:@bin(m)); end 运行结果：

Global optimal solution found.

Objective value: 84.00000 Objective bound: 84.00000 Infeasibilities: 0.1532108E-13 Extended solver steps: 8

15

Total solver iterations: 598

Variable Value Reduced Cost NS 4.000000 0.000000 NP 3.000000 0.000000 TMAX 84.00000 0.000000 T( S1, P1) 13.00000 0.000000 T( S1, P2) 15.00000 0.000000 T( S1, P3) 20.00000 0.000000 T( S2, P1) 10.00000 0.000000 T( S2, P2) 20.00000 0.000000 T( S2, P3) 18.00000 0.000000 T( S3, P1) 20.00000 0.000000 T( S3, P2) 16.00000 0.000000 T( S3, P3) 10.00000 0.000000 T( S4, P1) 8.000000 0.000000 T( S4, P2) 10.00000 0.000000 T( S4, P3) 15.00000 0.000000 X( S1, P1) 8.000000 0.000000 X( S1, P2) 21.00000 0.000000 X( S1, P3) 36.00000 0.000000 X( S2, P1) 26.00000 0.000000 X( S2, P2) 36.00000 0.000000 X( S2, P3) 56.00000 0.000000 X( S3, P1) 36.00000 0.000000 X( S3, P2) 56.00000 0.000000 X( S3, P3) 74.00000 0.000000 X( S4, P1) 0.000000 1.000000

16

X( S4, P2) 8.000000 0.000000 X( S4, P3) 21.00000 0.000000 M( S1, S2) 0.000000 -200.0000 M( S1, S3) 0.000000 0.000000 M( S1, S4) 1.000000 200.0000 M( S2, S3) 0.000000 -200.0000 M( S2, S4) 1.000000 0.000000 M( S3, S4) 1.000000 0.000000

Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 0.000000 0.000000 3 5.000000 0.000000 4 172.0000 0.000000 5 0.000000 1.000000 6 165.0000 0.000000 7 0.000000 0.000000 8 162.0000 0.000000 9 15.00000 0.000000 10 152.0000 0.000000 11 20.00000 0.000000 12 149.0000 0.000000 13 18.00000 0.000000 14 152.0000 0.000000 15 179.0000 0.000000 16 0.000000 1.000000 17 172.0000 0.000000 18 3.000000 0.000000 19 165.0000 0.000000

17

20 0.000000 0.000000 21 0.000000 0.000000 22 170.0000 0.000000 23 0.000000 0.000000 24 164.0000 0.000000 25 0.000000 1.000000 26 172.0000 0.000000 27 164.0000 0.000000 28 18.00000 0.000000 29 152.0000 0.000000 30 18.00000 0.000000 31 147.0000 0.000000 32 20.00000 0.000000 33 144.0000 0.000000 34 28.00000 0.000000 35 136.0000 0.000000 36 38.00000 0.000000 37 137.0000 0.000000 38 38.00000 0.000000 39 84.00000 -1.000000 40 28.00000 0.000000 41 10.00000 0.000000 42 0.000000 1.000000 43 48.00000 0.000000 44 0.000000 1.000000 45 0.000000 0.000000 46 0.000000 0.000000 47 0.000000 1.000000 48 0.000000 0.000000

18

49 2.000000 0.000000 50 0.000000 0.000000 51 3.000000 0.000000

附录三：

同学甲 同学乙 同学丙 同学丁

秘书初试 13 10 20 8 主观面试 15 20 16 10 经理面试 20 18 10 15 19