2022年面试顺序问题 .pdf

《2022年面试顺序问题 .pdf》由会员分享，可在线阅读，更多相关《2022年面试顺序问题 .pdf（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

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

4、同。表 1秘书初试主观面试经理面试同学甲13 15 20 同学乙10 20 18 同学丙20 16 10 同学丁8 10 15 根据题意这四名同学约定他们全部面试完成后一起离开公司，现在时间是早晨8:00 ，此题需要我们给出一种最合理的排序方案，使得他们最早能够离开公司。三、问题分析与基本假设在社会工作和生活中， 面试顺序问题十分常见。 题目中的面试流程分为三个阶段，每一位面试官同时期只能面试一位同学，下一名同学面试之前需要等待上一位该阶段面试结束， 由于 4 名同学在任何一阶段的顺序是一样的，公司在安排面试顺序的时候只需要考虑一次，使得总面试时间最短。 由于数据较少运用枚举法可以得出真正正确

5、的解。同时，这也是一个整数线性规划问题，针对此题，联系实际，可引入0-1变量，对目标函数进行优化求解。 在进行数据分析时， 不可能通过几个简单的假设就建立出一个完美的数学模型，这就需要对现有数据进行一个筛选，并在此基础上建立出简易的数学模型。因此，我们假设如下：1假设早晨时间 8:00 为 0 时刻。2假设上一位同学面试结束后，下一位同学立刻开始该阶段面试，且时间间精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 19 页3 隔为 0。3假设整个面试过程中任何一位面试官都连续工作。4假设面试过程中没有任何同学退出。5假设同学和面试官都在早

6、晨八点准时到场。6各位同学和各位面试官没有事先约定好面试顺序，整个过程公平公正四、基本符号说明枚举法符号说明：ijt表示第 i 个人在第 j 轮面试结束的时间ijx表示第 i 个人在第 j 轮面试所经历的时间kT表示每个面试顺序中每个面试者每轮面试结束时间矩阵Time表示各个同学完成各阶段面试的时刻finaltimeTime .1为每个面试顺序所对应的离开时间最优化方法符号说明：ijX表示第 i 个人面试第 j 阶段所用的时间；ijT表示第 i 个人面试第 j 阶段的开始时间；T表示 4 个人面试完成的总时间；ikM表示第 k 个人是否排在第 i 个人之前，ikM =1，表示第 k 个人排在第

7、 i 个人之前，否则，ikM=0 i =1,2,3,4; k =1,2,3,4; j =1,2,3 五、模型建立与求解一枚举法1. 模型概述设第 i 个人在第 j 轮面试结束的时间为ijt，所经历的时间为ijx， 每个面试顺序中每个面试者每轮面试结束时间设为矩阵kT24k0，44A24 ，则第一个人在第一轮结束的时间为ijijxt，1- jij1- iijijttmaxxt，则43t为最终结束时间。首先根据排列组合原理，可知所有面试顺序排列共有24A44种。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 19 页4 确定每一种排序的面试

8、结束时间为枚举对象，则每个矩阵中最后一行最后一列的时间即最早离开时间。根据题意编制模型如下：42, 32,max32 , 142, 11, 11111jiTimeTimexijxTimejixTimejixTimejijiijijjiijjiijij利用 MATLAB 求解结果，得出每一种顺序下每位面试者结束时间矩阵去掉了第一行第一列的固定时间 。流程图为了使过程更加显而易见， 我们制作了简易的算法流程图， 其想法是全排列出每一种面试排序方法，然后建立计算公式分别计算每个面试者的结束时间。图 1根据此思路我们用MATLAB 编写了相应程序得出精选学习资料 - - - - - - - - - 名

9、师归纳总结 - - - - - - -第 4 页，共 19 页5 最优解101620182010201513151085X，此顺序的面试者结束时间矩阵为847251745631563621331885Time3. 模型的优点1结合了企业面试时的要求和特点，一一列举所有可能，得到的结果肯定是正确的。2算法直观，容易理解，易于证明其正确性。3模型稳定，结果贴近实际。改良由于枚举法穷举了所有可能， 运算量比较大，解题效率低下，如果枚举范围太大，在时间上就难以承受，所以我们可以在以下方面进行改良：1减少状态总数 即减少枚举变量和枚举变量的值域 ，如采用隐枚举法可以设定条件减持。2减少重复计算。3将原问

