QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2597|回复: 0
打印 上一主题 下一主题

[建模教程] 有瓶颈设备的多级生产计划问题

[复制链接]
字体大小: 正常 放大
浅夏110 实名认证       

542

主题

15

听众

1万

积分

  • TA的每日心情
    开心
    2020-11-14 17:15
  • 签到天数: 74 天

    [LV.6]常住居民II

    邮箱绑定达人

    群组2019美赛冲刺课程

    群组站长地区赛培训

    群组2019考研数学 桃子老师

    群组2018教师培训(呼伦贝

    群组2019考研数学 站长系列

    跳转到指定楼层
    1#
    发表于 2020-6-16 10:03 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    问题实例 :在制造企业的中期或短期生产计划管理中,常常要考虑如下的生产计划优化问题: 在给定的外部需求和生产能力等限制条件下,按照一定的生产目标(通常是生产总费用 最小)编制未来若干个生产周期的最优生产计划,这种问题在文献上一般称为批量问题 (lotsizing problems)。所谓某一产品的生产批量(lotsize),就是每通过一次生产准备生 产该产品时的生产数量,它同时决定了库存水平。由于实际生产环境的复杂性,如需求 的动态性,生产费用的非线性,生产工艺过程和产品网络结构的复杂性,生产能力的限 制,以及车间层生产排序的复杂性等,批量问题是一个非常复杂、非常困难的问题。 我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段(工艺过程)生产出来的。 2 o2 Q# q- }) P
    & G1 N' f& i" s& h2 ]& d* y7 a7 E
    例 1  某工厂的主要任务是通过组装生产产品 A,用于满足外部市场需求。产品 A 的构成与组装过程见图 1,即 D , E,F,G 是从外部采购的零件,先将零件 D,E 组装成部件B ,零件 F,G 组装成部件C ,然后将部件 B,C 组装成产品 A出售。图中弧上的
    6 x+ {; w! o7 R  x数字表示的是组装时部件(或产品)中包含的零件(或部件)的数量(可以称为消耗系 数),例如DB弧上数字“9”表示组装 1 个部件B 需要用到 9 个零件D;BA弧上的 数字“5”表示组装 1 件产品 A需要用到 5 个部件B ;依此类推。
    4 ]! e' ]5 _3 K# a
    8 ^/ ~- P7 Y( Q( P$ t" g3 N
    - `! [/ ], ^- `
    0 {/ `3 q' w' f3 x+ R, `4 V假设该工厂每次生产计划的计划期为 6 周(即每次制定未来 6 周的生产计划),只 有最终产品 A有外部需求,目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。 部件  B,C 是在该工厂最关键的设备(可以称为瓶颈设备)上组装出来的,瓶颈设备的生产能力非常紧张,具体可供能力如表1第3行所示(第2周设备检修,不能使用)。 B,C的能力消耗系数分别为 5 和 8,即生产 1 件B 需要占用 5 个单位的能力,生产 1 件C 需 要占用 8 个单位的能力。  
    8 M, O' L$ \3 H" z' n/ c$ Z' M+ {/ R/ B

    ) v) r4 u7 v! t$ @% n; H9 F$ \. a/ a3 n* ^6 Q
    对于每种零部件或产品,如果工厂在某一周订购或者生产该零部件或产品,工厂 需要一个与订购或生产数量无关的固定成本(称为生产准备费用);如果某一周结束时该零部件或产品有库存存在,则工厂必须付出一定的库存费用(与库存数量成正比) 。 这些数据在表 1 第 5 、6 行给出。
    & m5 D* j) A" y! H
    7 _+ T. f# F. e; l5 h4 G按照工厂的信誉要求,目前接收的所有订单到期必须全部交货,不能有缺货;此外,不妨简单地假设目前该企业没有任何零部件或产品库存,也不希望第 6 周结束后留下任何零部件或产品库存。最后,假设不考虑生产提前期,即假设当周采购的零件马上 就可用于组装,组装出来的部件也可以马上用于当周组装成品 A。 在上述假设和所给数据下,如何制定未来 6 周的生产计划。5 Q- ?: x, n" V4 }4 Y, R
      s  ?6 X, M. \$ o( D
    2  建立模型
    & w- Y5 a- g4 i6 p3 }& O" f- ]* k2 I( d% @- N  K6 K" [; [' o
    (1)问题分析
    # @; o5 K/ C8 Z1 m! K' H8 r6 y
    7 n0 s, t" O. h; X这个实例考虑的是在有限的计划期内,给定产品结构、生产能力和相关费用及零 部件或成品(以下统称为生产项目)在离散的时间段上(这里是周,也可以是天、月等) 的外部需求之后,确定每一生产项目在每一时间段上的生产量(即批量),使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备(setup),所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实,细心的读者一定会问:是否需要考虑生产的直接成本(如原材料成本、人力成本、电力成本等)?这是因为本例中 假设了不能有缺货发生,且计划初期和末期的库存都是 0,因此在这个 6 周的计划期内 A的总产量一定正好等于 A的总需求,所以可以认为相应的直接生产成本是一个常数, 因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想,对于放松这些假 定条件以后的情形,也是很容易类似地建立优化模型的。
    ) K; m# X" h# n9 s5 t9 \/ e( M/ j% x  |: ?$ [5 P
    (2)符号说明
    . R. ^6 b5 k$ Z# |& ?: d6 `7 a3 }: K" [/ D' q
    为了建立这类问题的一般模型,我们定义如下数学符号:
    * ~: ]0 i: I/ P
    & T* x. O; q- V0 ]4 A/ F  q0 EN :生产项目总数(本例中 N =7);, ~" F8 f& s- {2 n

    # H+ }) n0 w2 M4 q( ^& QT :计划期长度(本例中 T =6) ;' ]$ H4 H& I! ^3 A2 l

    % K! g; t0 b! F6 T2 K2 xK :瓶颈资源种类数(本例中 K =1 ); ; I- |) A7 ?" l; Z: V3 i& j

    9 @2 s" B8 ?4 r, n2 ^/ P! CM :一个充分大的正数,在模型中起到使模型线性化的作用;
    + J, o, y9 Q3 J( L& o5 T  Q8 D
    1 G" T% ]8 M) Q- K/ l :项目i在t时段的外部需求(本例中只有产品 A有外部需求);6 i0 u- Q4 D9 b5 \# g

    % F! v* }# i* n :项目i在t时段的生产批量; / I& B1 h6 b( P2 Z6 K
    " D0 Q+ s# {% e3 z% f
    :项目i在t时段的库存量;
    9 s! |7 ^( x: o% s1 h! [) m: K8 f8 o0 D
    :项目i在t时段是否生产的标志(0:不生产,1:生产);
    * O& z# V! G( K2 B8 K9 k6 @  W8 g- w0 H
    :产品结构中项目i的直接后继项目集合; " B, Z7 G0 U; j2 A& g

    ; x4 H$ Y# S2 R7 l4 D: j3 L8 e :产品结构中项目 j 对项目i的消耗系数;
    ( W; ]5 L" T( D3 Y
    7 |" _8 X+ H! `- G% B. P  e) S :项目i在t时段生产时的生产准备费用; . R5 G, o+ K/ `

    * L( i, q3 M& ~2 B  :项目i在t时段的单件库存费用;
    & H: T$ c  f( L: ~* ^( a; E9 y7 e# @) T1 ^" O
    :资源k 在t时段的能力上限; % _% C. z( c: W5 Z$ s8 b/ G* s5 p
    # p) h/ D$ v: F+ Q1 ?3 l3 G" ^$ ]" ]' Y, T
    :项目i在t时段生产时,生产单个项目占用资源k 的能力; 1 K; @) Q2 M) s, S

    + I. p6 I% k8 {$ z! e; C9 t$ A3 P' N2 @& U8 V# ?
    , d* d) c# T7 C* f1 q, B4 I
    (3)目标函数7 y. k( A; k! g# @: n
    - ^$ O* k1 J8 Y% V3 T: }. N
    这个问题的目标是使生产准备费用和库存费用的总和最小。因此,目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和,即 8 a( C$ ~; o; j) l! f

    ; i" ~- P9 l* z" K9 f                                 ( 1 )
    ) I) c9 a6 _- p/ }; m! G$ {6 \# T, C
    (4)约束条件& c0 _1 U5 q9 e0 N

    $ o1 U) g* H9 R3 I( k这个问题中的约束有如下几类:每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束(对  是  0− 1约束)。 所谓物流守恒,是指对每个时段、每个项目(图中一个节点)而言,该项目在上一个时段的库存量加上当前时段的生产量,减去该项目当前时段用于满足外部需求的量 和用于组装其它项目(直接后继项目)的量,应当等于当前时段的库存量。具体可以写成如下表达式(假设 ):
    6 t  n8 J$ @  y4 r% C$ W' g
    3 K% L0 l& |- K0 f9 F3 P5 l+ g9 `                       ( 2 )       $ S& @3 J& A- p8 k+ J$ D6 Q6 m  [
    ) l# G1 o# V7 h: m8 z9 U0 y0 ~: e
    资源能力限制比较容易理解,即
    6 q, P% e2 o# e8 K( n5 Z) X6 Z( G( p* q! }6 @+ }
                          ( 3 )         
    5 {6 P: n2 x( x# q' Y* ]8 [& j. p$ W3 j
    ) {& X* S0 G# ^# h! A2 U

    / s- v* r8 n9 W+ y3 j7 ~" c3  求解模型 . h. i1 a( R. x8 J
    $ y: u, ?. e2 L0 q: g$ O

    , Q+ N: @- c2 C6 Z' e
    $ F) z3 D/ x6 w  g5 m1 v: P
    . o! u, o* x$ z, W. W# f2 [; b( i1 J. C8 h" T9 f) e. A
    : `, ^/ d2 O9 Q* g7 c2 o

    ' y  v( J$ e2 g3 M; ]  v3 P; RMODEL: $ {* f/ {: Y, |% p
    TITLE 瓶颈设备的多级生产计划;
    " n# {# t2 U" r  B+ M" `; n" OSETS:
    ! q( \$ @4 {- t5 u3 c" Q' [% C! PART=项目集合,Setup=生产准备费,Hold=单件库存成本,   A=对瓶颈资源的消耗系数;
    3 X% E/ s0 a4 }& r5 K1 D+ vPART/A B C D E F G/:Setup,Hold,A; " d+ a3 G! j  ~8 l' d6 v0 d2 j6 [
    ! TIME=计划期集合,Capacity=瓶颈设备的能力;
    & l- N2 W- R) q! B4 T" tTIME/1..6/:Capacity; / w5 M. Z* @, R
    ! USES=项目结构关系,Req=项目之间的消耗系数; 7 W' t0 ~+ G4 k' Q" J
    USES(PART,PART):Req;
    0 z' L) c6 `9 V! c" c" R! PXT=项目与时间的派生集合,Demand=外部需求,   X=产量(批量), Y=0/1变量,INV=库存; PXT(PART,TIME)emand,X,Y,Inv; * [- h9 f0 a: v& {. Z/ U
    ENDSETS
    4 X; ]! P) g' x! V$ ]! 目标函数; , N6 v" K# c9 z0 @. w* H( Z1 a
    [OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t)); - n4 ~* V4 V2 P# I+ Z, e: \
    ! 物流平衡方程;
    # l5 O# X7 q8 L* s: C) X" D3 v# m; O@FOR(PXT(i,t)|t #NE# + K# a. k8 `& }6 k7 b# j4 Z; c8 T
    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#
    * t. L' _7 l5 F3 t+ `1:[Ba0]X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t) )); 9 m6 ?* d5 D8 v/ F7 S2 ~- S
    ! 能力约束;
    : }9 `* E2 ]+ x2 S: ?@FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t));  
      Q* k2 P2 k+ t! 其他约束;
    7 ]0 F% l0 H+ n' N, |3 {/ h" A% {M = 25000; 8 F2 l- v+ s7 c- }2 l9 j: j5 Y
    @FOR(PXT(i,t):X(i,t)<=M*Y(i,t));
    $ x0 ]; }" m; v& T6 o  ?@FOR(PXTBIN(Y)); : u  s5 n, B. m& U
    DATA:
    8 @7 P6 h) |+ J* O4 a  Y9 iDemand=0;Req =0;  
    0 n! x5 [% o. w( l- p6 A4 X. e7 g) ICapacity=10000 0 5000 5000 1000 1000; 2 w) f5 @, b! s. ^! }& k" j% V
    Setup=400 500 1000 300 200 400 100;
    ( @: v8 H9 ?0 @. A0 y; z4 U; PHold=12 0.6 1.0 0.04 0.03 0.04 0.04; 6 ^: e4 ~) f) d4 j4 E9 P
    A=0 5 8 0 0 0 0;
    1 ]! r6 ]9 `' y$ z5 IENDDATA + r. S- o' z+ w; \! p* m
    CALC:
    - z& m5 `. R$ \5 y; r8 Y8 \. `demand(1,1)=40;demand(1,3)=100; 8 K/ K% [0 S' K% O3 L7 r5 |
    demand(1,5)=90;demand(1,6)=10;
    & }+ T0 h6 `6 c5 i! S6 @: ?* C3 j# dreq(2,1)=5;req(3,1)=7;req(4,2)=9;
    3 v4 g: W$ R& o8 h0 C; C# N5 o! S: vreq(5,2)=11;req(6,3)=13;req(7,3)=15; ) m, ~) q; f$ R5 m4 l9 n
    ENDCALC
    ; u* i8 I& t# O. x6 |& QEND- m7 G! p: l( l, l% m

    : B' ~' h  U; n# H/ M7 p0 h$ T: G4 F9 Q5 I# M
    习题:3 D) V# |: \9 i; a1 h3 V) M- d

    , x! C- k. {) N$ P) y1.某农户拥有 100 亩土地和 25000 元可供投资,每年冬季(9 月中旬至来年 5 月 中旬),该家庭的成员可以贡献 3500h 的劳动时间,而夏季为 4000h。如果这些劳动时 间有富裕,该家庭中的年轻成员将去附近的农场打工,冬季每小时 6.8 元,夏季每小时 7.0 元。
    2 P% l6 F& t/ g% }: z0 }$ s6 B% B* s3 d1 G: m$ ^
    现金收入来源于三种农作物(大豆、玉米和燕麦)以及两种家禽(奶牛和母鸡)。 农作物不需要付出投资,但每头奶牛需要 400 元的初始投资,每只母鸡需要 3 元的初始 投资。每头奶牛需要使用 1.5 亩土地,并且冬季需要付出 100h 劳动时间,夏季付出 50h 劳动时间,每年产生的净现金收入为 450 元;每只母鸡的对应数字为:不占用土地,冬 季 0.6h,夏季 0.3h,年净现金收入 3.5 元。养鸡厂房最多只能容纳 3000 只母鸡,栅栏 的大小限制了最多能饲养 32 头奶牛。
    9 S5 c7 ~+ }' m5 P( a" V- t# K* y! n% C
    根据估计,三种农作物每种植一亩所需要的劳动时间和收入如表 11 所示。建立数 学模型,帮助确定每种农作物应该种植多少亩,以及奶牛和母鸡应该各蓄养多少,使年净现金收入最大。 : q1 l" ]0 M, q( D! v( B

    * M( u. r2 [% N6 x+ [/ K
    4 U0 S9 `* T1 E
    9 [/ l1 p% A- N2.如图 4,有若干工厂的排污口流入某江,各口有污水处理站,处理站对面是居 民点。工厂 1 上游江水流量和污水浓度,国家标准规定的水的污染浓度,以及各个工厂 的污水流量和污水浓度均已知道。设污水处理费用与污水处理前后的浓度差和污水流量 成正比,使每单位流量的污水下降一个浓度单位需要的处理费用(称处理系数)为已知。 处理后的污水与江水混合,流到下一个排污口之前,自然状态下的江水也会使污水浓度降低一个比例系数(称自净系数),该系数可以估计。试确定各污水处理站出口的污水 浓度,使在符合国家标准规定的条件下总的处理费用最小。
    - K0 ^& i3 O/ h
    - Z9 d) z3 l- A6 C: X
    9 ~. x6 y' L% A; V" J- g. O5 d% c' ^. W; b

    * |% b+ V, f: a8 R( k6 ]4 j+ ?7 w: P  A4 i+ u
    先建立一般情况下的数学模型,再求解以下的具体问题: + l7 T. v  P$ f; e+ O
    2 i' |% p* c$ E% t, C/ \8 q
    (1)为了使江面上所有地段的水污染达到国家标准,最少需要花费多少费用?7 P5 U1 l* b' \3 y5 }

    , j7 l3 S& ^( ^# K9 V9 m& v3 s(2)如果只要求三个居民点上游的水污染达到国家标准,最少需要花费多少费 用? 1 C% w) n7 K( ~4 F+ E) I) J% E2 z* |
    ————————————————. F; m, n8 V) o, O
    版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。$ Q" F" j% R5 v0 ]7 N2 _: a$ ^
    原文链接:https://blog.csdn.net/qq_29831163/java/article/details/894139039 `! c" p3 E1 h* I9 v3 R- \! F1 V

    6 R# x5 u, f5 u! i% ^$ x/ D+ \  I( h& R3 q. r- i: Y
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-14 13:47 , Processed in 0.423496 second(s), 51 queries .

    回顶部