重庆工商大学数学建模算法讲义第27章 生产与服务运作管理中的优化问题

-386-第二十七章生产与服务运作管理中的优化问题本章主要介绍生产和服务运作管理方面的一些优化问题。实际上，生产和服务运作管理的内容也是非常丰富的，几乎包含了企业管理的所有方面，本章中只是介绍几个实例而已。§1有瓶颈设备的多级生产计划问题1.1问题实例在制造企业的中期或短期生产计划管理中，常常要考虑如下的生产计划优化问题：在给定的外部需求和生产能力等限制条件下，按照一定的生产目标（通常是生产总费用最小）编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题（lotsizingproblems）。所谓某一产品的生产批量（lotsize），就是每通过一次生产准备生产该产品时的生产数量，它同时决定了库存水平。由于实际生产环境的复杂性，如需求的动态性，生产费用的非线性，生产工艺过程和产品网络结构的复杂性，生产能力的限制，以及车间层生产排序的复杂性等，批量问题是一个非常复杂、非常困难的问题。我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级”的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。例1某工厂的主要任务是通过组装生产产品A，用于满足外部市场需求。产品A的构成与组装过程见图1，即GFED,,,是从外部采购的零件，先将零件ED,组装成部件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-生产能力非常紧张，具体可供能力如表1第3行所示（第2周设备检修，不能使用）。CB,的能力消耗系数分别为5和8，即生产1件B需要占用5个单位的能力，生产1件C需要占用8个单位的能力。表1生产计划的原始数据周次123456A的外部需求40010009010瓶颈能力1000005000500010001000零件编号ABCDEFG生产准备费用4005001000300200400100单件库存费用120.61.00.040.030.040.04对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂需要一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比）。这些数据在表1第5、6行给出。按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货；此外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第6周结束后留下任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上就可用于组装，组装出来的部件也可以马上用于当周组装成品A。在上述假设和所给数据下，如何制定未来6周的生产计划。1.2建立模型（1）问题分析这个实例考虑的是在有限的计划期内，给定产品结构、生产能力和相关费用及零部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等）的外部需求之后，确定每一生产项目在每一时间段上的生产量（即批量），使总费用最小。由于每一生产项目在每一时间段上生产时必须经过生产准备（setup），所以通常的讨论中总费用至少应考虑生产准备费用和库存费用。其实，细心的读者一定会问：是否需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？这是因为本例中假设了不能有缺货发生，且计划初期和末期的库存都是0，因此在这个6周的计划期内A的总产量一定正好等于A的总需求，所以可以认为相应的直接生产成本是一个常数，因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想，对于放松这些假定条件以后的情形，也是很容易类似地建立优化模型的。（2）符号说明为了建立这类问题的一般模型，我们定义如下数学符号：N：生产项目总数（本例中7=N）；T：计划期长度（本例中6=T）；K：瓶颈资源种类数（本例中1=K）；-388-M：一个充分大的正数，在模型中起到使模型线性化的作用；tid,：项目i在t时段的外部需求（本例中只有产品A有外部需求）；tiX,：项目i在t时段的生产批量；tiI,：项目i在t时段的库存量；tiY,：项目i在t时段是否生产的标志（0：不生产，1：生产）；)(iS：产品结构中项目i的直接后继项目集合；jir,：产品结构中项目j对项目i的消耗系数；tis,：项目i在t时段生产时的生产准备费用；tih,：项目i在t时段的单件库存费用；tkC,：资源k在t时段的能力上限；tika,,：项目i在t时段生产时，生产单个项目占用资源k的能力；在上述数学符号中，只有tiX,，tiI,，tiY,为决策变量，其余均为已知的计划参数。其实，真正的生产计划只是要求确定tiX,就可以了，因为知道tiX,以后tiI,，tiY,也就自然确定了。另外，在我们的具体例子中参数tis,，tih,，tika,,其实只与项目i有关，而不随时段t变化，我们这里加上下标t只是为了使模型能够更一般化。（3）目标函数这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该是每个项目在每个阶段上的生产准备费用和库存费用的总和，即∑∑==+NiTttitititiIhYs11,,,,)(（1）（4）约束条件这个问题中的约束有如下几类：每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束（对tiY,是10−约束）。所谓物流守恒，是指对每个时段、每个项目（图中一个节点）而言，该项目在上-389-一个时段的库存量加上当前时段的生产量，减去该项目当前时段用于满足外部需求的量和用于组装其它项目（直接后继项目）的量，应当等于当前时段的库存量。具体可以写成如下表达式（假设00,=iI）：tjiSjijtitititiXrdIXI,)(,,,1,∑∈−+=−+Ni,,2,1L=，Tt,,2,1L=（2）资源能力限制比较容易理解，即tktiNitikCXa,,1,,≤∑=，Kk,,2,1L=，Tt,,2,1L=（3）每时段生产某项目前必须经过生产准备，也就是说当0,=tiX时0,=tiY；0,tiX时1,=tiY。这本来是一个非线性约束，但是通过引入参数M（很大的正数，表示每个项目每个时段的最大产量）可以化成线性约束，即titiMYX,,0≤≤，}1,0{,∈tiY，Ni,,2,1L=，Tt,,2,1L=（4）另外有0,≥tiI，Ni,,2,1L=，Tt,,2,1L=，（5）总结上面的讨论，这个问题的优化模型就是在约束（2）~（4）下使目标函数（1）达到最小。这可以认为是一个混合整数规划模型（因为产量一般较大，可以把tiX,和tiI,看成连续变量（实数）求解，而只有tiY,为10−变量）。1.3求解模型本例中生产项目总数7=N（分别用1～7表示项目GFEDCBA,,,,,,），计划期长度6=T（周），瓶颈资源种类数1=K。只有A有外部需求，所以tid,中只有td,1可以取非零需求，即表1中的第2行的数据，其它tid,全部为零。参数tis,，tih,只与项目i有关，而不随时段t变化，所以可以略去下标t，其数值就是表1中的最后两行数据。由于只有一种资源，参数tkC,可以略去下标k，其数值就是表1中的第3行的数据；而tika,,只与项目i有关，而不随时段t变化，所以可以同时略去下标k和t，即52=a，-390-83=a（其它ia为0）。从图1中容易得到项目i的直接后继项目集合)(iS和消耗系数jir,。对本例，A的外部总需求为240，所以任何项目的产量不会超过25000157240=××（从图1可以知道，这里157×已经是每件产品A对任意一个项目的最大的消耗系数了），所以取25000=M就已经足够了。MODEL:TITLE瓶颈设备的多级生产计划;SETS:!PART=项目集合,Setup=生产准备费，Hold=单件库存成本，A=对瓶颈资源的消耗系数;PART/ABCDEFG/: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=1000005000500010001000;-391-Setup=4005001000300200400100;Hold=120.61.00.040.030.040.04;A=0580000;ENDDATACALC: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;ENDCALCEND计算结果见表2（只列出了生产产量tiX,，空格表示不生产，即产量为0）。表2生产计划的最后结果周次123456A的产量40100100B的产量2001000C的产量1055625D的产量18009000E的产量220011000F的产量137158125G的产量158259375§2下料问题生产中常会遇到通过切割、剪裁、冲压等手段，将原材料加工成所需大小这种工艺过程，称为原料下料（cuttingstock）问题。按照进一步的工艺要求，确定下料方案，使用料最省或利润最大，是典型的优化问题。本节通过两个实例讨论用数学规划模型解决这类问题的方法。2.1钢管下料问题例2某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是19m长。（1）现有一客户需要50根4m长，20根6m长和15根8m长的钢管。应如何下料最节省？（2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5m长的钢管。应如何下料最节省？2.1.1问题（1）的求解（1）问题分析首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要-392-在原料钢管上安排切割的一种组合。例如，我们可以将19m长的钢管切割成3根4m长的钢管，余料为7m；或者将19m长的钢管切割成4m，6m和8m长的钢管各1根，余料为1m。显然，可行的切割模式是很多的。其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不