QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2556|回复: 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),就是每通过一次生产准备生 产该产品时的生产数量,它同时决定了库存水平。由于实际生产环境的复杂性,如需求 的动态性,生产费用的非线性,生产工艺过程和产品网络结构的复杂性,生产能力的限 制,以及车间层生产排序的复杂性等,批量问题是一个非常复杂、非常困难的问题。 我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段(工艺过程)生产出来的。 7 ~) W( ~- ~( V1 J
    ) v& t4 l0 N1 s8 Q, S
    例 1  某工厂的主要任务是通过组装生产产品 A,用于满足外部市场需求。产品 A 的构成与组装过程见图 1,即 D , E,F,G 是从外部采购的零件,先将零件 D,E 组装成部件B ,零件 F,G 组装成部件C ,然后将部件 B,C 组装成产品 A出售。图中弧上的
    ( z2 ?5 P( M+ M5 w  d数字表示的是组装时部件(或产品)中包含的零件(或部件)的数量(可以称为消耗系 数),例如DB弧上数字“9”表示组装 1 个部件B 需要用到 9 个零件D;BA弧上的 数字“5”表示组装 1 件产品 A需要用到 5 个部件B ;依此类推。 ' x' p" G5 t: j+ e  b! n, B
      e0 D( J( L# X( B
    ' F3 I) Q' _8 ^# \. w
    4 A& I. [8 Y6 i$ f/ z+ p- O
    假设该工厂每次生产计划的计划期为 6 周(即每次制定未来 6 周的生产计划),只 有最终产品 A有外部需求,目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。 部件  B,C 是在该工厂最关键的设备(可以称为瓶颈设备)上组装出来的,瓶颈设备的生产能力非常紧张,具体可供能力如表1第3行所示(第2周设备检修,不能使用)。 B,C的能力消耗系数分别为 5 和 8,即生产 1 件B 需要占用 5 个单位的能力,生产 1 件C 需 要占用 8 个单位的能力。  - N& \9 C  ^7 p) h9 L

    # D  ~- q1 i4 h7 z- g4 a% h0 Z5 g, m; E( c

    % k# i8 i: |: L5 r& b/ T. B9 [对于每种零部件或产品,如果工厂在某一周订购或者生产该零部件或产品,工厂 需要一个与订购或生产数量无关的固定成本(称为生产准备费用);如果某一周结束时该零部件或产品有库存存在,则工厂必须付出一定的库存费用(与库存数量成正比) 。 这些数据在表 1 第 5 、6 行给出。6 M8 u1 b9 d! ~, R* z: @  p
    & ]3 v6 y& s0 B  Z& J
    按照工厂的信誉要求,目前接收的所有订单到期必须全部交货,不能有缺货;此外,不妨简单地假设目前该企业没有任何零部件或产品库存,也不希望第 6 周结束后留下任何零部件或产品库存。最后,假设不考虑生产提前期,即假设当周采购的零件马上 就可用于组装,组装出来的部件也可以马上用于当周组装成品 A。 在上述假设和所给数据下,如何制定未来 6 周的生产计划。
    9 g; t1 a$ g8 P! @6 \! n
    * f  q+ p6 M& G7 Y& g0 S2  建立模型2 T! d' [9 O. W0 D
    6 k1 H. y+ C6 E0 s+ f- P- F
    (1)问题分析
    ; J, U& ]( ~" |$ V! K
    $ s; z- b) t, l- [) h2 l! `这个实例考虑的是在有限的计划期内,给定产品结构、生产能力和相关费用及零 部件或成品(以下统称为生产项目)在离散的时间段上(这里是周,也可以是天、月等) 的外部需求之后,确定每一生产项目在每一时间段上的生产量(即批量),使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备(setup),所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实,细心的读者一定会问:是否需要考虑生产的直接成本(如原材料成本、人力成本、电力成本等)?这是因为本例中 假设了不能有缺货发生,且计划初期和末期的库存都是 0,因此在这个 6 周的计划期内 A的总产量一定正好等于 A的总需求,所以可以认为相应的直接生产成本是一个常数, 因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想,对于放松这些假 定条件以后的情形,也是很容易类似地建立优化模型的。
    8 F; W6 u" _& E/ f2 ?4 b$ n# D2 c
    ' x/ Z" T# P" {- [$ @" {9 Y3 f0 A/ N2 u(2)符号说明
    . `# @! c0 }. o; W7 }0 P; V7 M+ W) ~; u3 f6 V3 M, w
    为了建立这类问题的一般模型,我们定义如下数学符号: + q3 X! n( H. O

    4 q2 v: ^" w; A0 V. J& v8 h/ t9 zN :生产项目总数(本例中 N =7);+ B) p+ C4 ]! P) P/ i  v! y6 l
    9 N! o$ t: P" p) n
    T :计划期长度(本例中 T =6) ;* X2 y2 q/ C7 F8 E
    ! s' L9 ]' {  Q  X4 V- W
    K :瓶颈资源种类数(本例中 K =1 );
    . L, n' a8 X/ W1 _6 [- O5 k, X- r" i
    6 L, ?  s) R* a8 aM :一个充分大的正数,在模型中起到使模型线性化的作用;
    2 q2 t5 q. A3 p9 N  c% L8 H4 s% I, S: Q$ r
    :项目i在t时段的外部需求(本例中只有产品 A有外部需求);
    5 h* d$ g& M; ~: E
    & Z. h9 e2 {& [5 k1 [8 H+ S :项目i在t时段的生产批量; 3 o, Z( ~  ?) ?. y" H

    ! D0 q7 k& M0 g# g& Q' Z& o" S8 [8 A$ w :项目i在t时段的库存量;
    / m* _3 @# S7 o: P" L( }  C( Q& e, k1 P+ _' a
    :项目i在t时段是否生产的标志(0:不生产,1:生产);
    9 C' ~3 h1 @& D# g/ m
    ; I% I) r$ F( o9 q6 b- r+ M& ] :产品结构中项目i的直接后继项目集合; % C9 E! H% [0 v9 F6 B4 A3 K9 h

    0 H. m  m0 Z3 r. u :产品结构中项目 j 对项目i的消耗系数; . {, \) w! ?0 e: X, _
    * l2 l& O3 b8 ]4 `, [+ M
    :项目i在t时段生产时的生产准备费用;
    # y( g1 y( ^! s7 _8 \
    2 l: D# p1 y1 R( h- h" _1 \0 W  :项目i在t时段的单件库存费用; " H$ x. N/ |. h
    0 ?8 |# g( M' |$ G8 n1 T: ?
    :资源k 在t时段的能力上限;
    + [% |) ^( c& C( M& P* V0 Q; x# Y5 c6 p$ s% P. D$ L( x
    :项目i在t时段生产时,生产单个项目占用资源k 的能力;
    2 S* K2 o( P+ H2 E: o/ a! u3 m0 z
    0 m5 a+ u0 z  D
    7 M) b  ?2 H# [9 }! `
    (3)目标函数8 f# H( ~3 u2 \- n0 `% t# B( B

    0 b' _$ @5 Q& C. `0 y* N2 Y; F这个问题的目标是使生产准备费用和库存费用的总和最小。因此,目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和,即
    : R1 H( w6 H, Y4 Q. V$ A8 B1 |' U
    & S: ~4 W# U1 k& r( Z6 A. w' N                                 ( 1 )& K4 U- y( J. l$ ~. L3 D

    2 u3 W( v: P3 O(4)约束条件
    # l3 Z% A  E  V
    ) w2 N5 q7 B0 d1 G6 k; t8 Z这个问题中的约束有如下几类:每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束(对  是  0− 1约束)。 所谓物流守恒,是指对每个时段、每个项目(图中一个节点)而言,该项目在上一个时段的库存量加上当前时段的生产量,减去该项目当前时段用于满足外部需求的量 和用于组装其它项目(直接后继项目)的量,应当等于当前时段的库存量。具体可以写成如下表达式(假设 ): 5 |5 N* k, N) x) X2 u/ V, h! }

    5 I. S! P* b6 N- R                       ( 2 )      
    1 T+ l8 g( _& |2 Z- s
    " k( U- v3 |- [: o+ G4 f4 ~/ c资源能力限制比较容易理解,即 ; f% @6 _3 x/ L$ `
    4 s4 `& @% h. g, D6 r, X
                          ( 3 )          : {9 k% J9 V+ \

    . Y. |0 [/ [" Y2 r' u: ?: _+ F0 F) O( L& k: R; L8 K  r# V
    / o, R' a$ q1 U5 q% p
    3  求解模型
    8 O* W& E& i; u
    * A! t' ?+ {" v  Y8 I8 d4 D- a4 x, V: d3 P$ j5 X* G6 p# Q# l

    ( m, L; u* q& A( _
    2 Z! A: x% D0 z/ P+ T: x- [& X; b$ ^5 H

    $ l1 P1 C7 V" N$ V6 V; j
    $ w; N: R4 t+ _4 [+ S' ~) U. L) iMODEL: / B" P0 M/ D. D* C, ?. M% j
    TITLE 瓶颈设备的多级生产计划;
    8 b# }  H! N' t6 w# VSETS:
    / Q; k1 l9 i% Y2 ?* D! PART=项目集合,Setup=生产准备费,Hold=单件库存成本,   A=对瓶颈资源的消耗系数;
    , }* B# e! ?1 K9 C& e  e3 ePART/A B C D E F G/:Setup,Hold,A;
    ; A+ X7 D5 L! }( G( I! TIME=计划期集合,Capacity=瓶颈设备的能力; 0 n5 }1 r5 Y; e& ~/ R
    TIME/1..6/:Capacity; , z& P$ I# U, e$ m
    ! USES=项目结构关系,Req=项目之间的消耗系数;
    ) m9 p! B: @. }( K, PUSES(PART,PART):Req;
    7 F4 P1 s! F; P" y! PXT=项目与时间的派生集合,Demand=外部需求,   X=产量(批量), Y=0/1变量,INV=库存; PXT(PART,TIME)emand,X,Y,Inv;
    , n% c. R0 T- D5 ZENDSETS * G% ]4 }, W0 c! n  O/ c2 F
    ! 目标函数; 7 o( X+ F6 ^0 e4 B
    [OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t));
    + s; b5 d, k- s- y4 L! 物流平衡方程; 7 Z5 n6 B6 r* |5 {0 o
    @FOR(PXT(i,t)|t #NE#
    - {" ?0 J# ?1 }- u# }9 [  f$ [/ w  G1:[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#
    5 r0 Z- Z- F8 J2 K" [1:[Ba0]X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t) )); 0 X- ?0 P1 g# m6 I+ E5 \5 k  P
    ! 能力约束;
    3 O8 g# o8 ]  [: F. ~! @7 D@FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t));  ! v' K! Y) }+ x; T! @% I) u
    ! 其他约束;
    " P/ r  C0 p8 L0 L& I, XM = 25000;
    6 s2 l4 ~! {4 s% P& |( S9 D@FOR(PXT(i,t):X(i,t)<=M*Y(i,t)); ! }! [9 N$ U. n/ j' I2 ~
    @FOR(PXTBIN(Y)); : h: k! y2 n0 @+ G) |
    DATA: 1 }! F/ Q: y( @4 G
    Demand=0;Req =0;  ( R/ y& @6 p/ \: F0 ^6 O5 m
    Capacity=10000 0 5000 5000 1000 1000; 0 d7 t/ e. @8 q% y! W( W2 Y- t7 {0 V( c
    Setup=400 500 1000 300 200 400 100;
    1 e& z- c/ C7 T+ PHold=12 0.6 1.0 0.04 0.03 0.04 0.04;
    7 w% ?* Z& Z" ?* i) u6 R0 e' N% pA=0 5 8 0 0 0 0;
    1 M+ [* ~$ V( V6 X1 m8 }0 cENDDATA
    8 x! e1 K! T( V, u( GCALC: ) E+ ^8 [& E) A8 G
    demand(1,1)=40;demand(1,3)=100;
    ) O  s5 c+ H! c$ I' f- q( sdemand(1,5)=90;demand(1,6)=10;
    * o0 _- |1 L! c: Z: ]! }7 preq(2,1)=5;req(3,1)=7;req(4,2)=9; 8 s' k% ?' [3 [4 L
    req(5,2)=11;req(6,3)=13;req(7,3)=15; + w- u% Y+ G' D. @- K5 t: |4 b  o9 s
    ENDCALC
    ' `( K) X) f2 A. l, D' EEND2 A3 I; D8 Y0 D7 e/ s6 J; a

    1 r+ Z9 W" G! X. R* O' J3 d: S- Z: i; r( _, S  h0 i
    习题:
    2 U& s/ _& j& s5 e/ X' K* p! O* q* u  ]) d7 E* v+ c
    1.某农户拥有 100 亩土地和 25000 元可供投资,每年冬季(9 月中旬至来年 5 月 中旬),该家庭的成员可以贡献 3500h 的劳动时间,而夏季为 4000h。如果这些劳动时 间有富裕,该家庭中的年轻成员将去附近的农场打工,冬季每小时 6.8 元,夏季每小时 7.0 元。9 Z7 S$ Z, M& B

    2 j1 x& \# S" W0 F& t( t$ e9 i2 F现金收入来源于三种农作物(大豆、玉米和燕麦)以及两种家禽(奶牛和母鸡)。 农作物不需要付出投资,但每头奶牛需要 400 元的初始投资,每只母鸡需要 3 元的初始 投资。每头奶牛需要使用 1.5 亩土地,并且冬季需要付出 100h 劳动时间,夏季付出 50h 劳动时间,每年产生的净现金收入为 450 元;每只母鸡的对应数字为:不占用土地,冬 季 0.6h,夏季 0.3h,年净现金收入 3.5 元。养鸡厂房最多只能容纳 3000 只母鸡,栅栏 的大小限制了最多能饲养 32 头奶牛。
    ( n- }7 c& l( l# G+ z. V  M# o3 x+ A) f; o; N
    根据估计,三种农作物每种植一亩所需要的劳动时间和收入如表 11 所示。建立数 学模型,帮助确定每种农作物应该种植多少亩,以及奶牛和母鸡应该各蓄养多少,使年净现金收入最大。 ! v  T: A$ ?7 B9 Y( }

    2 B# D4 l" _8 p' o/ R1 |7 n8 B, `$ {! b

    & D! T' c; `" Q1 \: H2.如图 4,有若干工厂的排污口流入某江,各口有污水处理站,处理站对面是居 民点。工厂 1 上游江水流量和污水浓度,国家标准规定的水的污染浓度,以及各个工厂 的污水流量和污水浓度均已知道。设污水处理费用与污水处理前后的浓度差和污水流量 成正比,使每单位流量的污水下降一个浓度单位需要的处理费用(称处理系数)为已知。 处理后的污水与江水混合,流到下一个排污口之前,自然状态下的江水也会使污水浓度降低一个比例系数(称自净系数),该系数可以估计。试确定各污水处理站出口的污水 浓度,使在符合国家标准规定的条件下总的处理费用最小。 * G: g( w1 S0 N# D
    9 s6 F* B: \+ N

    7 C; U% Y' N4 w; @* ?4 z. \. [% Q3 J" j0 r4 C+ x# H
    8 R6 j( w$ [6 o
    ' Y8 Y/ E0 ?2 k( F% s$ v& {
    先建立一般情况下的数学模型,再求解以下的具体问题: % X7 Y7 q3 j8 Y$ _

    ; `) J, {" n2 p8 K(1)为了使江面上所有地段的水污染达到国家标准,最少需要花费多少费用?
    % e  J" t, n" f& d; b) P4 ?' }
    $ Y. c  p" d% a. g(2)如果只要求三个居民点上游的水污染达到国家标准,最少需要花费多少费 用?
    9 i( S/ p. R5 o3 W+ U* x3 n0 v  t————————————————
    + v! o3 L+ G+ H. ?# g版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。; {8 ~( m  ?% ~
    原文链接:https://blog.csdn.net/qq_29831163/java/article/details/89413903% o% v- r6 a% `- t6 Y3 v: z% v
    3 \' u" `  Y" m7 m- z3 ~" m

    6 U# X% s% s" [1 K3 V( @# @
    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-4-14 23:29 , Processed in 0.324278 second(s), 51 queries .

    回顶部