动态规划基本理论

动态规划基本理论1第一页，共四十二页，编辑于2023年，星期五第13讲动态规划的基本理论(6.1)多阶段决策过程动态规划的基本概念和基本方程动态规划的最优性原理最短路问题（逆推法、顺推法）

第二页，共四十二页，编辑于2023年，星期五引例：如图给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路，使总距离最短(或总费用最小)。AC1E3E2E1F2F1GD3D2D1C4C3C2B2B1531366822354876533312526638433多阶段决策过程（6.1.1)第三页，共四十二页，编辑于2023年，星期五多阶段决策过程最优化问题：有一些活动，它在时间或空间上可以分成若干个阶段，需要对每个阶段进行决策，使得活动的整体效果最好。每个阶段的决策都不是可以任意确定的，它依赖于当前的状况，同时，它的决策结果又影响到以后的决策。组成了一个决策序列。

这样的决策过程是在变化的过程中产生的，故有动态的含义。处理它的方法称为动态规划的方法。方法：多阶段问题转化成一系列互相联系的较容易的单阶段问题。12n……..状态决策状态决策决策状态状态状态第四页，共四十二页，编辑于2023年，星期五即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；每个阶段都要进行决策,目的是使整个过程的决策达到最优效果。动态决策问题的特点：系统所处的状态和时刻是进行决策的重要因素；找到不同时刻的最优决策以及整个过程的最优策略。多阶段决策问题：是动态决策问题的一种特殊形式；在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段；第五页，共四十二页，编辑于2023年，星期五

（一）、基本概念

1、阶段：把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。描述阶段的变量称为阶段变量,常用k表示。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。年、月、路段

K＝1，2，3，4，5，6动态规划的基本概念（6.1.2)第六页，共四十二页，编辑于2023年，星期五2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量，常用Sk表示。一个数、一组数、一个向量状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。注意：要明确每个阶段状态的集合或者范围。“状态”具有“无后效性”（“马尔科夫性”）：如果某阶段的状态给定后，当前的状态是以往历史的总结，则在这阶段以后过程的发展不受这阶段以前各阶段的影响。如：S2={B1，B2}；S3={C1，C2，C3，C4}第七页，共四十二页，编辑于2023年，星期五

3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量，称为决策变量。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。Uk(Sk)表示第k阶段处于Sk状态时的决策变量。

如：U2(B1)＝C2，表示处于第二阶段，以B1为始点选择C2作为第二阶段的终点。Dk(Sk)表示第k阶段处于Sk状态时的允许决策集合。D2(B1)＝{C1,C2,C3}。Uk(Sk)∈Dk(Sk)。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。第八页，共四十二页，编辑于2023年，星期五

4、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合，用P来表示。从允许策略集合中找出达到最优效果的策略称为最优策略。

把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n＝{u1,u2,……,un}称为全过程策略，简称策略；而在k子过程上的决策序列pk,n＝{uk,uk+1,……,un}称为k子过程策略，也简称子策略。第九页，共四十二页，编辑于2023年，星期五5、状态转移方程：若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1＝Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。如：S3=T2(S2,U2)C2＝T2(B1，C2)第十页，共四十二页，编辑于2023年，星期五图示如下：状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。状态转移方程（一般形式）12ks1u1s2u2s3skuksk+1能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。第十一页，共四十二页，编辑于2023年，星期五如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。动态规划中能处理的状态转移方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下无后效性(马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；状态变量要满足无后效性的要求；第十二页，共四十二页，编辑于2023年，星期五

6、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。常用Vk,n表示。

Vk,n＝Vk,n(Sk，Uk

，Sk＋1

，…,Sn+1)k=1,2,…,n

在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数，应具有可分离性，并满足递推关系。即Vk,n可表示为Sk，Uk

，Vk＋1,n的函数。

Vk,n(Sk，Uk

，Sk＋1

，…，Sn+1)＝φk(Sk，Uk

，Vk＋1,n(Sk＋1，Uk＋1…,Sn+1))第十三页，共四十二页，编辑于2023年，星期五常见的指标函数有：1)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的和。Vk,n（Sk，Uk

