面试顺序问题

1、面试顺序问题一、摘要本文立足现实生活中面试排序问题的特点， 站在面试者的角度， 要求整个面 试过程中使用时间最短，即所有面试者能最早离开公司，分析问题。首先，本文 的问题概述如下： 有 4 名同学到一家公司参加三个阶段的面试： 公司要求每个同 学都必须首先找公司秘书初试， 然后到部门主管处复试， 最后到经理处参加面试， 并且不允许插队（即在任何一个阶段 4 名同学的顺序是一样的） 。已知每个同学 在各个阶段面试所需时间（详见附录三） 。各同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最早何时能离开公司。针对这一问题，由于面试人数较少，运算量不大， 故可以运用枚举法将

2、所有面试的情况列举出来。 根据题目可知，共有 4 名同学参 加面试，不难得出， 4 名同学面试顺序的所有情况共有 24 种，然后计算出所有 情况下的面试结束时间， 根据比较， 可以得出题目要求下的最优结果， 枚举法虽 然解题效率相对要低，但是考虑的情况较为全面，得出的结果是可靠的。根据以上我们提到的枚举法解决该问题， 可能做了很多的无用功， 浪费了宝 贵的时间，效率低下。为此我们可以进行优化，对于枚举法产生的弊端，我们可 以运用 0-1 整数规划方法进行优化，根据题意建立较为优化的模型，建立相应的 目标函数和约束条件， 并且对目标函数进行进一步的改善， 能够提高解题的效率， 简化解决问题的过程

3、，最后将我们的模型在 lingo 中求解，得出结果与枚举法相 一致，即 4 名同学面试完成的最短时间是 84 分钟，并且给出面试时间最短排序 （丁-甲-乙-丙），为公司面试安排提供具有一定指导意义的建议。关键词： 面试问题 枚举法 0-1 整数线性规划二、问题重述题目给出有 4 名同学到一家公司参加三个阶段的面试， 公司要求每位同学都必须 首先找到公司秘书初试， 然后到主管处复试， 最后到经理处参加面试， 并且不允 许插队（即在任何一阶段， 4 名同学的顺序是一样的） 。由于 4 名同学的专业背 景不同，所以每人在三个阶段的面试时间也不同。表1秘书初试主观面试经理面试同学甲131520同学乙1

4、02018同学丙201610同学丁81015根据题意这四名同学约定他们全部面试完成后一起离开公司，现在时间是早晨8:00，本题需要我们给出一种最合理的排序方案，使得他们最早能够离开公司三、问题分析与基本假设在社会工作和生活中， 面试顺序问题十分常见。 题目中的面试流程分为三个 阶段，每一位面试官同时期只能面试一位同学， 下一名同学面试之前需要等待上 一位该阶段面试结束， 由于 4 名同学在任何一阶段的顺序是一样的， 公司在安排 面试顺序的时候只需要考虑一次， 使得总面试时间最短。 由于数据较少运用枚举 法可以得出真正正确的解。同时，这也是一个整数线性规划问题，针对本题，联系实际，可引入 0-1

5、 变 量，对目标函数进行优化求解。 在进行数据分析时， 不可能通过几个简单的假设 就建立出一个完美的数学模型， 这就需要对现有数据进行一个筛选， 并在此基础 上建立出简易的数学模型。因此，我们假设如下：（1）假设早晨时间 8:00为 0 时刻。2）假设上一位同学面试结束后，下一位同学立刻开始该阶段面试，且时间间 隔为 0。（3）假设整个面试过程中任何一位面试官都连续工作。（4）假设面试过程中没有任何同学退出。（5）假设同学和面试官都在早晨八点准时到场。（6）各位同学和各位面试官没有事先约定好面试顺序，整个过程公平公正四、基本符号说明枚举法符号说明：t ij表示第 i个人在第 j 轮面试结束的时

6、间xij 表示第 i 个人在第 j 轮面试所经历的时间Tk 表示每个面试顺序中每个面试者每轮面试结束时间矩阵Time表示各个同学完成各阶段面试的时刻Time1.finaltime 为每个面试顺序所对应的离开时间最优化方法符号说明：Xij 表示第 i 个人面试第 j 阶段所用的时间；Tij 表示第 i 个人面试第 j 阶段的开始时间；T 表示 4 个人面试完成的总时间；M ik 表示第 k 个人是否排在第 i 个人之前， M ik =1，表示第 k 个人排在第 i 个人之 前，否则， M ik =0i =1,2,3,4; k =1,2,3,4; j =1,2,3五、模型建立与求解（一）枚举法1.

