数学建模社区-数学中国

标题: 面试顺序问题:用数学建模优化生产与服务运作中的管理问题 [打印本页]

作者: 浅夏110    时间: 2020-6-16 14:57
标题: 面试顺序问题:用数学建模优化生产与服务运作中的管理问题
例题: 有 4 名同学到一家公司参加三个阶段的面试:公司要求每个同学都必须首先 找公司秘书初试,然后到部门主管处复试,最后到经理处参加面试,并且不允许插队(即 在任何一个阶段 4 名同学的顺序是一样的)。由于 4 名同学的专业背景不同,所以每人 在三个阶段的面试时间也不同,如表 5 所示。这 4 名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8:00,请问他们最早何时能离开公司?% X( Z7 n2 g4 Q" Q6 h( k  O

- t3 H/ @! `! x8 D- Z! J1 H6 o; |. Q6 U* P* y
/ c9 Y0 R, @& i6 T0 [
1 建立模型
+ D. z: N3 V% o( m  J! f6 [   实际上,这个问题就是要安排 4 名同学的面试顺序,使完成全部面试所花费的时 间最少。 , J, j5 Q% c9 j/ Y5 p7 h, ~/ A. K
( n: v, |; F: p7 @  i* W
  为第i名同学参加第 j 阶段面试需要的时间(已知),令   表示第i名同学参加第 j 阶段面试的开始时间(不妨记早上 8:00 面试开始为 0 时刻) (i=1,2,3,4 ; j =1,2,3),T 为完成全部面试所花费的最少时间。
0 \6 I# G  e/ o( E4 k* u- [" R/ d; C( U  X& m  M
优化目标为                            (1)
+ Q! c. y6 j1 k* |3 i/ O' s% s) i; c6 |) i1 o# H4 \0 b
约束条件:3 T/ Y3 I, g. Q0 t& ^& |6 F! _
4 p* {' Q' R0 R* ~  b
1)时间先后次序约束(每人只有参加完前一个阶段的面试后才能进入下一个阶段):                                (2)* B$ D& E. F. C: J& N3 D5 T

7 V  d# S" r6 d, A2 )每个阶段 j 同一时间只能面试 1 名同学:用  0− 1 变量  表示第k 名同学是否 排在第i名同学前面(1 表示“是”,0 表示“否”),则
4 `: q  E' u& `- {3 q6 C5 F
& d9 _* a* B" Q) ?8 q" Z7 c    (3)! g" U4 B) [; m* b
  r1 s% l2 i9 V" X) N
可以将上述非线性的优化目标(1) 改写为如下线性优化目标:
5 R" l! C4 l, O* N$ U( j7 U6 S8 l2 s/ v2 a) n6 G. M- O
                   (4), X" l! U  z2 j- |! n
2 L5 ?' i. J$ S4 J7 b
式(2)~(4)就是这个问题的  0−1  非线性规划模型(当然所有变量还有非负约束,变量   还有  0− 1约束)。 * u9 O* ^$ k) J0 `# ~0 Q

5 K0 r/ E+ ]6 p' F: Y2  求解模型 ( I, p3 Z; }4 _0 ]
编写 LINGO 程序如下:
+ i8 j+ q# w' M% |+ ~8 P2 ~
3 W9 i7 W; o8 V. g; i* jmodel:
$ O& x- a. b- s, y/ r# {& x$ \; g! i1 uTitle 面试问题; 6 g9 Q  W- T8 C7 {$ N$ e
SETS: Person/1..4/;
1 Q0 P. m( ~8 i% cStage/1..3/; & N& c3 h% K* y  w5 N+ s
PXS(Person,Stage): T, X; $ y3 `. S, `) i. P
PXP(Person,Person)|&1 #LT# &2: Y; 3 O- C* |, N1 }) M3 B
ENDSETS + K% A2 W- ]- Q9 t0 g, O
DATA:
  o/ A) W( I4 ^( J; n" XT=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15; 7 y* C( l' f0 n1 F8 \0 s4 w
ENDDATA
& U) F% g$ }4 n) @5 ~[obj] min=MAXT; ; U  c; k4 a) c* @0 G3 f
MAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j)); % c; i9 |7 {- z7 y% i
! 只有参加完前一个阶段的面试后才能进入下一个阶段;
: [, G% z3 ]' K- y$ _@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1)); ( x9 O5 {# x3 a# P& ^
! 同一时间只能面试1名同学; # E  B0 B9 ]8 r: `- y% E" p
@for(Stage(j):   ! C* K2 K0 T% f- D2 B
    @for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k));  
3 D) W1 y; t7 i    @for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k))));
# ^6 V: |$ H& S* X* |) E# `, ?@for(PXP: @bin(y));
& A1 ]1 t  O  ]& j; Yend & R: O; [7 @% b* i$ Y- j, }, Q0 i
计算结果为,所有面试完成至少需要 84min,面试顺序为 4-1-2-3(丁-甲- 乙-丙)。早上 8:00 面试开始,最早 9:24 面试可以全部结束。 ( A5 e& ?% ]( A( [
————————————————/ \6 y3 X( ?" j/ t: m% N
版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。2 V& E5 _  o9 t7 u, }, z
原文链接:https://blog.csdn.net/qq_29831163/java/article/details/893877239 M5 W% N- ?5 ^

. d* x  b+ K+ _  S) Z  l" x0 C# P* A4 S, J





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5