2022年面试顺序问题 .docx

精品_精品资料_面试次序问题一、摘要本文立足现实生活中面试排序问题的特点, 站在面试者的角度, 要求整个面试过程中使用时间最短,即全部面试者能最早离开公司,分析问题.第一,本文 的问题概述如下： 有 4 名同学到一家公司参与三个阶段的面试： 公司要求每个同学都必需第一找公司秘书初试, 然后到部门主管处复试, 最终到经理处参与面试, 并且不答应插队即在任何一个阶段4 名同学的次序是一样的.已知每个同学在各个阶段面试所需时间详见附录三 .各同学商定他们全部面试完以后一起离开公司.假定现在时间是早晨 8:00 , 问他们最早何时能离开公司.针对这一问题,由于面试人数较少,运算量不大,故可以运用枚举法将全部面试的情形列举出来.依据题目可知, 共有 4 名同学参加面试,不难得出, 4 名同学面试次序的全部情形共有24 种,然后运算出全部情形下的面试终止时间, 依据比较, 可以得出题目要求下的最优结果, 枚举法虽然解题效率相对要低,但是考虑的情形较为全面,得出的结果是牢靠的.依据以上我们提到的枚举法解决该问题, 可能做了很多的无用功, 铺张了珍贵的时间,效率低下.为此我们可以进行优化,对于枚举法产生的弊端,我们可 以运用 0-1 整数规划方法进行优化, 依据题意建立较为优化的模型, 建立相应的目标函数和约束条件, 并且对目标函数进行进一步的改善, 能够提高解题的效率, 简化解决问题的过程, 最终将我们的模型在 lingo中求解,得出结果与枚举法相一样,即 4 名同学面试完成的最短时间是 84 分钟,并且给出面试时间最短排序丁- 甲- 乙- 丙,为公司面试支配供应具有肯定指导意义的建议.关键词： 面试问题枚举法 0-1整数线性规划1可编辑资料 - - - 欢迎下载精品_精品资料_二、问题重述秘书初试表1主观面试经理面试同学甲131520同学乙102018同学丙201610同学丁81015题目给出有 4 名同学到一家公司参与三个阶段的面试, 公司要求每位同学都必需第一找到公司秘书初试, 然后到主管处复试, 最终到经理处参与面试, 并且不答应插队即在任何一阶段, 4 名同学的次序是一样的 .由于 4 名同学的专业背景不同,所以每人在三个阶段的面试时间也不同.依据题意这四名同学商定他们全部面试完成后一起离开公司,现在时间是早晨8:00 ,此题需要我们给出一种最合理的排序方案,使得他们最早能够离开公司.三、问题分析与基本假设在社会工作和生活中, 面试次序问题非常常见. 题目中的面试流程分为三个阶段,每一位面试官同时期只能面试一位同学, 下一名同学面试之前需要等待上一位该阶段面试终止, 由于 4 名同学在任何一阶段的次序是一样的,公司在支配面试次序的时候只需要考虑一次, 使得总面试时间最短. 由于数据较少运用枚举法可以得出真正正确的解.同时,这也是一个整数线性规划问题,针对此题,联系实际,可引入0-1变量,对目标函数进行优化求解. 在进行数据分析时, 不行能通过几个简洁的假设就建立出一个完善的数学模型, 这就需要对现有数据进行一个挑选, 并在此基础上建立出简易的数学模型.因此,我们假设如下：1假设早晨时间 8:00 为 0 时刻.2假设上一位同学面试终止后,下一位同学马上开头该阶段面试,且时间间2可编辑资料 - - - 欢迎下载精品_精品资料_隔为 0.3假设整个面试过程中任何一位面试官都连续工作.4假设面试过程中没有任何同学退出.5假设同学和面试官都在早晨八点准时到场.6各位同学和各位面试官没有事先商定好面试次序,整个过程公正公正四、基本符号说明枚举法符号说明：t ij 表示第 i 个人在第 j 轮面试终止的时间可编辑资料 - - - 欢迎下载精品_精品资料_xij表示第 i 个人在第 j 轮面试所经受的时间可编辑资料 - - - 欢迎下载精品_精品资料_Tk 表示每个面试次序中每个面试者每轮面试终止时间矩阵Time表示各个同学完成各阶段面试的时刻Time1. finaltime 为每个面试次序所对应的离开时间最优化方法符号说明：可编辑资料 - - - 欢迎下载精品_精品资料_X ij表示第 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. 模型概述五、模型建立与求解可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_设第 i 个人在第 j轮面试终止的时间为t ij ,所经受的时间为x ij , 每个面试可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_次序中每个面试者每轮面试终止时间设为矩阵Tk 0k24, 24A 4 ,就第可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_4一个人在第一轮终止的时间为t ijx ij , tijx ijmaxt i-1 j, tiA4j-1,就 t 43 为最终结可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_束时间.第一依据排列组合原理,可知全部面试次序排列共有424 种.可编辑资料 - - - 欢迎下载精品_精品资料_3可编辑资料 - - - 欢迎下载精品_精品资料_确定每一种排序的面试终止时间为枚举对象, 就每个矩阵中最终一行最终一列的时间即最早离开时间.依据题意编制模型如下：xiji1, j1Timei j 1xiji1,2j4Time i 1 jxijj1,2i3xijmax Timei 1 j ,Timei j 12i3,2j利用 MATLAB求解结果,得出每一种次序下每位面试者终止时间矩了第一行第一列的固定时间 .流程图为了使过程更加显而易见, 我们制作了简易的算法流程图, 其想出每一种面试排序方法,然后建立运算公式分别运算每个面试者的终止依据此思路我们用 MATLA图 1B编写了相应程序得出4Timeij4阵去掉法是全排列时间.可编辑资料 - - - 欢迎下载精品_精品资料_最优解 X 58101315102020161520,此次序的面试者终止时间矩阵为1810Time581833213656315674517284可编辑资料 - - - 欢迎下载精品_精品资料_3. 模型的优点1结合了企业面试时的要求和特点,一一列举全部可能,得到的结果确定是正确的.2算法直观,简洁懂得,易于证明其正确性.3模型稳固,结果贴近实际.改良由于枚举法穷举了全部可能, 运算量比较大,解题效率低下,假如枚举范畴太大,在时间上就难以承担,所以我们可以在以下方面进行改良：1削减状态总数 即削减枚举变量和枚举变量的值域 ,如采纳隐枚举法可以设定条件减持.2削减重复运算.3将原问题化为更小的问题,比方考虑等待时间最小即终止时间最少的算法实现.二优化模型可编辑资料 - - - 欢迎下载精品_精品资料_由于已知同学数量和阶段面试时间,只考虑固定一种次序的情形,记X ij 表可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_示第 i 个同学面试第 j 阶段所用的时间,Tij表示第 i 个同学面试第 j 阶段的开头时可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_间.引入 0-1 变量M ik , M ik 表示第 k 个人是否排在第 i 个同学之前,M ik =1,表可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_示第 k 个人排在第 i 个同学之前,否就,M ik =0.i1,2,3,4; j1,2,3,4可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_M ik1,第k个人排在第0,第 k个人排在第i个同学之前 i个同学之后可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_就X i3为第i 个同学面试第 3 阶段所用时间 ,Ti 3 为第 i 个同学面试第 3 阶段的开头可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_时间,要求四人完成面试后同时离开就可知Max X i 3Ti 3 表示四人完成面试后可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_的终止时间,设为为目标函数TMax X i 35Ti 3 .可编辑资料 - - - 欢迎下载精品_精品资料_这样T 越小就离开时间越早,于是对0-1整数线性规划模型进行改善,改写为可编辑资料 - - - 欢迎下载精品_精品资料_MinTMax X i 3Ti 3可编辑资料 - - - 欢迎下载精品_精品资料_同时依据面试中的四人必需同时离开,可以建立约束可编辑资料 - - - 欢迎下载精品_精品资料_此外,结合原题X 13X 23X 33X 43T13TT23TT33TT43T可编辑资料 - - - 欢迎下载精品_精品资料_1每个人必需面试完上一轮才能开头下一轮面试可编辑资料 - - - 欢迎下载精品_精品资料_X ijTijX ij1 i1,2,3,4; j1,2可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_2每个阶段 j 只能面试一个人 : 用 0-1 变量M ik表示第 k 个人是否排在第 i 个人可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_之前,即第 k 个人排在第 i 个人之前,M ik =1.否就,M ik =0.可编辑资料 - - - 欢迎下载精品_精品资料_假设 M ik =0, k 排在 i 后面X ijTijX kj0i , k1,2,3,4;j1,2,3; ik X kjTkjX ijT i , k1,2,3,4;j1,2,3; ik 假设 M ik =1,就 k 排在 i 前面可编辑资料 - - - 欢迎下载精品_精品资料_X ijTijX kjT i, k1,2,3,4; j1,2,3; ik 可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_X kjTkjX ij0i , k1,2,3,4; j1,2,3;ik可编辑资料 - - - 欢迎下载精品_精品资料_综上所述,可得可编辑资料 - - - 欢迎下载精品_精品资料_X ijTijX kjTM ik i, k1,2,3,4; j1,2,3; ik 可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_X kjTkjX ijTM ik i , k1,2,3,4; j1,2,3; ik 可编辑资料 - - - 欢迎下载精品_精品资料_加上之前的一个约束,综上,最终得出一个0-1 整数线性规划模型可编辑资料 - - - 欢迎下载精品_精品资料_MinTs.t.Max X i 3Ti 3 可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_X ijTijX kjTM ik ,i, k1,2,3,4; j1,2,3; ik 可编辑资料 - - - 欢迎下载精品_精品资料_6可编辑资料 - - - 欢迎下载精品_精品资料_X kjTkjX ijTM ik ,i, k1,2,3,4; j1,2,3; ik 可编辑资料 - - - 欢迎下载精品_精品资料_X 13T13TX 23T23TX 33T33TX 43T43T可编辑资料 - - - 欢迎下载精品_精品资料_M ik1,第 k个人排在第0,第k个人排在第i个同学之前 i个同学之后可编辑资料 - - - 欢迎下载精品_精品资料_该题是一个 0-1 整数线性规划问题, 直接利用 lingo编程求解.运算结果见图 2 和附录二.图 2依据结果,能使四人最早同时离开的面试排序用时84 分钟,同时运算并汇总出各同学面试时间和开头时间如下表2.表 2各阶段开头时间各阶段使用时间各阶段终止时间甲秘书初试81321甲主管初试211536甲经理面试362036乙秘书初试361036乙主管初试362056乙经理面试561874丙秘书初试3620567可编辑资料 - - - 欢迎下载精品_精品资料_丙主管初试561672丙经理面试741084丁秘书初试088丁主管初试81018丁经理面试211536可编辑资料 - - - 欢迎下载精品_精品资料_各同学各阶段面试时间及排序9080706050403020100各阶段使用时间各阶段开头时间可编辑资料 - - - 欢迎下载精品_精品资料_图 3图 4 显示了每位同学在各阶段面试时间长短的排序,可以看出甲的主管面试、 乙的秘书面试、丁的经理面试, 仍有甲的经理面试、 乙的主管面试、丙的秘书初试, 都分别是同时终止的.表 3VariableValueMS1,S2MS1,S3MS1,S4MS2,S3MS2,S4MS3,S4又依据表 5 的 0-1 变量运算结果可知最优面试排序为丁、甲、乙、丙,明显运算结果与枚举法模型结果相一样,确定正确.三结果分析通过枚举法和规划方法, 最终可以确定,公司应当支配四位同学依据丁、 甲、乙、丙这样的次序进行面试可以到达用时最短时间的成效, 即 84 分钟,早晨 9:24 面试终止 . 枚举结果如下.8可编辑资料 - - - 欢迎下载精品_精品资料_表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如此一来同学可以完成共同离开的心愿, 且公司可以以最高效率工作. 但是连续工作可能会导致面试官疲乏, 公司可以适当在面试过程中添加休息时间, 比方在 56 分钟时进行休息,此时刚好第一、二位同学丁和甲三轮面试终止,乙第二轮面试终止,丙其次轮面试尚未开头,全部人可以共同休息调整状态.图 4图 2 为全部排序方法的终止用时运算结果, 可以看出各种次序的用时差异相当大,当面试人数更多的时候, 这一差距会更加显著, 所以企业合理支配面试次序的具有重要现实意义.9可编辑资料 - - - 欢迎下载精品_精品资料_六、模型评判与改良本文第一通过枚举法列举出 24 种排序方案,并运算出每一种排序方式的所用时间,虽然运算量较大,但程序较为简洁实现,其正确性也较简洁证明.但是可以运用隐枚举法进行改良,提高解题效率.其次,构建了面试排队决策的优化模型, 通过目标函数, 从而建立成了一个线性规划模型, 求的了全部同学排序情形下, 被排在最终的一个同学面试完时所用总时间 T也即排序后,从第一个同学参与第一阶段面试时开头计时,到最终一个同学面试完最终一阶段的这段时间中最小的一个,然后,又建立了一个0-1 变量表示其约束条件,并使用 LINGO软件求解,所得结果具有肯定的正确性和指导意义. 但是, 本文只争论了四个同学面试三个阶段的合理排序方法,而没有争论更多同学面试更多的阶段的合理排序的解决方案,从而使得面试总时间最短.在实际应用中仍存在很多更复杂但是类似相关的情形,此时, 假设仍用本文中的解决方案未必是合理的. 因此,对更多同学面试更多的阶段的合理排序的解决方案是进一步应当争论和改良的方向.七、参考文献1 姜启源,谢金星,叶俊 . 数学模型 3 版. 北京：高等训练出版社, 2022.2 徐玖平,胡知能 . 运筹学- 数据·决策 . 北京：科学出版社, 2022.其次版 . 北京: 高等训练出版社, 20224 赵静,但琦,数学建模与数学试验 . 北京: 高等训练出版社, 2022.5 Frank R.Giordano, Maurice D.Weir , William P.Fox美. 数学建模 . 叶其孝,姜启源等译 . 北京：机械工业出版社, 20226 宋兆基等 .MATLABA在科学运算中的应用 . 北京：清华高校出版社. 2022.八、附录10可编辑资料 - - - 欢迎下载精品_精品资料_附录一：MATLA程B 序： student1.shijian=13 15 20;student2.shijian=10 20 18;student3.shijian=20 16 10;student4.shijian=8 10 15;%将 各同学面试时间存 到结 构体studentT=pailie4,student%求到全部面试次序所对应的面试时间存到结构体 Tfor i=1:24 for i=1:24string = sprintf'X%d', i ' = Ti.rearray;' ; evalstring;endend%将全部面试次序所对应的面试时间储存为矩阵附录 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=Qi,3;d=Qi,4;Ti.rearray=Sa.shijian;Sb.shijian;Sc.shijian;Sd.shijian;%将全排列得到的面试者面试时间存到T 结构体end end11可编辑资料 - - - 欢迎下载精品_精品资料_for k=1:24string = sprintf'Time%d1,1', k sprintf' = X%d1,1;',k ;evalstring;%对每一个面试次序中第一个面试者中秘书初始终止时间string=sprintf'Time%d1,2',ksprintf'=X%d1,1',k sprintf'+X%d1,2;',k ;evalstring;%对每一个面试次序中第一个面试者中主管复试终止时间string=sprintf'Time%d1,3',ksprintf'=X%d1,1',ksprintf'+X%d1,2',k sprintf'+X%d1,3;',k ;evalstring;%对每一个面试次序中第一个面试者中经理面试终止时间string=sprintf'Time%d2,1',ksprintf'=X%d1,1',k sprintf'+X%d2,1;',k ;evalstring;%对每一个面试次序中其次个面试者中秘书初始终止时间string=sprintf'Time%d3,1',ksprintf'=X%d1,1',ksprintf'+X%d2,1',k sprintf'+X%d3,1;',k ;evalstring;%对每一个面试次序中其次个面试者中秘书初始终止时间string=sprintf'Time%d4,1',ksprintf'=X%d1,1',ksprintf'+X%d2,1',ksprintf'+X%d3,1',k sprintf'+X%d4,1;',k ;evalstring;%对每一个面试次序中其次个面试者中秘书初始终止时间endfor k=1:24 for i=2:4 for j=2:312可编辑资料 - - - 欢迎下载精品_精品资料_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%d4,3;' str1=sprintfformat,i;evalstr1;end%把 24 种面试次序最终离开跌时刻输出为一个结构体barTime.finaltime%把最终离开时刻做成一张柱状图运行结果：其余数值结果冗长,故不予表述.13可编辑资料 - - - 欢迎下载精品_精品资料_1201008060402000510152025附录二： lingo 程序： model:sets :students;. 同学集三阶段面试模型 ; phases;. 阶段集; spstudents,phases:t,x;ssstudents,students|&1 #LT# &2:m; end setsdata : students=s1.s4; phases=p1.p3; t=13 15 2010 20 1820 16 1014可编辑资料 - - - 欢迎下载精品_精品资料_8 10 15;end datans=sizestudents;. 同学数; np=sizephases;. 阶段数;. 单个同学面试时间先后次序的约束 ; forspi,j|j #LT# np: xi,j+ti,j<=xi,j+1;. 同学间的面试先后次序保持不变的约束 ; 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:815可编辑资料 - - - 欢迎下载精品_精品资料_Total solver iterations:598VariableValueReduced CostNS4.000000NP3.000000TMAX84.0000016可编辑资料 - - - 欢迎下载精品_精品资料_RowSlack or SurplusDual Price17可编辑资料 - - - 欢迎下载精品_精品资料_18可编辑资料 - - - 欢迎下载精品_精品资料_附录三：秘书初试主观面试经理面试同学甲131520同学乙102018同学丙201610同学丁8101519可编辑资料 - - - 欢迎下载