面试等候最短时间建模

1课程设计题目：面试顺序摘要：文章以同学最早时间离开公司为研究课题，在同学人数和面试顺序确定的情况下，采用系统的观点对问题进行综合全面分析。根据题目已知的条件，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理出参加面试，并且不允许插队。假设，每个面试的同学都必须按照先到公司秘书处初试，然后到主管处复试，最后到经理处面试的顺序进行；在面试的任何一个阶段都不存在插队现象，即在任何一个阶段4名同学的顺序都是一样的；每个阶段一次只能面试一个同学；面试的每个过程都顺利进行，相邻两个过程之间没有间隔时间。建立模型，得出离开的最早时间。1.问题重述有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先到公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序都是一样的）。由于4名同学的专业背景不同，所以没人在三个阶段的面试时间不同，如表所示（单位：min）:秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015这4名同学约定他们全部面试完后一起离开公司。假定现在时间是早上8:00，问他们最早何时能离开公司？2.基本假设：1.每个面试的同学都必须按照先到公司秘书处初试，然后到主管处复试，最后到经理处面试的顺序进行；2.在面试的任何一个阶段都不存在插队现象，即在任何一个阶段4名同学的顺序都是一样的；3.每个阶段一次只能面试一个同学；4.面试的每个过程都顺利进行，相邻两个过程之间没有间隔时间。3.符号说明ijt第i名同学参加第j阶段面试所需要的时间ijx第i名同学参加第j阶段面试开始时刻（记早上8:00面试开始为0时刻）T所有同学参加完面试所需时间iky0-1变量，表示第k名同学是否排在第i名同学前面24.模型建立与求解4.1模型建立目标函数：minTmin33maxiixt其中，1,2,3,4i约束条件：1）每人只有参加完前一个阶段的面试才能进入下一阶段的面试：,1ijijijxtx1,2,3,4;1,2ij2）每个阶段j同一时间只能面试1名同学，用0-1变量表示第k名同学是否排在第i名同学前面：0,(1,ikkyk第名同学排在第i名同学前面）（第名同学不排在第i名同学前面）(1ijijkjikkjkjijikxtxTyxtxTy）其中，,1,2,3;1,2,3;ikjik因此，基本模型可以表示为：min33max{}iixt(1,2,3,4)i,1ijijijxtx1,2,3,4;1,2ij(1ijijkjikkjkjijikxtxTyxtxTy）0,(1,ikkyk第名同学排在第i名同学前面）（第名同学不排在第i名同学前面）4.2模型求解：将原模型进行修改后，用lingo求解，可得求解结果如下：Globaloptimalsolutionfound.Objectivevalue:84.00000Objectivebound:84.00000Infeasibilities:0.1532108E-13Extendedsolversteps:8Totalsolveriterations:598VariableValueReducedCostNS4.0000000.000000NP3.0000000.000000TMAX84.000000.000000S(1)0.0000000.000000S(2)0.0000000.000000S(3)0.0000000.000000S(4)0.0000000.000000P(1)0.0000000.000000P(2)0.0000000.000000P(3)0.0000000.0000003T(1,1)13.000000.000000T(1,2)15.000000.000000T(1,3)20.000000.000000T(2,1)10.000000.000000T(2,2)20.000000.000000T(2,3)18.000000.000000T(3,1)20.000000.000000T(3,2)16.000000.000000T(3,3)10.000000.000000T(4,1)8.0000000.000000T(4,2)10.000000.000000T(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)36.000000.000000X(3,2)56.000000.000000X(3,3)74.000000.000000X(4,1)0.0000001.000000X(4,2)8.0000000.000000X(4,3)21.000000.000000Y(1,2)0.000000-200.0000Y(1,3)0.0000000.000000Y(1,4)1.000000200.0000Y(2,3)0.000000-200.0000Y(2,4)1.0000000.000000Y(3,4)1.0000000.000000RowSlackorSurplusDualPrice10.0000000.00000020.0000000.00000035.0000000.0000004172.00000.00000050.0000001.0000006165.00000.00000070.0000000.0000008162.00000.000000915.000000.00000010152.00000.0000001120.000000.00000012149.00000.0000001318.000000.00000014152.00000.00000015179.00000.000000160.0000001.00000017172.00000.000000183.0000000.00000019165.00000.000000200.0000000.000000210.0000000.00000022170.00000.000000230.0000000.00000024164.00000.000000250.0000001.00000026172.00000.00000027164.00000.0000002818.000000.00000029152.00000.00000043018.000000.00000031147.00000.0000003220.000000.00000033144.00000.0000003428.000000.00000035136.00000.0000003638.000000.00000037137.00000.0000003838.000000.0000003984.00000-1.0000004028.000000.0000004110.000000.000000420.0000001.0000004348.000000.000000440.0000001.000000450.0000000.000000460.0000000.000000470.0000001.000000480.0000000.000000492.0000000.000000500.0000000.000000513.0000000.0000004.3结果分析：由上述结果可知，当面试顺序为丁-甲-乙-丙时，四人的面试时间可以达到最短，最短时间为84分钟。附录：源代码：model:sets:students/1..4/:s;phases/1..3/:p;sp(students,phases):t,x;ss(students,students)|&1#LT#&2:y;endsetsdata:t=13152010201820161081015;enddatans=@size(students);np=@size(phases);@for(sp(i,j)|j#LT#np:x(i,j)+t(i,j)=x(i,j+1));@for(ss(i,k):@for(phases(j):x(i,j)+t(i,j)-x(k,j)=200*y(i,k);x(k,j)+t(k,j)-x(i,j)=200*(1-y(i,k));));min=tmax;@for(students(i):x(i,3)+t(i,3)=tmax);@for(ss:@bin(y));end