多阶段面试排队决策模型.docx

《多阶段面试排队决策模型.docx》由会员分享，可在线阅读，更多相关《多阶段面试排队决策模型.docx（10页珍藏版）》请在优知文库上搜索。

1、目录摘要3一、问题重述4二、问题分析4三、模型假设4四、符号说明5五、模型建立5六、模型求解6七、模型评价7八、模型推广7参考文献7附录8多阶段面试排队决策模型摘要本文建立了多阶段面试排队决策的优化模型，研究在不同阶段怎样安排同学参加面试才能使得所花费的总时间最少（即本文中的最早何时能离开公司）问题。首先，本文的问题概述如下：有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。已知每个同学在各个阶段面试所需时间（详见附2表一）。各同学约定他们全部面试完以后一起离开

2、公司。假定现在时间是早晨8:00,问他们最早何时能离开公司。本问题是一个排列排序问题。对于阶段数不小于3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如20）的情况是无法精确求解的,为此人们找到了很多近似算法。然而，针对这一问题，本文建立了一个全部同学面试完时间最短的规划模型，可以实现该问题的精确求解，但它的变量和约束是学生数的平方。而在建立此模型的过程中，本文一开始将目标函数建立成一个线性规划模型，即求所有同学排序情况下，被排在最后的一个同学面试完时所用总时间T（也即排序后，从第一个同学参加第一阶段面试时开始计时，到最后一个同学面试完最后一阶段的这段时间）中最小的一个。然后，又建立了一

3、个01变量表示其约束条件。对该模型的求解，本文用LINGO的集合程序求解（程序及运行结果见附录）.得到的结果分析可得,所有面试完成至少需要84分钟，同时也得出面试的顺序为4-1-2-3（即丁-甲-乙-丙）.该模型具有简便、易懂，又有比较好的实用性和技巧性，因为它用几个简单的约束条件将所有情况都考虑在内了。关键词：多阶段面试，排队问题，OT线性规划一、问题重述在对同学进行排序时，人们常常就会想到底怎样将这四名同学排序，才能够使得四名同学全部面试完所用的时间最短。为了能够做到这一点，我们在排序之前必须对各种影响面试总时间的因素约束条件和题目中的一些要求进行分析。由于4名同学的专业背景不同，所以要去

4、了解这四名同学的一些相关信息，并得到如下表所示的每一个同学在每一个阶段面试所需时间：秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015而且公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试,并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。本题需要我们设计一种排序方案，使得四位同学面试的总时间最短，这样他们才能最早地离开公司。二、问题分析这是一个优化问题，要决策的是将甲乙丙丁进行排序，即所谓的排列排序，要达到的目标只有一个，就是要使得四名同学面试后能最早离开公司，也就是他们面试的总时间最少。但是将四名同学进行

5、排序时，得到的排序结果蛮多，所以我们要找到一个合适和简便的方法来求解每一种情况下，面试时间最短的那种排序。建立优化问题的模型最主要的是用数学符号和式子表述决策变量、构造目标函数和确定约束条件。对于本题决策变量是明确的，即第i个同学开始面试第三个阶段时的时刻Xi3,及第i个同学面试第三个阶段所用时间目标函数为所有同学排序情况下，被排在最后的一个同学面试完时所用总时间T（也即排序后，从第一个同学参加第一阶段面试时开始计时，到最后一个同学面试完最后一阶段的这段时间）中最小的一个，即MinTMaxxi3+ti3o约束条件为每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并

6、且不允许插队（即在任何一个阶段4名同学的顺序是一样的），及由于4名同学的专业背景不同，使得每人在三个阶段的面试时间也不同。三、模型假设1、面试时间是连续的，即在面试期间中间没有休息，也没有因为其他原因而使得面试时间有间断；2、每个同学在三个阶段面试的时间是确定不变的，就如表格中所给的；3、从O时刻开始面试；4、各个面试地点尽可能的接近（即人们从一个面试地点到另外一个面试地点的步行时间忽略）；5、每个同学被排序后的结果是等可能发生的；四、符号说明及名词定义xijs第i名同学参加第j阶段面试的开始时刻（记从O时刻开始面试）；tijs第i名同学参加第j阶段面试需要的时间；yik第k名同学是否排在i名

7、同学前面（1表示是，O表示否）；T:四个同学面试完后所用的总时间；五、模型建立（一）对于问题的OT线性规划模型记1为第i名同学参加第j阶段面试需要的时间，令Xij表示第i名同学参加第j阶段面试的开始时刻（记从0时刻开始面试）（i=l,2,3,4;j=l,2,3）.优化目标为MinTMaxxi3+ti3.约束条件：D面试阶段次序约束（每人参加完前一个阶段才能继续参加下一个阶段）ij*tijXi.j+（i1,2,3,4;j-l,2）2）每个阶段j在同一时间只能面试一名同学：用OT变量yik表示第k名同学是否排在i名同学前面（1表示是，0表示否），则当yi*0时，k同学在i同学后面，有Xij+tij

