面试顺序问题复习过程

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

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

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

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

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

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

7、j Xij， tij Xij max t i-1 j, ti j-1，则t43为最终结束时间。首先根据排列组合原理，可知所有面试顺序排列共有a 4 24确定每一种排序的面试结束时间为枚举对象，则每个矩阵中最后一行最后 一列的时间即最早离开时间。根据题意编制模型如下:Xji 1,j1Time j iXji 1,2j4TimeijTimei 1 j xijj 1,2i3xij max Timei 1 j ,Timei j 12 i3,2j 4利用MATLA求解结果，得出每一种顺序下每位面试者结束时间矩阵（去掉 了第一行第一列的固定时间）。2. 模型求解与算法流程图为了使过程更加显而易见，我们制作了

8、简易的算法流程图，其想法是全排 列出每一种面试排序方法，然后建立计算公式分别计算每个面试者的结束时 间。根据此思路我们用MATLABS写了相应程序得出8101581833最优解X5131520，此顺序的面试者结束时间矩阵为Time521365610 20 1831567420 16 105172843.模型的优点（1）结合了企业面试时的要求和特点，一一列举所有可能，得到的结果肯定是正确的。（2）算法直观，容易理解，易于证明其正确性。（3）模型稳定，结果贴近实际。5.模型的缺点和改进由于枚举法穷举了所有可能， 运算量比较大，解题效率低下，如果枚举范围太大，在时间上就难以承受，所以我们可以在以下方

9、面进行改进：（1）减少状态总数（即减少枚举变量和枚举变量的值域），如采用隐枚举法可 以设定条件减持。（2）减少重复计算。（3）将原问题化为更小的问题，比如考虑等待时间最小即结束时间最少的算法 实现。（二）优化模型1. 模型建立由于已知同学数量和阶段面试时间，只考虑固定一种顺序的情形，记Xj表示第i个同学面试第j阶段所用的时间，Tj表示第i个同学面试第j阶段的开始 时间。引入0-1变量Mik，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个

10、同学之后 则Xi3为第i个同学面试第3阶段所用时间，丁3为第i个同学面试第3阶段的开始时间，要求四人完成面试后同时离开则可知Max(Xi3 Ti3)表示四人完成面试后的结束时间，设为为目标函数T Max(Xi3 Ti3)。这样T越小则离开时间越早，于是对0-1整数线性规划模型进行改善，改写为MinT Max(Xi3 Ti3)同时根据面试中的四人必须同时离开，可以建立约束X13 T13 TX 23 T23 TX 33 T33 TX43 T43 T此外，结合原题(1) 每个人必须面试完上一轮才能开始下一轮面试Xj TjXj !(i 1,2,3,4; j 1,2)(2) 每个阶段j只能面试一个人：用

11、0-1变量Mik表示第k个人是否排在第i个 人之前，即第k个人排在第i个人之前，Mik=1;否则，Mik=0。若 Mik =0,k排在i后面XjTjXkj0(i,k1,234; j1,2,3; ik)X kjTkjXjT(i,k1,234; j1,2,3; ik)若 Mik=1,则k排在i 前面XjTjX kjT(i,k1,234; j1,2,3; ik)XkjTkjXj0(i,k1,2,3,4; j1,2,3;ik)综上所述，可得XijTjXkjTM ik(i,k1,2,3,4; j1,2,3; ik)XkjTkjXjTM ik(i,k1,2,3,4; j1,2,3; ik)加上之前的一个约

12、束，综上，最终得出一个0-1整数线性规划模型Mi nT Max(Xi3 Ti3)s.t.XjTjXkj TM ik,i,k 1,2,3,4; j 1,2,3;i k)XkjTkjXj TM ik ,i,k 1,2,3,4; j 1,2,3; i k)X13T13TX 23T23TX33T33TX 43T43TMik1,第k个人排在第i个同学之前0,第k个人排在第i个同学之后2. 模型求解该题是一个0-1整数线性规划问题，直接利用lingo编程求解。计算结果见图2和附录二ILTs>tdISonline uv；0Global Optjjectlre.94pCrtntrai ntsasilil

13、i =y；1 S32L1B-01459849DiiiiMsr：0Vi"补于卄绘沁吐mSilvarBandEoiJiLk.«r.094G#m*T6tor Man cry l5*J (刃0l> J E OIJJL d:Q4270Elapsed timt:me I.EK： nm： ss)0OC：Q0-OCLINGO 11.0 Soil/er Status Lingo 1 Sohtr StatusUpdateiELts-rnipt ScrlverClose图2根据结果，能使四人最早同时离开的面试排序用时84分钟，同时计算并汇总出各同学面试时间和开始时间如下表 2表2各阶段开始

