面试时间最优模型.doc

课 程 设 计 论 文

学 院:
理 学 院 
专 业:
 数学与应用数学
课程名称
数学建模课程设计
题目
面试时间最短模型

学生姓名
蔚斌斌
学 号
0907014125
指导教师
杨明 肖亚峰

2012年6月

面试时间最短模型
摘要
按照公司的要求，四名求职者的顺序一旦确定，在以下各阶段中面试的顺序将不再改变，由于每个求职者，三个阶段面试的时间不同（且固定）。
由题意易知，求4名同学最早离开公司的时间，即求4名同学在公司面试完毕所需的最短时间。由于每人在三个阶段的面试时间不同且每个同学都不允许插队，故可知道面试总时间的长短是由面试顺序决定的。而4名同学的面试顺序有4！=24种情况，也就是说本题可以用穷举法一一列出然后取使面试总时间最小的顺序，不难发现这样做的工作是冗杂的，且若面试人数很大时，这个方法就显得不科学。
考虑到本题求其所用时间的最小值也就是关于面试时间的最优解问题，所以本文采用规划模型，并利用LINGO软件辅助求解。

关键字
面试问题 线性规划 LINGO

一 问题重述
有4名同学到一家公司参加三个阶段的面试。面试要求为：每个同学应依次找秘书、主管、经理进行初试、复试、面试；每个同学都不允许插队。每人在三个阶段的面试时间都不同，具体如下表所示（单位：分钟）：

秘书初试
主管复试
经理面试
同学甲
12
15
18
同学乙
10
18
15
同学丙
20
16
14
同学丁
8
10
15

根据题意，本文应解决的问题有：
1、这4名同学约定他们全部面试完以后一起离开公司。假定现在的时间是早晨8：00，求他们最早离开公司的时间；
2、试着给出此类问题的一般描述，并试着分析问题的一般解法。

二 问题分析
由题意易知，求4名同学最早离开公司的时间，即求4名同学在公司面试完毕所需的最短时间。由于每人在三个阶段的面试时间不同且每个同学都不允许插队，故可知道面试总时间的长短是由面试顺序决定的。而4名同学的面试顺序有4！=24种情况，也就是说本题可以用穷举法一一列出然后取使面试总时间最小的顺序，不难发现这样做的工作是冗杂的，且若面试人数很大时，这个方法就显得不科学。
考虑到本题求其所用时间的最小值也就是关于面试时间的最优解问题，所以本文采用规划模型，并利用LINGO软件辅助求解。

三 符号说明
表示第n个同学第m阶段的面试时间；
表示第n个同学第m阶段开始面试的时刻；
表示若第j个同学排在第n个同学之前，记为，否则为；
表示4名参加面试的同学同时离开公司的时间；
分别表示取最小值和最大值；
附： ，，

四 模型假设
1、 假设面试者均能在8:00准时到达面试地点，且记此时为0时刻；
2、 每个面试者由一个阶段到下一个阶段，肯定有时间间隔（如若两阶段的面试地点有一段距离，那走到下一面试地点就要用一定的时间，或面试者和面试官中途上洗手间等），这里假设这个时间间隔为0；
3、 假设面试途中没有被淘汰的面试者，即面试中途没有人退出。

五 模型建立与求解
模型建立 由题意可知，求4名同学在公司面试完毕所需的最短时间，考虑到面试总时间的长短是由面试顺序决定的，即要找一个面试顺序 使得在取最后一阶段4名同学面试完毕的4个时刻的最大值这一情况时 所用的面试总时数最短。故由 （分钟）～第n个同学第m阶段的面试时间（如下表）：

13
15
20

10
20
18

20
16
10

8
10
15
及 （第n个同学第m阶段开始面试的时刻）可建立
目标函数为： （1） 的规划模型。
其中约束条件有：
（1）、首先易知有： （即第n个同学第m阶段面试完毕所用的时间小于等于总时间） （2）
（2）、由每个同学的各阶段面试顺序是确定的可得：
（3）
（3）、由（第j个同学排在第n个同学之前，记为，否则为）及同一时刻只能面试一个面试者可得：
（ 时即可理解为第n个同学在m阶段面试完毕的时刻减去第j个同学在m阶段开始面试的时刻得到的第j、n个同学在m阶段面试的时间总和要小于等于总时间） （4）
（ 时即可理解为第j个同学在m阶段面试完毕的时刻减去第n个同学在m阶段开始面试的时刻可知即为同一时刻结果为0） （5）

模型求解 由目标函数（1）式和约束条件（2）（3）（4），利用LINGO软件求解可得：
Global optimal solution found at iteration: 680
Objective value: 84.00000

Variable Value Reduced Cost
NS 4.000000 0.000000
NP 3.000000 0.000000
TMAX 83.00000 0.000000
C( S1, P1) 13.00000 0.000000
C( S1, P2) 15.00000 0.000000
C( S1, P3) 20.00000 0.000000
C( S2, P1) 10.00000 0.000000
C( S2, P2) 20.00000 0.000000
C( S2, P3) 18.00000 0.000000
C( S3, P1) 20.00000 0.000000
C( S3, P2) 16.00000 0.000000
C( S3, P3) 10.00000 0.000000
C( S4, P1) 8.000000 0.000000
C( S4, P2) 10.00000 0.000000
C( S4, P3) 15.00000 0.000000
X( S1, P1) 8.000000 0.000000
X( S1, P2) 20.00000 0.000000
X( S1, P3) 36.00000 0.000000
X( S2, P1) 20.00000 0.000000
X( S2, P2) 35.00000 0.000000
X( S2, P3) 54.00000 0.000000
X( S3, P1) 30.00000 0.000000
X( S3, P2) 53.00000 0.000000
X( S3, P3) 69.00000 0.000000
X( S4, P1) 0.000000 1.000000
X( S4, P2) 8.000000 0.000000
X( S4, P3) 18.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

由结果可知：面试所用总时间为84分钟，即他们同时离开公司的时刻为 上午9:24，他们的面试顺序为 丁 →甲 →乙→ 丙
结果检验 按照 丁 →甲 →乙→ 丙这一面试顺序，利用题中表里的数据，计算得面试所用时间刚好为84分钟。
六 参考文献
[1] 姜启源，谢金星，叶俊，数学模型（第三版），北京：高等教育出版社，2003
[2] 朱德通,《最优化模型与实验》,同济大学出版社,2003
[3] 院新生，《LINGO和Excel在数学建模中的应用》，科学出版社，2008
七 附录　
源代码：
model:
sets:
students; !学生集三阶段面试模型;
phases; !阶段集;
sp(students,phases):c,x;
ss(students,students) | &1 #LT# &2:y;
endsets
data:
students = s1..s4;
phases = p1..p3;
c=
13 15 20
10 20 18
20 16 0
8 10 15;
enddata
ns=@size(students); !学生数;
np=@size(phases); !阶段数;
!单个学生面试时间先后次序的约束;
@for(sp(N,M) | M #LT# np:
x(N,M)+c(N,M)<=x(N,M+1) ); !学生间的面试先后次序保持不变的约束;
@for(ss(N,J):
@for(phases(M):
x(N,M)+c(N,M)-x(J,M)<=200*y(N,J);
x(J,M)+c(J,M)-x(N,M)<=200*(1-y(N,J));
) );
min=TMAX; !目标函数;
@for(students(N):
x(N,3)+c(N,3)<=TMAX
); !把Y定义0-1变量;
@for(ss: @bin(y));
End