，Sk＋1

，…,Sn+1）＝Vk,n（Sk，Uk，Sk＋1，…,Sn+1）＝vk(sk,uk)+Vk+1,n（Sk+1，Uk+1

，Sk＋2

，…,Sn+1）2)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的乘积，即：Vk,n（Sk，Uk

，Sk＋1

，…,Sn+1）＝Vk,n(Sk，Uk

，Sk＋1

，…,Sn+1)＝vk(sk,uk)×Vk+1,n(Sk+1，Uk+1

，Sk＋2

，…,Sn+1)第十四页，共四十二页，编辑于2023年，星期五指标函数的最优值称为最优值函数，记为fk(sk)。表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。如：f1(A)＝18，f2(B1)＝13。即fk(sk)＝optVk,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,1fk(Sk)＝opt{vk(Sk,Uk(Sk))+fk+1(Uk(Sk))}k=n,n-1,…,2,1①边界条件为:fn+1(Sn+1)=0这种递推关系式①称为动态规划的基本方程。12ks1u1s2u2s3skuksk+1v1(s1,u1)v2(s2,u2)vk(sk,uk)第十五页，共四十二页，编辑于2023年，星期五小结:方程:状态转移方程概念:阶段变量k﹑状态变量sk﹑决策变量uk;指标:

动态规划本质上是多阶段决策过程;

效益指标函数形式:

和、积无后效性可递推第十六页，共四十二页，编辑于2023年，星期五解多阶段决策过程问题，求出

最优策略，即最优决策序列f1(s1)

最优轨线，即执行最优策略时的状态序列

最优目标函数值从k到终点最优策略子策略的最优目标函数值第十七页，共四十二页，编辑于2023年，星期五

1、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。（二）、动态规划的基本思想和基本方程第十八页，共四十二页，编辑于2023年，星期五

2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.

最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。

3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。第十九页，共四十二页，编辑于2023年，星期五最短路问题：如图给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路，使总距离最短(或总费用最小)。AC1E3E2E1F2F1GD3D2D1C4C3C2B2B1531366822354876533312526638433第二十页，共四十二页，编辑于2023年，星期五从A点到G点可分成6个阶段。以A为起点，终点有两个B1、B2，有两个选择。若选择B2，则B2为第一阶段决策的结果。同时它又是第二阶段的开始状态。当每个阶段做出决策的结果，直接影响到后面的选择和决策的结果。最短路线有一个重要特性：如果从起点A经过C2点和D1点到达终点G是一条最短的路线，则由C2

点经过D1

点到达G点的这条子路线，是由C2

点出发到达G点所有路线中的最短路线。寻找最短路线的方法，从最后一段开始，由后向前逐步推进，找出各点到G点的最短路线，最后就能确定一条从A点到G点的最短路线。第二十一页，共四十二页，编辑于2023年，星期五阶段6

本阶段始点（状态）本阶段各终点（决策）到G点的最短距离本阶段最优终点（最优决策）G

F14

4

GF233G

最短路线F1→G

最短路线F2→G第二十二页，共四十二页，编辑于2023年，星期五阶段5本阶段始点（状态）本阶段各终点（决策）到G点的最短距离本阶段最优终点（最优决策）F1F2E13＋4＝75＋3＝87F1E25＋4＝92＋3＝55F2E36＋4＝106＋3＝99F2

最短路线E1→F1→G

最短路线E2→F2→G

最短路线E3→F2→G第二十三页，共四十二页，编辑于2023年，星期五阶段4本阶段始点(状态)本阶段各终点（决策）到G点的最短距离本阶段最优终点（最优决策）E1E2E3D12＋7＝92＋5＝7

7E2D21＋5＝62＋9＝116E2D33＋5＝83＋9＝128E2

最短路线D1→E2→F2→G

最短路线D2→E2→F2→G

