《动态规划MATLab》PPT课件

《《动态规划MATLab》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、案例：最短路问题假设要从A城市到E城市铺设一条输油管道，中间需要经过三个地区，每个地区都有若干个转运站，构成了许多不同的输油路线，转运站间的数字表示站间的运输路径的长度，由于地理条件等原因，某些地区之间不能直接铺设相通的管道。现需求出一条使总路径最短的管道路线。动态规划AB1B2B3C1C2C3D1D2E1动态规划的基本概念一、阶段对于一个多阶段决策过程，可以根据问题的特点，把整个过程划分为几个相互联系的阶段，以便可以按一定的顺序去求解。这个根据时间和空间的自然特征来划分的次序称为阶段，描述阶段的变量称为阶段变量，一般用k

2、表示。如案例中的多阶段决策问题可划分为四个阶记为段，二、状态状态：表示系统每个阶段开始时所处的自然状况或客观条件。如案例中，状态就是某阶段的出发位置，它既是该阶段某支路的起点，又是前一阶段某支路的终点。第一个阶段有一个状态即为点A，第二个阶段有三个状态状态变量：描述状态的变量。常用表示第k阶段的状态变量。如案例中第三个阶段有3个状态，则状态可取三个值，即这三个点构成的集合称为第三个阶段的允许状态集，记为有时为了方便起见，也将阶段的状态编上号码即有一般地，第k个阶段的允许状态集记为当某个阶段的状态给定后，则这个阶段以后过程的

3、发展不受这个阶段及以前各阶段状态的影响。也是说，当前的状态只是以往历史的一个总结，过程的过去历史只能通过当前的状态去影响它未来的发展，这种性质称为无后效性。三、决策决策：各阶段状态确定后，确定下一个阶段的状态的各种选择。决策变量：描述决策的变量。常用表示第k阶段状态处于时的决策变量，它是状态变量的函数。允许决策集：决策变量的取值构成的集合，表明决策的约束条件，常用表示第k阶段系统处于状态时的允许决策集合，即有如案例中，第二阶段决策时，若从状态出发，则可做出三种不同决策，其允许决策集合为若选定的下一个状态是则四、策略策略：从

4、初始阶段到最终阶段，每个阶段均有一决策，各阶段决策形成一个决策序列，称为系统的一个策略。此序列最优策略：使系统达到最优效果的策略。全过程策略：对于具有几个阶段的多阶段决策问题，从第一个阶段的某一状态出发到终止阶段的状态做出的决策序列而形成的策略。记为即k后部子过程：从第k阶段到终止阶段状态的过程。简称为k子过程。后部子过程策略：k后部子过程相应的决策序列。简称为k子策略。记为即允许策略集：在实际问题中，可供选择的策略所在的范围，常记为P。五、状态转移方程状态转移方程：描述系统由一个阶段到下一个阶段的状态转移规律。例如，设系

5、统第k阶段的状态变量的值给定，该阶段的决策变量确定，则第k+1阶段的状态变量的值也就确定了，即的值随和变化而变化，这种对应关系我们记为的值的以上状态转移规律，即为状态转移方程。称为状态转移函数。六、指标函数与最优指标函数k阶段指标函数：第k阶段状态为决策变量取某个值后得到的一个反映这个局部策略效应的数量指标。也称为k阶段的效应函数。全过程的指标函数：常用表示。采用全过程的策略的数量指标。其指标函数值记为用表示第k阶段状态为采用策略时，后部子过程的指标函数值。最优指标函数：指标函数的最优值。记为表示从第k阶段的状态开始到第n

6、阶段的终止过程采取最优策略所得到的指标函数值，即在不同问题中，指标函数的含义是不同的，它可能指距离、利润、成本、产品的产量或资源消耗等。如案例中，指标函数是距离，如第二阶段状态为时，表示由出发采用决策到下一个阶段点的距离，表示从出发到F的总距离，而表示从B1出发到F的最短距离。该问题的总目标是求即从A到终点F的最短距离。2动态规划的基本原理下面我们结合案例的最短路问题来介绍动态规划的基本思想与基本原理。穷举法的计算量将非常大，显然不适合。考虑最短路线的一个重要特征：若从起点A经过B点和C点而达到终点D是一条最短路线，则由B

7、点出发经过C点到达终点D点的这条子路线，对于从B点出发达到终点D点的所有可能选择的不同路线来说，必定也是最短路线。在本例中，若找到了是由A到D的最短路线，则也应是从B1出发到D点的所有可能选择的不同路线中的最短路线。如果不是这样，则从B1点到D点有另一条距离更短的路线存在，把它和原来的最短路线有A点到B1点的那部分连接起来，就会得到一条从A点到D点的新路线，且比原来的那条最短路线的距离还要短些，这就与假设矛盾。基于最短路线的这一特性，我们考虑寻找最短路线的方法，就是从最后一段开始，用由后向前逆向递推的方法，逐步求出各点到终

8、点的最短路线，最后求得由起点到终点的最短路线。以本案例为例，我们按上述思想寻找从A到E的最短路线。AB1B2B3C1C2C3D1D2E第一步，从k=4出发，状态变量可取状态它们到E点的路长分别为第二步，k=3，状态变量可取三个值这是经过一个中途点到达终点E的两级决策变量。从到E有两条路线，需加以比较取其