数学建模社区-数学中国

标题: 有瓶颈设备的多级生产计划问题 [打印本页]

作者: 浅夏110    时间: 2020-6-16 10:03
标题: 有瓶颈设备的多级生产计划问题
问题实例 :在制造企业的中期或短期生产计划管理中,常常要考虑如下的生产计划优化问题: 在给定的外部需求和生产能力等限制条件下,按照一定的生产目标(通常是生产总费用 最小)编制未来若干个生产周期的最优生产计划,这种问题在文献上一般称为批量问题 (lotsizing problems)。所谓某一产品的生产批量(lotsize),就是每通过一次生产准备生 产该产品时的生产数量,它同时决定了库存水平。由于实际生产环境的复杂性,如需求 的动态性,生产费用的非线性,生产工艺过程和产品网络结构的复杂性,生产能力的限 制,以及车间层生产排序的复杂性等,批量问题是一个非常复杂、非常困难的问题。 我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段(工艺过程)生产出来的。
, y, i/ k, {  u  O
. A  C5 E6 S2 x/ Y' [+ Q4 n例 1  某工厂的主要任务是通过组装生产产品 A,用于满足外部市场需求。产品 A 的构成与组装过程见图 1,即 D , E,F,G 是从外部采购的零件,先将零件 D,E 组装成部件B ,零件 F,G 组装成部件C ,然后将部件 B,C 组装成产品 A出售。图中弧上的
6 D( F5 V$ b3 z+ d数字表示的是组装时部件(或产品)中包含的零件(或部件)的数量(可以称为消耗系 数),例如DB弧上数字“9”表示组装 1 个部件B 需要用到 9 个零件D;BA弧上的 数字“5”表示组装 1 件产品 A需要用到 5 个部件B ;依此类推。 ! y5 L0 Y1 h# j# X
4 h7 g* j" O" c9 w. Q% h

* G  a. V0 E$ D) d; U8 I2 o8 Z; F( p; n6 Y* d7 ?2 m) O
假设该工厂每次生产计划的计划期为 6 周(即每次制定未来 6 周的生产计划),只 有最终产品 A有外部需求,目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。 部件  B,C 是在该工厂最关键的设备(可以称为瓶颈设备)上组装出来的,瓶颈设备的生产能力非常紧张,具体可供能力如表1第3行所示(第2周设备检修,不能使用)。 B,C的能力消耗系数分别为 5 和 8,即生产 1 件B 需要占用 5 个单位的能力,生产 1 件C 需 要占用 8 个单位的能力。  
8 S1 P, C/ t; `; S
6 v+ ]+ `! i. _& a" \9 X4 x. r( M- f5 [$ E
' v; _/ _; @0 E. k, H
对于每种零部件或产品,如果工厂在某一周订购或者生产该零部件或产品,工厂 需要一个与订购或生产数量无关的固定成本(称为生产准备费用);如果某一周结束时该零部件或产品有库存存在,则工厂必须付出一定的库存费用(与库存数量成正比) 。 这些数据在表 1 第 5 、6 行给出。0 `' a( b- E* p' V# ~* [" h

, s; T4 {" k, m6 L按照工厂的信誉要求,目前接收的所有订单到期必须全部交货,不能有缺货;此外,不妨简单地假设目前该企业没有任何零部件或产品库存,也不希望第 6 周结束后留下任何零部件或产品库存。最后,假设不考虑生产提前期,即假设当周采购的零件马上 就可用于组装,组装出来的部件也可以马上用于当周组装成品 A。 在上述假设和所给数据下,如何制定未来 6 周的生产计划。
+ Y# L8 a3 H3 H7 B7 r8 a
) J( ^, U( w4 a, C, K2  建立模型* S: s7 o+ X% ~5 s
) x, K. |! X1 z7 X9 q+ Q4 T& p
(1)问题分析
0 v" |: n6 {# Z4 U
; G: }0 h( _7 h这个实例考虑的是在有限的计划期内,给定产品结构、生产能力和相关费用及零 部件或成品(以下统称为生产项目)在离散的时间段上(这里是周,也可以是天、月等) 的外部需求之后,确定每一生产项目在每一时间段上的生产量(即批量),使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备(setup),所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实,细心的读者一定会问:是否需要考虑生产的直接成本(如原材料成本、人力成本、电力成本等)?这是因为本例中 假设了不能有缺货发生,且计划初期和末期的库存都是 0,因此在这个 6 周的计划期内 A的总产量一定正好等于 A的总需求,所以可以认为相应的直接生产成本是一个常数, 因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想,对于放松这些假 定条件以后的情形,也是很容易类似地建立优化模型的。
6 T: X9 z7 o4 R$ F+ {- s' A& z6 u3 ^$ c4 }. O: o
(2)符号说明
6 I8 L" A4 o' |6 Q% `8 k5 E) A' x9 _! i3 d. q  g
为了建立这类问题的一般模型,我们定义如下数学符号: " x7 r. [% v) L: [4 G( G

