(7.2.1)--07_2_1动态规划的基本概念.pdf

《(7.2.1)--07_2_1动态规划的基本概念.pdf》由会员分享，可在线阅读，更多相关《(7.2.1)--07_2_1动态规划的基本概念.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划的基本概念（一）、基本概念1、阶段：把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。描述阶段的变量称为阶段变量,常用k表示。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。年、月、路段2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量，常用Sk表示。如：S2=B1；S3=C1状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。如：S2=B1，B2；S3=C1，C2，C3，C4注意：要明确每个阶段状态的集合或者范围。一个数、一组数、一个向量“状态”具有“无后效

2、性”（“马尔科夫性”）：如果某阶段的状态给定后，当前的状态是以往历史的总结，则在这阶段以后过程的发展不受这阶段以前各阶段的影响。3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量，称为决策变量。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。Uk(Sk)表示第k阶段处于Sk状态时的决策变量。如：U2(B1)C2，表示处于第二阶段，以B1为始点选择C2作为第二阶段的终点。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。Dk(Sk)表示第k阶段处于Sk状态时的允许决策集合。D2(B

3、1)C1,C2,C3。Uk(Sk)Dk(Sk)。4、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合，用P来表示。从允许策略集合中找出达到最优效果的策略称为最优策略。把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n u1,u2,un称为全过程策略，简称策略；而在k子过程上的决策序列pk,n uk,uk+1,un称为k子过程策略，也简称子策略。5、状态转移方程：若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，

4、下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。如：S3=T2(S2,U2)C2T2(B1，C2)状态变量要满足无后效性的要求；如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。状态具有无后效性的多阶段决策过程的状态转移方程如下动态规划中能处理的状态转移方程的形式。6、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。常用Vk,n表示。Vk,nVk,n(Sk，Uk，Sk1，,Sn+1)k=1,2,n在

5、不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数，应具有可分离性，并满足递推关系。即Vk,n可表示为Sk，Uk，Vk1,n的函数。Vk,n(Sk，Uk，Sk1，Sn+1)kSk，Uk，Vk1,n(Sk1，Uk1，Sn+1)常见的指标函数有：1)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的和。Vk,n（Sk，Uk，Sk1，,Sn+1）Vk,n（Sk，Uk，Sk1，,Sn+1）vk(sk,uk)+Vk+1,n（Sk+1，Uk+1，Sk2，,Sn+1）2)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的乘积，即：Vk

6、,n（Sk，Uk，Sk1，,Sn+1）Vk,n(Sk，Uk，Sk1，,Sn+1)vk(sk,uk)Vk+1,n(Sk+1，Uk+1，Sk2，,Sn+1)nkjjjjusv),(nkjjjjusv),(指标函数的最优值称为最优值函数，记为fk(sk)。表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。如：f1(A)18，f2(B1)13。即fk(sk)opt Vk,n(sk,uk,sn,un)（uk,un）式中的“opt”（optimization）可根据具体问题而取min或max。一般情况下，k阶段和k+1阶段之间的递推关系式可写成：fk(Sk)opt vk(Sk,Uk(Sk)+fk+1(Sk+1)k=n,n-1,2,1或fk(Sk)opt vk(Sk,Uk(Sk)*fk+1(Sk+1)k=n,n-1,2,1小结动态规划本质上是多阶段决策过程;概念:阶段变量k状态变量sk决策变量uk;方程:状态转移方程指标:指标函数形式:和、积无后效性效益可递推解多阶段决策过程问题，求出最优策略，即最优决策序列优轨线，即执行最优策略时的状态序列最优目标函数值f1(s1)从 k 到终点最优策略子策略的最优目标函数值