第六章动态规划.pptx

《第六章动态规划.pptx》由会员分享，可在线阅读，更多相关《第六章动态规划.pptx（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 例1 最短路线问题 如下图，是一线路网络，两点之间连线上的数字表示两点之间的距离（或费用）试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。1状态状态状态状态状态决策决策决策23456状态状态决策决策决策 B2 C3 D2 E3 F2 G B2 C3 D2 E3 F2 G AV6,6=3AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432V1,6=24V5,6=9V4,6=11V3,6=14V2,6=21V1,6=24第1页/共40页 例2 机器负荷分配问题 某种机器可以在高低两种不同负荷下进行生产。在高负荷下进行

2、生产时，产品的年产量g和投入生产的机器数u的关系为 在低负荷下进行生产时，产品的年产量h和投入生产的机器数u的关系为第2页/共40页1状态状态状态状态状态决策决策决策2345状态决策决策 u1 u2 u3 u4 u5 s2 s3 s4 s5 s6 s1设：第3页/共40页2 动态规划的基本概念和基本方程 2.1 动态规划的基本概念 1.阶段 把过程依据一定的时间和空间特征恰当地划分为若干个相互联系的阶段，以便利用动态规划的方法求解。描述阶段的变量称为阶段变量，用k表示。k=1，2，n 2.状态 每个阶段开始所处的自然状况或客观条件，称为状态。状态是不可控的，是客观存在的。描述状态的变量称为状态

3、变量，用sk表示。状态变量可以是一个数或一个向量。状态变量sk的取值范 围 称 为 可 达 状 态 集 合，用 Sk表 示。例 1中，S3=C1,C2,C3,C4。第4页/共40页 状态变量的性质（无后效性）如果某阶段的状态给定后，则该阶段以后的过程的发展不受该阶段以前各阶段状态的影响。即过程的过去历史只能通过当前的状态去影响未来的发展，当前的状态是以往历史的总结，以后发展的依据。这个性质称为无后效性（即马尔科夫性）。无后效性的特征：在每个阶段所作的决策只依据当前的状态，和以往的状态无关。在选取状态变量时，一定要保证状态变量具有无后效性，否则不能利用动态规划的方法求解。第5页/共40页 3.决

4、策 在每个阶段所作的决定或选择称为决策或控制。决策依据与当前状态，又决定下一阶段的状态。描述决策的变量称为决策变量，用uk(sk)表示。他是状态变量sk的函数。决策变量的取值范围称为容许决策集合，用Dk(sk)表示。在例1中 D1(A)=B1,B2 D2(B1)=C1,C2,C3，D2(B2)=C2,C3,C4 D4(D1)=E2,E3 在例2中 D1(s1)=u1(s1)|0u1(s1)s1 D2(s2)=u2(s2)|0u2(s2)s2 Dk(sk)=uk(sk)|0uk(sk)sk第6页/共40页 4.策略 按一定顺序排列的决策序列集合称为策略。由过程的第k阶段开始到终止状态为止的过程，

5、称为问题的后部子过程（或称为k子过程）。由k子过程的每个阶段的决策函数组成的决策函数序列集合uk(sk),uk+1(sk+1),un(sn)称为k子过程策略，简称为子策略，记为pk,n(sk)，即 pk,n(sk)=uk(sk),uk+1(sk+1),un(sn)当k=1时,此决策函数序列称为全过程的一个策略，简称为策略，记为p1,n(s1)。即 p1,n(sk)=u1(s1),u2(s2),un(sn)策略的取值范围称为容许策略集合，用P表示。在P中,使指标函数达到最优的策略称为最优策略。例1中，每一条线路就是一个策略，容许策略集合中有48个策略。A到G的最短线路就是最优策略。第7页/共40

6、页 5.状态转移方程 若给定第k个阶段状态变量sk的值，该阶段的决策变量uk的值一经确定，第k+1个阶段的状态变量sk+1的值也就完全确定了，即sk+1是sk和 uk的函数，记为 sk+1=Tk(sk,uk)该函数描述由第k个阶段到第k+1个阶段的状态转移规律,称为状态转移方程。例1中，状态转移方程为 例2 中，状态转移方程为 第8页/共40页 6.指标函数和最优值函数 用来衡量过程和子过程（策略和子策略）优劣的一种数量指标，称为指标函数。它是定义在全过程和后部子过程上的数量函数，用Vk,n表示。即 指标函数的性质：动态规划中的指标函数应具有可分离性，并满足地推关系，第9页/共40页 常见指标

