面试时间最短模型

面试时间最短模型面试时间最短模型面试时间最短模型面试时间最短模型编制仅供参考审核批准生效日期地址：电话：传真:邮编:面试时间最短模型问题提出有4名同学到一家公司参加三个阶段的面试。面试要求为：每个同学应依次找秘书、主管、经理进行初试、复试、面试；每个同学都不允许插队。每人在三个阶段的面试时间都不同，具体如下表所示（单位：分钟）：秘书初试主管复试经理面试同学甲121518同学乙101815同学丙201614同学丁81015根据题意，本文应解决的问题有：这4名同学约定他们全部面试完以后一起离开公司。假定现在的时间是早晨8：00，求他们最早离开公司的时间；问题分析由题知，求4名同学最早离开公司的时间，即求4名同学都在公司面试完毕所需的最短时间。由于每人在3个阶段的面试时间不同且每个同学都不允许插队，故可知道面试总时间的长短是由面试顺序决定的。而4名同学的面试顺序有4！=24种情况，也就是说本题可以用穷举法一一列出然后取使面试总时间最小的顺序，但是明显这样做的法会很麻烦，所以我想出用规划的方法并借助Lingo来解决这个问题。符号说明Tij表示第i个同学第j阶段的面试时间；Xij表示第i个同学第j阶段开始面试的时刻；Yik表示若第k个同学排在第i个同学之前，记为Yik=1，否则为Yik=0；T表示4名参加面试的同学同时离开公司的时间；MinMaX分别表示取最小值和最大值；附：i=1，2，3，4；j=1，2，3；k=1，2，3，4基本假设假设面试者均能在8:00准时到达面试地点，且记此时为0时刻；假设每个面试者由一个阶段到下一个阶段的时间间隔为0；假设面试中途没有被淘汰，也没人中途没退出。模型建立模型建立求4名同学在公司面试完毕所需的最短时间，考虑到面试总时间的长短是由面试顺序决定的，即要找一个面试顺序使得4名同学面试完毕的4个时刻的最大值这一情况时所用的面试总时数最短。故由Tij（分钟）～第i个同学第j阶段的面试时间（如下表）：Tijj=1j=2j=3i=1131520i=2102018i=3201610i=481015Xij（第i个同学第j阶段开始面试的时刻）可建立目标函数为：MinT=MaX{Xij+Tij}①的规划模型。其中约束条件有：（1）时间先后次序约束（没人只有参加完前一个阶段的面试才能进入下一个阶段）：Xij+Tij<=Xi，j+1（i=1，2，3，4；j=1，2）（2）每个阶段j同一时间只能面试一名同学：用变量Yik表示第k个同学排在第i个同学之前，记为Yik=1，否则为Yik=0，则有：Xij+Tij-Xkj<TYik(i,k,j=1,2,3;i<k)②Xkj+Tkj-Xij<T(1-Yik)(i,k,j=1,2,3;i<k)③模型求解模型求解由目标函数①式和约束条件②③，利用LINGO软件求解可得：由结果可知：面试所用总时间为84分钟，即他们同时离开公司的时刻为上午9:24，根据Y12=0,Y13=0,Y14=1,Y23=0,Y24=1,Y34=1,可知面试顺序为4-1-2-3，即：丁-甲-乙-丙。结果检验按照丁-甲-乙-丙这一面试顺序，利用题中表里的数据，计算得面试所用时间刚好为84分钟。模型改进方向（略）参考文献（略）附录：源代码model:min=T;X41+8<=X42;X42+10<=X43;X31+20<=X32;X32+16<=X33;X21+10<=X22;X22+20<=X23;X11+13<=X12;X12+15<=X13;T>=X43+15;T>=X33+10;T>=X23+18;T>=X13+20;X31+20-X41<T*Y34;X32+16-X42<T*Y34;X33+10-X43<T*Y34;X21+10-X31<T*Y23;X22+20-X32<T*Y23;X23+18-X33<T*Y23;X21+10-X41<T*Y24;X22+20-X42<T*Y24;X23+18-X43<T*Y24;X11+13-X21<T*Y12;X12+15-X22<T*Y12;X13+20-X23<T*Y12;X11+13-X31<T*Y13;X12+15-X32<T*Y13;X13+20-X33<T*Y13;X11+13-X41<T*Y14;X12+15-X42<T*Y14;X13+20-X43<T*Y14;X41+8-X31<T*(1-Y34);X42+10-X32<T*(1-Y34);X43+15-X33<T*(1-Y34);X41+8-X21<T*(1-Y24);X42+10-X22<T*(1-Y24);X43+15-X23<T*(1-Y24);X31+20-X21<T*(1-Y23);X32+16-X22<T*(1-Y23);X33+10-X23<T*(1-Y23);X21+10-X11<T*(1-Y12);X22+20-X12<T*(1-Y12);X23+18-X13<T*(1-Y12);X31+20-X11<T*(1-Y13);X32+16-X12<T*(1-Y13);X33+10-X13<T*(1-Y