基于动态规划的面试时间优化模型

2015年天津商业大学数学建模竞赛承诺书我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B中选择一项填写）：B参赛队员(打印并签名)：1.叶恒扬2.施艺敏3.张一鸣日期：2015年4月27日-1-基于动态规划的面试时间优化模型摘要现代信息社会中，求职面试已经成为就业的一个重要环节。科学有效的组织和安排无论对面试者还是对组织单位、用人单位都是省时省力、节略成本的。因此如何紧凑、高效、省时地安排面试者按顺序完成面试具有重要研究意义。本文综合运用运筹学、统计学、经济学、平面设计、计算机软件等知识，通过建立数学模型来求解面试的最短时间，进一步规划最优的面试流程。针对问题一，通过分析给定的面试阶段顺序和不允许插队等特性，为满足面试时间最短，建立了求解最短时间的0-1非线性规划模型（见公式（1）），然后利用Lingo11.0程序（见附录1），求解出最短面试时间为100分钟，最佳安排顺序为：35214，同学最早9:40一起离开。接着利用AutoCAD2007分别绘制出同学和面试官的面试过程时间图（见图1～2）。在此基础上，利用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:339:40针对问题二，同样满足给定的面试阶段顺序、不允许插队和同学们约定一起离开等特性，对于未知的m名同学和n个阶段构成的面试时间矩阵)(ijA，以最后一名同学面试的结束时间最早为目标函数，以不允许插队和同一面试官同一阶段只能面试一个同学为约束条件，建立求解面试最短时间的动态规划模型（见公式（15）），并由Matlab生成随机面试时间矩阵55A（面试由5名同学和5阶段组成）和56A（面试由6名同学和5阶段组成），由Lingo程序（见附录3、5）求解出最短面试时间分别为101分钟和135分钟，比未经优化按原始顺序面试的110分钟和142分钟分别缩短9分钟和7分钟，接着运用AutoCAD2007分别绘制出优化前后的面试过程时间图（见图3～13）。同样，运用Excel2007制作出同学的具体面试流程表(见表3～6)。优化后的面试时间较未优化的面试时间有所缩短，验证了模型的正确性，也是对模型的检验。针对问题三，基于第一问和第二问的建模思想，同时进一步考虑到同学和面试官的等待过程是对时间成本的极大消耗，摒弃现有面试模式中同学同时到达再一起离开这一传统模式，建立无论是对于同学还是面试官只要完成自己的面试便可离开的新模式，基于问题一的已知面试时间矩阵，绘制出同学和面试官的面试时间图（图1和图11），并分别绘制同学和面试官的具体面试时间流程表（见表7～8），同学和面试官可根据时间流程表提前安排行程和合理利用等待时间，节约时间见下表：【关键字】面试时间，排序，动态规划，优化模型，lingo软件-2-一、问题的提出与重述现代信息社会中，求职面试已经成为就业的一个重要环节。在面试的组织实施过程中，一个常见的基本问题是如何紧凑、高效、省时地安排面试者按顺序完成面试，科学有效的组织和安排无论对面试者还是对组织单位、用人单位都是省时省力、节略成本的。面试过程的安排无疑要根据面试者的基本情况、用人单位的要求与面试设置项目有直接关系。比较典型的情况是用人单位或组织单位设置了几个阶段的面试，参加面试的人员必须逐一完成各个阶段的面试才能录取，另外由于面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间也有所不同。对上述面试情况，作简化和抽象后可描述为以下数学问题。问题一某高校毕业生中有5名同学到一家公司参加四个阶段的面试。面试程序上，要求每个同学都必须从第一阶段面试开始，然后进行第二阶段面试,…，最后进行第四阶段的面试，并且在任何一个阶段5名同学的顺序是一样的,假定开始面试时间是早晨8:00，建立的数学模型，求出他们最早离开公司的时间。问题二假设该高校毕业生中有m名同学到一家公司应聘，按类似于问题1的面试规则需要参加该公司人事部门组织的n个阶段的面试。由于m名同学的专业背景不同,所以每人在每个阶段的面试时间也不同，这m名同学约定他们全部面试完以后一起离开公司。请建立数学模型，以此讨论他们最早何时能离开该面试的公司?问题三试设计一种更科学、更公平、更合理的面试模式，并给出理由。二、基本假设1．假设面试者从一个阶段到下一个阶段参加面试的时间间隔为0；2．假定面试者都能在8：00准时到达面试地点；3．假定可以任意排列面试者的面试顺序；4．假定面试者均会参加每个阶段的面试，而且没有中途退场的情况出现；5．假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关。三、主要变量的符号说明为了便于描述问题，本文将问题中涉及的主要变量用下表符号来表示：表一主要变量符号说明一览表符号表示的意义T完成全部面试所花费的最少时间ijx第i名同学参加第j阶段面试的开始时刻ijt第i名同学参加第j阶段面试需要的时间kjx第k名同学参加第j阶段面试的开始时刻iky第k名同学是否排在第i名同学前面(1表示是，0表示否))(ijA面试时间矩阵-3-四、问题分析问题是“面试如何安排才能尽早结束”，根据题意可知，因为面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间有所不同，这样就造成了按某种顺序进入各面试阶段时不能紧邻顺序完成，即当面试正式开始后，在某个面试阶段，某个面试者会因为前面的面试者所需时间长而等待，也可能会因为自己所需时间短而提前完成。因此本问题实质上是求面试时间总和的最小值问题，其中一个面试时间总和就是指在一个确定面试顺序下所有面试者按序完成面试所花费的时间之和，这样的面试时间总和的所有可能情况则取决于面试者的面试顺序的所有排列数。从而原问题可等价于:求所有可能的面试顺序中，使花费总时间最少的那种顺序，并求出所花费的总时间。就问题一而言，实际上，这个问题就是要安排5名面试者的面试顺序，使完成全部面试所花费的时间最少。通过分析给定的面试阶段顺序和不允许插队等特性，为满足面试时间最短，可建立求解最短时间的0-1非线性规划模型，然后利用lingo11.0程序求解出最短面试时间以及最佳安排顺序。最后根据模型结果可得出同学最早离开面试地点的时间。另外我们可以利用AutoCAD2007分别绘制出同学和面试官的面试过程时间图，在此基础上，还可以利用Excel2007制作出同学的具体面试流程表；就问题二而言，实际上就是要安排m名面试者的面试顺序，使完成全部面试阶段n所花费的时间最少。同样满足给定的面试阶段顺序、不允许插队和同学们约定一起离开等特性，我们可以尝试建立求解面试最短时间的动态规划模型，并可由Matlab生成随机面试时间矩阵，然后由Lingo程序求解出最短面试时间，再运用AutoCAD2007分别绘制出优化前后的面试过程时间图。同样，可运用Excel2007制作出同学的具体面试流程表。最后可以比较一下优化后的面试时间较未优化的面试时间的改变，从而验证模型的正确性，也是对模型的检验。就问题三而言，需要我们从科学性、公平性、合理性三个方面对面试模式进行改进。我们可以通过查阅资料了解当前面试模式中存在的普遍性不合理现象，然后针对不合理现象进行面试模式的改进。五、模型的建立与求解1.问题一建模和求解（1）模型建立记ijt为第i名同学参加第j阶段面试需要的时间(已知)，令ijx表示第i名同学参加第j阶段面试的开始时刻(不妨记早上8：00面试开始为0时刻))4,3,2,1;5,4,3,2,1(jiT为完成全部面试所花费的最少时间。则有优化目标为：}}{{44iiitxMaxMinT（1）面试时间矩阵：98111481510871016206182010520151345A-4-约束条件：①对时间先后次序进行约束，即每人只有参加完前一个阶段的面试后才能进入下一个阶段：1,jiijijxtx)3,2,1;5,4,3,2,1(ji（2）②每个阶段j同一时间只能面试1名同学，用0-1变量iky表示第k名同学是否排在第i名同学前面(1表示是，0表示否),则：ikkjijijTyxtx,);4,3,2,1;5,4,3,2,1,(kijki（3）)1(ikijkjkjyTxtx,);4,3,2,1;5,4,3,2,1,(kijki（4）可以将非线性的优化目标改写为如下线性优化目标：MinT（5）..ts1313txT（6）2323txT（7）3333txT（8）4343txT（9）这个问题的0-1非线性规划模型[1]为:MinT（10）..ts1,jiijijxtx，)2,1;4,3,2,1(ji（11）ikkjijijTyxtx，);3,2,1;4,3,2,1,(kijki（12）)1(ikijkjkjyTxtx，);3,2,1;4,3,2,1,(kijki（13）Ttxmjmj，)4,3,2,1(i（14）（2）模型求解根据以上所建的模型，我们可编出Lingo程序（详见附录1），部分运行结果见图1（详细结果请见附录2）：-5-图1问题一部分运行结果（3）结果分析由变量TMAX的最优解值为100.00000，知最短时间为100分钟，即5名同学一起离开公司的时间是9：40。由变量Y(S1,S2)的最优解值为0.000000，知student1排在student2之前，即1号同学排在2号同学之前。由变量Y(S1,S3)的最优解值为0.000000，知student1排在student3之前，即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排在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号同学之前。根据模型得出的结果，我们可以作出整个面试过程的图解如下：-6-图2整体面试过程（同学）图3整体面试过程（面试官）根据图解,我们可做出这五位同学的具体面试安排如下（不妨设8：00为0时刻）：第一个进行面试的是4号同学。4号同学在0时刻开始秘书面试，用时8分钟；秘书处面试结束后去副