数学建模社区-数学中国

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

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

5 V: w8 ]* b  _. L) g% y# B 1 建立模型
% F+ F$ H2 U& ]5 h; ~   实际上,这个问题就是要安排 4 名同学的面试顺序,使完成全部面试所花费的时 间最少。
1 X: V: P3 r* ^$ k9 y: H1 [) r) l9 {" @. z
  为第i名同学参加第 j 阶段面试需要的时间(已知),令   表示第i名同学参加第 j 阶段面试的开始时间(不妨记早上 8:00 面试开始为 0 时刻) (i=1,2,3,4 ; j =1,2,3),T 为完成全部面试所花费的最少时间。 ' E# C/ w/ s1 G! H+ T) j

8 E& C- y% M5 A7 s' x1 x 优化目标为                            (1)% p- Q" O9 v7 L6 @4 x

$ M" t2 B9 O0 C% j' g% ]约束条件:
1 D% U! j/ K1 G. L
. `4 H3 g. V" s3 e: T1)时间先后次序约束(每人只有参加完前一个阶段的面试后才能进入下一个阶段):                                (2)
1 S3 Y2 b- Y! d% b! @8 ?$ \/ `/ a' `! |( M* _- d9 t- l
2 )每个阶段 j 同一时间只能面试 1 名同学:用  0− 1 变量  表示第k 名同学是否 排在第i名同学前面(1 表示“是”,0 表示“否”),则 - h7 C/ t' _( F9 F1 I  Q
3 {' \' B* L+ ?% K* H4 T( F
    (3)
1 R* h: T% V( H- N* e$ j0 U4 @4 Q8 s* @
可以将上述非线性的优化目标(1) 改写为如下线性优化目标:% x. m" e$ P: r! q/ X+ c4 e! M- n
0 }& }2 D7 o8 @3 x
                   (4)& c  h- m3 q1 o0 x. o" c$ u+ K

2 J. J0 }. O  F( [式(2)~(4)就是这个问题的  0−1  非线性规划模型(当然所有变量还有非负约束,变量   还有  0− 1约束)。 . N6 C! w$ X+ \! m7 Q3 z( ^1 q4 s

3 ~; q1 H1 h5 P2 E. O: ]  ?2  求解模型
$ @" S; M: a1 k$ T3 d9 d' N编写 LINGO 程序如下:& R' o4 h0 b  O4 N/ K) s$ R" L; c

- F0 A, i0 a0 |2 n0 Rmodel:
$ `3 e& h% }1 A* A% x6 [Title 面试问题; 4 |6 k9 g4 G. Z& {2 ?' W
SETS: Person/1..4/;
  S9 Z. z" ~% K3 SStage/1..3/; + B) O$ x: C+ @* u- J3 R
PXS(Person,Stage): T, X; 0 x. K$ C. x  [* q, b
PXP(Person,Person)|&1 #LT# &2: Y; : a0 E% }! R: \* z. r
ENDSETS - Z: k1 C7 T6 i% V* V8 d& V
DATA:
' A0 a2 [$ B" B9 Y' k$ }T=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15; ! [5 o* }1 s5 ^/ V( z0 }
ENDDATA
; L7 I! a7 X2 H* R( K' J, M[obj] min=MAXT;
* j4 v. e9 D' qMAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j)); $ p8 i# U  e1 c* F
! 只有参加完前一个阶段的面试后才能进入下一个阶段; 4 a, q6 m3 M3 v3 P. z! l% A$ B
@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1)); # ]/ a% t9 _" P  j: C. z
! 同一时间只能面试1名同学; * N9 }; Y, b5 P  \' L$ N  I
@for(Stage(j):   / Q2 A2 A) Q% U$ e
    @for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k));  
3 N+ s  v: x) f( m2 j& ?5 y5 q) p    @for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k)))); 7 i/ C" e% y: ^, _$ f; _0 u2 G. B
@for(PXP: @bin(y)); . _# h, A% _' q  L5 [8 K' g* _
end 6 ^5 I' j  I8 E3 _+ N1 t
计算结果为,所有面试完成至少需要 84min,面试顺序为 4-1-2-3(丁-甲- 乙-丙)。早上 8:00 面试开始,最早 9:24 面试可以全部结束。 # t% Y; ]; `! x. z/ l- d7 R
————————————————5 s' n# L2 D4 M, q- l. i
版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。+ ?* F4 j) {8 j
原文链接:https://blog.csdn.net/qq_29831163/java/article/details/89387723
) K$ F5 h* H& ~- B
* u. F9 S. ]: y; U$ b& d4 _6 N& l# c/ g( H2 @





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