数学建模社区-数学中国

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

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

( v8 A1 K; o, u# ]5 \# [3 o3 X. I8 n& K) S+ P$ v
3 u" R( }5 D. _% v1 y
假设该工厂每次生产计划的计划期为 6 周(即每次制定未来 6 周的生产计划),只 有最终产品 A有外部需求,目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。 部件  B,C 是在该工厂最关键的设备(可以称为瓶颈设备)上组装出来的,瓶颈设备的生产能力非常紧张,具体可供能力如表1第3行所示(第2周设备检修,不能使用)。 B,C的能力消耗系数分别为 5 和 8,即生产 1 件B 需要占用 5 个单位的能力,生产 1 件C 需 要占用 8 个单位的能力。  ( F& T0 \; J6 s. H8 p
! H% D& X+ ]0 b2 W4 R$ Y$ W

/ e% U& a1 j0 K) n. P: i' ?7 z9 @/ ?  P) P. B( i
对于每种零部件或产品,如果工厂在某一周订购或者生产该零部件或产品,工厂 需要一个与订购或生产数量无关的固定成本(称为生产准备费用);如果某一周结束时该零部件或产品有库存存在,则工厂必须付出一定的库存费用(与库存数量成正比) 。 这些数据在表 1 第 5 、6 行给出。
+ a  K( g6 Z9 ~3 u
1 D7 y5 f6 N3 B按照工厂的信誉要求,目前接收的所有订单到期必须全部交货,不能有缺货;此外,不妨简单地假设目前该企业没有任何零部件或产品库存,也不希望第 6 周结束后留下任何零部件或产品库存。最后,假设不考虑生产提前期,即假设当周采购的零件马上 就可用于组装,组装出来的部件也可以马上用于当周组装成品 A。 在上述假设和所给数据下,如何制定未来 6 周的生产计划。
, R7 f  h% [& h3 i/ }# B3 Y: @7 `7 o. {0 A1 t4 e
2  建立模型9 k/ w0 C; s+ j$ \3 b' T# M

- f, l6 E0 A" p# c2 E0 |  A; h* {(1)问题分析  p( p' Z8 ^4 h& \1 t7 r8 Y% s

* J6 _9 ]" l( }5 u这个实例考虑的是在有限的计划期内,给定产品结构、生产能力和相关费用及零 部件或成品(以下统称为生产项目)在离散的时间段上(这里是周,也可以是天、月等) 的外部需求之后,确定每一生产项目在每一时间段上的生产量(即批量),使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备(setup),所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实,细心的读者一定会问:是否需要考虑生产的直接成本(如原材料成本、人力成本、电力成本等)?这是因为本例中 假设了不能有缺货发生,且计划初期和末期的库存都是 0,因此在这个 6 周的计划期内 A的总产量一定正好等于 A的总需求,所以可以认为相应的直接生产成本是一个常数, 因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想,对于放松这些假 定条件以后的情形,也是很容易类似地建立优化模型的。
( i& ?7 q1 V8 V, [8 @% v; P& [1 d" e% Y# v2 X
(2)符号说明
0 \) ?5 G! P& k! w0 h% F+ J
0 K. o0 |/ y* h6 x5 ^1 a为了建立这类问题的一般模型,我们定义如下数学符号: * b; p( D9 q& X0 Z
1 y, X$ F' `) |" J! K+ A
N :生产项目总数(本例中 N =7);( x& _) u( s+ O5 I. J' p5 ^0 ~
0 q8 `- k' G4 p2 P' |; B, d
T :计划期长度(本例中 T =6) ;) m; @/ c: k1 T/ p. ?  y
' T: K# y" I5 g6 ^7 M5 F
K :瓶颈资源种类数(本例中 K =1 ); . \; E4 V' ]/ T  }! n. u

' Z7 j' ~8 J5 I( i; Y# UM :一个充分大的正数,在模型中起到使模型线性化的作用;
5 s8 I0 [/ C- ?  b
8 D: d/ g+ T% s5 c; e+ i :项目i在t时段的外部需求(本例中只有产品 A有外部需求);
1 K/ A% Y0 F! `9 }, c
* H; N3 v/ a; S :项目i在t时段的生产批量;
3 P8 r, T6 X+ |2 q0 O" L% A3 O+ v8 t& T* |7 Z, m2 X
:项目i在t时段的库存量;
/ Y" M" C4 n# Y' N7 b3 N" \2 a) X* {
0 h! z& \- \) _1 d :项目i在t时段是否生产的标志(0:不生产,1:生产);
6 J/ J4 p, j& c5 |
- F, `' |) u6 [, Z :产品结构中项目i的直接后继项目集合;
+ c) b5 B% k2 P' I( p+ a
3 K2 Z  f4 a  F6 _9 n :产品结构中项目 j 对项目i的消耗系数;
' @" V( f  M2 ^6 O# q! q) q
/ D! r" Z7 b) Z1 {# k :项目i在t时段生产时的生产准备费用; $ J/ Q1 W: k2 f  [1 ^5 B. y

" [# I0 p- ^" ^2 G  :项目i在t时段的单件库存费用;
; d: d, L, B# P3 q7 G
# ~7 i. G1 A) _ :资源k 在t时段的能力上限; ' d; J( l7 s9 U4 G- V1 |
. _3 W6 a3 p9 |0 L3 s" ?1 t
:项目i在t时段生产时,生产单个项目占用资源k 的能力; / F8 w5 p" h9 v

0 O. u; ^6 [) v! O. G" c6 K1 ?- `2 Z# |1 O4 V3 H+ t8 Q7 K) k

3 F% p, O7 K6 ](3)目标函数
. g6 g7 R5 j. o& m. B, v
' E1 Y/ I1 i2 I, l& t. ]' x% L0 E这个问题的目标是使生产准备费用和库存费用的总和最小。因此,目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和,即 ' _! Q, t; G) b) b9 S+ Y

+ B" N2 J; X8 A' D$ G. Y                                 ( 1 )
! P/ V! R" p6 E! {
2 \1 e2 o( z5 {& _% y& j(4)约束条件8 T$ ^7 p3 p) z

, w( G' f  H' _4 ]2 d5 e9 f这个问题中的约束有如下几类:每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束(对  是  0− 1约束)。 所谓物流守恒,是指对每个时段、每个项目(图中一个节点)而言,该项目在上一个时段的库存量加上当前时段的生产量,减去该项目当前时段用于满足外部需求的量 和用于组装其它项目(直接后继项目)的量,应当等于当前时段的库存量。具体可以写成如下表达式(假设 ):
' j8 ^9 y( R6 k; z1 U5 ~9 w
5 a+ n" e+ C4 x$ ?3 F                       ( 2 )       " k: R+ h5 q0 ^+ C1 V) S/ ~! t
/ T  X1 q' L/ ~+ B. e6 ~1 z1 Y
资源能力限制比较容易理解,即 , ?7 r4 D- d) w7 i6 \, ?( \

! I& `$ H6 v  x6 F" p; G" }4 e                      ( 3 )         
1 {# f( j4 A; M0 y# q) W! [, J; ]$ \6 ^' a" K7 j. `! C
3 t( @1 W0 F7 e

& p8 T  i/ K1 d" @* _6 U  k+ H3  求解模型
" g. p9 y' ]" \: w5 b  x4 x( q3 n/ ?% D; z; t
9 J- l3 t3 l" `7 q
$ N! _9 Z9 K, Z# r9 c! I$ F
+ X; j/ E5 {' h9 z7 f
; H7 {; N. e5 A- v5 R7 f5 V
; K! S' f: O; ~  q/ X
0 m  E; X/ t( n! t; C, W7 |0 o/ B0 K
MODEL:
1 t- G0 S: f2 a+ V: b3 E: Q! I& QTITLE 瓶颈设备的多级生产计划;
, Z- Y7 L. f2 J; O; U1 P2 `9 s/ CSETS: % z% U/ r/ S0 ~
! PART=项目集合,Setup=生产准备费,Hold=单件库存成本,   A=对瓶颈资源的消耗系数;
, N: r% q5 I0 }- ~8 P; wPART/A B C D E F G/:Setup,Hold,A; # y$ Y& s4 P4 `; G4 a  ]
! TIME=计划期集合,Capacity=瓶颈设备的能力; + C6 d& `4 N% `' b. x
TIME/1..6/:Capacity;
: }& W8 |/ c4 |! USES=项目结构关系,Req=项目之间的消耗系数;
( s: Y2 Z3 X. x# s* k2 WUSES(PART,PART):Req; - r# ~: W% [% ~+ i+ x& ^
! PXT=项目与时间的派生集合,Demand=外部需求,   X=产量(批量), Y=0/1变量,INV=库存; PXT(PART,TIME)emand,X,Y,Inv; , d. ~. `$ c3 |( _( X; e0 W* u$ f
ENDSETS 5 W5 l! k1 Z" t/ T, X
! 目标函数;
) n7 ~- O1 k6 T' @" D3 J3 \[OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t)); ( t, I( w# @7 E3 f6 m/ f: l
! 物流平衡方程; ' e+ X1 Y. X7 T
@FOR(PXT(i,t)|t #NE# 3 t6 [, r- G4 g. R' i' L. R4 f
1:[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# & F' D! |% j0 a- \/ [5 N! k
1:[Ba0]X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t) )); . R$ M& q/ r& U: c6 g& I2 N: ?
! 能力约束;
2 O  w$ Z# I" S7 N@FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t));  # R3 V  S, G' d2 X3 Q& R* b
! 其他约束; ) M& {6 e/ k- P* D4 r4 g
M = 25000; 2 j% T7 l( z" [& u2 J
@FOR(PXT(i,t):X(i,t)<=M*Y(i,t)); 6 z& j2 d+ H' U. J- m
@FOR(PXTBIN(Y)); 1 q7 ^: o( m' ?/ l! W7 u& w0 v
DATA:
) c, J9 G$ M" d/ iDemand=0;Req =0;  
4 h# [  f1 H( B7 x3 ^Capacity=10000 0 5000 5000 1000 1000;
2 o# T+ l6 p$ E4 v2 a5 x/ aSetup=400 500 1000 300 200 400 100;
" H$ @% {+ I: h( V" d; O2 R4 u% G- \Hold=12 0.6 1.0 0.04 0.03 0.04 0.04;
3 w6 M1 J2 s$ O. X6 ]7 v0 LA=0 5 8 0 0 0 0; 2 D4 Z  ]" Z, i
ENDDATA
) b. x) _7 x. t, c. A7 T! ?CALC:
9 w& m0 x% A) W) ]demand(1,1)=40;demand(1,3)=100; . w  c: i+ ]; T$ h" Z
demand(1,5)=90;demand(1,6)=10; : F, w7 V  m: h2 w
req(2,1)=5;req(3,1)=7;req(4,2)=9;
: n5 V# X2 y0 \$ |req(5,2)=11;req(6,3)=13;req(7,3)=15; 1 Z8 E  [: C  Y* F# S
ENDCALC
7 T" T: N4 X9 d$ t3 b4 l; ]7 VEND" J8 H6 F5 j* d- {0 R% K

8 D3 E1 c- H. _- z& y  F% ^! u
) ^# Z% e: r( o习题:
. O. {: H" f/ v; g1 j+ i! ^7 Z
+ u$ `5 y- m* T- E# y$ G1.某农户拥有 100 亩土地和 25000 元可供投资,每年冬季(9 月中旬至来年 5 月 中旬),该家庭的成员可以贡献 3500h 的劳动时间,而夏季为 4000h。如果这些劳动时 间有富裕,该家庭中的年轻成员将去附近的农场打工,冬季每小时 6.8 元,夏季每小时 7.0 元。* a: q( [3 `  J0 n4 b5 ]. e6 r

7 s" _3 k* O) y( R1 W- S现金收入来源于三种农作物(大豆、玉米和燕麦)以及两种家禽(奶牛和母鸡)。 农作物不需要付出投资,但每头奶牛需要 400 元的初始投资,每只母鸡需要 3 元的初始 投资。每头奶牛需要使用 1.5 亩土地,并且冬季需要付出 100h 劳动时间,夏季付出 50h 劳动时间,每年产生的净现金收入为 450 元;每只母鸡的对应数字为:不占用土地,冬 季 0.6h,夏季 0.3h,年净现金收入 3.5 元。养鸡厂房最多只能容纳 3000 只母鸡,栅栏 的大小限制了最多能饲养 32 头奶牛。
# u: F7 V4 \) E  L* t, J1 @# T: j/ J7 x* L7 K# b: K( @
根据估计,三种农作物每种植一亩所需要的劳动时间和收入如表 11 所示。建立数 学模型,帮助确定每种农作物应该种植多少亩,以及奶牛和母鸡应该各蓄养多少,使年净现金收入最大。
1 ]! }" |+ m6 @9 A& G2 c7 B: a. a) a" q
9 v% i% ?1 K$ k/ x8 F4 D1 ?

3 J- Z4 q: Y* Z1 G2.如图 4,有若干工厂的排污口流入某江,各口有污水处理站,处理站对面是居 民点。工厂 1 上游江水流量和污水浓度,国家标准规定的水的污染浓度,以及各个工厂 的污水流量和污水浓度均已知道。设污水处理费用与污水处理前后的浓度差和污水流量 成正比,使每单位流量的污水下降一个浓度单位需要的处理费用(称处理系数)为已知。 处理后的污水与江水混合,流到下一个排污口之前,自然状态下的江水也会使污水浓度降低一个比例系数(称自净系数),该系数可以估计。试确定各污水处理站出口的污水 浓度,使在符合国家标准规定的条件下总的处理费用最小。
9 f9 W* d( i9 n( l& \
! Q4 O3 B4 F# g) W. s6 E1 _
3 U8 _& I" j- t5 h3 e' h/ B
( p$ K( i8 d; c) K& C6 x
7 V3 D: r7 S5 g; s! T* m" w! Q5 R& Z& X* p$ h- H
先建立一般情况下的数学模型,再求解以下的具体问题: 8 ^. r+ B% Z" o/ x; q9 t

# d  `9 }" u3 g5 Q* I(1)为了使江面上所有地段的水污染达到国家标准,最少需要花费多少费用?
+ u" G, w4 ]  T- W- C, ?5 ^: k5 P$ U# w& Z" B/ r
(2)如果只要求三个居民点上游的水污染达到国家标准,最少需要花费多少费 用? ( q' `) t5 l& \
————————————————
4 F2 [4 Z$ p& ^' s版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。1 F9 ^+ R  M' U* p) G  d! P2 I1 X
原文链接:https://blog.csdn.net/qq_29831163/java/article/details/89413903
% K$ W5 o) r1 [4 a0 q# K3 \# |3 ]* ^7 f
) u" U: _8 ]$ X7 w
3 F5 H" d, D6 U% b9 @) ?  N




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