建模论文-面试时间最短问题

东华理工大学数学建模一周论文论文题目：面试时间最短问题模型姓名1：学号：姓名2：学号：102032020姓名3：学号：10203202专业：环境工程班级：10203202指导教师：胡彬2012年6月15日摘要：本论文对题目C进行了研究，这个题目是一个比较现实的问题，面试求职普遍出现于公司招聘事务中，而随着求职者的增多，公司不得不考虑人数和时间的问题，若按照传统的办法，对面试人没有进行排序，随便来一个面试一个，这样的安排绝对是不科学的，务必会造成面试总时间较长的问题。有的人也许会说，每个人的面试时间都确定了，那无论他们怎么排，总时间不就确定了吗？这种思维肯定是不正确的。有题目介绍，公司对甲乙丙丁各阶段的面试时间都确定了，且不能插队(即在任何一个阶段4名同学的顺序是一样的)，那么就会存在下面两种问题：问题一：对任意两名求职者A、B，按A在前，B在后的顺序进行面试时，当A完成第二个阶段时，他用时15分钟，同时B在进行第一阶段的面试，但他只用时10分钟，这样就出现了面试人B等A的情况了。问题二：对任意两名求职者A、B，按A在前，B在后的顺序进行面试时,当A进行第二阶段的面试时，，他用时15分钟，同时B在进行第一阶段的面试，但他用时18分钟，这样就出现了面试考官面试A后等B的情况了。不利于面试时间的进行。要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要是考官等候求职者的时间和求职者等候求职者和考官的时间之和最短，这样就使求职者和考官的时间利用率达到了最高。他们就能以最短的时间完成面试一起离开公司。本文从时间，人数以及顺序的角度，并根据求最优值的方法建立了基本的线性方程模型。在建立模型以及模型求解中，我们借助Lingo8.0语言编程得出了四名同学分别按可以插队和不可以插队时的最优方案：即按丁、甲、乙、丙的顺序进行面试，秘书、主管、经理三人才能最早离开公司。为了形象表达出顺序问题我们绘制出了顺序图，以及另外一个相关的表格。最后本文列出了Lingo8.0中的源代码和解决问题的全过程，得出丁、甲、乙、丙的顺序为最优方案，共用84分钟。即4名同学可在9：24一起离开公司。关键词：排列排序0-1非线性规划模型线性优化Lingo,面试时间最短，整数规划问题重述如何安排好面试时间使其达到最优是目前面试者和面试部门值得考虑的问题。安排好时间，才能是个人和公司的利益达到最大化，因此研究并解决这类问题具有重要的意义。有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队(即在任何一个阶段4名同学的顺序是一样的)。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示(单位：分钟)：问题：这4名同学约定全部面试完以后一起离开公司，假定现在的时间是8：00，问他们最早何时能离开公司？模型假设：（1）、假设面试者从一个阶段到下一个阶段参加面试的时间间隔为0；（2）、假定面试者都能在8：00准时到达面试地点；（3）、假定可以任意排列面试者的面试顺序;（4）、假定甲乙丙丁均能顺利通过面试，而且没有中途退场的情况出现。（5）、我们假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关问题分析由题知，求4名同学最早离开公司的时间，即求4名同学都在公司面试完毕所需的最短时间。由于每人在3个阶段的面试时间不同且每个同学都不允许插队，故可知道面试总时间的长短是由面试顺序决定的。所以我想出用规划的方法并借助Lingo来解决这个问题。符号说明1、t(ij)(i=1,2,3,4;j=1,2,3)为面试者i在第j阶段参加面试所用时间，甲乙丙丁对应1，2，3，4；2、x（ij）表示第i个同学参加第j阶段的面试时间（8：00为0时刻）。秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁810153、T为全部面试所花费的最少时间。建立模型实际上，这个问题就是要安排4名同学的面试顺序，是完成全部面试所花费的时间最少。时间构成原始时间矩阵：A(ij)=a11a12a13a21a22a23a31a32a33a41a42a43A(ij)=13152010201820161081015优化目标：MinT=max(x(i3)+t(j3))约束条件：x(i,j)+t(i,j)=x(i,j+i);i=1,2,3,4;j=1,2(每个同学只能参加完前一阶段才能进入下一阶段的面试)每阶段j同一时间只能面试i名同学；0-1变量y(i,k)表示第k名同学是否排在第i名同学前面（1表示“是”，0表示“否”）x(i,j)+t(i,j)-x(k,j)=200*y(i,k);i,k=1,2,3,4;ik,j=1,2,3x(k,j)+t(k,j)-x(i,j)=200*(1-y(i,k));i,k=1,2,3,4;ik,j=1,2,3将非线性的优化目标改写成线性的优化目标：MinTs.tT=x(i3)+t(i3),i=1,2,3,4模型求解根据建立的模型，编写出lingo程序代码（见附录），通过lingo软件运行结果如下：LINGO程序结果：Globaloptimalsolutionfound.Objectivevalue:84.00000Extendedsolversteps:12Totalsolveriterations:476VariableValueReducedCostNs4.0000000.000000Np3.0000000.000000TMAX84.000000.000000T(S1,P1)13.000000.000000T(S1,P2)15.000000.000000T(S1,P3)20.000000.000000T(S2,P1)10.000000.000000T(S2,P2)20.000000.000000T(S2,P3)18.000000.000000T(S3,P1)20.000000.000000T(S3,P2)16.000000.000000T(S3,P3)10.000000.000000T(S4,P1)8.0000000.000000T(S4,P2)10.000000.000000T(S4,P3)15.000000.000000X(S1,P1)8.0000000.000000X(S1,P2)21.000000.000000X(S1,P3)36.000000.000000X(S2,P1)26.000000.000000X(S2,P2)36.000000.000000X(S2,P3)56.000000.000000X(S3,P1)36.000000.000000X(S3,P2)58.000000.000000X(S3,P3)74.000000.000000X(S4,P1)0.0000001.000000X(S4,P2)11.000000.000000X(S4,P3)21.000000.000000Y(S1,S2)0.000000-200.0000Y(S1,S3)0.0000000.000000Y(S1,S4)1.000000200.0000Y(S2,S3)0.000000-200.0000Y(S2,S4)1.0000000.000000Y(S3,S4)1.0000000.000000RowSlackorSurplusDualPrice10.0000000.00000020.0000000.00000035.0000000.0000004172.00000.00000050.0000001.0000006165.00000.00000070.0000000.0000008162.00000.000000915.000000.00000010152.00000.0000001122.000000.00000012147.00000.0000001318.000000.00000014152.00000.00000015179.00000.000000160.0000001.000000结果分析由变量TMAX的最优解值为84.00000，知最短时间为84分钟，即4名同学一起离开公司的时间是9：24.由变量Y(S1,S2)的最优解值0.000000，知student1排在student2之前，即同学甲排在同学乙之前。由变量Y(S1,S3)的最优解值为0.000000，知student1排在student3之前，即同学甲排在同学丙之前。由变量Y(S1,S4)的最优解值为1.000000，知student4排在student1之前，即同学丁排在同学甲之前。由变量Y(S2,S3)的最优解值为0.000000，知student2排在student3之前，即同学乙排在同学丙之前。由变量Y(S2,S4)的最优解值为1.000000，知student4排在student2之前，即同学丁排在同学乙之前。由变量Y(S3,S4)的最优解值为1.000000，知student4排在student3之前，即同学丁排在同学丙之前。所以面试顺序为丁甲乙丙。具体安排如下：先规定8:00:00为0时刻。同学丁在0时刻到秘书处进行初试，同学丁完成初试需要用时8分钟，当初试完成后再等3分钟，等到11分钟后到主管处进行复试，同学丁完成复试需要用时10分钟，复试完成后直接去经理处进行面试，此时时间为21分钟，同学顶丁完成面试需要用时15分钟，最终，同学丁在36分钟时刻完成整个面试过程。第二个进行面试的是同学甲，同学甲在8分钟时刻，即同学丁刚完成秘书初试后，进行初试。同学甲花13分钟，在21分钟时刻完成初试，此时同学丁刚完成复试离开，同学甲立刻到主管处进行复试，用时15分钟完成复试，此时为36分钟时刻，同学丁刚完成经理面试离开，同学甲立即到经理处进行面试，用时20分钟，最终在56分钟时刻完成整个面试过程。第三个进行面试的是同学乙，同学乙在26分钟时刻开始面试，此时刻为同学甲完成初试后再过5分钟，同学乙用时10分钟，在36分钟时刻完成秘书初试，此时同学甲刚完成主管复试离开，同学乙即刻去主管处进行复试，用时20分钟完成复试，此时为56分钟时刻，甲刚完成经理面试，同学乙可以立即到经理处进行面试，最终同学乙用时18分钟完成经理面试，并在74分钟时刻完成整个面试过程。最后剩下同学丙。在36分钟时刻开始秘书初试，此时同学乙刚完成秘书初试，同学丙用时20分钟，在56分钟时刻完成初试，此后再等2分钟在58分钟时刻开始主管复试，此时同学乙已经在进行经理面试，同学丙用时16分钟完成复试，此时为74分钟时刻，同学乙刚完成经理面试离开，这时同学丙立即去经理处面试，最终，同学丙用时10分钟完成经理面试，并在84分钟时刻完成整个面试过程。至此，丁甲乙丙四名同学依次总计用时84分钟完成所有面试，在9:24时刻离开。模型推广本模型的建立思路清晰、简单，是一个非常典型的0-1非线性规划模型。该模型就有实用性，能使个人和公司的利益达到最大化，因此次模型及其推广对研究并解决这类问题具有重要的意义。这种模型可以应用于某工厂用n种原料经过s个阶段生产出不同的产品，并且是一种原料生产必须经过第一个阶段，然后经过第二个阶段直到第s个阶段才能生产出一种产品，并且一种原料在第k个阶段生产的时候，其他原料不能进行第k个阶段的生产。原料i在j阶段生产的时间为c(i,j)i=1到n，j＝1到s。问如何安排这n种原料的生产顺序?使这n种产品在最短的时间内生产出来参考文献1.洪毅林建良等，数学模型，高等教育出版社，2004－05－1；2.王泽文，乐励华，颜七苼等东华理工大学数学实验与数学模型；2010.93.万宝成.LINGO8.0forwindows软件及应用，2005－6－34.数学建模方法杨学桢河北大学出版社2000附录model:sets:students;！学生集三阶段面试模型；phases;！阶段集；sp(students,phases):t,x;ss(students,students)|&1#LT#&