《基于动态规划的面试时间优化模型概述.docx》由会员分享，可在线阅读，更多相关《基于动态规划的面试时间优化模型概述.docx（39页珍藏版）》请在三一办公上搜索。
1、2015年天津商业大学数学建模竞赛承 诺 书我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B中选择一项填写）： B 参赛队员 (打印并签名) ：1. 叶恒扬 2. 施艺敏 3. 张一鸣 日期： 2015 年
2、4 月 27 日基于动态规划的面试时间优化模型摘 要现代信息社会中，求职面试已经成为就业的一个重要环节。科学有效的组织和安排无论对面试者还是对组织单位、用人单位都是省时省力、节略成本的。因此如何紧凑、高效、省时地安排面试者按顺序完成面试具有重要研究意义。本文综合运用运筹学、统计学、经济学、平面设计、计算机软件等知识，通过建立数学模型来求解面试的最短时间，进一步规划最优的面试流程。针对问题一，通过分析给定的面试阶段顺序和不允许插队等特性，为满足面试时间最短，建立了求解最短时间的0-1非线性规划模型（见公式（1），然后利用Lingo11.0程序（见附录1），求解出最短面试时间为100分钟，最佳安排
3、顺序为：，同学最早9:40一起离开。接着利用AutoCAD2007分别绘制出同学和面试官的面试过程时间图（见图12）。在此基础上，利用Excel2007制作出同学的具体面试流程表：秘书副主管主管经理开始时刻结束时刻开始时刻结束时刻开始时刻结束时刻开始时刻结束时刻同学48:008:088:088:188:188:338:338:41同学18:088:218:218:368:368:568:569:01同学28:218:318:368:568:569:149:149:20同学58:318:458:569:079:149:229:229:31同学38:459:059:079:239:239:339:
4、339:40针对问题二，同样满足给定的面试阶段顺序、不允许插队和同学们约定一起离开等特性，对于未知的m名同学和n个阶段构成的面试时间矩阵，以最后一名同学面试的结束时间最早为目标函数，以不允许插队和同一面试官同一阶段只能面试一个同学为约束条件，建立求解面试最短时间的动态规划模型（见公式（15），并由Matlab生成随机面试时间矩阵（面试由5名同学和5阶段组成）和（面试由6名同学和5阶段组成），由Lingo程序（见附录3、5）求解出最短面试时间分别为101分钟和135分钟，比未经优化按原始顺序面试的110分钟和142分钟分别缩短9分钟和7分钟，接着运用AutoCAD2007分别绘制出优化前后的面试
5、过程时间图（见图313）。同样，运用Excel2007制作出同学的具体面试流程表(见表36)。优化后的面试时间较未优化的面试时间有所缩短，验证了模型的正确性，也是对模型的检验。针对问题三，基于第一问和第二问的建模思想，同时进一步考虑到同学和面试官的等待过程是对时间成本的极大消耗，摒弃现有面试模式中同学同时到达再一起离开这一传统模式，建立无论是对于同学还是面试官只要完成自己的面试便可离开的新模式，基于问题一的已知面试时间矩阵，绘制出同学和面试官的面试时间图（图1和图11），并分别绘制同学和面试官的具体面试时间流程表（见表78），同学和面试官可根据时间流程表提前安排行程和合理利用等待时间，节约时间
6、见下表： 【关键字】 面试时间，排序，动态规划，优化模型，lingo软件- 2 -一、问题的提出与重述 现代信息社会中，求职面试已经成为就业的一个重要环节。在面试的组织实施过程中，一个常见的基本问题是如何紧凑、高效、省时地安排面试者按顺序完成面试，科学有效的组织和安排无论对面试者还是对组织单位、用人单位都是省时省力、节略成本的。面试过程的安排无疑要根据面试者的基本情况、用人单位的要求与面试设置项目有直接关系。比较典型的情况是用人单位或组织单位设置了几个阶段的面试，参加面试的人员必须逐一完成各个阶段的面试才能录取，另外由于面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间也有
7、所不同。对上述面试情况，作简化和抽象后可描述为以下数学问题。问题一 某高校毕业生中有5名同学到一家公司参加四个阶段的面试。面试程序上，要求每个同学都必须从第一阶段面试开始，然后进行第二阶段面试,，最后进行第四阶段的面试，并且在任何一个阶段5名同学的顺序是一样的,假定开始面试时间是早晨8:00，建立的数学模型，求出他们最早离开公司的时间。问题二 假设该高校毕业生中有m名同学到一家公司应聘，按类似于问题1的面试规则需要参加该公司人事部门组织的n个阶段的面试。由于m名同学的专业背景不同,所以每人在每个阶段的面试时间也不同，这m名同学约定他们全部面试完以后一起离开公司。请建立数学模型，以此讨论他们最早
8、何时能离开该面试的公司?问题三 试设计一种更科学、更公平、更合理的面试模式，并给出理由。2、 基本假设1假设面试者从一个阶段到下一个阶段参加面试的时间间隔为0；2假定面试者都能在8：00准时到达面试地点；3假定可以任意排列面试者的面试顺序；4假定面试者均会参加每个阶段的面试，而且没有中途退场的情况出现；5假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关。三、主要变量的符号说明为了便于描述问题，本文将问题中涉及的主要变量用下表符号来表示： 表一 主要变量符号说明一览表符号表示的意义完成全部面试所花费的最少时间第名同学参加第阶段面试的开始时刻第名同学参加第阶段面试需要的时间第名同学
9、参加第阶段面试的开始时刻第名同学是否排在第名同学前面(1表示是，0表示否)面试时间矩阵 四、问题分析 问题是“面试如何安排才能尽早结束”，根据题意可知，因为面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间有所不同，这样就造成了按某种顺序进入各面试阶段时不能紧邻顺序完成，即当面试正式开始后，在某个面试阶段，某个面试者会因为前面的面试者所需时间长而等待，也可能会因为自己所需时间短而提前完成。因此本问题实质上是求面试时间总和的最小值问题，其中一个面试时间总和就是指在一个确定面试顺序下所有面试者按序完成面试所花费的时间之和，这样的面试时间总和的所有可能情况则取决于面试者的面试顺序
10、的所有排列数。从而原问题可等价于:求所有可能的面试顺序中，使花费总时间最少的那种顺序，并求出所花费的总时间。就问题一而言，实际上，这个问题就是要安排5名面试者的面试顺序，使完成全部面试所花费的时间最少。通过分析给定的面试阶段顺序和不允许插队等特性，为满足面试时间最短，可建立求解最短时间的0-1非线性规划模型，然后利用lingo11.0程序求解出最短面试时间以及最佳安排顺序。最后根据模型结果可得出同学最早离开面试地点的时间。另外我们可以利用AutoCAD2007分别绘制出同学和面试官的面试过程时间图，在此基础上，还可以利用Excel2007制作出同学的具体面试流程表；就问题二而言，实际上就是要安
11、排m名面试者的面试顺序，使完成全部面试阶段n所花费的时间最少。同样满足给定的面试阶段顺序、不允许插队和同学们约定一起离开等特性，我们可以尝试建立求解面试最短时间的动态规划模型，并可由Matlab生成随机面试时间矩阵，然后由Lingo程序求解出最短面试时间，再运用AutoCAD2007分别绘制出优化前后的面试过程时间图。同样，可运用Excel2007制作出同学的具体面试流程表。最后可以比较一下优化后的面试时间较未优化的面试时间的改变，从而验证模型的正确性，也是对模型的检验。就问题三而言，需要我们从科学性、公平性、合理性三个方面对面试模式进行改进。我们可以通过查阅资料了解当前面试模式中存在的普遍性
12、不合理现象，然后针对不合理现象进行面试模式的改进。五、模型的建立与求解1. 问题一建模和求解（1）模型建立记为第名同学参加第阶段面试需要的时间(已知)，令表示第名同学参加第阶段面试的开始时刻(不妨记早上8：00面试开始为0时刻)为完成全部面试所花费的最少时间。 则有优化目标为： （1）面试时间矩阵：约束条件： 对时间先后次序进行约束，即每人只有参加完前一个阶段的面试后才能进入下一个阶段： （2） 每个阶段同一时间只能面试1名同学，用0-1变量表示第名同学是否排在第名同学前面(1表示是，0表示否),则： , （3） , （4） 可以将非线性的优化目标改写为如下线性优化目标： （5） （6） （7
13、） （8） （9）这个问题的0-1非线性规划模型1为: （10） ， （11） ， （12） ， （13） ， （14）（2） 模型求解根据以上所建的模型，我们可编出Lingo程序（详见附录1），部分运行结果见图1（详细结果请见附录2）：图1 问题一部分运行结果（3） 结果分析由变量的最优解值为100.00000，知最短时间为100分钟，即5名同学一起离开公司的时间是9：40。 由变量Y(S1,S2)的最优解值为0.000000，知student1排在student2之前，即1号同学排在2号同学之前。由变量Y(S1,S3)的最优解值为0.000000，知student1排在student3之前
14、，即1号同学排在3号同学之前。由变量Y(S1,S4)的最优解值为1.000000，知student4排在student1之前，即4号同学排在1号同学之前。由变量Y(S1,S5)的最优解值为0.000000，知student1排在student5之前，即1号同学排在5号同学之前。 由变量Y(S2,S3)的最优解值为0.000000，知student2排在student3之前，即2号同学排在3号同学之前。 由变量Y(S2,S4)的最优解值为1.000000，知student4排在student2之前，即4号同学排在2号同学之前。由变量Y(S2,S5)的最优解值为0.000000，知student2
15、排在student5之前，即2号同学排在5号同学之前。 由变量Y(S3,S4)的最优解值为1.000000，知student4排在student3之前，即4号同学排在3号同学之前。由变量Y(S3,S5)的最优解值为1.000000，知student5排在student3之前，即5号同学排在3号同学之前。由变量Y(S4,S5)的最优解值为0.000000，知student4排在student5之前，即4号同学排在5号同学之前。根据模型得出的结果，我们可以作出整个面试过程的图解如下：图2 整体面试过程（同学）图3 整体面试过程（面试官）根据图解,我们可做出这五位同学的具体面试安排如下（不妨设8：0
16、0为0时刻）： 第一个进行面试的是4号同学。4号同学在0时刻开始秘书面试，用时8分钟；秘书处面试结束后去副主管处进行面试，用时10分钟；接着去主管处面试，用时15分钟；最后去经理处面试，用时8分钟；最终，4号同学在8：41完成整个面试过程。 第二个进行面试的是1号同学。1号同学在8分钟时刻开始秘书面试，用时13分钟，此时4号同学已经完成副主管面试；1号同学直接进行副主管面试，用时15分钟，此时4号同学已经完成主管面试；1号同学直接进行主管面试，用时20分钟，此时4号同学已经完成经理面试；1号同学开始经理面试，用时5分钟；最终，1号同学在9:01完成整个面试过程。第三个进行面试的是2号同学。2号
17、同学在21分钟时刻开始秘书面试，用时10分钟完成秘书面试，此时1号同学还未完成副主管面试；2号同学等待5分钟后进行副主管面试，面试用时20分钟，此时1号同学刚好结束主管面试；2号同学直接进行主管面试，用时18分钟，此时1号同学已经完成经理面试；2号同学直接进行经理面试，用时6分钟。最终，2号同学在9:20完成整个面试过程。第四个进行面试的是5号同学。5号同学在31分钟时刻开始秘书面试，用时14分钟完成秘书面试，此时2号同学还未完成副主管面试；5号等待11分钟后进行副主管面试，面试副主管用时11分钟，副主管面试完，2号同学还未完成主管面试；5号同学等待7分钟后开始主管面试，用时8分钟，此时2号同
18、学已经完成经理面试；5号同学直接进行经理面试，用时9分钟。最终，5号同学在9:31完成整个面试过程。最后进行面试的是3号同学。3号同学在45分钟时刻开始秘书面试，用时20分钟完成秘书面试，此时5号同学还未完成副主管面试；3号同学等待2分钟后开始面试副主管，用时16分钟，此时5号同学已经完成主管面试；3号同学直接开始主管面试，用时10分钟，此时5号同学已经完成经理面试；3号同学直接进行经理面试，用时7分钟，最终，3号同学在9:40完成整个面试过程。为了更加直观地表示整个面试过程的时间安排，我们作出面试的时间安排表如下：表2 面试时间安排表秘书副主管主管经理开始时刻结束时刻开始时刻结束时刻开始时刻
19、结束时刻开始时刻结束时刻同学48:008:088:088:188:188:338:338:41同学18:088:218:218:368:368:568:569:01同学28:218:318:368:568:569:149:149:20同学58:318:458:569:079:149:229:229:31同学38:459:059:079:239:239:339:339:40至此，模型所得五位同学的面试顺序为，以此顺序依次进行面试，总计用时最短，为100分钟，即这五位同学最早可在9:40离开公司。2. 问题二建模和求解 对于问题一，所建立的数学模型是针对具体面试者与面试阶段的特定模型。而问题二需要
20、针对面试者与面试阶段不确定建立相应的数学模型，进而求出最短面试时间。为此，借助问题一的建模思想，将模型进一步推广，假设有m名面试者，n个面试阶段，建立求解最小面试时间的数学模型。（1）模型建立 实际上，这个问题就是要安排m名面试者的面试顺序，使完成全部面试所花费的时间最少。 面试时间矩阵： 优化目标： （15） 约束条件： 时间先后次序约束(每人只有参加完前一个阶段的面试后才能进入下一个阶段) （16） 每个阶段j同一时间只能面试1名同学：用0-1变量表示第名同学是否排在第名同学前面(1表示是，0表示否)，则, （17）, （18） 可以将非线性的优化目标改写为如下线性优化目标： （19） s
21、.t. （20） （21） （22） 则这个问题的0-1非线性规划模型为： （23） s.t. ， （24） ， （25） ， （26） ， （27）（2） 模型求解 根据模型，我们可编写LINGO程序如下：Model:SETS:! Person = 被面试者集合，Stage = 面试阶段的集合;Person/1.m/;Stage/1.n/;! T = 已知的面试所需要的时间，X = 面试开始时间;PXS(Person,Stage): T, X;! Y(i,k) = 1: k排在i前，0：否则;PXP(Person,Person)|&1 #LT# &2: Y;ENDSETSDATA: T=;E
22、NDDATAobj min =MAXT;! MAXT是面试的最后结束时间;MAXT = max(PXS(i,j)|j#EQ#size(stage): x(i,j)+t(i,j);! 只有参加完前一个阶段的面试后才能进入下一个阶段;for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)x(i,j+1);! 同一时间只能面试1名同学;for(Stage(j): for(PXP(i,k):SORT1x(i, j)+t(i, j)-x(k,j)MAXT*Y(i,k) ); for(PXP(i,k):SORT2x(k,j)+t(k,j)-x(i, j)= max
23、(PXS(i,j)|j#EQ#size(stage): x(i,j)+t(i,j);! 只有参加完前一个阶段的面试后才能进入下一个阶段;for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)x(i,j+1);! 同一时间只能面试1名同学;for(Stage(j): for(PXP(i,k):SORT1x(i, j)+t(i, j)-x(k,j)MAXT*Y(i,k) ); for(PXP(i,k):SORT2x(k,j)+t(k,j)-x(i, j)MAXT*(1-Y(i,k) ););for(PXP: bin(y);End 附录2 问题一Lingo运行结果 Local optimal solution found. Objective value: 100.0000 Objective bound:
