2022年面试顺序问题.docx

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

1、精选学习资料 - - - - - - - - - 面试次序问题一、摘要本文立足现实生活中面试排序问题的特点,站在面试者的角度, 要求整个面试过程中使用时间最短,即全部面试者能最早离开公司,分析问题；第一,本文 的问题概述如下： 有 4 名同学到一家公司参与三个阶段的面试：公司要求每个同 学都必需第一找公司秘书初试, 然后到部门主管处复试, 最终到经理处参与面试,并且不答应插队即在任何一个阶段4 名同学的次序是一样的 ；已知每个同学在各个阶段面试所需时间详见附录三 ；各同学商定他们全部面试完以后一起离开公司；假定现在时间是早晨8:00 ,问他们最早何时能离开公司；针对这一问题,由于面试人数较少,

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

3、,简化解决问题的过程, 最终将我们的模型在lingo中求解,得出结果与枚举法相一样,即 4 名同学面试完成的最短时间是84 分钟,并且给出面试时间最短排序丁 - 甲- 乙- 丙,为公司面试支配供应具有肯定指导意义的建议；关键词： 面试问题枚举法 0-1整数线性规划1 名师归纳总结 - - - - - - -第 1 页,共 19 页精选学习资料 - - - - - - - - - 二、问题重述题目给出有 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 名师归纳总结 - - - - - - -第 2 页,共 19 页精选学习资料 - - - - - - - - - 隔为 0；3假设整个面试过程中任何一位面试官都连续工作

6、；4假设面试过程中没有任何同学退出；5假设同学和面试官都在早晨八点准时到场；6各位同学和各位面试官没有事先商定好面试次序,整个过程公正公正四、基本符号说明枚举法符号说明：ijt 表示第i个人在第 j 轮面试终止的时间x 表示第 i 个人在第 j 轮面试所经受的时间T 表示每个面试次序中每个面试者每轮面试终止时间矩阵Time表示各个同学完成各阶段面试的时刻Time .finaltime为每个面试次序所对应的离开时间最优化方法符号说明：X 表示第 i 个人面试第 j 阶段所用的时间；T 表示第 i 个人面试第 j 阶段的开头时间；T 表示 4 个人面试完成的总时间；Mik表示第 k 个人是否排在第

7、 i 个人之前,Mik =1 ,表示第 k 个人排在第 i 个人之前,否就,Mik=0 i =1,2,3,4; k =1,2,3,4; j =1,2,3 五、模型建立与求解一枚举法1. 模型概述设第 i 个人在第 j 轮面试终止的时间为 ijt,所经受的时间为 x , 每个面试次序中每个面试者每轮面试终止时间设为矩阵 T 0 k 24,24 A 44,就第一个人在第一轮终止的时间为 t ij x ij,t ij x ij max t-i 1 j,t i-j 1,就 t 43 为最终结束时间；第一依据排列组合原理,可知全部面试次序排列共有 A 44 24 种；3 名师归纳总结 - - - - -

8、 - -第 3 页,共 19 页精选学习资料 - - - - - - - - - 确定每一种排序的面试终止时间为枚举对象,列的时间即最早离开时间；依据题意编制模型如下：就每个矩阵中最终一行最终一Time ijx ijxiji1j,Time ij1i,1j144Time ij1i,1 2jTimei1jxijj2,1i3x ijmaxTime2i,3 2j利用 MATLAB求解结果,得出每一种次序下每位面试者终止时间矩阵去掉 了第一行第一列的固定时间 ；流程图 为了使过程更加显而易见, 我们制作了简易的算法流程图, 其想法是全排列 出每一种面试排序方法,然后建立运算公式分别运算每个面试者的终止时

9、间；图 1依据此思路我们用MATLAB编写了相应程序得出4 名师归纳总结 - - - - - - -第 4 页,共 19 页精选学习资料 - - - - - - - - - 8101581833最优解X5131520,此次序的面试者终止时间矩阵为Time52136561020183156742016105172843. 模型的优点1结合了企业面试时的要求和特点,一一列举全部可能,得到的结果确定是正确的；2算法直观,简洁懂得,易于证明其正确性；3模型稳固,结果贴近实际；改良由于枚举法穷举了全部可能, 运算量比较大,解题效率低下,假如枚举范畴太大,在时间上就难以承担,所以我们可以在以下方面进行改良

