有瓶颈设备的多级生产计划问题

浅夏110

问题实例 ：在制造企业的中期或短期生产计划管理中，常常要考虑如下的生产计划优化问题： 在给定的外部需求和生产能力等限制条件下，按照一定的生产目标（通常是生产总费用 最小）编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题 （lotsizing problems）。所谓某一产品的生产批量（lotsize），就是每通过一次生产准备生 产该产品时的生产数量，它同时决定了库存水平。由于实际生产环境的复杂性，如需求 的动态性，生产费用的非线性，生产工艺过程和产品网络结构的复杂性，生产能力的限 制，以及车间层生产排序的复杂性等，批量问题是一个非常复杂、非常困难的问题。 我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。
" g" k* h8 Y# ?& D1 Y
例 1  某工厂的主要任务是通过组装生产产品 A，用于满足外部市场需求。产品 A 的构成与组装过程见图 1，即 D , E,F,G 是从外部采购的零件，先将零件 D,E 组装成部件B ，零件 F,G 组装成部件C ，然后将部件 B,C 组装成产品 A出售。图中弧上的
8 I, B) @* T4 M/ q数字表示的是组装时部件（或产品）中包含的零件（或部件）的数量（可以称为消耗系 数），例如DB弧上数字“9”表示组装 1 个部件B 需要用到 9 个零件D；BA弧上的 数字“5”表示组装 1 件产品 A需要用到 5 个部件B ；依此类推。

; K: C- Q/ D3 _) Q

, L5 f, i* I8 ?0 p假设该工厂每次生产计划的计划期为 6 周（即每次制定未来 6 周的生产计划），只 有最终产品 A有外部需求，目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。 部件  B,C 是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的生产能力非常紧张，具体可供能力如表1第3行所示（第2周设备检修，不能使用）。 B,C的能力消耗系数分别为 5 和 8，即生产 1 件B 需要占用 5 个单位的能力，生产 1 件C 需 要占用 8 个单位的能力。  
* l- h+ g" {6 r4 d$ g: x+ Z+ Z


& r6 N; D" ?8 s. c, T" ?/ g' M1 m对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂 需要一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比） 。 这些数据在表 1 第 5 、6 行给出。
; o" M3 y5 p( i& L  {" n
5 N6 G; V% p5 g6 b' |+ [  c, {" a  z按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货；此外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第 6 周结束后留下任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上 就可用于组装，组装出来的部件也可以马上用于当周组装成品 A。 在上述假设和所给数据下，如何制定未来 6 周的生产计划。

2  建立模型
4 u3 O+ }9 a6 A) k( ]5 S
（1）问题分析
/ u" ]$ l  q' W" w' m, F# E
4 F; y; Y+ C3 p) e这个实例考虑的是在有限的计划期内，给定产品结构、生产能力和相关费用及零 部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等） 的外部需求之后，确定每一生产项目在每一时间段上的生产量（即批量），使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备（setup），所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实，细心的读者一定会问：是否需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？这是因为本例中 假设了不能有缺货发生，且计划初期和末期的库存都是 0，因此在这个 6 周的计划期内 A的总产量一定正好等于 A的总需求，所以可以认为相应的直接生产成本是一个常数， 因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想，对于放松这些假 定条件以后的情形，也是很容易类似地建立优化模型的。