7、函数的形式 （1）过程和子过程的指标函数可分解为它所包含的阶段的指标的和，即 （2）过程和子过程的指标函数可分解为它所包含的阶段的指标的积，即第10页/共40页指标函数的最优值称为最优值函数，记为它表示最优的k子策略p*k,n(sk)对应的指标函数值。第11页/共40页 2.1 动态规划的基本思想和基本方程 最短路线的特征：如果由起点A经过P和H到达G是一条由A到G的最短路线，则由P到G的最短路线是 P H G即最短路线的子线路是最短路线。根据最短路线的特征，求A到G的最短路线，可以采用由后向前逐步递推的方法，从最后一个阶段开始，求出每个点到G的最短路线，最后出A到G的最短路线。P1 H1 G

8、P2 H2 GA12158318第12页/共40页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432437590第13页/共40页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432437597680第14页/共40页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221333552664324375976813109120第15页/共40页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687

9、6683533842213335526643243759768131091213160第16页/共40页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432437597681310912131618A B1 C2 D1 E2 F2 G最短路线为：最优策略为：P*=0第17页/共40页 该题中，在求解过程中，利用了第k阶段与第k+1阶段之间的递推关系：一般情况，第k阶段与第k+1阶段之间的递推关系式可表示为：该递推关系式称为动态规划的基本方程。边界条件 第18页/共40页 边界条件 即一般情况，第k阶段与第k+1阶段之间的递推关

10、系第19页/共40页 动态规划模型的建立步骤：1.将过程恰当地划分为阶段；2.正确选择状态变量sk，既要描述过程的演变，又要满足无后效性；3.确 定 决 策 变 量 uk及 uk的 容 许 决 策 集 合Dk(sk);4.写出状态转移方程 sk+1=Tk(sk,uk);5.写出指标函数Vk,n(sk,uk,sk+1,sn),应满足：（1）是定义在全过程和后部子过程上数量函数；（2）具有可分离性，并满足递推关系；（3）函数 对于变量 要严格单调；6.写出基本方程。第20页/共40页1状态状态状态状态状态决策决策2n-1n状态决策决策 u1 u2 un-1 un s2 s3 sn-1 sn sn+

11、1 s1 D(s1)D(s2)D(sn-1)D(sn)转移方程 指标函数基本方程第21页/共40页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221333552664324375976813109121316180AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842213335526643216151313151113681095301813标号法第22页/共40页3 动态规划的最优性原理和最优性定理 动态规划的最优性原理 最优策略的子策略必是最优策略。它是最优策略的必要条件，而不是充要条件。AB1B2C

12、1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221333552664324375976813109121316180第23页/共40页动态规划的最优性定理第24页/共40页4 动态规划与静态规划的关系 动态规划、线性规划和非线性规划都是属于数学规划的范畴，本质都是求极值问题，都是利用迭代法逐步求解。线性规划迭代中的每一步是就问题的整体加以改善。动态规划递推中的每一步是问题局部最优解向整体最优解的靠近。对于某些静态规划问题可以引入某些因素，使之转化为动态规划问题。静态规划问题动态规划问题第25页/共40页解：将该静态规划转化为动态规划如下：1状态状态状态状态决

13、策决策决策230 x1s10 x2s2 x3=s3s2=s1-x1 s3=s2-x2 s4=s3-x3=0 s1=c第26页/共40页1状态状态状态状态决策决策决策230 x1s10 x2s2 X3=s3s2=s1-x1 s3=s2-x2 s4=s3-x3=0 s1=c第27页/共40页第28页/共40页第29页/共40页第30页/共40页解：将该静态规划转化为动态规划如下：1状态状态状态状态决策决策决策230 x1c-s10 x2c-s2 x3=c-s3s2=s1+x1 s3=s2+x2 s4=s3+x3=c s1=0第31页/共40页1状态状态状态状态决策决策决策230 x1c-s10 x2c-s2 X3=c-s3s2=s1+x1 s3=s2+x2 s4=s3+x3=c s1=0第32页/共40页第33页/共40页第34页/共40页第35页/共40页解：将该静态规划转化为动态规划如下：1状态状态状态状态决策决策决策230 x1s1/30 x2s2/20 x3s3s2=s1-3x1 s3=s2-2x2 s4=s3-x30 s1=9第36页/共40页1状态状态状态状态决策决策决策230 x1s1/30 x2s2/20 x3s3 s4=s3-x30 s1=9s2=s1-3x1 s3=s2-2x2第37页/共40页第38页/共40页第39页/共40页感谢您的观看！第40页/共40页