7、模型概述设第i个人在第 j 轮面试结束的时间为 t ij ，所经历的时间为 xij， 每个面试顺 序中每个面试者每轮面试结束时间设为矩阵 Tk （0 k 24，24 A 44 ），则第一 个人在第一轮结束的时间为 tij xij，tij xij max t i-1j，ti j-1 ，则 t 43为最终结束时间。首先根据排列组合原理，可知所有面试顺序排列共有 A 44 24种确定每一种排序的面试结束时间为枚举对象， 则每个矩阵中最后一行最后一 列的时间即最早离开时间。根据题意编制模型如下：xiji 1, j1Timei j 1 xiji 1,2j4TimeijTime i 1 j xijj 1,

8、2i3xij max Time i 1 j ,Timei j 12i3,2j4利用 MATLAB求解结果， 得出每一种顺序下每位面试者结束时间矩阵 （去掉 了第一行第一列的固定时间） 。2.模型求解与算法流程图 为了使过程更加显而易见， 我们制作了简易的算法流程图， 其想法是全排列出每一种面试排序方法，然后建立计算公式分别计算每个面试者的结束时间。图1根据此思路我们用 MATLAB编写了相应程序得出8 10 158 18 33最优解 X 513 15 20，此顺序的面试者结束时间矩阵为 Time521 36 5610 20 1831 56 7420 16 1051 72 843.模型的优点（1

9、）结合了企业面试时的要求和特点，一一列举所有可能，得到的结果肯定是正确的。（2）算法直观，容易理解，易于证明其正确性。（3）模型稳定，结果贴近实际。5.模型的缺点和改进由于枚举法穷举了所有可能， 运算量比较大， 解题效率低下，如果枚举范围太大， 在时间上就难以承受， 所以我们可以在以下方面进行改进：（ 1）减少状态总数 （即减少枚举变量和枚举变量的值域） ，如采用隐枚举法可以 设定条件减持。（2）减少重复计算。 （3）将原问题化为更小的问题，比如考虑等待时间最小即结束时间最少的算法 实现。（二）优化模型1.模型建立 由于已知同学数量和阶段面试时间，只考虑固定一种顺序的情形，记Xij 表示第 i

10、 个同学面试第 j阶段所用的时间， Tij 表示第 i 个同学面试第 j 阶段的开始时 间。引入 0-1 变量 M ik， Mik 表示第 k个人是否排在第 i 个同学之前， Mik =1，表示第 k个人排在第 i个同学之前，否则， Mik =0。（i 1,2,3,4; j 1,2，3,4）ik1，第 k个人排在第 i个同学之前0，第 k个人排在第 i个同学之后则Xi3 为第i 个同学面试第 3 阶段所用时间 ,Ti3为第 i 个同学面试第 3 阶段的开始 时间，要求四人完成面试后同时离开则可知 Max（Xi3 Ti3） 表示四人完成面试后 的结束时间，设为为目标函数 T Max（ Xi3 T

11、i3）这样 T 越小则离开时间越早，于是对 0-1 整数线性规划模型进行改善，改写为MinT Max( Xi3 Ti3)TTTT同时根据面试中的四人必须同时离开，可以建立约束X13X23X33X43此外，结合原题1)每个人必须面试完上一轮才能开始下一轮面试Xij TijXij 1(i 1,2,3,4; j 1,2)2)每个阶段 j只能面试一个人 :用 0-1变量 Mik 表示第 k个人是否排在第 i个人之前，即第 k 个人排在第 i个人之前，M ik =1；否则，M ik =0。若 M ik=0， k排在i 后面XijTijX kj0(i,k1,2,3,4; j1,2,3;ik)X kjTkj

12、XijT(i,k1,2,3,4; j1,2,3;ik)若 M ik=1，则 k排在 i前面XijTijXkjT(i,k1,2,3,4; j1,2,3;ik)X kjTkjXij0(i,k1,2,3,4; j1,2,3;ik)综上所述，可得X ij TijX kjTM ik (i,k1,2,3,4; j1,2,3;ik)X kjTkjXijTM ik (i,k1,2,3,4; j1,2,3;ik)加上之前的一个约束，综上，最终得出一个 0-1 整数线性规划模型MinT Max( Xi3 Ti3)s.t.Xij Tij Xkj TM ik，(i,k 1,2,3,4; j 1,2,3;i k)Xkj

