学生面试时间最优规划模型.docx

1、学生面试时间最优规划模型学生面试时间最优规划模型摘要本文主要研究面试时间最优问题，并建立0-1非线性规划模型。首先我们对给出的面试时间表格进行分析将题中数据构成原始时间矩阵，然后列出单个学生面试时间先后次序的约束和学生间的面试先后次序保持不变约束，并将非线性的优化目标改写成线性优化目标。最后利用Lingo编程求解，得出丁、甲、乙、丙的顺序为最优方案，共用84分钟。即4名同学可在9：24一起离开公司。关键词： 排列排序 0-1非线性规划模型 线性优化一、 问题重述如何安排好面试时间使其达到最优是目前面试者和面试部门值得考虑的问题。安排好时间，才能是个人和公司的利益达到最大化，因此研究并解决这类问

2、题具有重要的意义。有4名学生到一家公司参加三阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管出复试，最后到经理出参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）由于4名同学的专业背景不同，所以每个学生在每个阶段的面试时间也不同，时间如下：秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015问题：这4名同学约定全部面试完以后一起离开公司，假定现在的时间是8：00，问他们最早何时能离开公司？ 二、 问题分析按照公司的要求，四名学生面试的顺序一旦确定，以下的各个阶段中面试的顺序将不再改变，由于每个学生的面试时间不同且固定

3、不变，所以对任意面试学生A、B，按A在前B在后的顺序进行面试，可能有两种情况：a) 当A进行完第i段面试后，B还未完成第i-1段的面试，所以第i段的考官必须要等待B完成第i-1段的面试后，才可以对B进行面试。b) 当B完成第i-1段面试后，A还未完成第i段面试，所以B必须等待A完成第i段面试后，才能进入第i段面试。以上两种情况，延长了面试的时间。所以要想四个面试学生能尽早离开公司，只要求考官等候学生的时间和面试学生等候面试学生的时间最短，这样学生和考官的时间利用率达到最高，学生就可以尽早离开公司，要想解决时间最短问题，必须满足：对任意两个学生之间，考官等候面试学生的时间与学生等候学生的时间之和

4、最短。三、 模型假设1、 面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，我们假设它为0；2、 我们假设参加面试的学生都是平等且独立的，他们的面试顺序与考官无关，也没有约好面试顺序；3、 每一位同学都能完成面试；4、 学生都准时达到面试点。四、 符号说明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时刻）。3、 T为全部面试所花费的最少时间。五、 模型建立实际上，这个问题就是要安排4名同学的面试顺序，是完成全部面试所花费的时间最少。时间构成原始时

5、间矩阵：A(ij)= a11 a12 a13 a21 a22 a23 a31 a32 a33 a41 a42 a43A(ij)=13 15 20 10 20 18 20 16 10 8 10 15优化目标：Min T=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;i

6、k,j=1,2,3x(k,j)+t(k,j)-x(i,j)=200*(1-y(i,k); i,k=1,2,3,4;i=x(i3)+t(i3),i=1,2,3,4六、 模型求解根据建立的模型，编写出lingo程序代码（见附录），通过lingo软件运行结果如下：LINGO 程序结果：Global optimal solution found.Objective value: 84.00000Extended solver steps: 12Total solver iterations: 476Variable Value Reduced Cost Ns 4.000000 0.000000 Np

7、3.000000 0.000000 TMAX 84.00000 0.000000 T(S1,P1) 13.00000 0.000000 T(S1,P2) 15.00000 0.000000 T(S1,P3) 20.00000 0.000000 T(S2,P1) 10.00000 0.000000 T(S2,P2) 20.00000 0.000000 T(S2,P3) 18.00000 0.000000 T(S3,P1) 20.00000 0.000000 T(S3,P2) 16.00000 0.000000 T(S3,P3) 10.00000 0.000000 T(S4,P1) 8.00000

8、0 0.000000 T(S4,P2) 10.00000 0.000000 T(S4,P3) 15.00000 0.000000 X(S1,P1) 8.000000 0.000000 X(S1,P2) 21.00000 0.000000 X(S1,P3) 36.00000 0.000000 X(S2,P1) 26.00000 0.000000 X(S2,P2) 36.00000 0.000000 X(S2,P3) 56.00000 0.000000 X(S3,P1) 36.00000 0.000000 X(S3,P2) 58.00000 0.000000 X(S3,P3) 74.00000 0

9、.000000 X(S4,P1) 0.000000 1.000000 X(S4,P2) 11.00000 0.000000 X(S4,P3) 21.00000 0.000000 Y(S1,S2) 0.000000 - 200.0000 Y(S1,S3) 0.000000 0.000000 Y(S1,S4) 1.000000 200.0000 Y(S2,S3) 0.000000 -200.0000 Y(S2,S4) 1.000000 0.000000 Y(S3,S4) 1.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 0.0

10、00000 2 0.000000 0.000000 3 5.000000 0.000000 4 172.0000 0.000000 5 0.000000 1.000000 6 165.0000 0.000000 7 0.000000 0.000000 8 162.0000 0.000000 9 15.00000 0.000000 10 152.0000 0.000000 11 22.00000 0.000000 12 147.0000 0.000000 13 18.00000 0.000000 14 152.0000 0.000000 15 179.0000 0.000000 16 0.000

11、000 1.000000最短时间为84分钟，即4名同学一起离开公司的时间是9：24.七、 模型推广本模型的建立思路清晰、简单，是一个非常典型的0-1非线性规划模型。该模型就有实用性，能使个人和公司的利益达到最大化，因此次模型及其推广对研究并解决这类问题具有重要的意义。八、 参考文献【1】 朱旭、李焕琴，MATLAB软件与基础数学实验；【2】 姜启源、谢金星、叶俊，数学模型（第三版）；【3】 姜启源、谢金星、叶俊，数学模型习题解答（第三版）【4】 肖华勇，实用数学建模与软件应用九、 附录model:sets:students;！学生集三阶段面试模型；phases; ！阶段集；sp(student

12、s,phases):t,x;ss(students,students)|&1 #LT# &2:y;endsetsdata:students=s1.s4;phases=p1.p3;t=13 15 20,10 20 18,20 16 10,8 10 15;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=TMAXfor(students(i):x(i,3)+t(i,3)=TMAX);！把y定义0-1变量；for(ss:bin(y);end