数学建模社区-数学中国

标题: 关于lingo的一个问题 [打印本页]

作者: ljwabc115 时间: 2009-7-17 09:05
标题: 关于lingo的一个问题
本帖最后由 ljwabc115 于 2009-7-17 09:09 编辑

有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：

	秘书初试	主管复试	经理面试
同学甲	13	15	20
同学乙	10	20	18
同学丙	20	16	10
同学丁	8	10	15

这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最早何时能离开公司?（建立规划模型求解）

本问题是一个排列排序问题。对于阶段数不小于3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如20）的情况是无法精确求解的。为此人们找到了很多近似算法。这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数的平方。因此，当学生数稍多一点儿规划模型的规模经很大，求解会花费很长时间。

三阶段面试模型.doc

42 KB, 下载次数: 11, 下载积分: 体力 -2 点

作者: ljwabc115 时间: 2009-7-17 09:05
!三阶段面试模型;
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

作者: ljwabc115 时间: 2009-7-17 09:07
!学生间的面试先后次序保持不变的约束;
  @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));
)
  );
这个约束条件怎么去理解呢?为什么有一个200??

作者: 咕哩咕噜 时间: 2010-3-20 13:38
回复 3# ljwabc115

200其实不必深究，只要这个系数大于等于63（就是Max（13+10+20+8,15+20+16+10,20+18+16+15））就可以满足约束了

作者: xiongluin 时间: 2010-4-28 20:26
如果用外部数据连接怎么做呢？我用txt文本文档做了，没做出来。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)