9 s( w  z2 Y7 a* M9 ?2 h0 n（2）符号说明
/ ^, d2 E3 P. P* x
+ d0 c" ?  h: N# Q, A为了建立这类问题的一般模型，我们定义如下数学符号：
6 l4 b7 Y7 B: G* v; N- h
N ：生产项目总数（本例中 N =7）；
& p# U% t) ?5 u. q
% E6 y' o. E4 Q7 p2 C6 `, _/ g( |T ：计划期长度（本例中 T =6） ；
. |9 k3 [) P" D  t# Y3 n7 W
K ：瓶颈资源种类数（本例中 K =1 ）；
6 `1 o3 P4 ~: H) }0 I
) _: S! ~4 k5 bM ：一个充分大的正数，在模型中起到使模型线性化的作用；
! M8 K) h: Y. B, l
  g) {. ]0 `' ?% J) \/ O+ J& H ：项目i在t时段的外部需求（本例中只有产品 A有外部需求）；
5 P$ O! u$ ?8 T5 l( [9 q/ z9 S
：项目i在t时段的生产批量；
) U3 B6 K$ D) j( H- {% j8 L
, i; @  @: }$ O0 q$ j ：项目i在t时段的库存量；

" j- k8 H. t4 e( D! i) }% K ：项目i在t时段是否生产的标志（0：不生产，1：生产）；
, K* Y  ^" |# S& ~: X/ }$ ?# Y; l, ]
：产品结构中项目i的直接后继项目集合；
' D% v4 x% g9 {. S8 e2 W. ^
：产品结构中项目 j 对项目i的消耗系数；
  D* }1 q. q3 h, [
! {7 B- w$ c, h  s ：项目i在t时段生产时的生产准备费用；

  ：项目i在t时段的单件库存费用；
$ \- j# K% [2 Y8 R# q( `
：资源k 在t时段的能力上限；

：项目i在t时段生产时，生产单个项目占用资源k 的能力；


8 G  U( A5 k2 \3 R7 }1 |
. {1 [5 ]3 q. q, W' a1 a" k（3）目标函数

6 U. l7 \) M" x) X0 M这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和，即

6 T2 S3 L4 o2 E1 |/ ^) ~$ q( P                                 ( 1 )

2 ]- c1 P0 B& ]0 k（4）约束条件
7 O: f' X& i0 L7 m! ]" {) V
! W) x( e- f1 o+ o这个问题中的约束有如下几类：每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束（对  是  0− 1约束）。 所谓物流守恒，是指对每个时段、每个项目（图中一个节点）而言，该项目在上一个时段的库存量加上当前时段的生产量，减去该项目当前时段用于满足外部需求的量 和用于组装其它项目（直接后继项目）的量，应当等于当前时段的库存量。具体可以写成如下表达式（假设 ）：
- {+ y; W7 ]0 i  a. Q
! x9 l9 J5 o$ z8 U0 d% d+ a                       ( 2 )      
5 a) z* g3 p$ c' r# T; ~4 }) ~
资源能力限制比较容易理解，即

: d! s1 B- ~9 [! R. D- i% t4 w                      ( 3 )         
4 B( ]7 O5 T" c( E. b: p7 e; a/ X


' Q' W- V8 P+ k7 M3  求解模型
% `( q/ ?# c& a0 U  p- Z






MODEL:
" l$ N. ]0 e( ETITLE 瓶颈设备的多级生产计划;
SETS:
! PART=项目集合,Setup=生产准备费，Hold=单件库存成本，   A=对瓶颈资源的消耗系数;
PART/A B C D E F G/:Setup,Hold,A;
! TIME=计划期集合，Capacity=瓶颈设备的能力;
TIME/1..6/:Capacity;
! USES=项目结构关系，Req=项目之间的消耗系数;
USES(PART,PART):Req;
  `1 O7 i8 }' ~2 b4 S! PXT=项目与时间的派生集合，Demand=外部需求,   X=产量（批量）, Y=0/1变量，INV=库存; PXT(PART,TIME)emand,X,Y,Inv;
: g& U' c  {6 HENDSETS
5 o& o9 c# \8 K- V/ Z+ v4 m( O! 目标函数;
  J' E" j* V& ?/ B" l4 s[OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t));
