[教育]第八章动态规划11-5-17.pptVIP

动 态 规 划 多阶段决策问题 最优化原理与动态规划的数学模型 动态规划模型的建立与求解 多阶段决策问题 例1 最短路问题 最优化原理与动态规划的数学模型 动态规划问题的解题思路 动态规划的基本概念 最优化原理与动态规划的数学模型 动态规划的数学模型： 动态规划模型的分类 动态规划模型的建立与求解 作业： * * 第八章 动 态 规 划 北京物资学院运筹学教学课件 北京物资学院信息学院 2011-5-8 动态规划是一种研究多阶段决策问题的理论和方法。 多阶段决策问题 是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 策略：每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的总效益达到最优。 设有一个旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路线可以选择，各点之间的距离如图所示，问该旅行者应该选择哪一条路线，才能使从A到达E的总行程最短？ A B1 B2 B3 C3 C2 C1 D1 D2 E 2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4 状态A 决策 阶段1 状态B1 阶段2 决策 状态D1 状态C3 阶段3 决策 阶段4 决策 状态E 行程1 行程2 行程3 行程4 例2 多阶段资源分配问题 设有某种机器设备，可用于完成两类工作A和B。若第k年初完好机器的数量为sk,若以数量xk用于工作A，余下的sk- xk用于工作B，则该年的预期收入为g(xk)+h(sk- xk)，其中g(xk) 和h(sk- xk) 是已知函数，并且g(0)=h(0)=0。又机器设备在使用中会有损坏，设机器用于工作A时，一年后能继续使用的完好机器数占年初投入量的a倍（0a1），若用于工作B时，一年后能继续使用的完好机器数占年初投入量的b倍(0b1)，即下一年初能继续用于完成这两项工作的机器数为sk+1=axk+b(sk- xk)。设第一年初完好的机器数为s1，问在连续三年内，每年应如何分配用于A、B两项工作的机器数，才能使三年的总收益达到最大。 状态S1 决策 第一年 阶段1 状态S2 第二年 阶段2 决策 状态S4 状态S3 第三年 阶段3 决策 收益1 收益2 收益3 动态规划问题的解题思路 动态规划的基本概念 最优化原理与动态规划的数学模型 动态规划模型的分类 思路：将一个n阶段的决策问题转化为依次求n个具有递推关系的单阶段决策问题，从而简化计算。 在例1中，这种转化的实现是从终点E出发一步步进行反推（逆序算法） （1）考虑一个阶段的选择。 到达E之前，上一步必然到达D1或D2， D1到E的最优策略是：D1?E，距离d(D1,E)=3,记 f(D1)=3. D2到E的最优策略是：D2?E，距离d(D2,E)=4,记 f(D2)=4. 1 A B1 B2 B3 C3 C2 C1 D1 D2 E 2 5 3 7 5 6 3 2 4 5 1 5 4 6 3 3 3 3 4 (2)联合考虑两个阶段的最优选择。 当旅行者离终点还有两站时，他必然处在C1，C2或C3的某一点上。 C1到终点的路有两条：C1?D1?E， C1?D2?E，旅行者从这两条路线中选最短的一条，并且不管是经过D1或D2，到达该点后，他应循着从D1或D2到E的最短路线继续走。因此 从C1到E的最短路程为： 即从C1到E的最短路线为C1?D1?E，记 如果从C2出发 如果从C3出发 （3）再联合起来考虑三个阶段的最优选择。 从B1点出发的最优选择为 从B2点出发的最优选择为 从B3点出发的最优选择为 （4）四个阶段联合考虑时从A到E的最优选择。 从A到E的最短路线为A?B3?C2?D2?E，距离为11。 1 A B1 B2 B3 C3 C2 C1 D1 D2 E 2 5 3 7 5 6 3 2 4 5 1 5 4 6 3 3 3 3 4 3 4 4 7 6 11 7 8 11 以上计算过程可以在图上通过标号法实现 1. 阶段(stage)：指一个问题需要作出决策的步数。 通常用k表示问题的阶段数。阶段一般是根据时间和空间的自然特征来划分的。 2. 状态(state)：表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，是动态规划中最关键的一个参数。 它既反映前面各个阶段决策的结局，又是本阶段决策的出发点和依据。它是动态规划问题各个阶段信息的传递点和结合点。通常一个阶段有多个状态。如例1中第一阶段有1个状态，A. 第三阶段有三个状态C1,C2,C3。 状态变量：描述状态的变量。可以是数、数组或向量。通常用Sk表示k阶段的状态集