《数学建模》算法全收录（算法大全）：第27章 生产与服务运作管理中的优化问题

第二十七章生产与服务运作管理中的优化问题 本章主要介绍生产和服务运作管理方面的一些优化问题。实际上,生产和服务运作 管理的内容也是非常丰富的,几乎包含了企业管理的所有方面,本章中只是介绍几个实 例而已 §1有瓶颈设备的多级生产计划问题 1.1问题实例 在制造企业的中期或短期生产计划管理中,常常要考虑如下的生产计划优化问题 在给定的外部需求和生产能力等限制条件下,按照一定的生产目标(通常是生产总费用 最小)编制未来若干个生产周期的最优生产计划,这种问题在文献上一般称为批量问题 ( lotsizing problems)。所谓某一产品的生产批量( lotsize),就是每通过一次生产准备生 产该产品时的生产数量,它同时决定了库存水平。由于实际生产环境的复杂性,如需求 的动态性,生产费用的非线性,生产工艺过程和产品网络结构的复杂性,生产能力的限 制,以及车间层生产排序的复杂性等,批量问题是一个非常复杂、非常困难的问题。 我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段(工艺过程)生产出来的。 例1某工厂的主要任务是通过组装生产产品A,用于满足外部市场需求。产品A 的构成与组装过程见图1,即D,E,F,G是从外部采购的零件,先将零件D,E组装成 部件B,零件F,G组装成部件C,然后将部件B,C组装成产品A出售。图中弧上的 数字表示的是组装时部件(或产品)中包含的零件(或部件)的数量(可以称为消耗系 数),例如DB弧上数字“9”表示组装1个部件B需要用到9个零件D;BA弧上的 数字“5”表示组装1件产品A需要用到5个部件B;依此类推 颈设备加工 图1产品构成与组装过程图 假设该工厂每次生产计划的计划期为6周(即每次制定未来6周的生产计划),只 有最终产品A有外部需求,目前收到的订单的需求件数按周的分布如表1第2行所示 部件B,C是在该工厂最关键的设备(可以称为瓶颈设备)上组装出来的,瓶颈设备的

-386- 第二十七章 生产与服务运作管理中的优化问题 本章主要介绍生产和服务运作管理方面的一些优化问题。实际上，生产和服务运作 管理的内容也是非常丰富的，几乎包含了企业管理的所有方面，本章中只是介绍几个实 例而已。 §1 有瓶颈设备的多级生产计划问题 1.1 问题实例 在制造企业的中期或短期生产计划管理中，常常要考虑如下的生产计划优化问题： 在给定的外部需求和生产能力等限制条件下，按照一定的生产目标（通常是生产总费用 最小）编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题 （lotsizing problems）。所谓某一产品的生产批量（lotsize），就是每通过一次生产准备生 产该产品时的生产数量，它同时决定了库存水平。由于实际生产环境的复杂性，如需求 的动态性，生产费用的非线性，生产工艺过程和产品网络结构的复杂性，生产能力的限 制，以及车间层生产排序的复杂性等，批量问题是一个非常复杂、非常困难的问题。 我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。 例 1 某工厂的主要任务是通过组装生产产品 A ，用于满足外部市场需求。产品 A 的构成与组装过程见图 1，即 D, E, F,G 是从外部采购的零件，先将零件 D, E 组装成 部件 B ，零件 F,G 组装成部件C ，然后将部件 B,C 组装成产品 A 出售。图中弧上的 数字表示的是组装时部件（或产品）中包含的零件（或部件）的数量（可以称为消耗系 数），例如 DB弧上数字“9”表示组装 1 个部件 B 需要用到 9 个零件 D ； BA 弧上的 数字“5”表示组装 1 件产品 A 需要用到 5 个部件 B ；依此类推。 图 1 产品构成与组装过程图 假设该工厂每次生产计划的计划期为 6 周（即每次制定未来 6 周的生产计划），只 有最终产品 A 有外部需求，目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。 部件 B,C 是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的

