动态规划-概念原理讲述.pptVIP

动态规划GXB制作 动态规划（Dynamic Programming) 2015/12/20 动态规划课件制作 多阶段的决策问题 最优化原理与动态规划的数学模型 离散确定性动态规划模型的求解 离散随机性动态规划模型的求解 一般数学规划模型的动态规划的解法 动态规划简介 动态规划——解决多阶段决策过程最优化的一种数学方法。 多阶段决策过程——可分成若干相互联系的阶段,在每一阶段分别对应一组可选决策,当每个阶段的决策选定之后,过程也随之确定. 动态规划GXB制作 应用 最短路问题 资源分配问题 生产调度问题 库存问题 排序问题 设备更新问题 生产过程最优控制问题 动态规划GXB制作 §1 多阶段决策问题举例 A D2 D1 B3 B2 B1 C3 C1 C2 E 2 3 8 7 7 3 5 6 6 8 7 4 6 3 5 3 2 4 3 4 第1阶段 第2阶段 第4阶段 第3阶段 1、最短路线问题:运输网络如下图,求从A到E的最短路. 动态规划GXB制作 第5阶段 2、资源分配问题 第一年: x1 s1-x1 第三年: x3 s3-x3 第二年: x2 s2-x2 连续三年内每年如何分配机 器数,使三年总收益最大? 按年分阶段,三年分为3个阶段逐次决策 设有某种机器设备,用于完成两类工作A和B.已知k年初完好机器的数量为sk,若以数量xk用于A,余下的(sk-xk)用于工作B,则该年的预期收入为g(xk)+h(sk-xk).这里和是已知函数,且g(0)=h(0)=0.又机器设备在使用中会有损坏,设机器用于工作A时,一年后能继续使用的完好机器数占年初投入量的a;若用于B项工作时,一年后能继续使用的完好机器数占年初投入量的b(a,b均小于1),即下一年出能继续用于完成这两项工作的机器数为sk+1=axk+b(sk-xk). §2 最优化原理与动态规划的数学模型 A C B A到C的最短路 B到C的最短路 逆 序 算 法 动态规划方法解题的基本思路：将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题,从而简化计算过程. 例1中这种转化的实现是从终点E出发一步步进行反推. 逆序算法 用逆序算法求 例1的最短路 A D2 D1 B3 B2 B1 C3 C1 C2 E 2 3 6 5 7 3 2 4 5 5 1 4 6 3 3 3 3 4 5 动态规划GXB制作 1 逆序算法 用d(A,B)表示A到B的距离, f(A)表示某阶段初从A出发到终点的最短距离 A D2 D1 B3 B2 B1 C3 C1 C2 E 2 3 6 5 7 3 2 4 5 5 1 4 6 3 3 3 3 4 5 1 f(D1)=3 f(D2)=4 f(C1)=4 f(C3)=6 f(C2)=7 f(B1)=11 f(B3)=8 f(B2)=7 f(A)=11 边界条件 动态规划方法基本思想总结 将多阶段决策过程划分为阶段，恰当选取状态变量、决策变量及定义最优指标函数，从而把问题化为一族同类型的子问题，逐个求解。 将前面的解传递并纳入下一个阶段一并考虑,即做到求解的各阶段间具有递推性,逐段递推寻优. 2015/12/20 动态规划GXB制作 动态规划的基本概念和基本原理 动态规划的基本概念 阶段 :做出决策的步数 状态、状态变量 、状态空间 决策xk(sk) 、允许决策集合Dk(sk) 策略 状态转移率律 指标函数 无后效性即 未来与过去无关 指标函数 ——阶段的指标函数：对应某一阶段状态和从该 状态出发的一个阶段的决策的某种效益度量 ——过程的指标函数：指从状态sk出发至过程最终, 当采取某种子策略时,按预定标准得到效益值. 对应于从状态 出发的最优子策略的效益值. 动态规划GXB制作 最优化原理 美国的利.贝尔曼(R.Bellman)提出求解动态规划的最优化原理如下：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略. 根据这个原理得到的计算动态规划问题的基本方程—逆序解法； 逆向过程的逆序解法—顺序解法 顺序解法与逆序解法的比较 1 n k 状态 决策 效益 1 n k 状态 决策 效益 顺序解法与逆序解法的比较 状态转移方程： 指标函数： 2015/12/20 动态规划GXB制作 顺序解法与逆序解法的比较 顺序解法基本方程： 当各阶段指标函数为求和关系时， 当各阶