10、题化为更小的问题，比方考虑等待时间最小即结束时间最少的算法实现。二优化模型由于已知同学数量和阶段面试时间，只考虑固定一种顺序的情形，记ijX表示第 i 个同学面试第 j 阶段所用的时间，ijT表示第 i 个同学面试第 j 阶段的开始时间。引入 0-1 变量ikM，ikM表示第 k个人是否排在第 i 个同学之前，ikM=1，表示第 k个人排在第 i 个同学之前，否则，ikM=0。)4, 32, 1; 4,3,2, 1(，ji个同学之后个人排在第，第个同学之前个人排在第，第ikikMik01则i3X为第 i 个同学面试第 3 阶段所用时间 ,3iT为第 i 个同学面试第 3 阶段的开始时间，要求四

11、人完成面试后同时离开则可知)(33iiTXMax表示四人完成面试后的结束时间，设为为目标函数)(33iiTXMaxT。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 19 页6 这样T越小则离开时间越早，于是对0-1 整数线性规划模型进行改善，改写为)(33iiTXMaxMinT同时根据面试中的四人必须同时离开，可以建立约束TTXTTXTTXTTX4343333323231313此外，结合原题1每个人必须面试完上一轮才能开始下一轮面试)2, 1;4 ,3,2, 1(1jiXTXijijij2 每个阶段 j 只能面试一个人 : 用 0-1

12、 变量ikM表示第 k个人是否排在第 i 个人之前，即第 k个人排在第 i 个人之前，ikM=1；否则，ikM=0。假设ikM=0， k排在 i 后面);3 ,2, 1; 4, 3,2, 1,(0kijkiXTXkjijij); 3, 2, 1; 4, 3,2, 1,(kijkiTXTXijkjkj假设ikM=1，则 k排在 i 前面); 3, 2, 1; 4, 3,2, 1,(kijkiTXTXkjijij);3 ,2, 1;4, 3,2, 1,(0kijkiXTXijkjkj综上所述，可得);3 ,2, 1; 4, 3,2, 1,(kijkiTMXTXikkjijij); 3,2, 1;4

