l第六章动态规划习题课.pptVIP

§6 动态规划应用举例 1 资源分配问题 2 生产与存储问题 3 排序问题 4 设备更新问题 1 资源分配问题 1.1 一维资源分配问题 1. 资源平行分配问题 例1 某部门拟建某种高效设备五台分配给所属的甲、乙、丙三个工厂，各工厂获得这种设备后，可以提供的盈利如下表，问应如何分配，才能使总盈利最大？ 解：该问题的动态规划问题模型为 2. 资源连续分配问题 设有数量为s1的资源，可投入A、B两种生产。 若以数量u投入生产A，则可得收入为 1.2 二维资源分配问题 在实际中，为了简化计算，经常采用下面的方法进行降维。 引入拉格朗日乘数λ，将二维分配问题化为一维分配问题。 2 生产与存储问题 再生产和经营管理中，经常遇到要合理安排生产（或购买）与库存的问题，达到既要满足社会的需求，又要尽量降低成本费用。因此，正确制定生产（或购买）策略，确定不同时期的生产量（或购买量）和库存量，以使总的生产成本费用和库存费用最低。这样的问题称为生产存储问题。 2.1 生产计划问题 例：某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量如下表。假定该厂生产每批产品的固定成本为3元，若不生产为就0，每单位产品成本为1千元，每个时期生产能力所容许的最大生产批量不超过6各单位；每个时期末未售出的产品，每单位需付存储费5百元。假定第一个时期初始库存量为0。试问该厂应如何安排各个时期的生产与库存，才能在满足市场需求的条件下，使总成本最小？ * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1 2 …… n-1 n x1 x2 xn-1 xn s2 s3 sn-1 sn sn+1 s1 D(s1) D(s2 ) D(sn-1) D(sn) 转移方程 指标函数 基本方程 容许决策集合 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 工厂 所得设备数 0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 工厂1 工厂2 工厂3 0≤x1≤s1 0≤x2≤s2 0≤x3≤s3 s2=s1-x1 s3=s2-x2 s4=s3-x3 s1=5 下面从最后一个阶段开始向前递推计算 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 0 1 2 3 4 5 0 1 2 3 4 5 0 0 4 0 4 6 0 4 6 11 0 4 6 11 12 0 4 6 11 12 12 0 4 6 11 12 12 0 1 2 3 4 5 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 0 1 2 3 4 5 0 1 2 3 4 5 0 0+4 0+6 0+11 0+12 5+11