《matlab--算法大全--第27章__生产与服务运作管理中优化问题》由会员分享，可在线阅读，更多相关《matlab--算法大全--第27章__生产与服务运作管理中优化问题（29页珍藏版）》请在金锄头文库上搜索。
1、 -386- 第二十七章第二十七章 生产与服务运作管理中的优化问题生产与服务运作管理中的优化问题 本章主要介绍生产和服务运作管理方面的一些优化问题。 实际上， 生产和服务运作 管理的内容也是非常丰富的， 几乎包含了企业管理的所有方面， 本章中只是介绍几个实 例而已。 1 有瓶颈设备的多级生产计划问题 1.1 问题实例 在制造企业的中期或短期生产计划管理中，常常要考虑如下的生产计划优化问题： 在给定的外部需求和生产能力等限制条件下， 按照一定的生产目标 （通常是生产总费用 最小） 编制未来若干个生产周期的最优生产计划， 这种问题在文献上一般称为批量问题 （lotsizing problems）
2、。所谓某一产品的生产批量（lotsize） ，就是每通过一次生产准备生 产该产品时的生产数量，它同时决定了库存水平。由于实际生产环境的复杂性，如需求 的动态性，生产费用的非线性，生产工艺过程和产品网络结构的复杂性，生产能力的限 制，以及车间层生产排序的复杂性等，批量问题是一个非常复杂、非常困难的问题。 我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。 例 1 某工厂的主要任务是通过组装生产产品A， 用于满足外部市场需求。 产品A 的构成与组装过程见图 1，即GFED,是从外部采购的零件，先将零件ED,组装成
3、 部件B，零件GF,组装成部件C，然后将部件CB,组装成产品A出售。图中弧上的 数字表示的是组装时部件（或产品）中包含的零件（或部件）的数量（可以称为消耗系 数） ，例如DB弧上数字“9”表示组装 1 个部件B需要用到 9 个零件D；BA弧上的 数字“5”表示组装 1 件产品A需要用到 5 个部件B；依此类推。 图 1 产品构成与组装过程图 假设该工厂每次生产计划的计划期为 6 周（即每次制定未来 6 周的生产计划） ，只 有最终产品A有外部需求，目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。 部件CB,是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的 -387
4、- 生产能力非常紧张， 具体可供能力如表1第3行所示 （第2周设备检修， 不能使用） 。CB, 的能力消耗系数分别为 5 和 8， 即生产 1 件B需要占用 5 个单位的能力， 生产 1 件C需 要占用 8 个单位的能力。 表 1 生产计划的原始数据 周次 1 2 3 4 5 6 A的外部需求 40 0 100 0 90 10 瓶颈能力 10000 0 5000 5000 1000 1000 零件编号 A B C D E F G 生产准备费用 400 500 1000 300 200 400 100 单件库存费用 12 0.6 1.0 0.04 0.03 0.04 0.04 对于每种零部件或产
5、品，如果工厂在某一周订购或者生产该零部件或产品，工厂 需要一个与订购或生产数量无关的固定成本（称为生产准备费用） ；如果某一周结束时 该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比） 。 这些数据在表 1 第 5 、6 行给出。 按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货；此 外， 不妨简单地假设目前该企业没有任何零部件或产品库存， 也不希望第 6 周结束后留 下任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上 就可用于组装，组装出来的部件也可以马上用于当周组装成品A。 在上述假设和所给数据下，如何制定未来 6 周的生
6、产计划。 1.2 建立模型 （1）问题分析 这个实例考虑的是在有限的计划期内，给定产品结构、生产能力和相关费用及零 部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等） 的外部需求之后，确定每一生产项目在每一时间段上的生产量（即批量） ，使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备（setup） ，所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实，细心的读者一定会问：是否 需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？这是因为本例中 假设了不能有缺货发生，且计划初期和末期的库存都是 0，因此在这个 6 周的计划期内
7、 A的总产量一定正好等于A的总需求， 所以可以认为相应的直接生产成本是一个常数， 因此就不予考虑了。 只要理解了我们下面建立优化模型的过程和思想， 对于放松这些假 定条件以后的情形，也是很容易类似地建立优化模型的。 （2）符号说明 为了建立这类问题的一般模型，我们定义如下数学符号： N ：生产项目总数（本例中7=N） ； T：计划期长度（本例中6=T） ； K：瓶颈资源种类数（本例中1=K） ； -388- M：一个充分大的正数，在模型中起到使模型线性化的作用； ti d , ：项目i在t时段的外部需求（本例中只有产品A有外部需求） ； ti X , ：项目i在t时段的生产批量； ti I ,
8、 ：项目i在t时段的库存量； ti Y , ：项目i在t时段是否生产的标志（0：不生产，1：生产） ； )(iS：产品结构中项目i的直接后继项目集合； ji r,：产品结构中项目j对项目i的消耗系数； ti s , ：项目i在t时段生产时的生产准备费用； ti h , ：项目i在t时段的单件库存费用； tk C , ：资源k在t时段的能力上限； tik a , ：项目i在t时段生产时，生产单个项目占用资源k的能力； 在上述数学符号中，只有 ti X , ， ti I , ， ti Y , 为决策变量，其余均为已知的计划参数。 其实，真正的生产计划只是要求确定 ti X , 就可以了，因为知道
9、ti X , 以后 ti I , ， ti Y , 也就 自然确定了。另外，在我们的具体例子中参数 ti s , ， ti h , ， tik a , 其实只与项目i有关，而 不随时段t变化，我们这里加上下标t只是为了使模型能够更一般化。 （3）目标函数 这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和，即 = + N i T t titititi IhYs 11 , )( （1） （4）约束条件 这个问题中的约束有如下几类：每个项目的物流应该守恒、资源能力限制应该满 足、每时段生产某项目前必须经过生产准备和非负约束（
10、对 ti Y,是10约束） 。 所谓物流守恒，是指对每个时段、每个项目（图中一个节点）而言，该项目在上 -389- 一个时段的库存量加上当前时段的生产量， 减去该项目当前时段用于满足外部需求的量 和用于组装其它项目（直接后继项目）的量，应当等于当前时段的库存量。具体可以写 成如下表达式（假设0 0, = i I） ： tj iSj ijtitititi XrdIXI , )( ,1, +=+ Ni, 2 , 1L=，Tt, 2 , 1L= （2） 资源能力限制比较容易理解，即 tkti N i tik CXa , 1 , = ，Kk, 2 , 1L=，Tt, 2 , 1L= （3） 每时段生产
11、某项目前必须经过生产准备， 也就是说当0 , = ti X时0 , = ti Y；0 , ti X 时1 , = ti Y。这本来是一个非线性约束，但是通过引入参数M（很大的正数，表示每个 项目每个时段的最大产量）可以化成线性约束，即 titi MYX , 0，1 , 0 , ti Y，Ni, 2 , 1L=，Tt, 2 , 1L= （4） 另外有 0 , ti I，Ni, 2 , 1L=，Tt, 2 , 1L=， （5） 总结上面的讨论，这个问题的优化模型就是在约束（2）（4）下使目标函数（1） 达到最小。 这可以认为是一个混合整数规划模型 （因为产量一般较大， 可以把 ti X , 和 t
12、i I , 看成连续变量（实数）求解，而只有 ti Y , 为10变量） 。 1.3 求解模型 本例中生产项目总数7=N（分别用 17 表示项目GFEDCBA,） ，计划期 长度6=T（周） ，瓶颈资源种类数1=K。只有A有外部需求，所以 ti d , 中只有 t d , 1 可 以取非零需求，即表 1 中的第 2 行的数据，其它 ti d , 全部为零。参数 ti s , ， ti h,只与项目 i有关，而不随时段t变化，所以可以略去下标t，其数值就是表 1 中的最后两行数据。 由于只有一种资源，参数 tk C , 可以略去下标k，其数值就是表 1 中的第 3 行的数据；而 tik a ,
13、只与项目i有关，而不随时段t变化，所以可以同时略去下标k和t，即5 2 =a， -390- 8 3 =a（其它 i a为 0） 。从图 1 中容易得到项目i的直接后继项目集合)(iS和消耗系数 ji r,。 对 本 例 ，A的 外 部 总 需 求 为 240 ， 所 以 任 何 项 目 的 产 量 不 会 超 过 25000157240=（从图 1 可以知道，这里157已经是每件产品A对任意一个项 目的最大的消耗系数了） ，所以取25000=M就已经足够了。 MODEL: TITLE 瓶颈设备的多级生产计划; SETS: ! PART=项目集合,Setup=生产准备费，Hold=单件库存成本，
14、 A=对瓶颈资源的消耗系数; PART/A B C D E F G/:Setup,Hold,A; ! TIME=计划期集合，Capacity=瓶颈设备的能力; TIME/16/:Capacity; ! USES=项目结构关系，Req=项目之间的消耗系数; USES(PART,PART):Req; ! PXT=项目与时间的派生集合，Demand=外部需求, X=产量（批量）, Y=0/1变量，INV=库存; PXT(PART,TIME):Demand,X,Y,Inv; ENDSETS ! 目标函数; OBJMin=sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(
15、i,t); ! 物流平衡方程; FOR(PXT(i,t)|t #NE# 1:BalInv(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:Ba0X(i,t)-Inv(i,t)=Demand(i,t)+SUM(USES(i,j):Req(i,j)*X(j,t) ); ! 能力约束; FOR(TIME(t):CapSUM(PART(i):A(i)*X(i,t)=b(i); for(col:gin(x); remaindery=sum(col:c0*x); end 求得按照模式 2 切割 15 根原料钢管，按模式 5 切割 5 根，按模式 7 切割 5 根，共 25 根，可算出总余料量为 35m。但各长度的钢管数恰好全部满足要求，没有多切割。 与上面得到的结果比较，总余料量增加了 8m，但是所用的原料钢管的总根数减少了 2 根。在余料没有什么用途的情况下，通常选择总根数最少为目标。 2.1.2 问题（2）的求解 （1）问题分析 按照问题（1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于 需要的钢管规格增加到 4 种， 所以
