实验报告书-应聘问题.doc

PAGE  PAGE 4 东南大学《数学实验》报告 学号 姓名 郭晨 成绩 实验内容： 应聘问题 一 实验目的 熟悉lingo软件 尝试将关键路径问题转化为线性规划问题 二 实验题目 初试复试面试甲131520乙102018丙201610丁81015有4名同学到一家公司参加三个阶段的应聘考试：公司要求每个同学都必须首先找秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如右表所示（单位：分钟）。这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最早何时能离开公司? 三 实验内容 模型建立 我们记tij为第i名同学参加第j阶段面试需要的时间（由题已知），令xij表示第i名同学参加第j阶段面试的开始时刻（早上8点为0时刻）。目标函数：最后一阶段的最迟面试结束时间T最小，即： Min T 限制条件： 由于每人只有参加完前一阶段的面试后才能进入下一阶段，所以我们得到约束条件： xij+tij≤xij+1 i=1,2,3,4 j=1,2 又由于每个阶段j同一时间只能面试1名同学，在这里，我们用0-1变量Yik表示第k名同学是否排在第i名同学前面，故有约束： xij+tij-xkj≤TYik i,k=1,2,3 ;ik;j=1,2,3 xkj+tkj-xij≤T1-Yik i,k=1,2,3 ;ik;j=1,2,3 至此，模型建立完毕。 Lingo求解 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= 13 15 20 10 20 18 20 16 10 8 10 15; 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 计算结果 Global optimal solution found at iteration: 898 Objective value: 84.00000 Variable Value Reduced Cost NS 4.000000 0.000000 NP 3.000000 0.000000 TMAX 84.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) 21.00000 0.000000 X( S2, P2) 36.00000 0.000000 X( S2, P3) 56.00000 0.000000 X( S3, P1) 31.00000 0.000000 X( S3, P2) 56.00000 0.000000 X( S3, P3) 74.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