数学建模-面试最优化问题.pdf

《数学建模-面试最优化问题.pdf》由会员分享，可在线阅读，更多相关《数学建模-面试最优化问题.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C 题 面试时间问题有 4 名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队(即在任何一个阶段4名同学的顺序是一样的)。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示(单位：分钟)：这 4 名同学约定他们全部面试完以后一起离开公司假定现在时间是早晨8:00 问他们最早何时能离开公司?面试时间最优化问题摘要：面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间有所不同，这样就造成了按某种顺序进入各面试阶段时不能紧邻顺序完成，即当面试正式开始后，在某个面试阶段，某个

2、面试者会因为前面的面试者所需时间长而等待，也可能会因为自己所需时间短而提前完成。因此本问题实质上是求面试时间总和的最小值问题，其中一个面试时间总和就是指在一个确定面试顺序下所有面试者按序完成面试所花费的时间之和，这样的面试时间总和的所有可能情况则取决于 n 位面试者的面试顺序的所有排列数根据列出来的时间矩阵，然后列出单个学生面试时间先后次序的约束和学生间的面试先后次序保持不变的约束，并将非线性的优化问题转换成线性优化目标，最后利用优化软件 lingo 变成求解。关键词：排列排序0-1 非线性规划模型线性优化(1)（一）问题的提出根据题意，本文应解决的问题有：1、这 4 名同学约定他们全部面试完

3、以后一起离开公司。假定现在的时间是早晨8：00，求他们最早离开公司的时间；2、试着给出此类问题的一般描述，并试着分析问题的一般解法。（二）问题的分析问题的约束条件主要有两个：一是每个面试者必须完成前一阶段的面试才能进入下一阶段的面试(同一个面试者的阶段次序或时间先后次序约束)，二是每个阶段同一时间只能有一位面试者(不同面试者在同一个面试阶段只能逐一进行)。对于任意两名求职者 P、Q，不妨设按P 在前，Q 在后的顺序进行面试，可能存在以下两情况：（一）、当P 进行完一个阶段 j 的面试后，Q 还未完成前一阶段 j-1 的面试，所以 j 阶段的考官必须等待 Q 完成 j-1 阶段的面试后，才可对

4、Q 进行 j 阶段的面试，这样就出现了考官等待求职者的情况。这一段等待时间必将延长最终的总时间。（二）、当Q 完成 j-1 的面试后，P 还未完成 j 阶段的面试，所以，Q 必须等待 P 完成 j 阶段的面试后，才能进入 j 阶段的面试，这样就出现了求职者等待求职者的情况。同样的，这个也会延长面试的总时间。以上两种情况，必然都会延长整个面试过程。所以要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要使考官等候求职者的时间和求职者等候求职者的时间之和最短，这样就使求职者和考官的时间利用率达到了最高。他们就能以最短的时间完成面试一起离开公司。这也是我们想要的结果。（三）模型的假设1

5、.我们假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关；2.面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，但我们在这里假定该时间间隔为 0；3.参加面试的求职者事先没有约定他们面试的先后顺序；4.假定中途任何一位参加面试者均能通过面试，进入下一阶段的面试。即：没有中途退出面试者；5.面试者及各考官都能在 8：00 准时到达面试地点。（四）名词及符号约束1.aij（i=1,2，3，4；j=1,2,3)为求职者 i 在 j 阶段参加面试所需的时间甲乙丙丁分别对应序号 i=1，2,3，42.xij（i=1,2，3，4；j=1,2,3)表示第 i 名同学参加 j 阶段面试的开

6、始时间（不妨把早上 8:00 记为面试的 0 时刻）(2)3.T 为完成全部面试所花费的最少时间（五）模型的建立设s1，s2，s3，s4为 4 位面试者的一个面试顺序,面试者 si 参加第 j 个阶段面试所需时间为 aij 根据问题的 2 个约束条件,可作出 n 位面试者在s1，s2，s3，s4）面试顺序下参加 3 个面试阶段的进展过程表，4 位面试者按序 s1，s2，s3，s4 参加 3 个阶段的面试进展过程表面试者 s1 s2 s3 s4 T1 T2 T3 as1,1 as1,2as1,3 as2,1as2,2as3,1 T4as2,3as3,2as4,1 T5as3,3as4,2 T6a