最短路线D3→E2→F2→G第二十四页，共四十二页，编辑于2023年，星期五阶段3本阶段始点(状态)本阶段各终点（决策）到G点的最短距离本阶段最优终点（最优决策）D1D2D3C16+7=138+6=14

13D1C23+7=105+6=11

10D1C3

3+6=93+8=119D2C4

8+6=144+8=1212D3C1→D1→E2→F2→GC2→D1→E2→F2→GC3→D2→E2→F2→GC4→D3→E2→F2→G第二十五页，共四十二页，编辑于2023年，星期五阶段2本阶段始点(状态)本阶段各终点（决策）到G点的最短距离本阶段最优终点（最优决策）C1C2C3C4B11+13=143+10=136+9=15

13C2B2

8+10=187+9=166+12=1816C3B1→C2→D1→E2→F2→GB2→C3→D2→E2→F2→G第二十六页，共四十二页，编辑于2023年，星期五阶段1

本阶段始点（状态）本阶段各终点（决策）到G点的最短距离本阶段最优终点（最优决策）B1B2A5+13=183+16=1918B1A→B1→C2→D1→E2→F2→G第二十七页，共四十二页，编辑于2023年，星期五

最短路线为A→B1→C2→D1→E2→F2→GAC1E3E2E1F2F1GD3D2D1C4C3C2B2B10349578671291013161318第二十八页，共四十二页，编辑于2023年，星期五

基本方程：通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,n＝∑vj(sj,uj)，则有fk(sk)＝opt{vk(sk,uk)+fk+1(sk+1)}

uk∈Dk(sk)(k＝n,n-1,…,1)递推方程

fn+1(sn+1)＝0边界条件递推方程和边界条件一起称为动态规划基本方程.

可根据边界条件，从k=n开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解。第二十九页，共四十二页，编辑于2023年，星期五（三）、建立动态规划模型的步骤

1、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。

2、正确选择状态变量Sk选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。

3、确定决策变量Uk及允许决策集合Dk通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。第三十页，共四十二页，编辑于2023年，星期五

4、确定状态转移方程Sk+1=Tk(Sk,Uk)

根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。

5、正确写出指标函数Vk,n的关系，它应满足下面三个性质：Vk,n是定义在全过程和所有后部子过程上的数量函数具有可分离性，并满足递推关系，即Vk,n(Sk,Uk,Sk＋1,……Sn+1)=φk(Sk,Uk,Vk＋1,n(Sk＋1,Uk＋1,Sn+1))函数φk（Sk，Uk

，Vk＋1,n）对于变量Vk＋1,n要严格单调。6、恰当地定义最优指标函数阶段指标函数是指第k

阶段的收益，最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值。

第三十一页，共四十二页，编辑于2023年，星期五动态规划模型分类

过程变量确定随机离散连续离散确定型离散随机型连续确定型连续随机型7、写出恰当的边界条件，从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优结果，就是这个问题的最优解，并找到相应的最优策略。第三十二页，共四十二页，编辑于2023年，星期五fk(sk)＝Min{dk(uk)+fk+1(sk+1)}

uk∈Dk(sk)

k＝6,5,4,3,2,1f7(s7)＝0AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643用dk(sk,uk)＝vk(sk,uk)表示从点Sk到Sk＋1的距离。Vk,n表示在第k阶段从点Sk到终点的距离。fk(Sk)

表示第k阶段状态为Sk时，从第k阶段开始到第n阶段的最短距离。f7(S7)＝0此问题的基本方程为第三十三页，共四十二页，编辑于2023年，星期五k=5，出发点E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1Gf6(F1)=4F2G

,f6(F2)=304375934第三十四页，共四十二页，编辑于2023年，星期五k=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D1f3(C4)=12

u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2第三十五页，共四十二页，编辑于2023年，星期五u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gu5(E3)=F2E3F2G759

u5(E2)=F2u6(F2)=G最优策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566430347597681310912131618第三十六页，共四十二页，编辑于2023年，