13、 Tkj Xij TM ik，(i, k 1,2,3,4; j 1,2,3;i k)X 13 T13 TX 23 T23 TX 33 T33 TX 43 T43 TMik1，第 k个人排在第 i个同学之前0，第 k个人排在第 i个同学之后 2.模型求解该题是一个 0-1 整数线性规划问题，直接利用 lingo 编程求解。计算结果见图 2 和附录二图2根据结果，能使四人最早同时离开的面试排序用时 84 分钟，同时计算并汇总出 各同学面试时间和开始时间如下表 2表2各阶段开始时间各阶段使用时间各阶段结束时间甲（秘书初试）81321甲（主管初试）211536甲（经理面试）362036乙（秘书初试）3

14、61036乙（主管初试）362056乙（经理面试）561874丙（秘书初试）362056丙（主管初试）561672丙（经理面试）741084丁（秘书初试）088丁（主管初试）81018丁（经理面试）211536图3图 4 显示了每位同学在各阶段面试时间长短的排序， 可以看出甲的主管面试、 乙 的秘书面试、丁的经理面试， 还有甲的经理面试、 乙的主管面试、 丙的秘书初试， 都分别是同时结束的。表3VariableValueM(S1,S2)0.000000M(S1,S3)0.000000M(S1,S4)1.000000M(S2,S3)0.000000M(S2,S4)1.000000M(S3,S4)

15、1.000000又根据表 5 的 0-1 变量运算结果可知最优面试排序为丁、甲、乙、丙，显然计算 结果与枚举法模型结果相一致，确定正确。（三）结果分析通过枚举法和规划方法， 最终可以确定， 公司应该安排四位同学按照丁、 甲、 乙、丙这样的顺序进行面试可以达到用时最短时间的效果， 即 84 分钟，早晨 9:24 面试结束 .枚举结果如下。表4序号面试顺序完成面试所用时间序号面试顺序完成面试所用时间1丁丙乙甲10213乙丙丁甲932丁丙甲乙9714乙丙甲丁963丁乙丙甲8915乙丁丙甲934丁乙甲丙8616乙丁甲丙935丁甲乙丙8417乙甲丁丙936丁甲丙乙9518乙甲丙丁937丙丁乙甲10419

16、甲丙乙丁1028丙丁甲乙9920甲丙丁乙979丙乙丁甲10921甲乙丙丁9110丙乙甲丁10922甲乙丁丙9111丙甲乙丁10423甲丁乙丙9112丙甲丁乙10424甲丁丙乙95如此一来同学可以完成共同离开的心愿， 且公司可以以最高效率工作。 但是 连续工作可能会导致面试官疲惫， 公司可以适当在面试过程中添加休息时间， 比 如在 56 分钟时进行休息，此时刚好第一、二位同学丁和甲三轮面试结束，乙第 二轮面试结束，丙第二轮面试尚未开始，所有人可以共同休息调整状态。图4图 2 为所有排序方法的结束用时计算结果， 可以看出各种顺序的用时差别相当大，当面试人数更多的时候， 这一差距会更加显着， 所以企

17、业合理安排面试顺 序的具有重要现实意义。六、模型评价与改进 本文首先通过枚举法列举出 24 种排序方案，并计算出每一种排序方式的所 用时间，虽然计算量较大，但程序较为容易实现，其正确性也较容易证明。但是 可以运用隐枚举法进行改进，提高解题效率。其次，构建了面试排队决策的优化模型， 通过目标函数， 从而建立成了一个 线性规划模型， 求地了所有同学排序情况下， 被排在最后的一个同学面试完时所 用总时间 T（也即排序后，从第一个同学参加第一阶段面试时开始计时，到最后 一个同学面试完最后一阶段的这段时间）中最小的一个，然后，又建立了一个 0-1 变量表示其约束条件，并使用 LINGO软件求解，所得结果

