OR9动态规划.pptVIP

求A到E的最短距离！ 第九章 动态规划 李 娜 2009.9 动态规划是解决多阶段决策过程最优化问题的一种方法——变换成单阶段问题。 根据时间参量分为：离散变量和连续变量 根据决策过程演变分为：确定性和随机性的 动态规划可分为：离散确定性、离散随机性、连续确定性、连续随机性四种。 §9.1　多阶段决策过程最优化问题举例 求最短路径！ 用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则 总共有3k-1×2条路径； 计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及 3k-1×2-1次比较。随着 k 的值增加时，需要进行的加法和比较的 次数将迅速增加； 例如当 k=20时，加法次数为 4.2550833966227×1015 次， 比较 1.3726075472977×1014 次。 若用1亿次/秒的计算机计算需要约508天。 逆序解法： 讨论： 1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路径问题。 逆序标号法： 顺序标号法： §9.2　基本概念、基本方程与最优化原理 一、基本概念： 1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。 例题：按照空间划分的A-B ；B-C ；C-D ；D-E 2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。 1阶段 A 2阶段Bi ,i=1,2,3,4 所以S2={B1，B2，B3，B4} 3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。 X2（B1）=C1 or C2 or C3 决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。 4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。 5、状态转移方程 sk+1=Tk(sk, xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。 6、阶段指标函数rk(sk, xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。 二、基本方程： 最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Rk,n的最优值，即 三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。 §9.3 动态规划的应用 资源分配问题 例2. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？ 分给三个工厂？--看成三阶段问题！求利润最大化！ 将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。 设sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、3）。xk=分配给第k个厂的设备台数。 已知s1=5, 作业： P225 （1、4） THE END * * B A C B D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 8 3 8 6 7 5 6 1 10 6 3 7 5 1 4 B A C B D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 8 3 8 6 7 5 6 1 10 6 3 7 5 1 4 第4阶段： D1?E，1条路，10， D2?E，1条路， 6， 不一定谁入选最终的最优 C1 C2 C3 D1 D2 E 8300 7500 1600 10 6 E 6 6 D2 E 10 10 D1 E 本阶段最优终点(最优决策) 到 E 的最短距离 本阶段各终点(决策) 本阶段始点(状态) 阶段4 确定每个Dk到达终点E的最短路的长度：10，6 该最短路线的下一步：E，E 第3阶段： C1?D1、D2，2 条路，8，6 C2?D1、D2，2 条路，7，5 C3?D1、D2，2 条路，1，6 6 + 6 = 12 5 + 6 = 11 6 + 6 = 12 D2 D2 11 7 + 10 =17 C2 D1 11 1 + 10 =11 C3 D2 12 8 + 10 = 18 C1 D1 最优决策 到 E 的最短距离 决策 状态 阶段3 确定每