数学建模-面试最优化问题

C题面试时间问题有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队(即在任何一个阶段4名同学的顺序是一样的)。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示(单位：分钟)：这4名同学约定他们全部面试完以后一起离开公司．假定现在时间是早晨8:00问他们最早何时能离开公司?面试时间最优化问题摘要：面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间有所不同，这样就造成了按某种顺序进入各面试阶段时不能紧邻顺序完成，即当面试正式开始后，在某个面试阶段，某个面试者会因为前面的面试者所需时间长而等待，也可能会因为自己所需时间短而提前完成。因此本问题实质上是求面试时间总和的最小值问题，其中一个面试时间总和就是指在一个确定面试顺序下所有面试者按序完成面试所花费的时间之和，这样的面试时间总和的所有可能情况则取决于n位面试者的面试顺序的所有排列数根据列出来的时间矩阵，然后列出单个学生面试时间先后次序的约束和学生间的面试先后次序保持不变的约束，并将非线性的优化问题转换成线性优化目标，最后利用优化软件lingo变成求解。关键词：排列排序0-1非线性规划模型线性优化(1)（一）问题的提出根据题意，本文应解决的问题有：1、这4名同学约定他们全部面试完以后一起离开公司。假定现在的时间是早晨8：00，求他们最早离开公司的时间；2、试着给出此类问题的一般描述，并试着分析问题的一般解法。（二）问题的分析问题的约束条件主要有两个：一是每个面试者必须完成前一阶段的面试才能进入下一阶段的面试(同一个面试者的阶段次序或时间先后次序约束)，二是每个阶段同一时间只能有一位面试者(不同面试者在同一个面试阶段只能逐一进行)。对于任意两名求职者P、Q，不妨设按P在前，Q在后的顺序进行面试，可能存在以下两情况：（一）、当P进行完一个阶段j的面试后，Q还未完成前一阶段j-1的面试，所以j阶段的考官必须等待Q完成j-1阶段的面试后，才可对Q进行j阶段的面试，这样就出现了考官等待求职者的情况。这一段等待时间必将延长最终的总时间。（二）、当Q完成j-1的面试后，P还未完成j阶段的面试，所以，Q必须等待P完成j阶段的面试后，才能进入j阶段的面试，这样就出现了求职者等待求职者的情况。同样的，这个也会延长面试的总时间。以上两种情况，必然都会延长整个面试过程。所以要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要使考官等候求职者的时间和求职者等候求职者的时间之和最短，这样就使求职者和考官的时间利用率达到了最高。他们就能以最短的时间完成面试一起离开公司。这也是我们想要的结果。（三）模型的假设1.我们假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关；2.面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，但我们在这里假定该时间间隔为0；3.参加面试的求职者事先没有约定他们面试的先后顺序；4.假定中途任何一位参加面试者均能通过面试，进入下一阶段的面试。即：没有中途退出面试者；5.面试者及各考官都能在8：00准时到达面试地点。（四）名词及符号约束1.aij（i=1,2，3，4；j=1,2,3)为求职者i在j阶段参加面试所需的时间甲乙丙丁分别对应序号i=1，2,3，42.xij（i=1,2，3，4；j=1,2,3)表示第i名同学参加j阶段面试的开始时间（不妨把早上8:00记为面试的0时刻）(2)3.T为完成全部面试所花费的最少时间（五）模型的建立设{s1，s2，s3，s4}为4位面试者的一个面试顺序,面试者si参加第j个阶段面试所需时间为aij根据问题的2个约束条件,可作出n位面试者在{s1，s2，s3，s4）面试顺序下参加3个面试阶段的进展过程表，4位面试者按序{s1，s2，s3，s4}参加3个阶段的面试进展过程表面试者T1T2T3T4T5T6s1as1,1as1,2as1,3s2as2,1as2,2as2,3s3as3,1as3,2as3,3s4as4,1as4,2as4,3表中Ti(i=l，2,⋯，P)表示能同时进行面试的人员所占用的时间段,如T3，表示面试者s1在第3个面试场,s2在第2个面试场,s3,在第1个面试场、其余人员在等待的那一个时间段.根据顺序性可知整个面试过程的时间段数为3+4-1=6模式：以各面试者结束全部面试阶段的时间为基础(以表的行为基础)目标函数minT=max{xi3+ai3}约束条件(1)面试阶段约束，即必须先完成上一阶段面试才能进人下一阶段面试。xij+aij≤xi，j+1i=l，2，3,4；j=1,2，3）(2)同一阶段只能有一个面试者xij+aij-xki≤Tyikxkj+akj-xij≤T(1-yik)（i，k=l，2,3,4，ik；j=l，2，3）yik={O，l}(3)整个面试总和时间大于等于各面试者结束全部阶段面试的时间T≥xi3+ai3；i=l,2,3,4其中y是O-1变量.表示第k个面试者是否排在第i个面试者的前面,O表示否，l表示是.由此,就将问题中的约束条件“同一面试阶段只能有一个面试者”改用“面试者的先后次序”来表示解决了问题中难于表达的约束条件，反应的关系清楚,而且在模型求解的,T值就是最小总面试时间,根据全部y值就可以排出所有面试者使T最小的面试顺序。(3)（六）模型的求解编写的lingo程序如下：model:title面试问题;sets:!person=被面试者集合,stage=面试阶段集合;person/1,2,3,4/;stage/1,2,3/;!a=面试所需时间,x面试开始时间;pxs(person,stage):a,x;!y(i,k)=1:k排在i前,0:否则;pxp(person,person)|&1#lt#&2:y;endsetsdata:a=13152010201820161081015;enddatamin=maxa;!maxa是面试最后结束时间;maxa=@max(pxs(i,j)|j#eq#@size(stage):x(i,j)+a(i,j));!完成前一段才能进入下一段;@for(pxs(i,j)|j#lt#@size(stage):x(i,j)+a(i,j)x(i,j+1));!同一时间只能面试一位同学;@for(stage(j):@for(pxp(i,k):x(i,j)+a(i,j)-x(k,j)maxa*y(i,k));@for(pxp(i,k):x(k,j)+a(k,j)-x(i,j)maxa*(1-y(i,k))););@for(pxp(i,k):@bin(y(i,k)));endLingo结果如下：Localoptimalsolutionfound.Objectivevalue:84.00000Extendedsolversteps:43Totalsolveriterations:1681ModelTitle:面试问题VariableValueReducedCostMAXA84.000000.000000A(1,1)13.000000.000000（4）A(1,2)15.000000.000000A(1,3)20.000000.000000A(2,1)10.000000.000000A(2,2)20.000000.000000A(2,3)18.000000.000000A(3,1)20.000000.000000A(3,2)16.000000.000000A(3,3)10.000000.000000A(4,1)8.0000000.000000A(4,2)10.000000.000000A(4,3)15.000000.000000X(1,1)8.0000000.000000X(1,2)21.000000.000000X(1,3)36.000000.000000X(2,1)26.000000.000000X(2,2)36.000000.000000X(2,3)56.000000.000000X(3,1)38.000000.000000X(3,2)58.000000.000000X(3,3)74.000000.000000X(4,1)0.0000000.9999970X(4,2)11.000000.000000X(4,3)21.000000.000000Y(1,2)0.000000-83.99950Y(1,3)0.0000000.000000Y(1,4)1.00000083.99950Y(2,3)0.000000-83.99950Y(2,4)1.0000000.000000Y(3,4)1.0000000.000000RowSlackorSurplusDualPrice184.00000-1.00000020.000000-0.999997030.0000000.999997040.0000000.999997050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000093.0000000.000000100.0000000.000000115.0000000.0000001217.000000.000000(5)1363.000000.000000142.0000000.0000001548.000000.0000001626.000000.0000001756.000000.0000001834.000000.000000190.0000000.99999702052.000000.0000002118.000000.0000002230.000000.000000230.0000000.0000002422.000000.0000002559.000000.000000262.0000000.0000002739.000000.0000002821.000000.0000002949.000000.0000003031.000000.000000310.0000000.0000003246.000000.0000003315.000000.0000003437.000000.000000350.0000000.99999703618.000000.0000003749.000000.000000380.0000000.99999703931.000000.0000004021.000000.0000004146.000000.0000004236.000000.000000430.0000000.0000004456.000000.0000004520.000000.0000004638.000000.000000计算结果为：所有面试完成至少需要84min。面试序号为丁-甲-乙-丙。早上8:00面试，最早9:24面试可以完成.（七）模型的推广该模式是时间最优化的模型，有推广的价值。例如：车间生产的流水线作业，多(6)个部件如何按照先后次序在不同车间进行生产等。(八）主要参考文献[1]文章编号：1672-612x(2007)08-0017-05作者：谭代伦，刘益，张世禄论文名：多阶段有序面试问题的数学模型与算法研究出版报：绵阳师范学院学报出版时间：2007年8月第26卷第8期[2]谢金星,薛毅,优化建模Lingo／Lindo软件[M]．北京:清华大学出版社,2005．[3]姜启源,谢金星,叶俊.数学模型(第三版)[M].北京:高等教育出版社,2003．[4]姜启源,谢金星,叶俊.数学模型(第三版)习题参考解答[M].北京:高等教育出版社,2003.(7）