Question

帮忙编下简单的Lingo程序

有 4 名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，中间休息20分钟，最后到经理处参加面试，并且不允许插队（即在任何一个阶段 4 名同学的顺序是一样的，其中中间休息必须休满20分钟，可以一起休息），由于 4 名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表所示。这 4 名同学约定他们全部面试完以后一起离开公司，请问他们最快需多长时间能离开公司？
秘书初试 主管复试 中间休息 经理面试
同学甲 13 15 20 20
同学乙 10 20 20 18
同学丙 20 16 20 10
同学丁 8 10 20 15
这段程序该怎么改成能解决上面的问题
Title 面试问题;
SETS:
Person/1..4/;
Stage/1..3/;
PXS(Person,Stage): T, X;
PXP(Person,Person)|&1 #LT# &2: Y;
ENDSETS
DATA:
T=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15;
ENDDATA
[obj] min=MAXT;
MAXT>=@max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));
!只有参加完前一个阶段的面试后才能进入下一个阶段;
@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
! 同一时间只能面试1名同学;
@for(Stage(j):@for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k));
@for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k))));
@for(PXP: @bin(y));
end

Answer 1

此问题可以转化为网络优化中的关键路径问题，但不同的是需要确定甲乙丙丁四人的先后顺序，顺序不同，关键路径就不同，所以需要穷搜索四个人一共24种顺序，然后用关键路径算法算出每一种顺序的关键路径，这24条关键路径中时间最短一条就是最快离开公司所用的时间，所对应的顺序就是甲乙丙丁面试的先后顺序。
代码如下：
----------------------------------------------------------------------
Title 面试问题;
!有4名同学到一家公司参加三个阶段的面试,公司要求:每个同学都必须首先找公司秘书初试，然后到部门主管处复试，中间休息20分钟，最后到经理处参加面试，
并且不允许插队（即在任何一个阶段 4 名同学的顺序是一样的，其中中间休息必须休满20分钟，可以一起休息），由于 4 名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表所示。
这 4 名同学约定他们全部面试完以后一起离开公司，请问他们最快需多长时间能离开公司？
秘书初试 主管复试 中间休息 经理面试
同学甲 13 15 20 20
同学乙 10 20 20 18
同学丙 20 16 20 10
同学丁 8 10 20 15 ;
SETS:
s/1..4/:a,b,c;
PX(s,s):w,x,y;
ENDSETS
DATA:
w=13 15 20 20
10 20 20 18
20 16 20 10
8 10 20 15;
ENDDATA
min=b(4)+y(4,4);

@for(s(i):@sum(s(j):x(i,j))=1);
@for(s(j):@sum(S(i):x(i,j))=1);
@for(PX:@bin(x));!矩阵x是矩阵w的行交换矩阵，用来调整甲乙丙丁的先后顺序，比如：要让丙第一个面试，甲最后一个面试，则需交换矩阵w第1和4行，
此时只需让x=0 0 0 1
0 1 0 0
0 0 1 0
1 0 0 0，然后用x乘以w就可以达到交换w的行向量的目的了;
@for(PX(i,j):y(i,j)=@sum(s(k):x(i,k)*w(k,j)));!矩阵y就是矩阵w进行了行交换后的矩阵，y=x*w;

c(1)=y(1,1);
@for(s(i)|i#GT#1 #and# i#LE#3:c(i)=c(i-1)+y(i,1));!记录第i人秘书初试的结束时间;

a(1)=y(1,1);
a(4)=a(3)+y(4,2);
@for(s(i)|i#GT#1 #and# i#LE#3:a(i)=c(i-1)+@smax(y(i+1,1),y(i,2)));!记录第i个人主管面试的开始时间;

b(1)=a(1)+y(1,3)+y(1,2);
@for(s(i)|i#GT#1:b(i)=@smax(a(i)+y(i,3)+y(i,2),b(i-1)+y(i-1,4)));!记录第i个人经理面试的开始时间;
end