14、时间各阶段使用时间各阶段结束时间甲（秘书初试）81321甲（主管初试）211536甲（经理面试）362036乙（秘书初试）361036乙（主管初试）362056乙（经理面试）561874丙（秘书初试）362056丙（主管初试）561672丙（经理面试）741084丁（秘书初试）088丁（主管初试）81018丁（经理面试）211536各同学各阶段面试时间及排序各阶段使用时间各阶段开始时间住覚、瓷' 生' 童、配=養、住冷賣、住、 X "-ii -jO*" 'JO-6,F1. -C-k «.CC-44仗仗4令1?仑0化 金图4显示了每位同学在各

15、阶段面试时间长短的排序，可以看出甲的主管面试、 乙的秘书面试、丁的经理面试，还有甲的经理面试、乙的主管面试、丙的秘书 初试，都分别是同时结束的。VariableValueM(S1,S2)0.000000M(S1,S3)0.000000M(S1,S4)1.000000M(S2,S3)0.000000M(S2,S4)1.000000M(S3,S4)1.000000又根据表5的0-1变量运算结果可知最优面试排序为丁、甲、乙、丙，显然计 算结果与枚举法模型结果相一致，确定正确。（三）结果分析通过枚举法和规划方法，最终可以确定，公司应该安排四位同学按照丁、甲、乙、丙这样的顺序进行面试可以达到用时最短时间

16、的效果，即84分钟，早晨9:24面试结束.枚举结果如下。表4序号面试顺序完成面试所用时间序号面试顺序完成面试所用时间1丁丙乙甲10213乙丙丁甲932丁丙甲乙9714乙丙甲丁963丁乙丙甲8915乙丁丙甲934丁乙甲丙8616乙丁甲丙935丁甲乙丙8417乙甲丁丙936丁甲丙乙9518乙甲丙丁937丙丁乙甲10419甲丙乙丁1028丙丁甲乙9920甲丙丁乙979丙乙丁甲10921甲乙丙丁9110丙乙甲丁10922甲乙丁丙9111丙甲乙丁10423甲丁乙丙9112丙甲丁乙10424甲丁丙乙95如此一来同学可以完成共同离开的心愿，且公司可以以最高效率工作。但 是连续工作可能会导致面试官疲惫，公司可

17、以适当在面试过程中添加休息时 间，比如在56分钟时进行休息，此时刚好第一、二位同学丁和甲三轮面试结 束，乙第二轮面试结束，丙第二轮面试尚未开始，所有人可以共同休息调整状 态。H' r 一 e " U口IUOJ£!4图2为所有排序方法的结束用时计算结果，可以看出各种顺序的用时差别 相当大，当面试人数更多的时候，这一差距会更加显著，所以企业合理安排面 试顺序的具有重要现实意义。六、模型评价与改进本文首先通过枚举法列举出24种排序方案，并计算出每一种排序方式的所 用时间，虽然计算量较大，但程序较为容易实现，其正确性也较容易证明。但 是可以运用隐枚举法进行改进，提高解题效率

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

19、的。因此，对更多同学面试更多的阶 段的合理排序的解决方案是进一步应该研究和改进的方向。七、参考文献1姜启源，谢金星，叶俊数学模型（3版）北京：高等教育出版社，2003. 2徐玖平，胡知能.运筹学-数据决策.北京：科学出版社，2006.3 茆诗松，程依明，濮晓龙.概率论与数理统计（第二版）.北京：高等教育出 版社，20024 赵静，但琦，数学建模与数学实验.北京：高等教育出版社，2003. Frank R.Giordano, Maurice D.Weir , William P.Fox（ 美）.数学建模.叶其孝，姜启源等译.北京：机械工业出版社，2005 宋兆基等.MATLABA在科学计算中的应

20、用.北京：清华大学出版社。2005.八、附录附录一：MATLA程 序：stude nt(1).shijia n=13 15 20;stude nt(2).shijia n=10 20 18;stude nt(3) .shijia n=20 16 10;stude nt(4).shijia n=8 10 15;%各各学生面试时间存到结构体stude ntT=pailie(4,stude nt)%求到所有面试顺序所对应的面试时间存到结构体Tfor i=1:24for i=1:24stri ng = spri ntf('X%d', i) ' = T(i).rearray;&#