10、：1削减状态总数 即削减枚举变量和枚举变量的值域 ,如采纳隐枚举法可以 设定条件减持；2削减重复运算；3将原问题化为更小的问题,比方考虑等待时间最小即终止时间最少的算法 实现；二优化模型由于已知同学数量和阶段面试时间,只考虑固定一种次序的情形,记 X 表示第 i 个同学面试第 j 阶段所用的时间,T 表示第 i 个同学面试第 j 阶段的开头时间；引入 0-1 变量 M ik,M ik 表示第 k 个人是否排在第 i 个同学之前,M ik =1,表示第 k 个人排在第 i 个同学之前,否就,M ik =0； i ,1 2 , 3 , ;4 j ,1 2,3 4 1,第 k 个人排在第 i 个同学

11、之前M ik0,第 k 个人排在第 i 个同学之后就 X i3 为第 i 个同学面试第 3 阶段所用时间 , iT 为第 i 个同学面试第 3 阶段的开头时间,要求四人完成面试后同时离开就可知 Max X i 3 T i 3 表示四人完成面试后的终止时间,设为为目标函数 T Max X i 3 T i 3 ；5 名师归纳总结 - - - - - - -第 5 页,共 19 页精选学习资料 - - - - - - - - - 这样 T 越小就离开时间越早,于是对MinTMaxXi3T i30-1 整数线性规划模型进行改善,改写为同时依据面试中的四人必需同时离开,可以建立约束X13T 13TX23

12、T 23TX33T 33TX43T 43T此外,结合原题1每个人必需面试完上一轮才能开头下一轮面试X ij T ij X ij 1 i ,1 2 , 3 4, ; j ,1 2 2每个阶段 j 只能面试一个人 : 用 0-1 变量 M ik 表示第 k 个人是否排在第 i 个人之前,即第 k 个人排在第 i 个人之前,M ik =1；否就,M ik =0；假设 M ik =0, k 排在 i 后面X ij T ij X kj 0 i , k ,1 2 , ,3 ;4 j ,1 2 3, ; i k X kj T kj X ij T i , k ,1 2 , ,3 ;4 j ,1 ,2 ;3 i

13、 k 假设 M ik =1,就 k 排在 i 前面X ij T ij X kj T i , k ,1 2 , ,3 ;4 j ,1 ,2 ;3 i k X kj T kj X ij 0 i , k ,1 2 , ,3 4 ; j ,1 2 3, ; i k 综上所述,可得XijTijXkjTMiki,k,12 ,3;4j,12 3, ;ikkjijikXT kjXTMi,k,12 ,34 ;j,12 ,;3ik加上之前的一个约束,综上,最终得出一个MinTMaxXi3T i3s.t. 0-1 整数线性规划模型XijT ijXkjTMik,k,1,23 4,;j1 2,3, ;ik6 名师归纳总

14、结 - - - - - - -第 6 页,共 19 页精选学习资料 - - - - - - - - - XkjT kjXijTMik,k,12 ,34 ;j,12 3, ;ikX13T 13Ti个同学之前X23T23TX33T33TX43T43TM ik1,第k 个人排在第0,第k 个人排在第i个同学之后该题是一个 0-1 整数线性规划问题, 直接利用 lingo 图 2 和附录二；图 2编程求解；运算结果见依据结果,能使四人最早同时离开的面试排序用时 84 分钟,同时运算并汇总出各同学面试时间和开头时间如下表 2；表 2甲秘书初试各阶段开头时间各阶段使用时间各阶段终止时间8 13 21 甲主

15、管初试21 15 36 甲经理面试36 20 36 乙秘书初试36 10 36 乙主管初试36 20 56 乙经理面试56 18 74 丙秘书初试36 20 56 7 名师归纳总结 - - - - - - -第 7 页,共 19 页精选学习资料 - - - - - - - - - 丙主管初试56 16 72 丙经理面试74 10 84 丁秘书初试0 8 8 丁主管初试8 10 18 丁经理面试21 15 36 各同学各阶段面试时间及排序90 80 70 60 5040 30 2010 0各阶段使用时间 各阶段开头时间图 3图 4 显示了每位同学在各阶段面试时间长短的排序,可以看出甲的主管面试、

