数学建模求解

Question

有四名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段四名同学的顺序是一样的）由于四名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示：
同学甲：（秘书初试：13分钟，主管复式：15分钟，经理面试：20分钟）
同学已：（秘书初试：10分钟，主管复式：20分钟，经理面试：18分钟）
同学丙：（秘书初试：20分钟，主管复式：16分钟，经理面试：10分钟）
同学丁：（秘书初试：8分钟，主管复式：10分钟，经理面试：15分钟）
这四名同学约定他们全部面试完以后一起离开公司，假定现在时间是早晨8点，问他们最早何时离开公司。

Answer 1

本问题是一个排列排序问题。对于阶段数不小于3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如20）的情况是无法精确求解的。为此人们找到了很多近似算法。这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数的平方。因此，当学生数稍多一点儿规划模型的规模经很大，求解会花费很长时间。
!三阶段面试模型;
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.000000
Y( S3, S4) 1.000000 0.000000

Answer 2