21、39;eval(stri ng);endend%各所有面试顺序所对应的面试时间保存为矩阵附录 1 (pailie.m 的内容)：function T = pailie( k,S)%k为进行全排列的个数A=1:k;Q=perms(A);m, n=size(Q);for i=1:m%对A进行全排列得到的数组%寻到Q的大小a=Q(i,1);b=Q(i,2);c=Q(i,3);d=Q(i,4);T(i).rearray=S(a).shijia n; S(b).shijia n;S(c).shijia n; S(d).shijia n;%将全排列得到的面试者面试时间存到T结构体endendfor k=1

22、:24stri ng = spri ntf('Time%d(1,1)', k) spri ntf(' = X%d(1,1);',k);eval(stri ng);%对每一个面试顺序中第一个面试者中秘书初始结束时间stri ng = spri ntf('Time%d(1,2)', k) spri ntf(' = X%d(1,1) ',k)spri ntf('+X%d(1,2);',k);eval(stri ng);%对每一个面试顺序中第一个面试者中主管复试结束时间stri ng = spri ntf('Tim

23、e%d(1,3)', k) spri ntf(' = X%d(1,1) ',k)spri ntf('+X%d(1,2) ',k) spri ntf('+X%d(1,3);',k);eval(stri ng);%对每一个面试顺序中第一个面试者中经理面试结束时间stri ng = spri ntf('Time%d(2,1)', k) spri ntf(' = X%d(1,1) ',k)spri ntf('+X%d(2,1);',k);eval(stri ng);%对每一个面试顺序中第二个面试者中

24、秘书初始结束时间 stri ng = spri ntf('Time%d(3,1)', k) spri ntf( ' = X%d(1,1) ：k)spri ntf('+X%d(2,1)', k) spri ntf('+X%d(3,1);',k);eval(stri ng);%对每一个面试顺序中第二个面试者中秘书初始结束时间stri ng = spri ntf('Time%d(4,1)', k) spri ntf(' = X%d(1,1) ',k)spri ntf('+X%d(2,1)', k)

25、 spri ntf('+X%d(3,1) ',k)spri ntf('+X%d(4,1);',k);eval(stri ng);%对每一个面试顺序中第二个面试者中秘书初始结束时间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=spri ntf(formatSpec,k,k,k,k);eval(str);%把每个面试顺序中每个面试者每轮面试剩下4个结束时间endendend则每个矩阵中最后一行最后

26、一列的时间即最早离开时间for i=1:24time(i).fi nal=T(i).rearray(4,3);end>> for i=1:24format='Time(i).fi naltime=Time%d(4,3);'str仁spri ntf(format,i);eval(str1);end%把24种面试顺序最终离开跌时刻输出为一个结构体bar(Time.fi naltime)%把最终离开时刻做成一张柱状图运行结果：附录二：lingo程序：model:sets :students;!学生集三阶段面试模型phases; !阶段集;sp(stude nts,phas

27、es):t,x;ss(stude nts,stude nts)|&1 #LT# & 2:m; end setsdata : stude nts=s1.s4;phases=p1.p3;t=13 15 2010 20 1820 16 108 10 15;end datans=size(students);!学生数;np=size(phases); !阶段数;!单个学生面试时间先后次序的约束；for(sp(i,j)|j #LT# np:x(i,j)+t(i,j)v=x(i,j+1);!学生间的面试先后次序保持不变的约束for(ss(i,k):for(phases(j):x(i,j)+

28、t(i,j)-x(k,j)v=200*m(i,k);x(k,j)+t(k,j)-x(i,j)v=200*(1-m(i,k););!目标函数；mi n=TMAX;for(stude nts(i):x(i,3)+t(i,3)<=TMAX);!把丫定义0-1变量；for(ss: bin(m);end运行结果：Global optimal solutio n found.Objective value:84.00000Objective bound:84.00000In feasibilities:0.1532108E-13Exte nded solver steps:8Total solver

29、 iteratio ns:598VariableValueReduced CostNS4.0000000.000000NP3.0000000.000000TMAX84.000000.000000T( S1, P1)13.000000.000000T( S1, 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.0

30、00000T( S3, P3)10.000000.000000T( S4, P1)8.0000000.000000T( S4, P2)10.000000.000000T( S4, P3)15.000000.000000X( S1, P1)8.0000000.000000X( 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.0000