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

学生面试时间最优规划模型 摘要 本文主要研究面试时间最优问题，并建立0-1非线性规划模型。 首先我们对给出的面试时间表格进行分析将题中数据构成原始时间矩阵，然后列出单个学生面试时间先后次序的约束和学生间的面试先后次序保持不变约束，并将非线性的优化目标改写成线性优化目标。最后利用Lingo编程求解，得出丁、甲、乙、丙的顺序为最优方案，共用84分钟。即4名同学可在9：24一起离开公司。 关键词： 排列排序 0-1非线性规划模型 线性优化 问题重述 如何安排好面试时间使其达到最优是目前面试者和面试部门值得考虑的问题。安排好时间，才能是个人和公司的利益达到最大化，因此研究并解决这类问题具有重要的意义。 有4名学生到一家公司参加三阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管出复试，最后到经理出参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）由于4名同学的专业背景不同，所以每个学生在每个阶段的面试时间也不同，时间如下： 秘书初试 主管复试 经理面试 同学甲 13 15 20 同学乙 10 20 18 同学丙 20 16 10 同学丁 8 10 15 问题：这4名同学约定全部面试完以后一起离开公司，假定现在的时间是8：00，问他们最早何时能离开公司？ 问题分析 按照公司的要求，四名学生面试的顺序一旦确定，以下的各个阶段中面试的顺序将不再改变，由于每个学生的面试时间不同且固定不变，所以对任意面试学生A、B，按A在前B在后的顺序进行面试，可能有两种情况： 当A进行完第i段面试后，B还未完成第i-1段的面试，所以第i段的考官必须要等待B完成第i-1段的面试后，才可以对B进行面试。 当B完成第i-1段面试后，A还未完成第i段面试，所以B必须等待A完成第i段面试后，才能进入第i段面试。 以上两种情况，延长了面试的时间。所以要想四个面试学生能尽早离开公司，只要求考官等候学生的时间和面试学生等候面试学生的时间最短，这样学生和考官的时间利用率达到最高，学生就可以尽早离开公司，要想解决时间最短问题，必须满足：对任意两个学生之间，考官等候面试学生的时间与学生等候学生的时间之和最短。 模型假设 面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，我们假设它为0； 我们假设参加面试的学生都是平等且独立的，他们的面试顺序与考官无关，也没有约好面试顺序； 每一位同学都能完成面试； 学生都准时达到面试点。 符号说明 t(ij)(i=1,2,3,4;j=1,2,3) 为面试者i在第j阶段参加面试所用时间，甲乙丙丁对应1，2，3，4； x（ij）表示第i个同学参加第j阶段的面试时间（8：00为0时刻）。 T为全部面试所花费的最少时间。 模型建立 实际上，这个问题就是要安排4名同学的面试顺序，是完成全部面试所花费的时间最少。 时间构成原始时间矩阵： A(ij)= a11 a12 a13 a21 a22 a23 a31 a32 a33 a41 a42 a43 A(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;ik,j=1,2,3 x(k,j)+t(k,j)-x(i,j)=200*(1-y(i,k)); i,k=1,2,3,4;ik,j=1,2,3 将非线性的优化目标改写成线性的优化目标： Min T s.t T=x(i3)+t(i3),i=1,2,3,4 模型求解 根据建立的模型，编写出lingo程序代码（见附录），通过lingo软件运行结果如下： LINGO 程序结果： Global optimal solution found. Objective value: 84.00000 Extended solver steps: 12 Total solver iterations: 476 Variable Value Reduced Cost Ns 4