8、-Xkj0(i,k=l,2,3,4；j=l,2,3;ik)xk.i+tk,i-ijWT(i,k=l,2,3,4;j=l,2,3;ii=l时，i同学在k同学后面，有Xij+tij - Xkj T Xkj+tt Xij WO 故综合上述得 Xijtij-Xkj Tyik Xkj+tkj一Xij T(I-Yik)(i,k=l,2,3,4;j=l,2,3;ik)(i,k=l,2,3,4；j=l,2,3;ik)(i,k=l,2,3,4;j=l,2,3;ik)(i,k=l,2,3,4;j=l,2,3;ik)（二）对于问题的OT线性规划模型进行改善将目标函数改写为:MinT满足面试完同时离开这一约束,则TX

9、3taT2x23+t23T2X33+t33T2x,3+t,3加上约束条件1)、2)目标函数：MinT(i=l,2, 3, 4； J=I, 2)(i,k=l,2, 3,4;j=l,2,3;ik)(i,k=l,2, 3,4;j=l,2,3;ik)约束条件：Xij+tijXi,j1xij+tij-kjTyikxkj+tkj-kjT(l-yik)TXl3ti3T2x23+t232x33+t33Tx13+t43六、模型求解根据模型，用LINGo软件编程求解（详细的程序说明及运行结果见附录）并对结果进行分析得各同学在各个阶段的面试情况。各阶段开始时刻各阶段所需时间各阶段结束时时刻甲，阶段一81321甲，阶

10、段二211536甲，阶段三362056乙，阶段一261036乙，阶段二362056乙，阶段三561874丙，阶段362056丙，阶段二561672丙，阶段三741084T,阶段一088T,阶段二81018T,阶段三211536由已知数据，进行图形描绘得:时间/分密从结果分析可得，丙同学第三阶段的面试结束时间最晚，即所有面试完成至少需要84分钟。而面试的顺序为4-1-2-3（即丁-甲-乙-丙）.七、模型评价本文建立了多阶段面试排队决策的优化模型，通过目标函数，从而建立成了一个线性规划模型，求地了所有同学排序情况下，被排在最后的一个同学面试完时所用总时间T（也即排序后，从第一个同学参加第一阶段面试

11、时开始计时，到最后一个同学面试完最后一阶段的这段时间）中最小的一个，然后，又建立了一个01变量表示其约束条件，并使用LlNGO软件求解，所得结果具有一定的正确性和指导意义。但是，本文只讨论了四个同学面试三个阶段的合理排序方法，而没有讨论更多同学面试更多的阶段的合理排序的解决方案，从而使得面试总时间最短。在实际应用中还存在许多更复杂但是类似相关的情形，此时，若还用本文中的解决方案未必是合理的。因此，对更多同学面试更多的阶段的合理排序的解决方案是进一步应该研究和改进的方向。八、模型推广由于在模型求解中利用了Lingo软件，大大简化了编程工作，而且模型本身跟结合软件的使用就具有很强的可移植性，便于模

12、型的推广。例如，本文只讨论了四个同学面试三个阶段的合理排序方法，所以该模型还可以进一步推广到更多同学面试更多的阶段的层面上去，这样就更具有实际运用的意义了。参考文献1姜启源、谢金星、叶俊，数学模型（第三版），北京高等教育出版社，2003.8；2肖华勇，基于MATLAB和LlNGo的数学实验,西安西北工业大学出版社，2003.9；3洪文、吴本忠，Lingo4.Oforwindows最优化软件及应用，北京大学出版，2001；4越名义、韩继业,n个零件在m台机床上的加工顺序，中国科学（第五期），1975.9；附录附1详细的程序说明及运行结果：model:sets:StUdents;!学生集三阶段面试

13、模型；PhaSes;!阶段集；sp(students,phases):t,x;ss(students,students)&1#LT#&2:y;endsetsdata:students=si.s4;phases=pl.p3;t=13152010201820161081015;enddatans=0size(students);!学生数；np=SiZe(PhaSes);!阶段数；!单个学生面试时间先后次序的约束；0for(sp(i,j)Ij#LT#np:x(i,j)+t(i,j)=x(i,j+l)；!学生间的面试先后次序保持不变的约束；for(ss(i,k):Qfor(phases(j):x(i,

14、j)+t(i,j)-x(k,j)=200*y(i,k);x(k,j)+t(k,j)-(i,j)=200*(l-y(i,k);)；!目标函数；min=TMAX;or(students(i):x(i,3)+t(i,3)=TMAX)；!把Y定义0-1变量；for(ss:bin(y);end运行结果：Globaloptimalsolutionfound.84. OOOOO84. 000000.1532108E-138598Objectivevalue:Objectivebound:Infeasibilities:Extendedsolversteps:Totalsolveriterations:VariableValueReducedCostNS4.0000000.000000NP3.0000000.000000TMAX84.000000.000000(Si,PD13.000000.000000(si,P2)15.000000.000000(si,P3)20.000000.000000(S2,PD10.000000.000000(S2,P2)20.000000.000000(S2,P3)18.000000.0