生产能力非常紧张,具体可供能力如表1第3行所示(第2周设备检修,不能使用)。B,C 的能力消耗系数分别为5和8,即生产1件B需要占用5个单位的能力,生产1件C需 要占用8个单位的能力。 表1生产计划的原始数据 周次 A的外部需求40 瓶颈能力10000 0 1000 1000 零件编号 B C E F 生产准备费用400 300 单件库存费用 0.04 0.040.04 对于每种零部件或产品,如果工厂在某一周订购或者生产该零部件或产品,工厂 需要一个与订购或生产数量无关的固定成本(称为生产准备费用);如果某一周结束时 该零部件或产品有库存存在,则工厂必须付出一定的库存费用(与库存数量成正比) 这些数据在表1第5、6行给出。 按照工厂的信誉要求,目前接收的所有订单到期必须全部交货,不能有缺货;此 外,不妨简单地假设目前该企业没有任何零部件或产品库存,也不希望第6周结束后留 下任何零部件或产品库存。最后,假设不考虑生产提前期,即假设当周采购的零件马上 就可用于组装,组装出来的部件也可以马上用于当周组装成品A。 在上述假设和所给数据下,如何制定未来6周的生产计划。 12建立模型 (1)问题分析 这个实例考虑的是在有限的计划期内,给定产品结构、生产能力和相关费用及零 部件或成品(以下统称为生产项目)在离散的时间段上(这里是周,也可以是天、月等) 的外部需求之后,确定每一生产项目在每一时间段上的生产量(即批量),使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备( setup),所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实,细心的读者一定会问:是否 需要考虑生产的直接成本(如原材料成本、人力成本、电力成本等)?这是因为本例中 假设了不能有缺货发生,且计划初期和末期的库存都是0,因此在这个6周的计划期内 A的总产量一定正好等于A的总需求,所以可以认为相应的直接生产成本是一个常数, 因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想,对于放松这些假 定条件以后的情形,也是很容易类似地建立优化模型的。 (2)符号说明 为了建立这类问题的一般模型,我们定义如下数学符号 N:生产项目总数(本例中N=7) T:计划期长度(本例中T=6); K:瓶颈资源种类数(本例中K=1);

-387- 生产能力非常紧张，具体可供能力如表 1 第 3 行所示（第 2 周设备检修，不能使用）。B,C 的能力消耗系数分别为 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 对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂 需要一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时 该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比）。 这些数据在表 1 第 5 、6 行给出。 按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货；此 外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第 6 周结束后留 下任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上 就可用于组装，组装出来的部件也可以马上用于当周组装成品 A 。 在上述假设和所给数据下，如何制定未来 6 周的生产计划。 1.2 建立模型 （1）问题分析 这个实例考虑的是在有限的计划期内，给定产品结构、生产能力和相关费用及零 部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等） 的外部需求之后，确定每一生产项目在每一时间段上的生产量（即批量），使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备（setup），所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实，细心的读者一定会问：是否 需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？这是因为本例中 假设了不能有缺货发生，且计划初期和末期的库存都是 0，因此在这个 6 周的计划期内 A 的总产量一定正好等于 A 的总需求，所以可以认为相应的直接生产成本是一个常数， 因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想，对于放松这些假 定条件以后的情形，也是很容易类似地建立优化模型的。 （2）符号说明 为了建立这类问题的一般模型，我们定义如下数学符号： N ：生产项目总数（本例中 N = 7）； T ：计划期长度（本例中T = 6 ）； K ：瓶颈资源种类数（本例中 K =1）；

M:一个充分大的正数,在模型中起到使模型线性化的作用 d:项目i在t时段的外部需求(本例中只有产品A有外部需求) 项目i在t时段的生产批 1:项目i在t时段的库存量; Y,:项目i在t时段是否生产的标志(0:不生产,1:生产); S():产品结构中项目i的直接后继项目集合; 产品结构中项目j对项目i的消耗系数 s,:项目i在t时段生产时的生产准备费用; h,:项目i在t时段的单件库存费用 Cb,:资源k在I时段的能力上限 a:项目i在t时段生产时,生产单个项目占用资源k的能力; 在上述数学符号中,只有X,,Y为决策变量,其余均为已知的计划参数。 其实,真正的生产计划只是要求确定X就可以了,因为知道X以后L,H,也就 自然确定了。另外,在我们的具体例子中参数S,h,ak,其实只与项目i有关,而 不随时段t变化,我们这里加上下标t只是为了使模型能够更一般化 (3)目标函数 这个问题的目标是使生产准备费用和库存费用的总和最小。因此,目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和,即 ∑∑(s,Y+h,L2) (1) isl tel (4)约束条件 这个问题中的约束有如下几类:每个项目的物流应该守恒、资源能力限制应该满 足、每时段生产某项目前必须经过生产准备和非负约束(对Y是0-1约束)。 所谓物流守恒,是指对每个时段、每个项目(图中一个节点)而言,该项目在上