18、具有一定的正确性 和指导意义。 但是，本文只讨论了四个同学面试三个阶段的合理排序方法， 而没 有讨论更多同学面试更多的阶段的合理排序的解决方案， 从而使得面试总时间最 短。在实际应用中还存在许多更复杂但是类似相关的情形， 此时，若还用本文中 的解决方案未必是合理的。 因此，对更多同学面试更多的阶段的合理排序的解决 方案是进一步应该研究和改进的方向。七、参考文献1 姜启源，谢金星，叶俊 .数学模型（ 3 版） .北京：高等教育出版社， 2003.2 徐玖平，胡知能 .运筹学-数据决策 .北京：科学出版社， 2006.3 茆诗松，程依明，濮晓龙 .概率论与数理统计（第二版） .北京 :高等教育出版

19、 社， 20024 赵静，但琦，数学建模与数学实验 .北京 :高等教育出版社， 2003.5 Frank R.Giordano，Maurice D.Weir，William P.Fox（美）.数学建模 .叶其孝，姜启 源等译 .北京：机械工业出版社， 20056 宋兆基等 .MATLABA在科学计算中的应用 .北京：清华大学出版社。 2005.八、附录附录一：MATLAB程序： student(1).shijian=13 15 20; student(2).shijian=10 20 18; student(3).shijian=20 16 10;student(4).shijian=8 10

20、 15;%将各学生面试时间存到结构体 studentT=pailie(4,student) 构体 T%求到所有面试顺序所对应的面试时间存到结for i=1:24for i=1:24 string = sprintf(X%d, i) = T(i).rearray; ;eval(string);endend%将所有面试顺序所对应的面试时间保存为矩阵附录 1(pailie.m 的内容 )：function T = pailie( k,S) %k 为进行全排列的个数 A=1:k;Q=perms(A);%对 A 进行全排列得到的数组m,n=size(Q);%得到 Q 的大小for i=1:ma=Q(i,

21、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; %将全排列得到的面试者面试时间存到 T 结构体 end end for k=1:24string = 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(+

22、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); 束时间%对每一个面试顺序中第二个面

23、试者中秘书初始结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(3,1),k) sprintf(+X%d(4,1);,k) ;eval(string);束时间%对每一个面试顺序中第二个面试者中

24、秘书初始结endfor k=1:24for i=2:4for j=2:3formatSpec=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);% 结束时间%把每个面试顺序中每个面试者每轮面试剩下4 个endend end 则每个矩阵中最后一行最后一列的时间即最早离开时间 for i=1:24time(i).final=T(i).rearray(4,3);end for i=1:24 format=Time(i).finaltime=Time%d(4,3

25、);str1=sprintf(format,i);eval(str1);end%把 24 种面试顺序最终离开跌时刻输出为一个结构体bar(Time.finaltime)%把最终离开时刻做成一张柱状图运行结果：附录二：lingo程序：model: sets:students; !学生集三阶段面试模型 ; phases; !阶段集 ; sp(students,phases):t,x; ss(students,students)|&1 #LT# &2:m; end setsdata:students=s1.s4;phases=p1.p3;t=13 15 2010 20 1820 16 108 10

26、15;end datans=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定义

27、0-1变量;for(ss:bin(m); end运行结果：Global optimal solution found.Objective value:84.00000Objective bound:84.00000Infeasibilities:0.1532108E-13Extended solver steps:8Total solver iterations:598VariableValueReduced CostNS4.0000000.000000NP3.0000000.000000TMAX84.000000.000000T( S1, P1)13.000000.000000T( S1,

28、P2)15.000000.000000T( S1, P3)20.000000.000000T( S2, P1)10.000000.000000T( S2, P2)20.000000.000000T( S2, P3)18.000000.000000T( S3, P1)20.000000.000000T( S3, P2)16.000000.000000T( S3, P3)10.000000.000000T( S4, P1)8.0000000.000000T( S4, P2)10.000000.000000T( S4, P3)15.000000.000000X( S1, P1)8.0000000.0

29、00000X( S1, P2)21.000000.000000X( S1, P3)36.000000.000000X( S2, P1)26.000000.000000X( S2, P2)36.000000.000000X( S2, P3)56.000000.000000X( S3, P1)36.000000.000000X( S3, P2)56.000000.000000X( S3, P3)74.000000.000000X( S4, P1)0.0000001.000000X( S4, P2)8.0000000.000000X( S4, P3)21.000000.000000M( S1, S2)0.000000-200.0000M( S1, S3)0.0000000.000000M( S1, S4)1.000000200.0000M( S2, S3)0.000000-200.0000M( S2, S4)1.0000000.000000M( S3, S4)1.0000000.000000RowSlac