资源描述：
《运筹学-动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Yunchouxue第七章动态规划1以最短路问题为例，来说明动态规划的概念B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621343ABCDEF2一、动态规划基本概念：1、阶段:将所要研究的问题,按时间或空间特征分成若干个互相联系的阶段.简称“阶段”。阶段就是作出决策的若干轮次。描述阶段的变量叫阶段变量，常用k表示阶段变量.上例中k＝1，2，3，4，5。32、状态及性质各阶段开始时的客观条件叫做状态.描述各阶段状态的变量叫做状态变量,常用sk表示第ｋ阶段的状态变量,sk的取值集合称为状态集合,用Sk表
2、示。阶段的出发位置，即阶段的起点。上例中，第二阶段有两个状态，即Sk={B1,B2}动态规划中状态具有以下性质:某阶段状态一旦确定,以后过程的状态变化不受这个状态以前的影响,也就是说某状态以后的过程和以前无关,只与当前状态有关,我们称这种特性为“无后效性.”(即马尔科夫性。）P19443、决策和策略指从一个阶段某状态演变到下一阶段某状态的选择（决定）称为决策。表示决策的变量叫做决策变量,常用uk(sk)表示.第k阶段当状态为sk时的决策变量.在实际问题中决策变量的取值往往限制在一定的范围内,我们称此范围为允许决策集,常用Dk(sk)表示第
3、k阶段从状态sk出发的允许决策集,因此有uk(sk)∈Dk(sk).在例1中D2(B1)={C1,C2,C3}.5策略在例1中D2(B1)={C1,C2,C3}.表示什么？表示从第二阶段的状态B1出发，可选择下一阶段的{C1,C2,C3}。即允许决策集是D2(B1).如果我们决策选择了C3,则u2(B1)=C3.全过程中各个阶段的决策组成的有序总体称为策略。上例中每一条路线都被称为一个策略。使整个问题达到最优效果的策略就是最优策略.即上例中，路最短的策略就是最优策略。6状态转移方程动态规划中本阶段的状态是上一阶段的决策结果.如果给定了第k
4、阶段的状态sk,本阶段的决策就为uk(sk),则第k+1段的状态uk+1也就完全确定了,它们的关系可表示为:sk+1=Tk(sk,uk).由于它表示了由k到k＋1段的状态转移规律,所以称为状态转移方程.即前一阶段的终点（决策）是后一阶段的起点（状态）。例1的转移方程为:sk+1=Tk(sk,uk)=uk(sk).7指标函数用于衡量所选定策略优劣的数量指标称为指标函数.一个n段决策过程,从1到n叫作问题的全过程,对于任意一个给定的k,从第k到n段的过程称为全过程的一个后部子过程.指标函数是定义在全过程和后部子过程上确定的数量函数。常用Vk,
5、n表示，即Vk,n＝Vk,n(sk,uk,sk+1,…sn+1),k=1,2,…n指标函数的最优值称为最优指标函数，记为fk(sk),它表示从第k阶段状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即fk(sk)=optVk,n(sk,pk,n),fk(sk)可能是最大值，也可能是最小值，依题意而定。当k=1时F1(s1)就是从初始状态到全过程的整体最优函数.8指标函数的常见形式：（1）过程和它的任一子过程的指标是它所包含的各阶段的指标的和。（2）过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。指标函数应
6、具有可分离性，并满足递推关系。vj(sj,uj)表示第j阶段的指标，则1，2式分别写为：Vk,n(sk,uk,sk+1,…sn+1)＝vk(sk,uk)+Vk+1,n(sk+1,uk+1,sk+2,…sn+1)Vk,n(sk,uk,sk+1,…sn+1)＝vk(sk,uk)Vk+1,n(sk+1,uk+1,sk+2,…sn+1)Vk,n(sk,uk,sk+1,…sn+1)＝Vk,n(sk,uk,sk+1,…sn+1)＝121`2`9回到例1在例1中指标函数是距离.如第2阶段,状态为B1时,V2,5(B1)表示从B1到F的距离,而f2(B1
7、)则表示从B1到F的最短距离.该问题总目标是求f1(A),即从A到终点F的最短距离.B1B2AC1C2C3C4D1D2D3E1E2F45235877584534843562134310⑴阶段从网络图中可看到问题可分为k=5段.⑵状态由A-F分为5段,存在6种状态允许集:S1-S6S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3},S5={E1,E2},S6={F}B1B2AC1C2C3C4D1D2D3E1E2F45235877584534843562134311⑶例1中的决策允许集D1(A)=
8、{B1,B2}D2(B1)={C1,C2,C3}D2(B2)={C2,C3,C4}D3(C1)={D1,D2},…D3(C4)=?D4(D1)={E1,E2},D4(D2)={E1,E2}D5
