面试最短时间数学建模论文.doc

东华理工大学数学建模论文论文题目：面试时间最短问题 姓名1： 曾祥威 学号：1021112208姓名2： 程涛 学号：1021112210姓名3： 饶远 学号：1021112224专 业：软件工程电子商务班 级：10211122指导教师： 乐励华 2012年06月10日题目：面试最短时间问题摘要参加面试是大部分大学生毕业之后必须经历的环节，几位同学一起去招聘单位参加面试，怎样才能用最优时间来完成面试呢？当今社会的主旨是倡导绿色，节约和可持续发展，减少不必要的浪费对于达到我们节约型社会的要求是很必要的。而节约面试的时间对于招聘单位和应聘者都有着巨大的好处，所以我们怎样来解决这个问题呢？从表格中的数据可以看出，每个面试者在每个面试阶段所花费的时间是不同的，最终造成的面试总时间也是有长有短的。所以统筹规划可以让我们也让企业节省时间还有金钱，怎样才能找出在最优时间内面试完毕是我们所要解决的问题。求4名同学最早离开公司的时间，即求4名同学都在公司面试完毕所需的最优时间。由于每人在3个阶段的面试时间不同且每个同学都不允许插队，故可知道面试总时间的长短是由面试顺序决定的。所以应当用整数规划的方法并借助Lingo来解决这个问题。题目中要注意的是每一个阶段在同一个时间内只能面试一名同学，所以要判断第k名同学是否在第i位同学之前，这就需要我们进行分类讨论前跟后的问题，要针对这两种情况列出不同的约束条件；我们还要注意一个就是题目中说到的每个同学都只有参加完前面一个面试才能去参加接着的面试，故时间上就有Xij+Tij=Xi，j+1。这个问题结果求得面试所用总时间为84分钟，即他们同时离开公司的时刻为 上午9:24，根据Y12=0,Y13=0,Y14=1,Y23=0,Y24=1,Y34=1,可知面试顺序为4-1-2-3，即：丁-甲-乙-丙关键字：Lingo,整数规划，面试，最优时间重述问题、问题提出:有4名同学到一家公司参加三个阶段的面试。面试要求为：每个同学应依次找秘书、主管、经理进行初试、复试、面试；每个同学都不允许插队。每人在三个阶段的面试时间都不同，具体如下表所示（单位：分钟）：秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015根据题意，本文应解决的问题有：这4名同学约定他们全部面试完以后一起离开公司。假定现在的时间是早晨8：00，求他们最早离开公司的时间、问题图形分析：（1）、总体柱形图（2）各个同学的扇形图由上图可知：同学甲在秘书初试上花的时间最短，越往后花的时间越长。同学乙在主管面试上花的时间最长，其次是经理面试。同学丙在秘书初试上花的时间最长，越往后越短。同学丁在秘书初试上花的时间最短，越往后花的时间越长。其中，这4人在面试所花费的平均时间由高到低依次是:经理面试、主管复试、秘书初试。、问题解决；由题可知，求4名同学最早离开公司的时间，即求4名同学都在公司面试完毕所需的最短时间。由于每人在3个阶段的面试时间不同且每个同学都不允许插队，故可知道面试总时间的长短是由面试顺序决定的。而4名同学的面试顺序有4！=24种情况，也就是说本题可以用穷举法一一列出然后取使面试总时间最小的顺序，不难发现这样做的工作是冗杂的，且若面试人数很大时，这个方法就显得不科学。考虑到本题求其所用时间的最小值也就是关于面试时间的最优解问题，所以，我想出用线性规划的方法建立模型并借助Lingo软件来解决这问题。四、需求分析：1、根据题目中的表格算出这4名同学全部面试完以后最早一起离开公司的时间。假定现在的时间是早晨8：00。2、试着给出此类问题的一般描述，并试着分析问题的一般解法。模型的分析：1、问题建立：在问题描述中有这样的规定：在任何一个阶段4名同学的顺序是一样的，这说明，我们要寻找最短时间，必须找到一个合适的顺序，从合适的顺序入手达到时间最短。与此同时，要考虑到最大面试时间问题，专业不同的人，他们的面试时间是不一样的，那么，我们的顺序是要参照他们所面试的时间而定的。4名同学最早离开公司的时间，就是4名同学都在公司面试完毕所需的最短时间。由于每人在3个阶段的面试时间不同且不允许插队，则面试总时间的长短是由面试顺序决定的。而4名同学的面试顺序有4！=24种情况，也就是说本题可以用穷举法一一列出然后取使面试总时间最小的顺序，但是明显这样做的法会很麻烦，所以我想出用规划的方法并借助Lingo来解决这个问题。利用规划的方法，首先是参考了一些资料文件，考虑到进度和时间读，我们决定，用划分模板的方式解决问题。2、模型的建立求4名同学在公司面试完毕所需的最短时间，考虑到面试总时间的长短是由面试顺序决定的，即要找一个面试顺序使得4名同学面试完毕的4个时刻的最大值这一情况时 所用的面试总时数最短。故由 （分钟）第i个同学第j阶段的面试时间（如下表）：表示第n个同学第m阶段的面试时间； 表示第n个同学第m阶段开始面试的时刻； 表示若第j个同学排在第n个同学之前，记为，否则为； 表示4名参加面试的同学同时离开公司的时间； 分别表示取最小值和最大值；附： ，121518101815201614810153、架构流程：开始规划方式，利用所规划的特例情况来分析代码求解代码分析结束这模板是我们在数学建模的框架所采用的比较简单的构架方式，每一个框架都是一个流程。模型的求解过程与结果1、代码过程：model: sets: students; !学生集三阶段面试模型; phases; !阶段集; sp(students,phases):c,x; ss(students,students) | &1 #LT# &2:y; endsets data: students = s1.s4; phases = p1.p3; c= 12 15 18 10 18 15 20 16 14 8 10 15; enddata ns=size(students); !学生数; np=size(phases); !阶段数; !单个学生面试时间先后次序的约束; for(sp(N,M) | M #LT# np: x(N,M)+c(N,M)=x(N,M+1) ); !学生间的面试先后次序保持不变的约束; for(ss(N,J): for(phases(M): x(N,M)+c(N,M)-x(J,M)=200*y(N,J); x(J,M)+c(J,M)-x(N,M)=200*(1-y(N,J); ) ); min=TMAX; !目标函数; for(students(N): x(N,3)+c(N,3)=TMAX ); !把Y定义0-1变量; for(ss: bin(y); End2、 结果：结果：83.000000按照 丁 甲 乙 丙 或丁 乙丙甲这一面试顺序，利用题中表里的数据，计算得面试所用时间刚好为83分钟。模型评价与推广1、模型评价本模型是整数线性规划模型，模型的分析清晰明了，模型的建立简便实用，模型的求解，借助了lingo软件，（lingo软件的特点是程序执行