第二十七章生产与服务运作管理中的优化问题 本章主要介绍生产和服务运作管理方面的一些优化问题。实际上,生产和服务运作 管理的内容也是非常丰富的,几乎包含了企业管理的所有方面,本章中只是介绍几个实 例而已 §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;
setup=4005001000300200400100; Ho1d=120.61.00.040.030.040.04; A=0580000 ENDDATA CALC demand(1,1)=40; demand(1,3)=100; demand(1,5)=90; demand(1,6)=10; req(2,1)=5;req(3,1)=7;req(4,2)=9; req(5,2)=11;req(6,3)=13;req(7,3)=15 ENDCALC END 计算结果见表2(只列出了生产产量X,,空格表示不生产,即产量为0) 表2生产计划的最后结果 周次 A的产量 100 B的产量 1000 C的产量1055 D的产量 9000 E的产量 11000 F的产量13715 8125 G的产量15825 9375 §2下料问题 生产中常会遇到通过切割、剪裁、冲压等手段,将原材料加工成所需大小这种工 艺过程,称为原料下料( cutting stock)问题。按照进一步的工艺要求,确定下料方案 使用料最省或利润最大,是典型的优化问题。本节通过两个实例讨论用数学规划模型解 决这类问题的方法。 2.1钢管下料问题 例2某钢管零售商从钢管厂进货,将钢管按照顾客的要求切割后售出。从钢管厂 进货时得到的原料钢管都是19m长 (1)现有一客户需要50根4m长,20根6m长和15根8m长的钢管。应如何下 料最节省? (2)零售商如果采用的不同切割模式太多,将会导致生产过程的复杂化,从而增 加生产和管理成本,所以该零售商规定采用的不同切割模式不能超过3种。此外,该客 户除需要(1)中的三种钢管外,还需要10根5m长的钢管。应如何下料最节省? 2.1.1问题(1)的求解 (1)问题分析 首先,应当确定哪些切割模式是可行的。所谓一个切割模式,是指按照客户需要 391
-391- Setup=400 500 1000 300 200 400 100; Hold=12 0.6 1.0 0.04 0.03 0.04 0.04; A=0 5 8 0 0 0 0; ENDDATA CALC: demand(1,1)=40;demand(1,3)=100; demand(1,5)=90;demand(1,6)=10; req(2,1)=5;req(3,1)=7;req(4,2)=9; req(5,2)=11;req(6,3)=13;req(7,3)=15; ENDCALC END 计算结果见表 2（只列出了生产产量 Xi,t ，空格表示不生产，即产量为 0）。 表 2 生产计划的最后结果 周次 1 2 3 4 5 6 A 的产量 40 100 100 B 的产量 200 1000 C 的产量 1055 625 D 的产量 1800 9000 E 的产量 2200 11000 F 的产量 13715 8125 G 的产量 15825 9375 §2 下料问题 生产中常会遇到通过切割、剪裁、冲压等手段，将原材料加工成所需大小这种工 艺过程，称为原料下料（cutting stock）问题。按照进一步的工艺要求，确定下料方案， 使用料最省或利润最大，是典型的优化问题。本节通过两个实例讨论用数学规划模型解 决这类问题的方法。 2.1 钢管下料问题 例 2 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂 进货时得到的原料钢管都是 19m 长。 （1）现有一客户需要 50 根 4m 长，20 根 6m 长和 15 根 8m 长的钢管。应如何下 料最节省？ （2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增 加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过 3 种。此外，该客 户除需要（1）中的三种钢管外，还需要 10 根 5m 长的钢管。应如何下料最节省？ 2.1.1 问题（1）的求解 （1）问题分析 首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要
在原料钢管上安排切割的一种组合。例如,我们可以将19m长的钢管切割成3根4m 长的钢管,余料为7m;或者将19m长的钢管切割成4m,6m和8m长的钢管各1根 余料为1m。显然,可行的切割模式是很多的 其次,应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不 应该大于或等于客户需要的钢管的最小尺寸。例如,将19m长的钢管切割成3根4m 的钢管是可行的,但余料为7m,可以进一步将7m的余料切割成4m钢管(余料为3m) 或者将7m的余料切割成6m钢管(余料为1m)。在这种合理性假设下,切割模式一共 有7种,如表3所示。 表3钢管下料的合理切割模式 4m钢管根数 6m钢管根数 8m钢管根数 余料(m) 模式2 模式3 0102 3133 模式4 模式5 模式6 0 模式7 2 问题化为在满足客户需要的条件下,按照哪些种合理的模式,切割多少根原料钢 管,最为节省。而所谓节省,可以有两种标准,一是切割后剩余的总余料量最小,二是 切割原料钢管的总根数最少。下面将对这两个目标分别讨论 (2)模型建立 决策变量:用x表示按照第i种模式(=1,2,…,7)切割的原料钢管的根数,显 然它们应当是非负整数。 决策目标:以切割后剩余的总余料量最小为目标,则由表3可得 min1=3x1+x2+3x3+3x4+x5+x6+3x7 (6) 以切割原料钢管的总根数最少为目标,则有 下面分别在这两种目标下求解 约束条件:为满足客户的需求,按照表3应用 x1+3x2+2x3+x4+x5 x2+x4+x5+3x6≥ (9)
-392- 在原料钢管上安排切割的一种组合。例如，我们可以将 19m 长的钢管切割成 3 根 4m 长的钢管，余料为 7m；或者将 19m 长的钢管切割成 4m，6m 和 8m 长的钢管各 1 根， 余料为 1m。显然，可行的切割模式是很多的。 其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不 应该大于或等于客户需要的钢管的最小尺寸。例如，将 19m 长的钢管切割成 3 根 4m 的钢管是可行的，但余料为 7m，可以进一步将 7m 的余料切割成 4m 钢管（余料为 3m）， 或者将 7m 的余料切割成 6m 钢管（余料为 1m）。在这种合理性假设下，切割模式一共 有 7 种，如表 3 所示。 表 3 钢管下料的合理切割模式 4m 钢管根数 6m 钢管根数 8m 钢管根数 余料（m） 模式 1 4 0 0 3 模式 2 3 1 0 1 模式 3 2 0 1 3 模式 4 1 2 0 3 模式 5 1 1 1 1 模式 6 0 3 0 1 模式 7 0 0 2 3 问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢 管，最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是 切割原料钢管的总根数最少。下面将对这两个目标分别讨论。 （2）模型建立 决策变量：用 i x 表示按照第i 种模式（i = 1,2,L,7 ）切割的原料钢管的根数，显 然它们应当是非负整数。 决策目标：以切割后剩余的总余料量最小为目标，则由表 3 可得 min 1 3 1 2 3 3 3 4 5 6 3 7 z = x + x + x + x + x + x + x （6） 以切割原料钢管的总根数最少为目标，则有 ∑= = 7 1 min 2 i i z x （7） 下面分别在这两种目标下求解。 约束条件：为满足客户的需求，按照表 3 应用 4x1 + 3x2 + 2x3 + x4 + x5 ≥ 50 （8） x2 + x4 + x5 + 3x6 ≥ 20 （9）
x2+x4+2x≥15 (10) (3)模型求解 i)将式(6)、(8)~(9)构成的整数线性规划模型(加上整数约束)输入LⅠNG nodel TITLE钢管下料一最小化余量 w/1..3/:b link(row, col) endsets data 3133113 b=502015 a=4321100 0102130 0010102 enddata min=@sum(col: c*x)i @for (row(i): @sum(col(3):a(i,3)*x(3))>=b(1))i @for(col: @gin(x)) 求得按照模式2切割12根原料钢管,按照模式5切割15根原料钢管,共27根, 总余料量为27m。但4m长的钢管比要求多切割了1根,6m长的钢管比要求多切割了 7根。显然,在总余料量最小的目标下,最优解将是使用余料尽可能小的切割方式(模 式2和模式5的余料为lm),这会导致切割原料钢管的总根数较多。 i)将式(7)~(10)构成的整数线性规划模型输入LING model TITLE钢管下料一最小钢管数; co1/1..7/:c0,C,x; row/1..3/:b link(row, col): a endsets data c0=3133113; C=1111111 b=502015 a=4321100
-393- x3 + x5 + 2x7 ≥15 （10） （3）模型求解 i）将式（6）、（8）～（9）构成的整数线性规划模型（加上整数约束）输入 LINGO model: TITLE 钢管下料－最小化余量; sets: col/1..7/:c,x; row/1..3/:b; link(row,col):a; endsets data: c=3 1 3 3 1 1 3; b=50 20 15; a=4 3 2 1 1 0 0 0 1 0 2 1 3 0 0 0 1 0 1 0 2; enddata min=@sum(col:c*x); @for(row(i):@sum(col(j):a(i,j)*x(j))>=b(i)); @for(col:@gin(x)); end 求得按照模式 2 切割 12 根原料钢管，按照模式 5 切割 15 根原料钢管，共 27 根， 总余料量为 27m。但 4m 长的钢管比要求多切割了 1 根，6m 长的钢管比要求多切割了 7 根。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割方式（模 式 2 和模式 5 的余料为 1m），这会导致切割原料钢管的总根数较多。 ii）将式（7）～（10）构成的整数线性规划模型输入 LINGO model: TITLE 钢管下料－最小钢管数; sets: col/1..7/:c0,c,x; row/1..3/:b; link(row,col):a; endsets data: c0=3 1 3 3 1 1 3; c=1 1 1 1 1 1 1; b=50 20 15; a=4 3 2 1 1 0 0
0102130 0010102 enddata @for(row(i): [conl]esum(col(j):a(1,3)*x(3))>=b(i)); @for (col: egin(x)) [remainder]y=@sum(col: c0*x) end 求得按照模式2切割15根原料钢管,按模式5切割5根,按模式7切割5根,共 25根,可算出总余料量为35m。但各长度的钢管数恰好全部满足要求,没有多切割。 与上面得到的结果比较,总余料量增加了8m,但是所用的原料钢管的总根数减少了2 根。在余料没有什么用途的情况下,通常选择总根数最少为目标。 2.1.2问题(2)的求解 (1)问题分析 按照问题(1)的思路,可以通过枚举法首先确定哪些切割模式是可行的。但由于 需要的钢管规格增加到4种,所以枚举法的工作量较大。下面介绍的整数非线性规划模 型,可以同时确定切割模式和切割计划,是带有普遍性的方法。 同问题(1)类似,一个合理的切割模式的余料不应该大于或等于客户需要的钢管 的最小尺寸(本题中为4m),切割计划中只使用合理的切割模式,而由于本题中参数都 是整数,所以合理的切割模式的余量不能大于3m。此外,这里我们仅选择总根数最少 为目标进行求解 (2)模型建立 决策变量:由于不同切割模式不能超过3种,可以用x,表示按照第j种模式 (j=1,2,3)切割的原料钢管的根数,显然它们应当是非负整数。设所使用的第j种 切割模式下每根原料钢管生产4m长,5m长,6m长和8m长的钢管数量分别为 F,y,3y4,(非负整数)。记客户需求的4种钢管的长度为1,数量为b(i=1,2,34)。 决策目标:以切割原料钢管的总根数最少为目标,即目标为 mn∑x (11) 约束条件:为满足客户的需求,应有 ∑冖x≥b,i= 每一种切割模式必须可行、合理,所以每根原料钢管的成品量不能超过19m,也 不能少于16m(余量不能大于3m),于是 394
-394- 0 1 0 2 1 3 0 0 0 1 0 1 0 2; enddata min=@sum(col:c*x); @for(row(i):[con1]@sum(col(j):a(i,j)*x(j))>=b(i)); @for(col:@gin(x)); [remainder]y=@sum(col:c0*x); end 求得按照模式 2 切割 15 根原料钢管，按模式 5 切割 5 根，按模式 7 切割 5 根，共 25 根，可算出总余料量为 35m。但各长度的钢管数恰好全部满足要求，没有多切割。 与上面得到的结果比较，总余料量增加了 8m，但是所用的原料钢管的总根数减少了 2 根。在余料没有什么用途的情况下，通常选择总根数最少为目标。 2.1.2 问题（2）的求解 （1）问题分析 按照问题（1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于 需要的钢管规格增加到 4 种，所以枚举法的工作量较大。下面介绍的整数非线性规划模 型，可以同时确定切割模式和切割计划，是带有普遍性的方法。 同问题（1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管 的最小尺寸（本题中为 4m），切割计划中只使用合理的切割模式，而由于本题中参数都 是整数，所以合理的切割模式的余量不能大于 3m。此外，这里我们仅选择总根数最少 为目标进行求解。 （2）模型建立 决策变量：由于不同切割模式不能超过 3 种，可以用 j x 表示按照第 j 种模式 （ j =1,2,3）切割的原料钢管的根数，显然它们应当是非负整数。设所使用的第 j 种 切割模式下每根原料钢管生产 4m 长，5m 长，6m 长和 8m 长的钢管数量分别为 j j j j r r r r 1 2 3 4 , , , （非负整数）。记客户需求的 4 种钢管的长度为 i l ，数量为b（i i =1,2,3,4 ）。 决策目标：以切割原料钢管的总根数最少为目标，即目标为 ∑= 3 1 min j j x （11） 约束条件：为满足客户的需求，应有 j i j ∑rij x ≥ b = 3 1 ，i = 1,2,3,4 （12） 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过 19m，也 不能少于 16m（余量不能大于 3m），于是
j=1,2,3 (3)模型求解 式(11)~(13)构成这个问题的优化模型。由于在式(11)~(13)中出现了决 策变量的乘积,所以这是一个整数非线性规划模型,虽然用 LINGO软件可以直接求解, 但我们发现有时 LINGO软件运行很长时间也难以得到最优解。为了减少运行时间,可 以增加一些显然的约束条件,从而缩小可行解的搜索范围 例如,由于3种切割模型的排列顺序是无关紧要的,所以不妨增加以下约束: (14) 又如,我们注意到所需原料钢管的总根数有着明显的上界和下界。首先,无论如何,原 料钢管的总根数不可能少于[4×50+5×10+6×20+8×15)/19]=26(根)。其次, 考虑一种非常特殊的生产计划:第一种切割模式下只生产4m钢管,1根原料钢管切割 成4根4m钢管,为满足50根4m钢管的需求,需要13根原料钢管;第二种切割模式 下只生产5m、6m钢管,一根原料钢管切割成1根5m钢管和2根6m钢管,为满足10 根5m钢管和20根6m钢管的需求,需要10根原料钢管;第三种切割模式下只生产8 钢管,1根原料钢管切割成2根8m钢管,为满足15根8m钢管的需求,需要8根原料 钢管。于是满足要求的这种生产计划共需13+10+8=31根原料钢管,这就得到了最 优解的一个上界。所以可增加以下约束: 26 x≤31 (15) 将式(11)~(15)构成的模型输入 LINGO如下 model Title钢管下料-最小化钢管根数的 LINGO模型; NEEDS/1. 4/: LENGTH, b; PATTERNS(NEEDS, CUTS): R ENDSETS LENGTH=4 5 8: b=50102015 CAPACITY=19 ENDDATA min=@SUM (CUTS (I): x(I)) @FOR(NEEDS(I): eSUM (CUTS(J): x(J)*R(I,J))>b(I))i
-395- 16 19 4 1 ≤ ∑ ≤ i= i ij l r ， j = 1,2,3 （13） （3）模型求解 式（11）～（13）构成这个问题的优化模型。由于在式（11）～（13）中出现了决 策变量的乘积，所以这是一个整数非线性规划模型，虽然用 LINGO 软件可以直接求解， 但我们发现有时 LINGO 软件运行很长时间也难以得到最优解。为了减少运行时间，可 以增加一些显然的约束条件，从而缩小可行解的搜索范围。 例如，由于 3 种切割模型的排列顺序是无关紧要的，所以不妨增加以下约束： 1 2 3 x ≥ x ≥ x （14） 又如，我们注意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原 料钢管的总根数不可能少于[(4×50 + 5×10 + 6× 20 + 8×15)/19] = 26 （根）。其次， 考虑一种非常特殊的生产计划：第一种切割模式下只生产 4m 钢管，1 根原料钢管切割 成 4 根 4m 钢管，为满足 50 根 4m 钢管的需求，需要 13 根原料钢管；第二种切割模式 下只生产 5m、6m 钢管，一根原料钢管切割成 1 根 5m 钢管和 2 根 6m 钢管，为满足 10 根 5m 钢管和 20 根 6m 钢管的需求，需要 10 根原料钢管；第三种切割模式下只生产 8m 钢管，1 根原料钢管切割成 2 根 8m 钢管，为满足 15 根 8m 钢管的需求，需要 8 根原料 钢管。于是满足要求的这种生产计划共需13 +10 + 8 = 31根原料钢管，这就得到了最 优解的一个上界。所以可增加以下约束： 26 31 3 1 ≤ ∑ ≤ i= i x （15） 将式（11）～（15）构成的模型输入 LINGO 如下： model: Title 钢管下料 - 最小化钢管根数的LINGO模型; SETS: NEEDS/1..4/:LENGTH,b; CUTS/1..3/:X; PATTERNS(NEEDS,CUTS):R; ENDSETS DATA: LENGTH=4 5 6 8; b=50 10 20 15; CAPACITY=19; ENDDATA min=@SUM(CUTS(I): X(I) ); @FOR(NEEDS(I):@SUM(CUTS(J):X(J)*R(I,J))>b(I) );
