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

浅夏110

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

" O% H' ~7 r5 _3 a! h$ ^
% ?5 ~1 F0 c0 b+ H+ }
. D- m' R0 y% Q& G8 k0 ~* y8 r* S 1 建立模型
, j* }3 e  L' r   实际上，这个问题就是要安排 4 名同学的面试顺序，使完成全部面试所花费的时 间最少。
5 a- q! c7 V- b0 o& W6 {. T3 E1 x
8 j# ]1 x+ R4 d记  为第i名同学参加第 j 阶段面试需要的时间（已知），令   表示第i名同学参加第 j 阶段面试的开始时间（不妨记早上 8:00 面试开始为 0 时刻） （i=1,2,3,4 ; j =1,2,3），T 为完成全部面试所花费的最少时间。
6 l: Y# R/ E3 [/ U- C+ X  B
优化目标为                            （1）

5 j2 d) @, T& L8 I/ P7 l+ k约束条件：
) h4 X& D* F1 M! O
1）时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）：                                （2）
0 L3 V5 L2 W: w/ y( E( _$ g
- \9 C% w! b" g# B9 P2 ）每个阶段 j 同一时间只能面试 1 名同学：用  0− 1 变量  表示第k 名同学是否 排在第i名同学前面（1 表示“是”，0 表示“否”），则
! T5 h. d" r% L9 ^5 z# j
    （3）

# e: p( O; x4 q" j可以将上述非线性的优化目标（1） 改写为如下线性优化目标：
$ r% ?3 D- B1 S, k* O! e, F, \
# U3 N. X7 f8 @  Z                   （4）

9 ~, c: u& R6 t& |. A+ l式（2）～（4）就是这个问题的  0−1  非线性规划模型（当然所有变量还有非负约束，变量   还有  0− 1约束）。
$ I& {# w& _$ Z! i: b$ [5 v
3 p5 j2 T4 b7 ]1 j7 i2  求解模型
, m; t+ r4 {9 v编写 LINGO 程序如下：

% w  Z, G/ u' \. m! \9 xmodel:
Title 面试问题;
SETS: Person/1..4/;
Stage/1..3/;
PXS(Person,Stage): T, X;
PXP(Person,Person)|&1 #LT# &2: Y;
& U6 @4 }" y1 `9 yENDSETS
, D0 ]6 D. f1 T; D4 d- K& P, _+ bDATA:
T=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15;
ENDDATA
- \& N- S6 R5 r  i% j6 ^! H, T. P[obj] min=MAXT;
' U8 V$ a( s! b5 l) WMAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));
) g* F4 n/ a4 _" {+ {6 ^+ w/ Y! 只有参加完前一个阶段的面试后才能进入下一个阶段;
@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));  
; @& {' Q7 J8 v) U7 D5 }0 v    @for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k))));
@for(PXP: @bin(y));
( T- v. w: h( g/ s" G- p$ _& bend
5 S) ]# r2 X7 q1 @; K6 G计算结果为，所有面试完成至少需要 84min，面试顺序为 4－1－2－3（丁－甲－ 乙－丙）。早上 8:00 面试开始，最早 9:24 面试可以全部结束。
  I* {# @9 r  k————————————————
( F7 _4 r0 S" y. J  x版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 C2 k, D3 W& J7 P原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89387723
" y3 F3 r! x% {. S8 J" L' R! H

# j& l, @1 D9 M) h- M- F