7、s4,3表中 Ti(i=l，2,，P)表示能同时进行面试的人员所占用的时间段,如 T3，表示面试者 s1 在第 3 个面试场,s2 在第 2 个面试场,s3,在第 1 个面试场、其余人员在等待的那一个时间段.根据顺序性可知整个面试过程的时间段数为 3+4-1=6模式：以各面试者结束全部面试阶段的时间为基础(以表的行为基础)目标函数 minT=maxxi3+ai3约束条件(1)面试阶段约束，即必须先完成上一阶段面试才能进人下一阶段面试。xij+aij xi，j+1 i=l，2，3,4；j=1,2，3）(2)同一阶段只能有一个面试者xij+aij-xki Tyikxkj+akj-xijT(1-yi

8、k)（i，k=l，2,3,4，i=max(pxs(i,j)|j#eq#size(stage):x(i,j)+a(i,j);!完成前一段才能进入下一段;for(pxs(i,j)|j#lt#size(stage):x(i,j)+a(i,j)x(i,j+1);!同一时间只能面试一位同学;for(stage(j):for(pxp(i,k):x(i,j)+a(i,j)-x(k,j)maxa*y(i,k);for(pxp(i,k):x(k,j)+a(k,j)-x(i,j)maxa*(1-y(i,k););for(pxp(i,k):bin(y(i,k);endLingo 结果如下：Local optimal

9、 solution found.Objective value:84.00000 Extended solver steps:43 Total solver iterations:1681 Model Title:面试问题 Variable Value Reduced Cost MAXA 84.00000 0.000000 A(1,1)13.00000 0.000000（4）A(1,2)15.00000 0.000000 A(1,3)20.00000 0.000000 A(2,1)10.00000 0.000000 A(2,2)20.00000 0.000000 A(2,3)18.00000

10、0.000000 A(3,1)20.00000 0.000000 A(3,2)16.00000 0.000000 A(3,3)10.00000 0.000000 A(4,1)8.000000 0.000000 A(4,2)10.00000 0.000000 A(4,3)15.00000 0.000000 X(1,1)8.000000 0.000000 X(1,2)21.00000 0.000000 X(1,3)36.00000 0.000000 X(2,1)26.00000 0.000000 X(2,2)36.00000 0.000000 X(2,3)56.00000 0.000000 X(3

11、,1)38.00000 0.000000 X(3,2)58.00000 0.000000 X(3,3)74.00000 0.000000 X(4,1)0.000000 0.9999970 X(4,2)11.00000 0.000000 X(4,3)21.00000 0.000000 Y(1,2)0.000000 -83.99950 Y(1,3)0.000000 0.000000 Y(1,4)1.000000 83.99950 Y(2,3)0.000000 -83.99950 Y(2,4)1.000000 0.000000 Y(3,4)1.000000 0.000000 Row Slack or

12、 Surplus Dual Price 1 84.00000 -1.000000 2 0.000000 -0.9999970 3 0.000000 0.9999970 4 0.000000 0.9999970 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 3.000000 0.000000 10 0.000000 0.000000 11 5.000000 0.000000 12 17.00000 0.000000(5)13 63.00000 0.000000 14 2.0000

13、00 0.000000 15 48.00000 0.000000 16 26.00000 0.000000 17 56.00000 0.000000 18 34.00000 0.000000 19 0.000000 0.9999970 20 52.00000 0.000000 21 18.00000 0.000000 22 30.00000 0.000000 23 0.000000 0.000000 24 22.00000 0.000000 25 59.00000 0.000000 26 2.000000 0.000000 27 39.00000 0.000000 28 21.00000 0.

14、000000 29 49.00000 0.000000 30 31.00000 0.000000 31 0.000000 0.000000 32 46.00000 0.000000 33 15.00000 0.000000 34 37.00000 0.000000 35 0.000000 0.9999970 36 18.00000 0.000000 37 49.00000 0.000000 38 0.000000 0.9999970 39 31.00000 0.000000 40 21.00000 0.000000 41 46.00000 0.000000 42 36.00000 0.0000

15、00 43 0.000000 0.000000 44 56.00000 0.000000 45 20.00000 0.000000 46 38.00000 0.000000计算结果为：所有面试完成至少需要 84min。面试序号为丁-甲-乙-丙。早上 8:00面试，最早 9:24 面试可以完成.（七）模型的推广该模式是时间最优化的模型，有推广的价值。例如：车间生产的流水线作业，多(6)个部件如何按照先后次序在不同车间进行生产等。(八）主要参考文献 1 文章编号：1672-612x(2007)08-0017-05作者：谭代伦，刘益，张世禄论文名：多阶段有序面试 问题的数学模型与算法研究出版报：绵阳师范学院学报 出版时间：2007 年 8 月 第 26 卷第 8 期2 谢金星,薛毅,优化建模 LingoLindo 软件 M北京:清华大学出版社,20053姜启源,谢金星,叶俊.数学模型(第三版)M.北京:高等教育出版社,20034姜启源,谢金星,叶俊.数学模型(第三版)习题参考解答M.北京:高等教育出版社,2003.(7）