已阅读5页,还剩14页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1 面试顺序问题 一 摘要 本文立足现实生活中面试排序问题的特点 站在面试者的角度 要求整个 面试过程中使用时间最短 即所有面试者能最早离开公司 分析问题 首先 本文的问题概述如下 有 4 名同学到一家公司参加三个阶段的面试 公司要求 每个同学都必须首先找公司秘书初试 然后到部门主管处复试 最后到经理处 参加面试 并且不允许插队 即在任何一个阶段 4 名同学的顺序是一样的 已 知每个同学在各个阶段面试所需时间 详见附录三 各同学约定他们全部面试完以后一起离开公司 假定现在时间是早晨 8 00 问他们最早何时能离开公司 针对这一问题 由于面试人数较少 运算 量不大 故可以运用枚举法将所有面试的情况列举出来 根据题目可知 共有 4 名同学参加面试 不难得出 4 名同学面试顺序的所有情况共有 24 种 然后 计算出所有情况下的面试结束时间 根据比较 可以得出题目要求下的最优结 果 枚举法虽然解题效率相对要低 但是考虑的情况较为全面 得出的结果是 可靠的 根据以上我们提到的枚举法解决该问题 可能做了很多的无用功 浪费了 宝贵的时间 效率低下 为此我们可以进行优化 对于枚举法产生的弊端 我 们可以运用 0 1 整数规划方法进行优化 根据题意建立较为优化的模型 建立 相应的目标函数和约束条件 并且对目标函数进行进一步的改善 能够提高解 题的效率 简化解决问题的过程 最后将我们的模型在 lingo 中求解 得出结 果与枚举法相一致 即 4 名同学面试完成的最短时间是 84 分钟 并且给出面试 时间最短排序 丁 甲 乙 丙 为公司面试安排提供具有一定指导意义的建议 关键词 关键词 面试问题 枚举法 0 1 整数线性规划 2 二 问题重述 题目给出有 4 名同学到一家公司参加三个阶段的面试 公司要求每位同学都必 须首先找到公司秘书初试 然后到主管处复试 最后到经理处参加面试 并且 不允许插队 即在任何一阶段 4 名同学的顺序是一样的 由于 4 名同学的专 业背景不同 所以每人在三个阶段的面试时间也不同 表 1 秘书初试主观面试经理面试 同学甲 131520 同学乙 102018 同学丙 201610 同学丁 81015 根据题意这四名同学约定他们全部面试完成后一起离开公司 现在时间是早晨 8 00 本题需要我们给出一种最合理的排序方案 使得他们最早能够离开公司 三 问题分析与基本假设 在社会工作和生活中 面试顺序问题十分常见 题目中的面试流程分为三 个阶段 每一位面试官同时期只能面试一位同学 下一名同学面试之前需要等 待上一位该阶段面试结束 由于 4 名同学在任何一阶段的顺序是一样的 公司 在安排面试顺序的时候只需要考虑一次 使得总面试时间最短 由于数据较少 运用枚举法可以得出真正正确的解 同时 这也是一个整数线性规划问题 针对本题 联系实际 可引入 0 1 变量 对目标函数进行优化求解 在进行数据分析时 不可能通过几个简单的 假设就建立出一个完美的数学模型 这就需要对现有数据进行一个筛选 并在 此基础上建立出简易的数学模型 因此 我们假设如下 3 1 假设早晨时间 8 00 为 0 时刻 2 假设上一位同学面试结束后 下一位同学立刻开始该阶段面试 且时间间 隔为 0 3 假设整个面试过程中任何一位面试官都连续工作 4 假设面试过程中没有任何同学退出 5 假设同学和面试官都在早晨八点准时到场 6 各位同学和各位面试官没有事先约定好面试顺序 整个过程公平公正 四 基本符号说明 枚举法符号说明 表示第 个人在第 j 轮面试结束的时间 ij ti 表示第 个人在第 j 轮面试所经历的时间 ij xi 表示每个面试顺序中每个面试者每轮面试结束时间矩阵 k T 表示各个同学完成各阶段面试的时刻Time 为每个面试顺序所对应的离开时间finaltimeTime 1 最优化方法符号说明 表示第 个人面试第阶段所用的时间 ij Xij 表示第 个人面试第阶段的开始时间 ij Tij 表示 4 个人面试完成的总时间 T 表示第个人是否排在第 个人之前 1 表示第个人排在第 个人 ik Mki ik Mki 之前 否则 0 ik M 1 2 3 4 1 2 3 4 1 2 3ikj 五 模型建立与求解 一 枚举法 一 枚举法 1 模型概述 设第 个人在第 j 轮面试结束的时间为 所经历的时间为 每个面试i ij t ij x 顺序中每个面试者每轮面试结束时间设为矩阵 则 k T24k0 4 4 A24 第一个人在第一轮结束的时间为 则为最 ijij xt 1 jij1 iijij ttmaxxt 43 t 4 终结束时间 首先根据排列组合原理 可知所有面试顺序排列共有种 24A 4 4 确定每一种排序的面试结束时间为枚举对象 则每个矩阵中最后一行最后 一列的时间即最早离开时间 根据题意编制模型如下 42 32 max 32 1 42 1 1 1 11 1 1 jiTimeTimex ijxTime jixTime jix Time jijiij ijji ijji ij ij 利用 MATLAB 求解结果 得出每一种顺序下每位面试者结束时间矩阵 去掉 了第一行第一列的固定时间 2 模型求解与算法流程图 为了使过程更加显而易见 我们制作了简易的算法流程图 其想法是全排 列出每一种面试排序方法 然后建立计算公式分别计算每个面试者的结束时间 5 图 1 根据此思路我们用 MATLAB 编写了相应程序得出 最优解 此顺序的面试者结束时间矩阵为 101620 182010 201513 15108 5 X 847251 745631 563621 33188 5 Time 3 模型的优点 1 结合了企业面试时的要求和特点 一一列举所有可能 得到的结果肯定是 正确的 2 算法直观 容易理解 易于证明其正确性 3 模型稳定 结果贴近实际 5 模型的缺点和改进 由于枚举法穷举了所有可能 运算量比较大 解题效率低下 如果枚举范围太 大 在时间上就难以承受 所以我们可以在以下方面进行改进 1 减少状态总数 即减少枚举变量和枚举变量的值域 如采用隐枚举法可 以设定条件减持 2 减少重复计算 3 将原问题化为更小的问题 比如考虑等待时间最小即结束时间最少的算法 实现 二 优化模型 二 优化模型 1 模型建立 由于已知同学数量和阶段面试时间 只考虑固定一种顺序的情形 记表 ij X 示第 个同学面试第 阶段所用的时间 表示第 个同学面试第 阶段的开始ij ij Tij 时间 引入 0 1 变量 表示第 个人是否排在第 个同学之前 1 ik M ik Mki ik M 表示第 个人排在第 个同学之前 否则 0 ki ik M 4 32 1 4 3 2 1 ji 个同学之后个人排在第 第 个同学之前个人排在第 第 ik ik Mik 0 1 则为第 个同学面试第 3 阶段所用时间 为第 个同学面试第 3 阶段的开始 i3 Xi 3i Ti 6 时间 要求四人完成面试后同时离开则可知表示四人完成面试后 33ii TXMax 的结束时间 设为为目标函数 33ii TXMaxT 这样越小则离开时间越早 于是对 0 1 整数线性规划模型进行改善 改写为T 33ii TXMaxMinT 同时根据面试中的四人必须同时离开 可以建立约束 TTX TTX TTX TTX 4343 3333 2323 1313 此外 结合原题 1 每个人必须面试完上一轮才能开始下一轮面试 2 1 4 3 2 1 1 jiXTX ijijij 2 每个阶段 只能面试一个人 用 0 1 变量表示第 个人是否排在第 个j ik Mki 人之前 即第 个人排在第 个人之前 1 否则 0 ki ik M ik M 若 0 排在 后面 ik Mki 3 2 1 4 3 2 1 0kijkiXTX kjijij 3 2 1 4 3 2 1 kijkiTXTX ijkjkj 若 1 则 排在 前面 ik Mki 3 2 1 4 3 2 1 kijkiTXTX kjijij 3 2 1 4 3 2 1 0kijkiXTX ijkjkj 综上所述 可得 3 2 1 4 3 2 1 kijkiTMXTX ikkjijij 3 2 1 4 3 2 1 kijkiTMXTX ikijkjkj 加上之前的一个约束 综上 最终得出一个 0 1 整数线性规划模型 33ii TXMaxMinT 7 s t 3 2 1 4 3 2 1 kijkiTMXTX ikkjijij 3 2 1 4 3 2 1 kijkiTMXTX ikijkjkj TTX TTX TTX TTX 4343 3333 2323 1313 个同学之后个人排在第 第 个同学之前个人排在第 第 ik ik Mik 0 1 2 模型求解 该题是一个 0 1 整数线性规划问题 直接利用 lingo 编程求解 计算结果 见图 2 和附录二 图 2 根据结果 能使四人最早同时离开的面试排序用时 84 分钟 同时计算并汇总出 各同学面试时间和开始时间如下表 2 表 2 各阶段开始时间各阶段使用时间各阶段结束时间 甲 秘书初试 81321 甲 主管初试 211536 甲 经理面试 362036 乙 秘书初试 361036 乙 主管初试 362056 8 乙 经理面试 561874 丙 秘书初试 362056 丙 主管初试 561672 丙 经理面试 741084 丁 秘书初试 088 丁 主管初试 81018 丁 经理面试 211536 丁 秘 书 初 试 丁 主 管 复 试 甲 秘 书 初 试 甲 主 管 复 试 乙 秘 书 初 试 丁 经 理 面 试 甲 经 理 面 试 乙 主 管 复 试 丙 秘 书 初 试 丙 主 管 复 试 乙 经 理 面 试 丙 经 理 面 试 0 20 40 60 80 各阶段开始时间 各阶段使用时间 各同学各阶段面试时间及排序 图 3 图 4 显示了每位同学在各阶段面试时间长短的排序 可以看出甲的主管面试 乙的秘书面试 丁的经理面试 还有甲的经理面试 乙的主管面试 丙的秘书 初试 都分别是同时结束的 表 3 VariableValue M S1 S2 0 000000 M S1 S3 0 000000 M S1 S4 1 000000 M S2 S3 0 000000 M S2 S4 1 000000 M S3 S4 1 000000 又根据表 5 的 0 1 变量运算结果可知最优面试排序为丁 甲 乙 丙 显然计 算结果与枚举法模型结果相一致 确定正确 三 结果分析 通过枚举法和规划方法 最终可以确定 公司应该安排四位同学按照丁 甲 乙 丙这样的顺序进行面试可以达到用时最短时间的效果 即 84 分钟 早 晨 9 24 面试结束 枚举结果如下 9 表 4 序号面试顺序 完成面试所 用时间 序号面试顺序 完成面试所 用时间 1 丁丙乙甲 10213 乙丙丁甲 93 2 丁丙甲乙 9714 乙丙甲丁 96 3 丁乙丙甲 8915 乙丁丙甲 93 4 丁乙甲丙 8616 乙丁甲丙 93 5 丁甲乙丙 8417 乙甲丁丙 93 6 丁甲丙乙 9518 乙甲丙丁 93 7 丙丁乙甲 10419 甲丙乙丁 102 8 丙丁甲乙 9920 甲丙丁乙 97 9 丙乙丁甲 10921 甲乙丙丁 91 10 丙乙甲丁 10922 甲乙丁丙 91 11 丙甲乙丁 10423 甲丁乙丙 91 12 丙甲丁乙 10424 甲丁丙乙 95 如此一来同学可以完成共同离开的心愿 且公司可以以最高效率工作 但 是连续工作可能会导致面试官疲惫 公司可以适当在面试过程中添加休息时间 比如在 56 分钟时进行休息 此时刚好第一 二位同学丁和甲三轮面试结束 乙 第二轮面试结束 丙第二轮面试尚未开始 所有人可以共同休息调整状态 图 4 图 2 为所有排序方法的结束用时计算结果 可以看出各种顺序的用时差别 相当大 当面试人数更多的时候 这一差距会更加显著 所以企业合理安排面 10 试顺序的具有重要现实意义 六 模型评价与改进 本文首先通过枚举法列举出 24 种排序方案 并计算出每一种排序方式的所 用时间 虽然计算量较大 但程序较为容易实现 其正确性也较容易证明 但 是可以运用隐枚举法进行改进 提高解题效率 其次 构建了面试排队决策的优化模型 通过目标函数 从而建立成了一 个线性规划模型 求地了所有同学排序情况下 被排在最后的一个同学面试完 时所用总时间 T 也即排序后 从第一个同学参加第一阶段面试时开始计时 到最后一个同学面试完最后一阶段的这段时间 中最小的一个 然后 又建立 了一个 0 1 变量表示其约束条件 并使用 LINGO 软件求解 所得结果具有一定 的正确性和指导意义 但是 本文只讨论了四个同学面试三个阶段的合理排序 方法 而没有讨论更多同学面试更多的阶段的合理排序的解决方案 从而使得 面试总时间最短 在实际应用中还存在许多更复杂但是类似相关的情形 此时 若还用本文中的解决方案未必是合理的 因此 对更多同学面试更多的阶段的 合理排序的解决方案是进一步应该研究和改进的方向 七 参考文献 1 姜启源 谢金星 叶俊 数学模型 3 版 北京 高等教育出版社 2003 2 徐玖平 胡知能 运筹学 数据 决策 北京 科学出版社 2006 3 茆诗松 程依明 濮晓龙 概率论与数理统计 第二版 北京 高等教育出 版社 2002 4 赵静 但琦 数学建模与数学实验 北京 高等教育出版社 2003 5 Frank R Giordano Maurice D Weir William P Fox 美 数学建模 叶其 孝 姜启源等译 北京 机械工业出版社 2005 6 宋兆基等 MATLABA 在科学计算中的应用 北京 清华大学出版社 2005 11 八 附录 附录一 MATLAB程序 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 将所有面试顺序所对应的面试时间保存为矩阵 附录 1 pailie 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 12 end 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 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 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 对每一个面试顺序中第二个面试者中秘书初始 结束时间 end for k 1 24 for i 2 4 13 for j 2 3 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 format i eval str1 end 把 24 种面试顺序最终离开跌时刻输出为一个结构 体 bar Time finaltime 把最终离开时刻做成一张柱状图 运行结果 其余数值结果冗长 故不予表述 14 0510152025 0 20 40 60 80 100 120 附录二 lingo程序 model sets students 学生集三阶段面试模型 phases 阶段集 sp students phases t x ss students students end sets data students s1 s4 phases p1 p3 t 13 15 20 10 20 18 20 16 10 15 8 10 15 end data ns 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定义0 1变量 for ss bin m end 运行结果 Global optimal solution found Objective value 84 00000 Objective bound 84 00000 Infeasibilities 0 1532108E 13 Extended solver steps 8 16 Total solver iterations 598 Variable Value Reduced Cost NS 4 000000 0 000000 NP 3 000000 0 000000 TMAX 84 00000 0 000000 T S1 P1 13 00000 0 000000 T S1 P2 15 00000 0 000000 T S1 P3 20 00000 0 000000 T S2 P1 10 00000 0 000000 T S2 P2 20 00000 0 000000 T S2 P3 18 00000 0 000000 T S3 P1 20 00000 0 000000 T S3 P2 16 00000 0 000000 T S3 P3 10 00000 0 000000 T S4 P1 8 000000 0 000000 T S4 P2 10 00000 0 000000 T S4 P3 15 00000 0 000000 X S1 P1 8 000000 0 000000 X S1 P2 21 00000 0 000000 X S1 P3 36 00000 0 000000 X S2 P1 26 00000 0 000000 X S2 P2 36 00000 0 000000 X S2 P3 56 00000 0 000000 X S3 P1 36 00000 0 000000 X S3 P2 56 00000 0 000000 X S3 P3 74 00000 0 000000 X S4 P1 0 000000 1 000000 17 X S4 P2 8 000000 0 000000 X S4 P3 21 00000 0 000000 M S1 S2 0 000000 200 0000 M S1 S3 0 000000 0 000000 M S1 S4 1 000000 200 0000 M S2 S3 0 000000 200 0000 M S2 S4 1 000000 0 000000 M S3 S4 1 000000 0 000000 Row Slack or Surplus Dual Price 1 0 000000 0 000000 2 0 000000 0 000000 3 5 000000 0 000000 4 172 0000 0 000000 5 0 000000 1 000000 6 165 0000 0 000000 7 0
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年河南省西学中题库及答案
- 2026年文献选读模拟试卷目(含答案)
- 2026年国家公务员考试(国考)行测点睛题库及答案
- 2026年农资肥料考试题库及答案
- 2026年维修电工技师题库及参考答案
- 2026年信息素养学赛题库带答案
- 2026年江西大学考试题库及参考答案
- 2026年精神障碍护理实践题库及参考答案
- 2026年护理人员层级N2理论考核题库及参考答案
- 2026年能源地质学题库及参考答案
- 2025年中国职场人亚健康情况调查研究报告
- 音乐职高说课课件
- 美食城经营管理合同范本
- 直流系统培训课件
- 佣金合同协议书
- 《人才盘点完全应用手册》
- 人员推销课件
- 2024年共青团团课考试测试题库及答案
- 特殊教育教师职业生涯规划
- 医学大数据分析 课件 第1章 医学大数据概述
- 《急性会厌炎》课件
评论
0/150
提交评论