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

浅夏110

例题： 有 4 名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先 找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即 在任何一个阶段 4 名同学的顺序是一样的）。由于 4 名同学的专业背景不同，所以每人 在三个阶段的面试时间也不同，如表 5 所示。这 4 名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8:00，请问他们最早何时能离开公司？
% M1 v2 h( m$ r8 X
" {% T4 d# `4 g; Y* n2 K
! V& u; L$ f3 `2 v$ F
5 x, b9 E( W. _3 |! y 1 建立模型
   实际上，这个问题就是要安排 4 名同学的面试顺序，使完成全部面试所花费的时 间最少。

* C$ U3 Q/ X6 t4 ]; U记  为第i名同学参加第 j 阶段面试需要的时间（已知），令   表示第i名同学参加第 j 阶段面试的开始时间（不妨记早上 8:00 面试开始为 0 时刻） （i=1,2,3,4 ; j =1,2,3），T 为完成全部面试所花费的最少时间。

3 u, E" {( V% }% o. {! W8 w 优化目标为                            （1）

* |$ R9 v8 C4 l, G% P  `约束条件：

: t" w, z$ C! g" T2 |" \5 c1）时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）：                                （2）
" `" c+ }5 R  v) I6 t* X3 I
9 W" c# F1 ], s, r) W" i2 ）每个阶段 j 同一时间只能面试 1 名同学：用  0− 1 变量  表示第k 名同学是否 排在第i名同学前面（1 表示“是”，0 表示“否”），则

( H7 T4 ^- [3 ]" y, T9 g6 W" L! N4 p    （3）

可以将上述非线性的优化目标（1） 改写为如下线性优化目标：
  U6 A1 m# e& _7 ?7 M% ?
" }; {7 }! A9 E7 }  s                   （4）

7 v* h# C  J! d' t% Z式（2）～（4）就是这个问题的  0−1  非线性规划模型（当然所有变量还有非负约束，变量   还有  0− 1约束）。

7 l; U5 W4 y9 R) @2  求解模型
( b) ~- L1 a& c( e" N' _编写 LINGO 程序如下：
5 Y1 N; z/ U; Q2 S4 j' i5 y" r
/ I  v4 ^! c- e4 x9 `$ Pmodel:
Title 面试问题;
SETS: Person/1..4/;
Stage/1..3/;
PXS(Person,Stage): T, X;
0 t! ]# l$ |, T" T1 yPXP(Person,Person)|&1 #LT# &2: Y;
ENDSETS
DATA:
. Z# I, X2 ~  m3 a: V5 Y. ST=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15;
$ E# U& W; e7 Y3 S! RENDDATA
7 u0 V5 l9 V* h# Y+ }: }1 Y[obj] min=MAXT;
. k4 b3 Y9 r! }+ k/ O3 p8 qMAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));
! 只有参加完前一个阶段的面试后才能进入下一个阶段;
@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
: u. E3 P" Y7 Z) |! 同一时间只能面试1名同学;
@for(Stage(j):   
' M; |9 `2 K) j! U8 d( L    @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));
0 ~/ ]$ G0 b/ Y$ j- a! m. c( jend
计算结果为，所有面试完成至少需要 84min，面试顺序为 4－1－2－3（丁－甲－ 乙－丙）。早上 8:00 面试开始，最早 9:24 面试可以全部结束。
————————————————
& i: z5 J& g) y. Z3 Q版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 B' ]5 e$ K7 U& B1 m; U! {原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89387723
1 y8 |/ k0 F" v6 `
) S8 {# L  I$ J! h