! F# r, p2 }/ ]! X9 ]8 f! 物流平衡方程;
2 ?: n# {" E$ I* S7 E$ O@FOR(PXT(i,t)|t #NE#
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#
1:[Ba0]X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t) ));
2 \% T  @- t! ^% c9 @% g! 能力约束;
( E( S- a$ p7 E, F8 U* L@FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t));  
' N9 m; L( r$ B  F9 b! 其他约束;
. m9 \7 f4 I* L, `5 I; Z7 QM = 25000;
2 l( ?& H' O2 H5 c( y. J! X@FOR(PXT(i,t):X(i,t)<=M*Y(i,t));
@FOR(PXTBIN(Y));
DATA:
0 G/ B$ B& u* L8 u  [% j0 \9 nDemand=0;Req =0;  
1 F& |; @% ?+ h) p* b) bCapacity=10000 0 5000 5000 1000 1000;
& v! e3 ^& k) {: {Setup=400 500 1000 300 200 400 100;
' z4 L9 {9 ]! l, r  a+ yHold=12 0.6 1.0 0.04 0.03 0.04 0.04;
( q+ m/ w4 d# a; y! W2 lA=0 5 8 0 0 0 0;
ENDDATA
+ N: J9 I9 @( v4 ~8 c4 [CALC:
# A4 P( y$ {' D% ?( Ademand(1,1)=40;demand(1,3)=100;
, R2 b' i% m; Q8 I$ c' G1 N/ |demand(1,5)=90;demand(1,6)=10;
" [& ^) t2 i) B8 H# B% W4 R$ k$ t2 Lreq(2,1)=5;req(3,1)=7;req(4,2)=9;
. l& A& E; b! b8 }( F2 Areq(5,2)=11;req(6,3)=13;req(7,3)=15;
2 }8 m7 t6 X4 dENDCALC
END


习题：

1．某农户拥有 100 亩土地和 25000 元可供投资，每年冬季（9 月中旬至来年 5 月 中旬），该家庭的成员可以贡献 3500h 的劳动时间，而夏季为 4000h。如果这些劳动时 间有富裕，该家庭中的年轻成员将去附近的农场打工，冬季每小时 6.8 元，夏季每小时 7.0 元。

1 f! Y: Z5 J! r/ Q% ^7 A现金收入来源于三种农作物（大豆、玉米和燕麦）以及两种家禽（奶牛和母鸡）。 农作物不需要付出投资，但每头奶牛需要 400 元的初始投资，每只母鸡需要 3 元的初始 投资。每头奶牛需要使用 1.5 亩土地，并且冬季需要付出 100h 劳动时间，夏季付出 50h 劳动时间，每年产生的净现金收入为 450 元；每只母鸡的对应数字为：不占用土地，冬 季 0.6h，夏季 0.3h，年净现金收入 3.5 元。养鸡厂房最多只能容纳 3000 只母鸡，栅栏 的大小限制了最多能饲养 32 头奶牛。

% o0 w# ]1 D) q. I' a0 O根据估计，三种农作物每种植一亩所需要的劳动时间和收入如表 11 所示。建立数 学模型，帮助确定每种农作物应该种植多少亩，以及奶牛和母鸡应该各蓄养多少，使年净现金收入最大。


8 j. e, P* T3 {) ^  J3 X; y
$ ]# X8 T. D% _5 U+ L2．如图 4，有若干工厂的排污口流入某江，各口有污水处理站，处理站对面是居 民点。工厂 1 上游江水流量和污水浓度，国家标准规定的水的污染浓度，以及各个工厂 的污水流量和污水浓度均已知道。设污水处理费用与污水处理前后的浓度差和污水流量 成正比，使每单位流量的污水下降一个浓度单位需要的处理费用（称处理系数）为已知。 处理后的污水与江水混合，流到下一个排污口之前，自然状态下的江水也会使污水浓度降低一个比例系数（称自净系数），该系数可以估计。试确定各污水处理站出口的污水 浓度，使在符合国家标准规定的条件下总的处理费用最小。
6 G, |0 [9 r- T$ a$ N4 i4 [

- n: ], f1 h  F1 K, l

3 Y7 Q- ]. G) k$ `7 R  C
先建立一般情况下的数学模型，再求解以下的具体问题：

（1）为了使江面上所有地段的水污染达到国家标准，最少需要花费多少费用？

3 n: p; {1 @7 o5 V  c  i$ r（2）如果只要求三个居民点上游的水污染达到国家标准，最少需要花费多少费 用？
& ]0 S3 \5 y& E" n/ o( r# Z————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 S' U! I: o4 E3 ~1 r原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89413903
9 @2 q6 L1 W  B0 H1 x

# q: s& |2 m" `4 K( B7 ~* b9 T