最优化原理与动态规划的数学模型.ppt

最优化原理与动态规划的数学模型现在学习的是第1页，共36页BACDEFG本例中分为本例中分为k=1,2,3,4,5,6，共六个阶段。，共六个阶段。(1)阶段阶段将所给问题的过程，按时间或空间特征分解成若干相互联将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每个阶段的解，常用字母系的阶段，以便按次序去求每个阶段的解，常用字母k表表示阶段变量示阶段变量.现在学习的是第2页，共36页(2)状态状态各阶段开始时的客观条件各阶段开始时的客观条件叫做叫做状态状态。描述各阶段状态的变描述各阶段状态的变量量称为称为状态变量状态变量，常用，常用sk表示第表示第k阶段的状态变量，阶段的状态变量，状态状态变量变量sk的取值集合的取值集合称为称为状态集合状态集合，用，用Sk表示。表示。无后效性无后效性：当某阶段状态给定以后，在这阶段以后过程的：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前的各阶段的影响。即发展不受这段以前的各阶段的影响。即当前的阶段是过当前的阶段是过去历史的一个完整总结，过程的过去历史只能通过当前去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展状态去影响它未来的发展。现在学习的是第3页，共36页状态变量可以是一个数或一个向量。在本例中状态变量可以是一个数或一个向量。在本例中s2可取可取B1,B2,或将或将Bi定义为定义为i(i=1,2)，则，则s2=1,2，则，则 S2=1,2S1=AS2=B1,B2S3=C1,C2,C3,C4S4=D1,D2,D3S5=E1,E2,E3S6=F1,F2现在学习的是第4页，共36页(3)决策和策略决策和策略 当一个阶段的状态确定后，可以作出各种选择从而演变到当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种下一阶段的某个状态，这种选择手段选择手段称为称为决策决策，在最优控，在最优控制问题中也称为制问题中也称为控制控制。描述决策的变量描述决策的变量称称决策变量决策变量，变量允许取值的范围变量允许取值的范围称称允允许决策集合许决策集合。用。用uk(sk)表示第表示第 k阶段处于状态阶段处于状态sk时的决策变量，时的决策变量，它是它是 sk的函数，用的函数，用 Dk(sk)表示表示 sk的允许决策集合。的允许决策集合。决策变量简称决策。决策变量简称决策。现在学习的是第5页，共36页由第由第k个状态个状态sk开始到终止状态的后部子过程的策略记作开始到终止状态的后部子过程的策略记作类似地，由第类似地，由第k到第到第j阶段的子过程的策略记作阶段的子过程的策略记作 可供选择的策略有一定的范围，称为可供选择的策略有一定的范围，称为允许策略集合允许策略集合，用用 表示表示 决策组成的序列决策组成的序列称为称为策略策略。由初始状态。由初始状态s1开始的全过程的开始的全过程的策略记作策略记作 现在学习的是第6页，共36页 在本例中，从第二阶段的状态在本例中，从第二阶段的状态B1出发，可选择下一段的出发，可选择下一段的C1,C2,C3，即允许决策集合为。，即允许决策集合为。D2(B1)=C1,C2,C3如果决定选择如果决定选择C3则可表示为：则可表示为：u2(B1)=C3表示表示 一个策略一个策略现在学习的是第7页，共36页(4)状态转移方程状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程表示这种演变规律，段的状态便完全确定。用状态转移方程表示这种演变规律，写作写作本例中状态转移方程：本例中状态转移方程：(5)指标函数指标函数用于衡量所选定策略优劣的数量指标称为用于衡量所选定策略优劣的数量指标称为指标函数指标函数.现在学习的是第8页，共36页阶段指标函数阶段指标函数：指第指第k阶段，从状态阶段，从状态sk出发，采取决策出发，采取决策uk时的效益时的效益，用，用d(sk,uk)表示。表示。过程指标函数过程指标函数：是定义在全过程和后部子过程上确定的是定义在全过程和后部子过程上确定的数量函数。数量函数。一个一个n段决策过程段决策过程,从从1到到n叫作叫作问题的全过程问题的全过程；对于任意一个给定的对于任意一个给定的k,从第从第k到到n段的过程称为段的过程称为全过程的全过程的一个后部子过程一个后部子过程.V1,n(s1,p1,n)表示在第表示在第1阶段，状态为阶段，状态为s1，采用策略，采用策略p1,n时，时，原过程的指标函数值；原过程的指标函数值；Vk,n(sk,pk,n)表示在第表示在第k阶段，状态为阶段，状态为sk，采用策略，采用策略pk,n时，时，后部子过程的指标函数值。后部子过程的指标函数值。现在学习的是第9页，共36页fk(sk)与与Vk,n(sk,pk,n)间的关系为：间的关系为：当当k=1时时f1(s1)就是从初始状态到全过程的整体最优函数就是从初始状态到全过程的整体最优函数.其中其中opt可根据具体情况取可根据具体情况取max或或min 指标函数的最优值指标函数的最优值称为称为最优指标函数最优指标函数，记为，记为fk(sk)，表示从，表示从第第k阶段状态阶段状态sk采用最优策略采用最优策略p*k,n到过程中止时的最佳效益。到过程中止时的最佳效益。现在学习的是第10页，共36页本例中，指标函数是距离，如第二阶段，本例中，指标函数是距离，如第二阶段，阶段指标阶段指标：状态为：状态为B1时时d(B1,C2)表示由表示由B1出发采用决策到出发采用决策到下一段下一段C2点的两点距离；点的两点距离；过程指标过程指标：V2,6(B1)表示从表示从B1到到G 的距离，的距离，f2(B1)则表示从则表示从B1到到G的最短距离。的最短距离。现在学习的是第11页，共36页三、基本思想与最优化原理三、基本思想与最优化原理 从例从例4的求解过程说明动态规划的基本思想：的求解过程说明动态规划的基本思想：例例4 最短路问题最短路问题如图所示，给定一个线路网络图，要从如图所示，给定一个线路网络图，要从A地向地向F地铺设一地铺设一条输油管道，各点间条输油管道，各点间 连线上的数字表示距离，问应选择连线上的数字表示距离，问应选择什么路线，可使总距离最短？什么路线，可使总距离最短？A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 85 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1现在学习的是第12页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 85 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1第一步：从第一步：从k=5开始，状态变量开始，状态变量s5可取两种状态可取两种状态E1,E2，它们到它们到F点的路长分别为点的路长分别为4,3。即。即现在学习的是第13页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 85 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1第二步：第二步：k=4时，状态变量时，状态变量s4可取三个值可取三个值D1,D2,D3，这是经过中，这是经过中途点到达终点途点到达终点F的两级决策问题，从的两级决策问题，从D1到到F有两条路线，比较取有两条路线，比较取最短者最短者此时从此时从D1到到F的最短路径：的最短路径：相应决策：相应决策：现在学习的是第14页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 84 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1同理，从同理，从D2到到F有两条路线，比较取最短者有两条路线，比较取最短者此时从此时从D2到到F的最短路径：的最短路径：相应决策：相应决策：现在学习的是第15页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 84 44 46 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1同理，从同理，从D3到到F有两条路线，比较取最短者有两条路线，比较取最短者此时从此时从D3到到F的最短路径：的最短路径：相应决策：相应决策：现在学习的是第16页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 84 44 46 65 53 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1同理，同理，k=3时有：时有：此时最短路径：此时最短路径：相应决策：相应决策：现在学习的是第17页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F8 84 44 46 65 53 33 33 33 32 24 42 2C4C47 77 75 55 51 1同理，同理，k=2时有：时有：此时最短路径：此时最短路径：相应决策：相应决策：现在学习的是第18页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 44 45 53 33 33 33 34 42 2C4C47 75 55 51 1k=1时，只有一个状态点时，只有一个状态点A，则：，则：此时最短路径：此时最短路径：相应决策：相应决策：现在学习的是第19页，共36页在计算过程中可以看到，在求解的个阶段，都利用了第在计算过程中可以看到，在求解的个阶段，都利用了第k段和第段和第k+1段的如下关系：段的如下关系：这种这种递推关系递推关系称为称为动态规划的基本方程动态规划的基本方程，第二个方程称为，第二个方程称为边界条件边界条件。基本方程基本方程和和边界条件边界条件统称为动态规划的数学模型统称为动态规划的数学模型现在学习的是第20页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 44 43 33 33 33 34 42 2C4C47 75 55 51 1在图上直接计算的方法在图上直接计算的方法叫叫标号法标号法。动态规划较之于穷举法的优点：动态规划较之于穷举法的优点：一、计算量小一、计算量小二、计算结果不仅得到最短路线，而且得到了中间段任一二、计算结果不仅得到最短路线，而且得到了中间段任一点到点到F的最短路线的最短路线现在学习的是第21页，共36页动态规划的基本思想：动态规划的基本思想：（1）将多阶段决策过程划分阶段，恰当选取状态变量、决策）将多阶段决策过程划分阶段，恰当选取状态变量、决策变量以及定义最优指标函数，从而把问题化成一族同类型的变量以及定义最优指标函数，从而把问题化成一族同类型的子问题。子问题。（2）求解时从边界条件开始，逆（顺）序逐段递推寻优。在）求解时从边界条件开始，逆（顺）序逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。优结果，最后一个子问题的最优解，就是整个问题的最优解。（3）动态规划方法是既把当前一段与未来各段分开，）动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般不同的最优选择一般不同.现在学习的是第22页，共36页最优化原理：最优化原理：作为整个过程的最优策略具有这样的性质：作为整个过程的最优策略具有这样的性质：“无论过去的状态和决策如何，相对于前面的决策无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优所形成的状态而言，余下的决策序列必然构成最优子策略。子策略。”也就是说，一个最优策略的子策略也是最优的。也就是说，一个最优策略的子策略也是最优的。动态规划方法基于贝尔曼等人提出的最优化原理：动态规划方法基于贝尔曼等人提出的最优化原理：现在学习的是第23页，共36页练习：求从练习：求从A到到E的最短路径的最短路径路线为路线为AB2C1 D1 E，最短路径为，最短路径为19AB2B1B3C1C3D1D2EC25214126101043121113965810521现在学习的是第24页，共36页四、逆序解法与顺序解法四、逆序解法与顺序解法 动态规划求解的两种基本方法：动态规划求解的两种基本方法：逆序解法（后向动态规划方法）逆序解法（后向动态规划方法）顺序解法（向前动态规划方法）顺序解法（向前动态规划方法）逆序解法逆序解法：从最后一段开始计算逐段前推，求得全过：从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法。程的最优策略，称为逆序解法。顺序解法顺序解法：从第一阶段开始逐段向后递推，计算后一阶：从第一阶段开始逐段向后递推，计算后一阶段要用到前一阶段的寻优结果，最后一段计算的结果就段要用到前一阶段的寻优结果，最后一段计算的结果就是全过程的最优结果。是全过程的最优结果。再次以例再次以例4为例说明顺序解法：为例说明顺序解法：现在学习的是第25页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 85 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1k=0时，时，f0(s1)=f0(A)=0，为边界条件，为边界条件k=1时，按时，按f1(s2)的定义，有的定义，有现在学习的是第26页，共36页A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 85 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1k=2时，状态变量时，状态变量s3可取四个值可取四个值C1,C2,C3,C4，从从C1到到B只有一条只有一条路线，故路线，故此时从此时从C1到到A的最短路径：的最短路径：现在学习的是第27页，共36页同理，从同理，从C2到到A有两条路线，比较取最短者有两条路线，比较取最短者此时从此时从C2到到A的最短路径：的最短路径：A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 48 85 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1现在学习的是第28页，共36页同理，从同理，从C3到到A有两条路线，比较取最短者有两条路线，比较取最短者此时从此时从C3到到A的最短路径：的最短路径：A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 45 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 77 78 85 54 45 51 1现在学习的是第29页，共36页同理，从同理，从C4到到A只有一条路线，只有一条路线，此时从此时从C4到到A的最短路径：的最短路径：A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 45 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 78 85 54 45 51 1现在学习的是第30页，共36页同理，同理，k=3时有：时有：此时最短路径：此时最短路径：相应决策：相应决策：A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 45 54 44 46 66 65 53 33 33 33 33 32 24 48 82 2C4C47 78 85 54 45 51 1现在学习的是第31页，共36页同理，同理，k=4时有：时有：此时最短路径：此时最短路径：相应决策：相应决策：A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F5 54 44 46 66 65 53 33 33 33 32 24 42 2C4C47 75 54 45 51 1现在学习的是第32页，共36页k=5时，只有一个状态点时，只有一个状态点F，则：，则：此时最短路径：此时最短路径：A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F4 44 46 65 53 33 33 32 24 42 2C4C47 75 54 45 5现在学习的是第33页，共36页类似于逆序解法，写出顺序解法的递推方程：类似于逆序解法，写出顺序解法的递推方程：这里这里一般，当初始状态给定时可用逆序解法，当中止状一般，当初始状态给定时可用逆序解法，当中止状态给定时可用顺序解法。若问题给定了一个初始状态给定时可用顺序解法。若问题给定了一个初始状态与一个中止状态，则两种方法均可使用。二者并态与一个中止状态，则两种方法均可使用。二者并无本质区别。无本质区别。现在学习的是第34页，共36页逆序解法与顺序解法的区别：逆序解法与顺序解法的区别：1.状态转移方式不同：状态转移方式不同：1状态s1决策u1效益v1(s1,u1)s2k状态sk决策uk效益vk(sk,uk)sk+1n状态sn决策un效益vn(sn,un)sn+1.状态s11决策u1效益v1(s2,u1)s2k状态sk决策uk效益vk(sk+1,uk)sk+1n状态sn决策un效益vn(sn+1,un)sn+1.逆序解法逆序解法:顺序解法顺序解法:现在学习的是第35页，共36页2.指标函数的定义不同：指标函数的定义不同：逆序解法中，最优指标函数逆序解法中，最优指标函数fk(sk)表示第表示第k阶段从状态阶段从状态sk出发，出发，到终点后部子过程最优效益值，到终点后部子过程最优效益值，f1(s1)是整体最优函数值是整体最优函数值顺序解法中，最优指标函数顺序解法中，最优指标函数fk(sk+1)表示第表示第k阶段从状态阶段从状态sk+1出发，到起点前部子过程最优效益值，出发，到起点前部子过程最优效益值，fn(sn+1)是整体最优是整体最优函数值函数值现在学习的是第36页，共36页