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

浅夏110

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

+ s, q* o) \- [5 B: s1 f# z+ b 1 建立模型
/ J$ B/ |9 L: F1 @+ E, ?0 A   实际上，这个问题就是要安排 4 名同学的面试顺序，使完成全部面试所花费的时 间最少。
$ P& N1 n/ W" L9 @5 V; ~0 N
记  为第i名同学参加第 j 阶段面试需要的时间（已知），令   表示第i名同学参加第 j 阶段面试的开始时间（不妨记早上 8:00 面试开始为 0 时刻） （i=1,2,3,4 ; j =1,2,3），T 为完成全部面试所花费的最少时间。

9 Q% r; d4 `4 r0 k( G$ Z 优化目标为                            （1）
; }- y' V% p. F& B  _
5 i& r9 ~2 Y  G" |( I约束条件：
# I8 _8 F! j) g% b1 _! B
/ y$ Q5 N$ ^: r9 H1）时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）：                                （2）

2 ）每个阶段 j 同一时间只能面试 1 名同学：用  0− 1 变量  表示第k 名同学是否 排在第i名同学前面（1 表示“是”，0 表示“否”），则

    （3）
- A" E5 M8 f. p5 y
' k' ?6 j+ g8 I, N/ d4 n6 v可以将上述非线性的优化目标（1） 改写为如下线性优化目标：

                   （4）
( N" z7 J7 q  E9 F( x' R
# R) z$ K+ @  X0 ~& i! [式（2）～（4）就是这个问题的  0−1  非线性规划模型（当然所有变量还有非负约束，变量   还有  0− 1约束）。

2  求解模型
% p1 g7 N5 Q  c2 @1 v7 A编写 LINGO 程序如下：

model:
Title 面试问题;
. R+ z. Z5 p- p3 _SETS: Person/1..4/;
Stage/1..3/;
: P- f3 _' E$ b* f* pPXS(Person,Stage): T, X;
' G& e7 x: Y$ v8 E1 l) sPXP(Person,Person)|&1 #LT# &2: Y;
ENDSETS
DATA:
T=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15;
ENDDATA
( w5 a" h/ G; w) F: H/ t- J3 @6 e[obj] min=MAXT;
. T* f; T% V% u: ]1 uMAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));
) ?1 H( l0 E" W# E) z+ [# Y2 `3 N! 只有参加完前一个阶段的面试后才能进入下一个阶段;
0 l2 _/ @$ r; r% G9 ]8 b@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
2 {" V1 ^. L6 z: }" I& f, m: R! 同一时间只能面试1名同学;
@for(Stage(j):   
- I$ f9 T/ b3 X( f" v3 T    @for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k));  
# g( t4 ^3 b- y7 L& v    @for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k))));
@for(PXP: @bin(y));
end
# i" Y& ]* c! B+ U: O6 J计算结果为，所有面试完成至少需要 84min，面试顺序为 4－1－2－3（丁－甲－ 乙－丙）。早上 8:00 面试开始，最早 9:24 面试可以全部结束。
5 w! X. [1 d2 F8 S————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
/ G! K4 h) _: ]5 @原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89387723

& g% S# j8 \3 j0 k! O; ~
' b& d7 G, B4 V  @3 l( P