0 P! M% e  Z& {6 p3 B0 RN :生产项目总数(本例中 N =7);; {7 z0 z- r% m: P% o* B9 E
8 I" r7 m9 J: U7 j, A4 k
T :计划期长度(本例中 T =6) ;; y. c6 r7 `1 q; k9 d

1 h  p7 m3 m3 C+ I! c2 |K :瓶颈资源种类数(本例中 K =1 );
# S- h: [- n: \' }4 z* N' b, V& x1 A( U
M :一个充分大的正数,在模型中起到使模型线性化的作用;
1 w5 v$ J7 `2 \6 O, s2 ?; ~
* L0 R! c# {% a2 N :项目i在t时段的外部需求(本例中只有产品 A有外部需求);1 E8 W2 [( a0 d: k/ u8 r

! e  E$ q$ L8 l0 t4 L7 V$ g :项目i在t时段的生产批量; ! F- b# d* D! [+ E& `
$ Z2 k" X% j$ m/ }
:项目i在t时段的库存量;
9 h( l  G& P6 d9 j
3 p2 p5 H) j3 P$ l8 C :项目i在t时段是否生产的标志(0:不生产,1:生产);
) [% D9 V% I! o8 S
0 Z+ T) i9 f& g! u, e :产品结构中项目i的直接后继项目集合; ( e. ]6 @! A4 W. T- b

1 g9 {$ K* Z- ~$ h$ n. q' k/ c :产品结构中项目 j 对项目i的消耗系数;
5 D3 m8 H3 o+ Q& a" ]; V* D3 F% G$ }# s! ]
:项目i在t时段生产时的生产准备费用;
+ g1 S3 U6 J# V( D# X7 T0 [( O. H6 `! X/ Q' y7 F
  :项目i在t时段的单件库存费用; & @: G9 S+ z" U6 v5 \: h6 c

( z8 W  v7 ~. @6 s/ ~ :资源k 在t时段的能力上限; ! ~* L& P: w. }3 J" s, \8 L

8 q* ^1 R$ N6 d9 Q: o7 i1 p :项目i在t时段生产时,生产单个项目占用资源k 的能力; 2 _& T9 E8 o* w7 c) r8 R1 U

9 ~( `  G* A/ L& j* h1 L% B+ E% \1 V: V

6 E. \! w$ D& v( T8 x7 T4 w(3)目标函数* @3 g$ e/ t9 T

& J$ E9 Y* K, y5 O: @这个问题的目标是使生产准备费用和库存费用的总和最小。因此,目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和,即 9 [9 d0 U* }$ s' e

' v$ v, \; A" G' S2 {                                 ( 1 )
+ }" i& I4 W$ X  a1 @% ]7 J/ g0 L) s8 X6 _; x" X1 S, B" l) i
(4)约束条件$ w: P0 H8 W3 v& b7 K/ _+ C9 O( |

, I* V, S7 B( q7 F1 t这个问题中的约束有如下几类:每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束(对  是  0− 1约束)。 所谓物流守恒,是指对每个时段、每个项目(图中一个节点)而言,该项目在上一个时段的库存量加上当前时段的生产量,减去该项目当前时段用于满足外部需求的量 和用于组装其它项目(直接后继项目)的量,应当等于当前时段的库存量。具体可以写成如下表达式(假设 ): $ V3 K/ N1 @2 _$ `

( w% M5 ^2 V& S                       ( 2 )      
$ _$ B- X1 N/ r. p* C, B2 r
9 u5 n- _& _8 V% z* s资源能力限制比较容易理解,即
; Y1 i& W2 }4 @% M, \- ?4 X
: b6 _) r" M% l7 j9 ^: X                      ( 3 )         
( C  a( j. F3 H  x3 r. I& F" `4 K, E7 f& o, b
& ]. }: z; H; Q6 i6 z9 z) c

