学生面试时间最优规划模型.docx
《学生面试时间最优规划模型.docx》由会员分享，可在线阅读，更多相关《学生面试时间最优规划模型.docx（6页珍藏版）》请在冰点文库上搜索。
学生面试时间最优规划模型
学生面试时间最优规划模型
摘要
本文主要研究面试时间最优问题，并建立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）当A进行完第i段面试后，B还未完成第i-1段的面试，所以第i段的考官必须要等待B完成第i-1段的面试后，才可以对B进行面试。
b）当B完成第i-1段面试后，A还未完成第i段面试，所以B必须等待A完成第i段面试后，才能进入第i段面试。
以上两种情况，延长了面试的时间。
所以要想四个面试学生能尽早离开公司，只要求考官等候学生的时间和面试学生等候面试学生的时间最短，这样学生和考官的时间利用率达到最高，学生就可以尽早离开公司，要想解决时间最短问题，必须满足：
对任意两个学生之间，考官等候面试学生的时间与学生等候学生的时间之和最短。
三、模型假设
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名同学的面试顺序，是完成全部面试所花费的时间最少。
时间构成原始时间矩阵：
A（ij）=a11a12a13
a21a22a23
a31a32a33
a41a42a43
A（ij）=131520
102018
201610
81015
优化目标：
MinT=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;ix（k,j）+t（k,j）-x（i,j）<=200*（1-y（i,k））;i,k=1,2,3,4;i将非线性的优化目标改写成线性的优化目标：
MinTs.tT>=x（i3）+t（i3）,i=1,2,3,4
六、模型求解
根据建立的模型，编写出lingo程序代码（见附录），通过lingo软件运行结果如下：
LINGO程序结果：
Globaloptimalsolutionfound.
Objectivevalue:
84.00000
Extendedsolversteps:
12
Totalsolveriterations:
476
VariableValueReducedCost
Ns4.0000000.000000
Np3.0000000.000000
TMAX84.000000.000000
T（S1,P1）13.000000.000000
T（S1,P2）15.000000.000000
T（S1,P3）20.000000.000000
T（S2,P1）10.000000.000000
T（S2,P2）20.000000.000000
T（S2,P3）18.000000.000000
T（S3,P1）20.000000.000000
T（S3,P2）16.000000.000000
T（S3,P3）10.000000.000000
T（S4,P1）8.0000000.000000
T（S4,P2）10.000000.000000
T（S4,P3）15.000000.000000
X（S1,P1）8.0000000.000000
X（S1,P2）21.000000.000000
X（S1,P3）36.000000.000000
X（S2,P1）26.000000.000000
X（S2,P2）36.000000.000000
X（S2,P3）56.000000.000000
X（S3,P1）36.000000.000000
X（S3,P2）58.000000.000000
X（S3,P3）74.000000.000000
X（S4,P1）0.0000001.000000
X（S4,P2）11.000000.000000
X（S4,P3）21.000000.000000
Y（S1,S2）0.000000-200.0000
Y（S1,S3）0.0000000.000000
Y（S1,S4）1.000000200.0000
Y（S2,S3）0.000000-200.0000
Y（S2,S4）1.0000000.000000
Y（S3,S4）1.0000000.000000
RowSlackorSurplusDualPrice
10.0000000.000000
20.0000000.000000
35.0000000.000000
4172.00000.000000
50.0000001.000000
6165.00000.000000
70.0000000.000000
8162.00000.000000
915.000000.000000
10152.00000.000000
1122.000000.000000
12147.00000.000000
1318.000000.000000
14152.00000.000000
15179.00000.000000
160.0000001.000000
最短时间为84分钟，即4名同学一起离开公司的时间是9：
24.
七、模型推广
本模型的建立思路清晰、简单，是一个非常典型的0-1非线性规划模型。
该模型就有实用性，能使个人和公司的利益达到最大化，因此次模型及其推广对研究并解决这类问题具有重要的意义。
八、参考文献
【1】朱旭、李焕琴，MATLAB软件与基础数学实验；
【2】姜启源、谢金星、叶俊，数学模型（第三版）；
【3】姜启源、谢金星、叶俊，数学模型习题解答（第三版）
【4】肖华勇，实用数学建模与软件应用
九、附录
model:
sets:
students;！
学生集三阶段面试模型；
phases;！
阶段集；
sp（students,phases）:
t,x;
ss（students,students）|&1#LT#&2:
y;
endsets
data:
students=s1..s4;
phases=p1..p3;
t=131520,102018,201610,81015;
enddata
ns=@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=TMAX
@for（students（i）:
x（i,3）+t（i,3）<=TMAX）;
！
把y定义0-1变量；
@for（ss:
@bin（y））;
end
升级会员 