数学建模社区-数学中国
标题:
面试顺序问题：用数学建模优化生产与服务运作中的管理问题
[打印本页]
作者:
浅夏110
时间:
2020-6-16 14:57
标题:
面试顺序问题：用数学建模优化生产与服务运作中的管理问题
例题： 有 4 名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先 找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即 在任何一个阶段 4 名同学的顺序是一样的）。由于 4 名同学的专业背景不同，所以每人 在三个阶段的面试时间也不同，如表 5 所示。这 4 名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8:00，请问他们最早何时能离开公司？
: A7 c" }" [3 w8 z0 N& z0 n* \
+ D. H0 P# n7 [# T' z7 H: [
$ z8 R! N. N: W. E8 B7 \- B) I" D
* r( J; j) s: _) V) q( A
1 建立模型
/ ~9 l) j* X7 l0 q
实际上，这个问题就是要安排 4 名同学的面试顺序，使完成全部面试所花费的时 间最少。
o" [% s& E! r4 I. F
2 Q: Y& ?: l8 V
记
为第i名同学参加第 j 阶段面试需要的时间（已知），令
表示第i名同学参加第 j 阶段面试的开始时间（不妨记早上 8:00 面试开始为 0 时刻） （i=1,2,3,4 ; j =1,2,3），T 为完成全部面试所花费的最少时间。
6 n2 }% n& X& H5 m
* S( G' {4 F5 C: X7 |. q
优化目标为
（1）
* _& O- V0 o9 I8 K' ~/ {$ R
1 @: B2 A- v. X+ n
约束条件：
& X9 o; r) }! ^
9 T" C. G; w7 A# D9 z) T- v
1）时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）：
（2）
* |1 k" e2 T& E$ {- T' \ j9 {
( `& K& L) I3 {$ c4 o
2 ）每个阶段 j 同一时间只能面试 1 名同学：用 0− 1 变量 表示第k 名同学是否 排在第i名同学前面（1 表示“是”，0 表示“否”），则
2 l3 K; ~- g' K* J9 s* E+ D
2 l* n/ j+ w; o8 {) t" ~# p
（3）
1 k; P2 E2 }) E7 z# A
# I1 Y3 L. B. B% n
可以将上述非线性的优化目标（1） 改写为如下线性优化目标：
6 p8 X: ^. I m7 X( E( y3 r
6 c6 b5 h& [7 \
（4）
: }# A) h4 c* i9 S- M/ _7 K
; i# W9 T# Y+ \9 ?8 e6 w! ~$ @
式（2）～（4）就是这个问题的 0−1 非线性规划模型（当然所有变量还有非负约束，变量
还有 0− 1约束）。
! W, {) m8 S1 q7 y- H4 y/ J# B
q4 s1 g% l8 {5 c: ?
2 求解模型
$ _- s: \4 D K/ X# I
编写 LINGO 程序如下：
7 M, v3 t! _2 J& e' P* K
* X6 y( o' x* R
model:
" L4 O1 _: D# ?. Y) v
Title 面试问题;
' e8 |5 U) V. j4 \( r
SETS: Person/1..4/;
- K* A+ F+ f4 w0 t: P: z! C
Stage/1..3/;
! Y2 j2 Q+ W7 o0 U2 a
PXS(Person,Stage): T, X;
- q+ x/ m& _- v7 |! ^# b0 v- ?1 w
PXP(Person,Person)|&1 #LT# &2: Y;
! f! g; m9 O- j& J% ?7 B
ENDSETS
) \ m0 H. _4 z& O
DATA:
/ w$ h/ w) ?7 B. x
T=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15;
0 g6 o2 } {0 p# I4 V2 _/ k
ENDDATA
3 n& @, \9 n+ D0 H; f/ I w
[obj] min=MAXT;
+ P0 e0 x: y0 a: m& O
MAXT>= @max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));
6 {0 F! s* g3 p& M+ z6 ?6 Q! B
! 只有参加完前一个阶段的面试后才能进入下一个阶段;
& T# w8 \) s* s3 G/ D
@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
n, D N F" z$ n7 M; F! N& p
! 同一时间只能面试1名同学;
% ]' } L9 C, {4 X0 }
@for(Stage(j):
2 t5 k7 g4 i+ L2 P
@for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k));
* _3 Y4 J0 U4 I. j5 t- |
@for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k))));
5 b% r* Q: R% Q' d h
@for(PXP: @bin(y));
0 A, n m$ U- P7 n9 c9 O% j# x
end
2 J1 s: M8 h' b5 K9 r$ o0 T
计算结果为，所有面试完成至少需要 84min，面试顺序为 4－1－2－3（丁－甲－ 乙－丙）。早上 8:00 面试开始，最早 9:24 面试可以全部结束。
- |; Z2 P) ?, m. O0 H d4 X) j
————————————————
8 X. _$ x- B: R. [8 o) `* p: w, ?1 t
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" T, m9 q0 J2 k) z$ m
原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89387723
' Q' A, ]9 B0 i" a9 j
. L7 l, g$ p6 D/ K& [* {0 _" p4 P
: j. }- }, k) p# N% ^& m
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
（2）* |1 k" e2 T& E$ {- T' \ j9 {
（3）