13、, 3,2, 1,(kijkiTMXTXikijkjkj加上之前的一个约束，综上，最终得出一个0-1 整数线性规划模型)(33iiTXMaxMinTs.t. );3 ,2 ,1;4 ,3, 2, 1,(kijkiTMXTXikkjijij，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 19 页7 );3 ,2, 1;4, 3,2, 1,(kijkiTMXTXikijkjkj，TTXTTXTTXTTX4343333323231313个同学之后个人排在第，第个同学之前个人排在第，第ikikMik01该题是一个 0-1 整数线性规划问题，

14、直接利用 lingo编程求解。计算结果见图 2 和附录二。图 2根据结果，能使四人最早同时离开的面试排序用时84 分钟，同时计算并汇总出各同学面试时间和开始时间如下表2。表 2各阶段开始时间各阶段使用时间各阶段结束时间甲秘书初试8 13 21 甲主管初试21 15 36 甲经理面试36 20 36 乙秘书初试36 10 36 乙主管初试36 20 56 乙经理面试56 18 74 丙秘书初试36 20 56 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 19 页8 丙主管初试56 16 72 丙经理面试74 10 84 丁秘书初试0

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

16、进行面试可以到达用时最短时间的效果，即 84 分钟， 早晨 9:24面试结束 . 枚举结果如下。0102030405060708090各同学各阶段面试时间及排序各阶段使用时间各阶段开始时间精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 19 页9 表 4序号面试顺序完成面试所用时间序号面试顺序完成面试所用时间1 丁丙乙甲102 13 乙丙丁甲93 2 丁丙甲乙97 14 乙丙甲丁96 3 丁乙丙甲89 15 乙丁丙甲93 4 丁乙甲丙86 16 乙丁甲丙93 5 丁甲乙丙84 17 乙甲丁丙93 6 丁甲丙乙95 18 乙甲丙丁93 7

17、 丙丁乙甲104 19 甲丙乙丁102 8 丙丁甲乙99 20 甲丙丁乙97 9 丙乙丁甲109 21 甲乙丙丁91 10 丙乙甲丁109 22 甲乙丁丙91 11 丙甲乙丁104 23 甲丁乙丙91 12 丙甲丁乙104 24 甲丁丙乙95 如此一来同学可以完成共同离开的心愿，且公司可以以最高效率工作。 但是连续工作可能会导致面试官疲惫，公司可以适当在面试过程中添加休息时间，比方在 56 分钟时进行休息，此时刚好第一、二位同学丁和甲三轮面试结束，乙第二轮面试结束，丙第二轮面试尚未开始，所有人可以共同休息调整状态。图 4图 2 为所有排序方法的结束用时计算结果， 可以看出各种顺序的用时差异相当

18、大，当面试人数更多的时候， 这一差距会更加显著， 所以企业合理安排面试顺序的具有重要现实意义。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 19 页10 六、模型评价与改良本文首先通过枚举法列举出24 种排序方案，并计算出每一种排序方式的所用时间，虽然计算量较大，但程序较为容易实现，其正确性也较容易证明。但是可以运用隐枚举法进行改良，提高解题效率。其次，构建了面试排队决策的优化模型，通过目标函数， 从而建立成了一个线性规划模型， 求地了所有同学排序情况下， 被排在最后的一个同学面试完时所用总时间 T也即排序后，从第一个同学参加第一阶段

19、面试时开始计时，到最后一个同学面试完最后一阶段的这段时间中最小的一个，然后，又建立了一个0-1 变量表示其约束条件，并使用LINGO软件求解，所得结果具有一定的正确性和指导意义。 但是，本文只讨论了四个同学面试三个阶段的合理排序方法，而没有讨论更多同学面试更多的阶段的合理排序的解决方案，从而使得面试总时间最短。在实际应用中还存在许多更复杂但是类似相关的情形，此时，假设还用本文中的解决方案未必是合理的。 因此，对更多同学面试更多的阶段的合理排序的解决方案是进一步应该研究和改良的方向。七、参考文献1 姜启源，谢金星，叶俊 . 数学模型 3 版. 北京：高等教育出版社，2003. 2 徐玖平，胡知能

20、 . 运筹学 -数据决策 . 北京：科学出版社， 2006. 第二版 . 北京: 高等教育出版社， 2002 4 赵静，但琦，数学建模与数学实验. 北京: 高等教育出版社， 2003. 5 Frank R.Giordano，Maurice D.Weir ，William P.Fox(美). 数学建模 . 叶其孝，姜启源等译 . 北京：机械工业出版社，2005 6 宋兆基等 .MATLABA 在科学计算中的应用 . 北京：清华大学出版社。2005. 八、附录精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 19 页11 附录一：MATLA

21、B 程序：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 % 将所有面试顺序所对应的面

22、试时间保存为矩阵附录 1pailie.m的内容 )：function T = pailie( k,S) %k为进行全排列的个数A=1:k; Q=perms(A); % 对 A进行全排列得到的数组m,n=size(Q); % 得到 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; % 将全排列得到的面试者面试时间存到T结构体end end 精选学习资料 - - - - - - - - - 名师归纳总结 - -

23、 - - - - -第 11 页，共 19 页12 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( =

24、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) sprint

25、f(+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); % 对每一个面试顺序中第二个面试者中秘书初始结束时间end for k=1:24 for i=2:4 for j=2:3 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -

26、第 12 页，共 19 页13 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);% % 把每个面试顺序中每个面试者每轮面试剩下4个结束时间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(f

27、ormat,i); eval(str1); end % 把 24 种面试顺序最终离开跌时刻输出为一个结构体bar(Time.finaltime) % 把最终离开时刻做成一张柱状图运行结果：其余数值结果冗长，故不予表述。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 19 页14 附录二：lingo 程序：model: sets : students; ! 学生集三阶段面试模型 ;phases; ! 阶段集 ;sp(students,phases):t,x; ss(students,students)|&1 #LT# &2:m; end

28、 setsdata : students=s1.s4; phases=p1.p3; t= 13 15 20 10 20 18 20 16 10 0510152025020406080100120精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 19 页15 8 10 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) ); ! 学生间的面试

29、先后次序保持不变的约束;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: Objective bound: Infeasibilities: Extended s

30、olver steps: 8 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 19 页16 Total solver iterations: 598 Variable Value Reduced Cost NS 4.000000 NP 3.000000 TMAX 84.00000 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 19 页17 Row Slack or Surplus Dual Price 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 19 页18 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 19 页19 附录三：秘书初试主观面试经理面试同学甲13 15 20 同学乙10 20 18 同学丙20 16 10 同学丁8 10 15 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 19 页