10动态规划.ppt.ppt

动态规划
最优化原理介绍:
设从A到C的最优路线为ABOC,则从最优化原理可以断定:AC的一部分BOC必为从B到C的最优路线。事实上,如果从B到C另有最优路线EOC ,如虚线所示,则ABO’C会比ABOC更优。这与上面假设的A BC为最优路线相矛盾。
动态规划是运筹学的一个重要分枝,它在20世纪50年代提出。动态规划的基础是“最优化原理”,在最优化原理的基础上,推导出动态规划基本方程,从而解决了多阶段最优化决策问题。
最短路径问题
在图中,用圈表示城市,现有A、B1、B2、C1、C2、C3、Dl、J2、E共9个城市。因间的连线表示城市问有道路相连。连线旁的数字表示道路长度。现要求从城市A到E之间寻找出一条最短践线。
术语解释;
(1)阶段:在采用动态规划求解时,首先要把整个过程分为几个阶段c对于上述员短路线问题,可分4个阶段来进行讨论‘,第一阶段:A到B1,B2,第二阶段:B1,B2 到C1,C2,C3,第三阶段:C1,C2,C3到D1,D2,第四阶段:Dl,D2到E。
(2)状态:状态表不某个阶段的起点,也是前一阶段的终点。描述状态的变量称为状态变量。例如,在最短路问题中,第一阶段起点只有1个A,因而,只有1个状态。但第二阶段有2个状态Bl,B2,第三阶段有3个状态C1,C2,C3,第四阶段有2个状态D1,D2,状态的选取应使状态具有无后效性。所谓无后效性(或称为马尔可夫性),就是指状态有这样的性质:在某阶段状态给定后,过程今后的发展仅与当前状态相关,而与过去的历史,即它是怎样到达当前状态的无关。
(3)决策:决策就是作出决定。例如,在第一阶段过程处于状态A,此时,从A到B1,,或由A到B2。,B2为第一阶段的允许决策集合,记为D(A)=B1,B2当做出决定从A到B1后,记为U1(A)=Bl,称为过程第一阶段的决策。反之,若选择由A到B2,则此阶段决策写成Ul(A)=B2。在第二阶段中,(B1)=C1,C2,C3,D(B2)=C1,C2,C3。若选定由d1到c1,则第二阶段决策为U(B1)=c1。由此类推,可以得出各个阶段的决策。
对于最短路线来讲,假如当前处于C1状态,则从C1到E的最短路线仅与当前状态C1有关,而与前两阶段中怎样到达C1无关。
(4)策略:策略是按顺序排序的决策集合。例如,在最短路例子中,P34(C2)={U3(C2),U4(D2)},表示在第三阶段从状态C2作出决策U3(C2)=D2,再在第四阶段从状态D2作出决策U4(D2)=E,从而完成从C2到终止状态E的过程,称为—个子过程策略。
,简称为策略,记为P1,4={U1(A),U2(B1),U3(C3),U4(D1)},从而,决定从A开始,经过B1,C3,D1,最后到达E的一条路线.
(5)状态转移方程:状态转移方程是确定前一阶段状态转变到后一状态的过程。当作出决定后,状态转移方程也随之确定了。例如,当过程处于E的状态时,作出决策U3(C