运筹学大学课件10-1动态规划基本概念和基本原理1文档.pptx

动态规划（Dynamic Programming)n n 多阶段决策过程的最优化（简介）n n 动态规划的基本概念和基本原理 n n 动态规划模型的解题步骤动态规划简介n n动态规划动态规划解决多阶段决策过程最优化的一种解决多阶段决策过程最优化的一种数学方法。数学方法。n n“动态 动态”随着 随着“时间 时间”过程的发展而决定各时段的 过程的发展而决定各时段的决策，产生一个决策序列。决策，产生一个决策序列。n n 1951 1951 年，年，R.Bellman R.Bellman 动态规划提出：动态规划提出：“最优化原理 最优化原理”-”-把多阶段过程转化为一系列相互联系的单阶 把多阶段过程转化为一系列相互联系的单阶段问题，逐个求解。段问题，逐个求解。n n动态规划模型分类动态规划模型分类1 1、离散确定型；、离散确定型；2 2、离散随机型；、离散随机型；3 3、连续确定型；、连续确定型；4 4、离散随机型；、离散随机型；n n 应用n n最短路问题最短路问题n n资源分配问题资源分配问题n n生产调度问题生产调度问题n n库存问题库存问题n n排序问题排序问题n n设备更新问题设备更新问题n n生产过程最优控制问题生产过程最优控制问题多阶段决策过程最优化n n 多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。多阶段决策过程最优化问题举例AD2D1B3B2B1C3C1C2E23877356687463532434 第 1阶段 第 2阶段 第 4阶段 第 3阶段 第 5阶段1、最短路问题：运输网络如下图，求从A 到E 的最短路。2、生产与存储问题 某厂每月供应市场一定数量的产品，如某厂每月供应市场一定数量的产品，如何安排每月的产量？何安排每月的产量？增加产量成本降低库存费增加一年总费用最低？按月分阶段，全年分为12个阶段逐次决策动态规划的基本概念和基本原理n n 动态规划的基本概念n n阶段阶段n n状态、状态变量状态、状态变量、状态空间、状态空间n n决策决策、允许决策集合、允许决策集合 策略策略n n状态转移（方程）状态转移（方程）n n指标函数指标函数无后效性即未来与过去无关动态规划的基本概念和基本原理阶段（Stage）将所给问题的过程，按时间或空间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解，常用k 表示阶段变量。动态规划的基本概念和基本原理状态（State）各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k 阶段的状态变量，状态变量的取值集合称为状态集合，用Sk表示。动态规划的基本概念和基本原理动态规划中的状态具有如下性质：动态规划中的状态具有如下性质：某阶段的状态，只对该阶段该状态以后过程的演变某阶段的状态，只对该阶段该状态以后过程的演变起作用，而不受以前各阶段状态的影响。即：过程起作用，而不受以前各阶段状态的影响。即：过程的过去历史只能通过当前状态去影响它未来的发展，的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。性，就不能作为状态变量来构造动态规划模型。动态规划中的状态变量满足如下动态规划中的状态变量满足如下33个特性：个特性：（11）代表性。能够反映过程的演变特性。）代表性。能够反映过程的演变特性。（22）可知性。能够通过某种方式，直接或间接地确定）可知性。能够通过某种方式，直接或间接地确定（33）无后效性。）无后效性。动态规划的基本概念和基本原理决策和策略（Decision and Policy）当各段的状态确定以后，就可以做出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量用uk(sk)表示，允许决策集合用Dk(Sk)表示。动态规划的基本概念和基本原理 各个阶段决策确定后，整个问题的决策序列就构成一个策略，用p1,n(u1,u2,un)表示。对每个实际问题，可供选择的策略有一定的范围，称为允许策略集合，用P 表示。使整个问题达到最优效果的策略就是最优策略。动态规划的基本概念和基本原理状态转移方程 动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第k 段的状态sk，本阶段决策为uk(sk)，则第k+1 段的状态sk+1由公式：sk+1=Tk（sk，uk）确定，称为状态转移方程。动态规划的基本概念和基本原理指标函数 用于衡量所选定策略优劣的数量指标称为指标函数。最优指标函数记为fk(sk)。指标函数表示初始状态为 且采取策略 时，原（全）过程的指标函数表示第k阶段状态为 且采取策略 时，后部子过程的指标函数表示第k阶段状态为 且采取最优策略 到终止时的最佳效益值。动态规划的基本思想与基本原理n n 最短路的重要性质：ACBA 到C 的最短路B 到C 的最短路逆序递推法逆序递推法n n 用逆序递推法求 例1 的最短路AD2D1B3B2B1C3C1C2E23877356687463532434 用逆序递推方法求解，逐步求出各段各点到用逆序递推方法求解，逐步求出各段各点到EE的的最短路线，最后求得最短路线，最后求得AA点到点到EE点的最短路线。点的最短路线。当当k=4k=4时，时，ff44(D(D11)表示在第表示在第44段由段由DD11到到EE的最短距的最短距离，故有离，故有ff44(D(D11)=4)=4。同理，。同理，ff44(D(D22)=3)=3。当当k=3k=3时，若从时，若从CC11出发，则有两个选择，一个是出发，则有两个选择，一个是至至DD11一个是至一个是至DD22，则：，则：C1到最终点最短距离为8，最短路线：C1D1E相应决策为 u3*(C1)=D1 C2到最终点最短距离为7，最短路线：C2D1E相应决策为 u3*(C2)=D1 C3到最终点最短距离为6，最短路线：C3D1（D2）E相应决策为 u3*(C3)=D1（D2）依此类推，可得：依此类推，可得：k=2 k=2时，有时，有 ff22(B(B11)=14 u)=14 u22*(B*(B11)=C)=C22(C(C33)f f22(B(B22)=11 u)=11 u22*(B*(B22)=C)=C11 f f22(B(B33)=13 u)=13 u22*(B*(B33)=C)=C33 k=1 k=1时，只有一种状态时，只有一种状态AA，则，则即从A 到E 的最短距离15，本段决策为 u1*(A)=B2。再按计算顺序反推可得最优决策序列uk,即u1*(A)=B2，u2*(B2)=C1,u3*(C1)=D1,u4*(D1)=E所以最优路线：A B2 C1D1EAD2D1B3B2B1C3C1C2E23877356687463532434动态规划的函数基本方程动态规划的函数基本方程边界条件 这种递推关系称为动态规划的函数基本方程。其一般这种递推关系称为动态规划的函数基本方程。其一般形式为：形式为：动态规划方法基本思想总结n n 将多阶段决策过程划分为阶段，恰当选取状态变量、决策变量及定义最优指标函数，从而把问题化为一族同类型的子问题，逐个求解。n n 从边界条件开始，按逆（或顺）过程行进方向，逐段递推寻优。贝尔曼(Ballman)最优化原理 作为整个过程的最优策略具有这样的性质，即作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。成的状态而言，余下的诸决策必须构成最优策略。这就是说，不管引导到这个现时状态的头一个状这就是说，不管引导到这个现时状态的头一个状态和决策是什么，所有的未来决策应是最优的。态和决策是什么，所有的未来决策应是最优的。动态规划的模型的建立n n动态规划模型的构成动态规划模型的构成n n正确选择阶段变量正确选择阶段变量n n正确选择状态变量，状态变量需满足条件：正确选择状态变量，状态变量需满足条件：n n（1 1）代表性；）代表性；n n（2 2）可知性；）可知性；n n（3 3）无后效性。）无后效性。n n正确选择决策变量正确选择决策变量n n列出状态转移方程列出状态转移方程n n列出指标函数，它具有按阶段可加性列出指标函数，它具有按阶段可加性n n列出函数基本方程。列出函数基本方程。