16、 乙的秘书面试、丁的经理面试,仍有甲的经理面试、 乙的主管面试、丙的秘书初试,都分别是同时终止的；表 3Variable Value MS1,S2 MS1,S3 MS1,S4 MS2,S3 MS2,S4 MS3,S4 又依据表 5 的 0-1 变量运算结果可知最优面试排序为丁、甲、乙、丙,明显运算结果与枚举法模型结果相一样,确定正确；三结果分析通过枚举法和规划方法, 最终可以确定,公司应当支配四位同学依据丁、 甲、乙、丙这样的次序进行面试可以到达用时最短时间的成效,面试终止 . 枚举结果如下；8 即 84 分钟,早晨 9:24名师归纳总结 - - - - - - -第 8 页,共 19 页精选

17、学习资料 - - - - - - - - - 表 4序号面试次序完成面试所序号面试次序完成面试所1 丁丙乙甲用时间13 乙丙丁甲用时间102 93 2 丁丙甲乙97 14 乙丙甲丁96 3 丁乙丙甲89 15 乙丁丙甲93 4 丁乙甲丙86 16 乙丁甲丙93 5 丁甲乙丙84 17 乙甲丁丙93 6 丁甲丙乙95 18 乙甲丙丁93 7 丙丁乙甲104 19 甲丙乙丁102 8 丙丁甲乙20 甲丙丁乙99 97 9 丙乙丁甲109 21 甲乙丙丁91 10 丙乙甲丁109 22 甲乙丁丙91 11 丙甲乙丁104 23 甲丁乙丙91 12 丙甲丁乙104 24 甲丁丙乙95 如此一来同学可以

18、完成共同离开的心愿,且公司可以以最高效率工作； 但是连续工作可能会导致面试官疲乏,公司可以适当在面试过程中添加休息时间,比方在 56 分钟时进行休息,此时刚好第一、二位同学丁和甲三轮面试终止,乙第二轮面试终止,丙其次轮面试尚未开头,全部人可以共同休息调整状态；图 4图 2 为全部排序方法的终止用时运算结果, 可以看出各种次序的用时差异相当大,当面试人数更多的时候, 这一差距会更加显著, 所以企业合理支配面试顺序的具有重要现实意义；9 名师归纳总结 - - - - - - -第 9 页,共 19 页精选学习资料 - - - - - - - - - 六、模型评判与改良本文第一通过枚举法列举出24

19、种排序方案,并运算出每一种排序方式的所用时间,虽然运算量较大,但程序较为简洁实现,其正确性也较简洁证明；但是 可以运用隐枚举法进行改良,提高解题效率；其次,构建了面试排队决策的优化模型,通过目标函数, 从而建立成了一个线性规划模型, 求地了全部同学排序情形下, 被排在最终的一个同学面试完时所 用总时间 T也即排序后,从第一个同学参与第一阶段面试时开头计时,到最终一个同学面试完最终一阶段的这段时间中最小的一个,然后,又建立了一个0-1 变量表示其约束条件,并使用LINGO软件求解,所得结果具有肯定的正确性和指导意义； 但是,本文只争论了四个同学面试三个阶段的合理排序方法,而没有争论更多同学面试更

20、多的阶段的合理排序的解决方案,短；在实际应用中仍存在很多更复杂但是类似相关的情形,从而使得面试总时间最 此时,假设仍用本文中的解决方案未必是合理的； 因此,对更多同学面试更多的阶段的合理排序的解 决方案是进一步应当争论和改良的方向；七、参考文献1 姜启源,谢金星,叶俊 . 数学模型 3 版 . 北京：高等训练出版社,2003. 2 徐玖平,胡知能 . 运筹学 - 数据 决策 . 北京：科学出版社, 2006. 其次版 . 北京: 高等训练出版社, 2002 4 赵静,但琦,数学建模与数学试验. 北京 : 高等训练出版社, 2003. 5 Frank R.Giordano,Maurice D.W

21、eir ,William P.Fox 美. 数学建模 . 叶其孝,姜启源等译 . 北京：机械工业出版社,2005 6 宋兆基等 .MATLABA在科学运算中的应用 . 北京：清华高校出版社；2005. 八、附录10 名师归纳总结 - - - - - - -第 10 页,共 19 页精选学习资料 - - - - - - - - - 附录一：MATLAB程序：student1.shijian=13 15 20; student2.shijian=10 20 18; student3.shijian=20 16 10; student4.shijian=8 10 15; student T=pail

