面试等候最短时间建模

1、实验六1.问题重述有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先到公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序都是一样的）。由于4名同学的专业背景不同，所以没人在三个阶段的面试时间不同，如表6所示（单位：min）:表6秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015这4名同学约定他们全部面试完后一起离开公司。假定现在时间是早上8:00，问他们最早何时能离开公司？2.基本假设：1. 每个面试的同学都必须按照先到公司秘书处初试，然后到主管处复试，最后到经理处面试的顺序进行；

2、2. 在面试的任何一个阶段都不存在插队现象，即在任何一个阶段4名同学的顺序都是一样的；3. 每个阶段一次只能面试一个同学；4. 面试的每个过程都顺利进行，相邻两个过程之间没有间隔时间。3.符号说明第名同学参加第阶段面试所需要的时间第名同学参加第阶段面试开始时刻（记早上8:00面试开始为0时刻）所有同学参加完面试所需时间0-1变量，表示第名同学是否排在第名同学前面4.模型建立与求解4.1模型建立目标函数： 其中，约束条件：1）每人只有参加完前一个阶段的面试才能进入下一阶段的面试： 2）每个阶段同一时间只能面试1名同学，用0-1变量表示第名同学是否排在第名同学前面：其中，因此，基本模型可以表示为：

3、 4.2模型求解：将原模型进行修改后，用lingo求解，可得求解结果如下：Global optimal solution found. Objective value: 84.00000 Objective bound: 84.00000 Infeasibilities: 0.1532108E-13 Extended solver steps: 8 Total solver iterations: 598 Variable Value Reduced Cost NS 4.000000 0.000000 NP 3.000000 0.000000 TMAX 84.00000 0.000000 S(

4、 1) 0.000000 0.000000 S( 2) 0.000000 0.000000 S( 3) 0.000000 0.000000 S( 4) 0.000000 0.000000 P( 1) 0.000000 0.000000 P( 2) 0.000000 0.000000 P( 3) 0.000000 0.000000 T( 1, 1) 13.00000 0.000000 T( 1, 2) 15.00000 0.000000 T( 1, 3) 20.00000 0.000000 T( 2, 1) 10.00000 0.000000 T( 2, 2) 20.00000 0.000000

5、 T( 2, 3) 18.00000 0.000000 T( 3, 1) 20.00000 0.000000 T( 3, 2) 16.00000 0.000000 T( 3, 3) 10.00000 0.000000 T( 4, 1) 8.000000 0.000000 T( 4, 2) 10.00000 0.000000 T( 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(

6、 2, 2) 36.00000 0.000000 X( 2, 3) 56.00000 0.000000 X( 3, 1) 36.00000 0.000000 X( 3, 2) 56.00000 0.000000 X( 3, 3) 74.00000 0.000000 X( 4, 1) 0.000000 1.000000 X( 4, 2) 8.000000 0.000000 X( 4, 3) 21.00000 0.000000 Y( 1, 2) 0.000000 -200.0000 Y( 1, 3) 0.000000 0.000000 Y( 1, 4) 1.000000 200.0000 Y( 2

7、, 3) 0.000000 -200.0000 Y( 2, 4) 1.000000 0.000000 Y( 3, 4) 1.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 0.000000 0.000000 3 5.000000 0.000000 4 172.0000 0.000000 5 0.000000 1.000000 6 165.0000 0.000000 7 0.000000 0.000000 8 162.0000 0.000000 9 15.00000 0.000000 10 152.000

8、0 0.000000 11 20.00000 0.000000 12 149.0000 0.000000 13 18.00000 0.000000 14 152.0000 0.000000 15 179.0000 0.000000 16 0.000000 1.000000 17 172.0000 0.000000 18 3.000000 0.000000 19 165.0000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 170.0000 0.000000 23 0.000000 0.000000 24 164.0000 0.00

9、0000 25 0.000000 1.000000 26 172.0000 0.000000 27 164.0000 0.000000 28 18.00000 0.000000 29 152.0000 0.000000 30 18.00000 0.000000 31 147.0000 0.000000 32 20.00000 0.000000 33 144.0000 0.000000 34 28.00000 0.000000 35 136.0000 0.000000 36 38.00000 0.000000 37 137.0000 0.000000 38 38.00000 0.000000 3

10、9 84.00000 -1.000000 40 28.00000 0.000000 41 10.00000 0.000000 42 0.000000 1.000000 43 48.00000 0.000000 44 0.000000 1.000000 45 0.000000 0.000000 46 0.000000 0.000000 47 0.000000 1.000000 48 0.000000 0.000000 49 2.000000 0.000000 50 0.000000 0.000000 51 3.000000 0.0000004.3结果分析：由上述结果可知，当面试顺序为丁-甲-乙-丙时，四人的面试时间可以达到最短，最短时间为84分钟。附录：源代码：model:sets:students/1.4/:s;phases/1.3/:p;sp(students,phases):t,x;ss(students,students)|&1 #LT# &2:y;endsetsdata:t=13152010201820161081015;enddatans=size(students);np=size(phases);for(sp(i,j)|j #LT# np:x(i,j)+t(i