运筹学课程07-动态规划.ppt

《运筹学课程07-动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划DynamicProgramming不要过河拆桥追求全局最优多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容一、多阶段决策过程的最优化示例1（工厂生产安排）：某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制

2、订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。设有数量为y的某种资源，将它分别投入两种生产方式A和B，已知收益函数分别是g(x)和h(x)，x为资源投入量。设这种资源用于生产后还可以回收一部分用于生产，A、B的回收率分别为a和b（0≤a≤1，0≤b≤1），问：对总数量为y的资源进行n个阶段的生产，应如何分配每个阶段投入A、B的资源数量，才能使总收益最大？推广：多阶段资源分配问题示例2（设备更新问题）：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理

3、价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。示例3（连续生产过程的控制问题）：示例4、最短路径问题给定一个交通网络图如下，其中两点之间的数字表示距离（

4、或花费），试求从A点到G点的最短距离（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643示例5（生产与存储问题）：某工厂生产并销售某种产品。已知今后四个月市场需求预测及每月生产j个单位产品的费用如下：每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。每个月视为一个阶段，每个阶段都须决定生产

5、几个、库存几个上一个阶段的决策直接影响下一个阶段的决策月1234需求2324由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。示例6（航天飞机飞行控制问题）：所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策均确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达

6、到最优。动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n维决策问题变换为几个一维最优化问题，从而一个一个地去解决。12n状态决策状态决策状态状态决策10不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。某些线性规划、非线性规划等静态规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。DP是上个世纪五十年代贝尔曼(B.E.Bellman)为代表的研究成果，属于现代控制理论的一部分。其最优化原理，可归结为一个递推公式。

7、注意：动态规划是求解某类多阶段决策问题的一种方法，是考察问题的一种途径，不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。动态规划思想示例：BACBDBCDEC412312312322164724838675611063751以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从A到E的最短路径问题。第四阶段：两个始点和，终点只有一个；阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D2106106

8、EE分析得知：从和到E的最短路径唯一。第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题：分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，