-388- M ：一个充分大的正数，在模型中起到使模型线性化的作用； di,t ：项目i 在t 时段的外部需求（本例中只有产品 A 有外部需求）； Xi,t ：项目i 在t 时段的生产批量； i t I , ：项目i 在t 时段的库存量； Yi,t ：项目i 在t 时段是否生产的标志（0：不生产，1：生产）； S(i) ：产品结构中项目i 的直接后继项目集合； i j r, ：产品结构中项目 j 对项目i 的消耗系数； i t s , ：项目i 在t 时段生产时的生产准备费用； hi,t ：项目i 在t 时段的单件库存费用； Ck ,t ：资源 k 在t 时段的能力上限； ak ,i,t ：项目i 在t 时段生产时，生产单个项目占用资源 k 的能力； 在上述数学符号中，只有 Xi,t ， i t I , ，Yi,t 为决策变量，其余均为已知的计划参数。 其实，真正的生产计划只是要求确定 Xi,t 就可以了，因为知道 Xi,t 以后 i t I , ，Yi,t 也就 自然确定了。另外，在我们的具体例子中参数 i t s , ，hi,t ，ak ,i,t 其实只与项目i 有关，而 不随时段t 变化，我们这里加上下标t 只是为了使模型能够更一般化。 （3）目标函数 这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和，即 ∑∑= = + N i T t i t i t i t i t s Y h I 1 1 , , , , ( ) （1） （4）约束条件 这个问题中的约束有如下几类：每个项目的物流应该守恒、资源能力限制应该满 足、每时段生产某项目前必须经过生产准备和非负约束（对Yi,t 是0 −1约束）。 所谓物流守恒，是指对每个时段、每个项目（图中一个节点）而言，该项目在上

