面试顺序问题：用数学建模优化生产与服务运作中的管理问题

浅夏110

例题： 有 4 名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先 找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即 在任何一个阶段 4 名同学的顺序是一样的）。由于 4 名同学的专业背景不同，所以每人 在三个阶段的面试时间也不同，如表 5 所示。这 4 名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8:00，请问他们最早何时能离开公司？

" q2 @3 m/ y+ A% m4 Z
1 ^/ {2 n( I- @7 q5 o$ ]+ Q
6 C) _0 R$ t/ V. ^ 1 建立模型
4 c  v8 e$ G9 h" e/ w   实际上，这个问题就是要安排 4 名同学的面试顺序，使完成全部面试所花费的时 间最少。
0 R& }; ~1 j7 g1 S- y
记  为第i名同学参加第 j 阶段面试需要的时间（已知），令   表示第i名同学参加第 j 阶段面试的开始时间（不妨记早上 8:00 面试开始为 0 时刻） （i=1,2,3,4 ; j =1,2,3），T 为完成全部面试所花费的最少时间。

( ~) E8 e! W8 u# q% B! \ 优化目标为                            （1）
  O# s* Q' |$ V. C2 t1 h# T( F0 U
5 O; P4 b% \( ~6 _0 r1 u0 d约束条件：

1）时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）：                                （2）
/ F8 p; j( U0 n+ i* r4 i1 \1 Q
6 T5 q& z5 _4 r2 ）每个阶段 j 同一时间只能面试 1 名同学：用  0− 1 变量  表示第k 名同学是否 排在第i名同学前面（1 表示“是”，0 表示“否”），则
, p* W, f0 r" Q/ t% b5 H/ d+ h
# e0 x4 M3 v& v' z, z  Z: R    （3）

可以将上述非线性的优化目标（1） 改写为如下线性优化目标：

. S9 Q. u8 T8 b0 e6 }! \! I) q" ^                   （4）

4 \$ [! V! X- [9 W7 {3 o  d式（2）～（4）就是这个问题的  0−1  非线性规划模型（当然所有变量还有非负约束，变量   还有  0− 1约束）。

2  求解模型
编写 LINGO 程序如下：

5 E( `2 H0 M9 K& t8 o- xmodel:
* m# R. Z. d7 o% `9 XTitle 面试问题;
SETS: Person/1..4/;
Stage/1..3/;
7 d" P) ^: [0 LPXS(Person,Stage): T, X;
/ W0 w% t  V8 ]PXP(Person,Person)|&1 #LT# &2: Y;
# z, [( r5 q: o; X$ cENDSETS
DATA:
5 \1 J+ ^( f3 P( l) l- D2 M+ bT=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15;
' E- i1 Y) K8 [' {. ]3 t+ I; HENDDATA
9 X# J9 m7 g" d0 A' \9 c[obj] min=MAXT;
MAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));
. X; M$ b2 m2 n5 x9 o; {! 只有参加完前一个阶段的面试后才能进入下一个阶段;
@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
! 同一时间只能面试1名同学;
: l% H! _# p+ I2 l@for(Stage(j):   
* a' o5 o+ t) Y: D# |# L, h' }' i! e    @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));
5 U( c9 ]! j: @end
计算结果为，所有面试完成至少需要 84min，面试顺序为 4－1－2－3（丁－甲－ 乙－丙）。早上 8:00 面试开始，最早 9:24 面试可以全部结束。
2 m0 U* W' c) e2 p2 m0 O3 e6 _————————————————
" A; l8 h8 O" g& G版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, @# m7 [9 @: ^& Q原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89387723
3 {+ f" a; [  a% ]$ O  z% _
/ u( _8 ^5 r0 h) h5 Y0 t