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

浅夏110

例题： 有 4 名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先 找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即 在任何一个阶段 4 名同学的顺序是一样的）。由于 4 名同学的专业背景不同，所以每人 在三个阶段的面试时间也不同，如表 5 所示。这 4 名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8:00，请问他们最早何时能离开公司？
7 V( O3 P1 C  E  s
9 j2 b. L6 o( }8 ?8 p6 M
$ p9 \9 }/ _7 t. s
1 建立模型
9 N1 d5 F4 R, ]2 ]5 y" a  r   实际上，这个问题就是要安排 4 名同学的面试顺序，使完成全部面试所花费的时 间最少。

7 k% ?7 u: L0 p% Z记  为第i名同学参加第 j 阶段面试需要的时间（已知），令   表示第i名同学参加第 j 阶段面试的开始时间（不妨记早上 8:00 面试开始为 0 时刻） （i=1,2,3,4 ; j =1,2,3），T 为完成全部面试所花费的最少时间。

9 a6 r5 |6 R& ^4 b& R) I 优化目标为                            （1）

约束条件：

- L0 r  v) g7 J3 d. n1）时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）：                                （2）

  N) d- _' j- a! O( y9 u2 ）每个阶段 j 同一时间只能面试 1 名同学：用  0− 1 变量  表示第k 名同学是否 排在第i名同学前面（1 表示“是”，0 表示“否”），则

    （3）
3 D: \) F" N) V3 R
0 D: e- z& u  J# T  b可以将上述非线性的优化目标（1） 改写为如下线性优化目标：
6 Z/ L! K6 F- f9 i1 t9 f7 \; ^9 q
5 T0 @( ?- X% z( T) `4 D                   （4）

式（2）～（4）就是这个问题的  0−1  非线性规划模型（当然所有变量还有非负约束，变量   还有  0− 1约束）。
3 ^8 D  U+ o6 {6 n' Q
2  求解模型
* K! p3 s. V3 w. R" P% Q编写 LINGO 程序如下：
1 [. ?% y6 h) R+ ?* ]
$ N' }% `) J' ^model:
7 s  y# z0 I$ a( RTitle 面试问题;
  n: t- @7 h. D) N3 m: K7 l# C1 M9 nSETS: Person/1..4/;
8 J6 |& r& K9 x" R6 v8 H1 O5 I# IStage/1..3/;
/ E- [% R- K: lPXS(Person,Stage): T, X;
PXP(Person,Person)|&1 #LT# &2: Y;
+ f! N( x/ m& X0 y# sENDSETS
+ X7 L/ Z3 A6 Y( x8 i# S, U6 lDATA:
T=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15;
ENDDATA
[obj] min=MAXT;
MAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));
! 只有参加完前一个阶段的面试后才能进入下一个阶段;
, t9 d: N6 r- u3 V# P@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
8 g# n+ r" E2 Y& F! 同一时间只能面试1名同学;
% |9 F0 [$ }! i4 d@for(Stage(j):   
' v4 y& t" Z; y) `8 T    @for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k));  
- |" o# H, o4 C, \/ ^    @for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k))));
@for(PXP: @bin(y));
# ]( M9 Y5 ?" _' ^end
: v/ @& w, H6 f% J3 o计算结果为，所有面试完成至少需要 84min，面试顺序为 4－1－2－3（丁－甲－ 乙－丙）。早上 8:00 面试开始，最早 9:24 面试可以全部结束。
————————————————
6 v) t+ x4 D  q1 E. U# |3 w版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89387723
/ _0 c; C. R% \8 I1 Z0 u

  W- q6 \4 J* Z1 \# Z