个时段的库存量加上当前时段的生产量,减去该项目当前时段用于满足外部需求的量 和用于组装其它项目(直接后继项目)的量,应当等于当前时段的库存量。具体可以写 成如下表达式(假设l,0=0 1.,1+X d +>r X 1,2…,N,t=1,2,…,T 资源能力限制比较容易理解,即 akX1≤Ck,k=12…,K,t=1,2,…,T 每时段生产某项目前必须经过生产准备,也就是说当X,=0时Y,=0;X>0 时Y,=1。这本来是一个非线性约束,但是通过引入参数M(很大的正数,表示每个 项目每个时段的最大产量)可以化成线性约束,即 0≤X≤M,Y1∈{0},=1,2,…,N,t=1,2,…,T (4) 另外有 ≥0,i=1,2,…N,t=1,2,…,T, 总结上面的讨论,这个问题的优化模型就是在约束(2)~(4)下使目标函数(1) 达到最小。这可以认为是一个混合整数规划模型(因为产量一般较大,可以把x,和l 看成连续变量(实数)求解,而只有Y为0-1变量)。 1.3求解模型 本例中生产项目总数N=7(分别用1~7表示项目A,B,C,D,E,F,G),计划期 长度T=6(周),瓶颈资源种类数K=1。只有A有外部需求,所以d中只有d,可 以取非零需求,即表1中的第2行的数据,其它d,全部为零。参数s,h,只与项目 i有关,而不随时段t变化,所以可以略去下标【,其数值就是表1中的最后两行数据 由于只有一种资源,参数Ck可以略去下标k,其数值就是表1中的第3行的数据:而 a只与项目i有关,而不随时段t变化,所以可以同时略去下标k和t,即a2=5

-389- 一个时段的库存量加上当前时段的生产量，减去该项目当前时段用于满足外部需求的量 和用于组装其它项目（直接后继项目）的量，应当等于当前时段的库存量。具体可以写 成如下表达式（假设 Ii,0 = 0 ）： j t j S i Ii t Xi t Ii t di t rij X , ( ) , 1 , , , ∑∈ − + − = + i = 1,2,L,N ，t = 1,2,L,T （2） 资源能力限制比较容易理解，即 i t k t N i ak i t X , C , 1 ∑ , , ≤ = ，k = 1,2,L,K ，t = 1,2,L,T （3） 每时段生产某项目前必须经过生产准备，也就是说当 Xi,t = 0 时Yi,t = 0；Xi,t > 0 时Yi,t = 1。这本来是一个非线性约束，但是通过引入参数 M （很大的正数，表示每个 项目每个时段的最大产量）可以化成线性约束，即 0 ≤ Xi,t ≤ MYi,t ， {0,1} Yi,t ∈ ，i = 1,2,L, N ，t = 1,2,L,T （4） 另外有 Ii,t ≥ 0 ，i = 1,2,L,N ，t = 1,2,L,T ， （5） 总结上面的讨论，这个问题的优化模型就是在约束（2）~（4）下使目标函数（1） 达到最小。这可以认为是一个混合整数规划模型（因为产量一般较大，可以把 Xi,t 和 i t I , 看成连续变量（实数）求解，而只有Yi,t 为0 −1变量）。 1.3 求解模型 本例中生产项目总数 N = 7（分别用 1～7 表示项目 A, B,C, D, E, F,G ），计划期 长度T = 6 （周），瓶颈资源种类数 K =1。只有 A 有外部需求，所以 di,t 中只有 d1,t 可 以取非零需求，即表 1 中的第 2 行的数据，其它 di,t 全部为零。参数 i t s , ，hi,t 只与项目 i 有关，而不随时段t 变化，所以可以略去下标t ，其数值就是表 1 中的最后两行数据。 由于只有一种资源，参数Ck ,t 可以略去下标 k ，其数值就是表 1 中的第 3 行的数据；而 ak ,i,t 只与项目i 有关，而不随时段t 变化，所以可以同时略去下标 k 和t ，即 5 a2 =

a3=8(其它a1为0)。从图1中容易得到项目i的直接后继项目集合S()和消耗系数 对本例,A的外部总需求为240,所以任何项目的产量不会超过 240×7×15=25000(从图1可以知道,这里7×15已经是每件产品A对任意一个项 目的最大的消耗系数了),所以取M=25000就已经足够了。 TITLE瓶颈设备的多级生产计划; ETS !PART=项目集合, Setup=生产准备费,Hold=单件库存成本 A=对瓶颈资源的消耗系数 PARTA C DE F G/: Setup, Hold,A !TIME=计划期集合, Capacity=瓶颈设备的能力 TIME/1.6/: Capacity !UsEs=项目结构关系,Req=项目之间的消耗系数 USES(PART, PART): Req PxT=项目与时间的派生集合, Demand=外部需求, X=产量(批量),Y=0/1变量,INV=库存 PXT(PART, TIME): Demand, x, Y, In !目标函数 [OBJ]Min=@sum(PXT(主,t): setup(i)*Y(主,t)+ho1d(i)*n(主,t)) 物流平衡方程 FoR(PXT(主,t)|t#NE 1: [Bal]Inv(i, t-1)+X(i, t)-Inv(i, t)=Demand(i, t)+GSUM (USES (1,3): Reg( i,j)*X(j,t))); FoR(PXT(i,t)|t#eq井 1: [Ba0]x(i, t)-Inv(i, t)=Demand(i, t)+@SUM(USES (1,3): Req(i, 3)*X(, t) !能力约束 @FOR (TIME (t): [Cap]@SUM(PART(i): A(i)*X(i, t))<Capacity(t)) !其他约束 M=25000 @FOR (PXT(i t):x(i t)<=M*Y (i t))i @FOR(PXT: GBIN(Y))i DATA 005000500010001000;

-390- a3 = 8 （其它 ai 为 0）。从图 1 中容易得到项目i 的直接后继项目集合 S(i) 和消耗系数 i j r, 。 对本例， A 的外部总需求为 240 ，所以任何项目的产量不会超过 240× 7 ×15 = 25000 （从图 1 可以知道，这里7 ×15已经是每件产品 A 对任意一个项 目的最大的消耗系数了），所以取 M = 25000 就已经足够了。 MODEL: TITLE 瓶颈设备的多级生产计划; 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; ! PXT=项目与时间的派生集合，Demand=外部需求, X=产量（批量）, Y=0/1变量，INV=库存; PXT(PART,TIME):Demand,X,Y,Inv; ENDSETS ! 目标函数; [OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t)); ! 物流平衡方程; @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) )); ! 能力约束; @FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t)); ! 其他约束; M = 25000; @FOR(PXT(i,t):X(i,t)<=M*Y(i,t)); @FOR(PXT:@BIN(Y)); DATA: Demand=0;Req =0; Capacity=10000 0 5000 5000 1000 1000;