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

浅夏110

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

5 ]+ t' ]! E& ~' V 1 建立模型
   实际上，这个问题就是要安排 4 名同学的面试顺序，使完成全部面试所花费的时 间最少。
- z) Y9 F! A  m9 r8 L9 F
记  为第i名同学参加第 j 阶段面试需要的时间（已知），令   表示第i名同学参加第 j 阶段面试的开始时间（不妨记早上 8:00 面试开始为 0 时刻） （i=1,2,3,4 ; j =1,2,3），T 为完成全部面试所花费的最少时间。

1 Y% [% Y  v$ z% x0 H% |: v: | 优化目标为                            （1）
" B% V3 }$ `3 d# Y+ M
5 c1 g$ E( T$ a+ w. K约束条件：
7 y8 t# ?! W$ V0 h
& N' T# X6 u* j4 x& e0 ]" T  w9 e. f1）时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）：                                （2）
6 @  a: X/ l! Q6 j- |% K. C2 _) B
2 ）每个阶段 j 同一时间只能面试 1 名同学：用  0− 1 变量  表示第k 名同学是否 排在第i名同学前面（1 表示“是”，0 表示“否”），则

' _; b$ S; v* g5 h0 O: {# O    （3）
) L* [7 h; d0 m) a1 n! u
# ^% U1 @. Z8 O- ~" R可以将上述非线性的优化目标（1） 改写为如下线性优化目标：
. o% O: l1 K& I+ Z2 Y/ Y
/ m& j3 n, n( R                   （4）
$ e7 H) j/ s, e( H3 Q
7 x1 O, u. \" L  o, @/ X式（2）～（4）就是这个问题的  0−1  非线性规划模型（当然所有变量还有非负约束，变量   还有  0− 1约束）。

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

model:
- `2 H; g$ y: P- W1 u9 H) ~Title 面试问题;
& N" B$ a' i* r1 Z6 `6 N$ W! OSETS: Person/1..4/;
Stage/1..3/;
PXS(Person,Stage): T, X;
3 P* |5 P- H7 R* n$ bPXP(Person,Person)|&1 #LT# &2: Y;
% e5 v, Y, Z2 U+ R/ O  JENDSETS
DATA:
4 _. L7 @$ X" r3 OT=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15;
ENDDATA
[obj] min=MAXT;
2 ]+ ^# }& ]' R5 ^; u: OMAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));
! 只有参加完前一个阶段的面试后才能进入下一个阶段;
8 X& A1 {: `, M3 R- ]. C@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
& A8 \' g: }' O% |- k& K' o! 同一时间只能面试1名同学;
@for(Stage(j):   
    @for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k));  
3 h' a5 N. U2 w6 a* ?4 l7 d    @for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k))));
@for(PXP: @bin(y));
( f: ~% ]/ _- I9 s# w# tend
计算结果为，所有面试完成至少需要 84min，面试顺序为 4－1－2－3（丁－甲－ 乙－丙）。早上 8:00 面试开始，最早 9:24 面试可以全部结束。
8 T7 S/ p1 H$ T) a. e+ b9 d- M: w4 W————————————————
7 O& o7 ]5 ]$ H% K版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
8 w2 r/ W/ j; j" J, q4 ?原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89387723
4 c& k& c1 v5 c9 K/ \0 F: S1 E7 o" z
1 J1 |0 Q( x, H- M