5 {4 f2 v9 }/ Y# G$ p3  求解模型 ( {  w/ C5 b) a) V
5 S) j' P+ p+ _* I/ J  [9 |! l0 p

2 ?+ T, V1 L1 [% [& o4 H4 x) H6 @! X% h! w, s: j9 ?
/ `6 \- o* B" l0 M8 K, @
) W8 W7 `6 j9 \8 U5 `9 W

) v4 V  Z; O3 y8 j: N% p' X" \9 Y7 `( o! ]% K7 K3 b4 A
MODEL:
3 N" k) W1 t6 w3 Z+ q: STITLE 瓶颈设备的多级生产计划;
( ~3 Y! T+ w& r: l: i9 |, B5 jSETS:
* `: W! K0 c, F8 ^( [! PART=项目集合,Setup=生产准备费,Hold=单件库存成本,   A=对瓶颈资源的消耗系数; 2 K' p0 Q7 _) K: k( a0 z) x
PART/A B C D E F G/:Setup,Hold,A; & m9 x/ N: T1 _: `) I6 G- S3 E
! TIME=计划期集合,Capacity=瓶颈设备的能力;
, k6 V! V, ?( _% S; H! O1 J7 HTIME/1..6/:Capacity; 0 }7 C& H' n/ e& H: u* c- W
! USES=项目结构关系,Req=项目之间的消耗系数;
$ @0 \# C# S7 V, x, fUSES(PART,PART):Req; 5 W7 Y& y9 ~2 v) w% d  Q9 ]  x
! PXT=项目与时间的派生集合,Demand=外部需求,   X=产量(批量), Y=0/1变量,INV=库存; PXT(PART,TIME)emand,X,Y,Inv; ' M# g" l  I  a1 I* W; e& Y+ U9 @
ENDSETS : h# G7 t& C# O1 h& u
! 目标函数; ; p2 G, K6 M7 t" w3 i
[OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t)); " ~+ b4 X4 ]" y, j
! 物流平衡方程; ! b& D6 Z/ u3 R# W5 @- Z- \
@FOR(PXT(i,t)|t #NE#
$ ^( H( o6 A" H3 w5 h5 y1:[Bal]Inv(i,t-1)+X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req( i,j)*X(j,t))); @FOR(PXT(i,t)|t #eq# 8 x+ F9 e5 k- a6 r
1:[Ba0]X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t) ));
2 z% @1 s3 F7 a$ l! 能力约束; ( V" G% l* X! [4 X9 ]
@FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t));  7 s' V" x! {$ ~2 s/ g
! 其他约束; 8 `* a) q1 U+ J; d; M
M = 25000; ' |; [' R% C: G: m9 e
@FOR(PXT(i,t):X(i,t)<=M*Y(i,t)); * n7 f) q  T4 \
@FOR(PXTBIN(Y));
, f9 q8 o# T  m5 {DATA: 9 N/ O3 n5 u$ Z* O/ b
Demand=0;Req =0;  4 N% S( X: A/ _3 E- F2 g
Capacity=10000 0 5000 5000 1000 1000;
% E. T; t3 S; B4 W/ J6 K5 |Setup=400 500 1000 300 200 400 100; : H7 H# P; b( B3 Q. N/ R
Hold=12 0.6 1.0 0.04 0.03 0.04 0.04; 5 Q" J) H5 @0 g9 o/ m
A=0 5 8 0 0 0 0;
) `) h6 x. a/ |* J& Y  N- J2 ?ENDDATA
: O. M8 e- d( Q% H% k/ oCALC:   s) I2 X2 |1 s0 J: G
demand(1,1)=40;demand(1,3)=100; 1 ]1 _+ H$ _$ e" q$ n* A
demand(1,5)=90;demand(1,6)=10;
; X: p& L% A* @3 X9 z% Vreq(2,1)=5;req(3,1)=7;req(4,2)=9;
$ V" G/ E7 ^1 Q& e, i, g8 [9 ^, Breq(5,2)=11;req(6,3)=13;req(7,3)=15;   E: d8 c$ l1 i6 `4 e
ENDCALC
; E3 _+ N8 [% {- ~  ~$ xEND
) B$ O/ Q! W  f8 m8 e" g1 m- q/ [$ ?& w

) Z# k% k8 y% z, R" g习题:
# W$ J8 b1 x( j6 j9 \) C7 j4 Y8 y7 `3 @7 {! C
1.某农户拥有 100 亩土地和 25000 元可供投资,每年冬季(9 月中旬至来年 5 月 中旬),该家庭的成员可以贡献 3500h 的劳动时间,而夏季为 4000h。如果这些劳动时 间有富裕,该家庭中的年轻成员将去附近的农场打工,冬季每小时 6.8 元,夏季每小时 7.0 元。* c+ d1 E3 C: D
/ i+ b* d6 h0 p! Y/ j( \
现金收入来源于三种农作物(大豆、玉米和燕麦)以及两种家禽(奶牛和母鸡)。 农作物不需要付出投资,但每头奶牛需要 400 元的初始投资,每只母鸡需要 3 元的初始 投资。每头奶牛需要使用 1.5 亩土地,并且冬季需要付出 100h 劳动时间,夏季付出 50h 劳动时间,每年产生的净现金收入为 450 元;每只母鸡的对应数字为:不占用土地,冬 季 0.6h,夏季 0.3h,年净现金收入 3.5 元。养鸡厂房最多只能容纳 3000 只母鸡,栅栏 的大小限制了最多能饲养 32 头奶牛。
3 N: k4 p. a$ U9 d) E/ x6 G" U" \9 V0 s  _
根据估计,三种农作物每种植一亩所需要的劳动时间和收入如表 11 所示。建立数 学模型,帮助确定每种农作物应该种植多少亩,以及奶牛和母鸡应该各蓄养多少,使年净现金收入最大。
5 k$ b0 i* B$ q' W: z/ R4 I
6 i- {/ m. y7 }7 s- L5 s2 W
. w* j+ ]/ Z+ D! {4 `
* k1 n( O6 p4 c" L. h6 M- }2.如图 4,有若干工厂的排污口流入某江,各口有污水处理站,处理站对面是居 民点。工厂 1 上游江水流量和污水浓度,国家标准规定的水的污染浓度,以及各个工厂 的污水流量和污水浓度均已知道。设污水处理费用与污水处理前后的浓度差和污水流量 成正比,使每单位流量的污水下降一个浓度单位需要的处理费用(称处理系数)为已知。 处理后的污水与江水混合,流到下一个排污口之前,自然状态下的江水也会使污水浓度降低一个比例系数(称自净系数),该系数可以估计。试确定各污水处理站出口的污水 浓度,使在符合国家标准规定的条件下总的处理费用最小。
/ @' j* O  V/ H/ g' q' P- @, x1 f0 }' C
+ c( ]+ T2 @  e% w$ |( T
( v$ r( r; X5 `4 G% J

9 H' d, ]. x# _7 I& H* _7 v6 b
$ c3 N  H" n/ J% |6 V先建立一般情况下的数学模型,再求解以下的具体问题: ! ]& _2 r) ?. F% e1 V. M/ X
+ K) M% P! A9 l  L# X
(1)为了使江面上所有地段的水污染达到国家标准,最少需要花费多少费用?
7 `2 j+ O# |* L
$ W' d9 M+ x, K' z/ K% A% u& z9 J/ y(2)如果只要求三个居民点上游的水污染达到国家标准,最少需要花费多少费 用? + B8 w% w2 ~) c, k2 D  }
————————————————$ S+ c1 f( k6 ?3 _; E
版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。. b, x! H- G: Z" N( G- K6 i
原文链接:https://blog.csdn.net/qq_29831163/java/article/details/89413903
3 p( T+ T" |* r, x0 t) V- v6 o7 _  c1 v: O0 N

, W. u/ e5 x4 G% z0 `* i* E% s




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