22、ie4,student 结构体 T for i=1:24 for i=1:24 %将 各 学 生 面 试 时 间 存 到 结 构 体%求到全部面试次序所对应的面试时间存到string = sprintfX%d, i = Ti.rearray; ; evalstring; end end %将全部面试次序所对应的面试时间储存为矩阵 附录 1pailie.m 的内容 ：function T = pailie k,S %k为进行全排列的 个数 A=1:k; Q=permsA; %对 A 进行全排列得到的数组m,n=sizeQ; %得到 Q的大小 for i=1:m a=Qi,1; b=Qi,2; c

23、=Qi,3; d=Qi,4; Ti.rearray=Sa.shijian;Sb.shijian;Sc.shijian;Sd.shijian; %将全排列得到的面试者面试时间存到 T 结构体 end end 11 名师归纳总结 - - - - - - -第 11 页,共 19 页精选学习资料 - - - - - - - - - for k=1:24 string = sprintfTime%d1,1, k sprintf = X%d1,1;,k ; evalstring; %对每一个面试次序中第一个面试者中秘书初始 终止时间string = sprintfTime%d1,2, k sprintf

24、 = X%d1,1,k sprintf+X%d1,2;,k ; evalstring; %对每一个面试次序中第一个面试者中主管复试 终止时间string = sprintfTime%d1,3, k sprintf = X%d1,1,k sprintf+X%d1,2,k sprintf+X%d1,3;,k ; evalstring; %对每一个面试次序中第一个面试者中经理面试 终止时间string = sprintfTime%d2,1, k sprintf = X%d1,1,k sprintf+X%d2,1;,k ; evalstring; %对每一个面试次序中其次个面试者中秘书初始 终止时间s

25、tring = sprintfTime%d3,1, k sprintf = X%d1,1,k sprintf+X%d2,1,k sprintf+X%d3,1;,k ; evalstring; %对每一个面试次序中其次个面试者中秘书初始 终止时间string = sprintfTime%d4,1, k sprintf = X%d1,1,k sprintf+X%d2,1,k sprintf+X%d3,1,k sprintf+X%d4,1;,k ; evalstring; %对每一个面试次序中其次个面试者中秘书初始 终止时间 end for k=1:24 for i=2:4 for j=2:3 12

26、 名师归纳总结 - - - - - - -第 12 页,共 19 页精选学习资料 - - - - - - - - - formatSpec=Time%di,j=X%di,j+maxTime%di-1,j,Time%di,j-1; str=sprintfformatSpec,k,k,k,k; evalstr;% %把每个面试次序中每个面试者每轮面试剩下4个终止时间 end end end 就每个矩阵中最终一行最终一列的时间即最早离开时间 for i=1:24 timei.final=Ti.rearray4,3; end for i=1:24 format=Timei.finaltime=Time

27、%d4,3; str1=sprintfformat,i; evalstr1; end %把 24 种面试次序最终离开跌时刻输出为一个结构 体barTime.finaltime 运行结果：%把最终离开时刻做成一张柱状图其余数值结果冗长,故不予表述；13 名师归纳总结 - - - - - - -第 13 页,共 19 页精选学习资料 - - - - - - - - - 1201008060402000510152025附录二：lingo 程序：model: sets : students; . 同学集三阶段面试模型 ; phases; . 阶段集 ; spstudents,phases:t,x;

28、ssstudents,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 名师归纳总结 - - - - - - -第 14 页,共 19 页精选学习资料 - - - - - - - - - 8 10 15; end data ns=sizestudents; . 同学数 ; np=sizephases; . 阶段数 ; . 单个同学面试时间先后次序的约束 ; forspi,j|j #LT# np: xi,j+ti,j=xi,j+1 ; . 同学

29、间的面试先后次序保持不变的约束 ; forssi,k: forphasesj: xi,j+ti,j-xk,j=200*mi,k; xk,j+tk,j-xi,j=200*1-mi,k; ; . 目标函数 ; min=TMAX; forstudentsi: xi,3+ti,3=TMAX ; . 把Y定义 0-1 变量; forss: binm; end运行结果：Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: 8 15 名师归纳总结 - -

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