动态规划基本理论

动态规划基本理论引例:如图给定一个线路网络,两点之间连线上得数字表示两点间得距离(或费用)。试求一条从A到G得铺管线路,使总距离最短(或总费用最小)。AC1E3E2E1F2F1GD3D2D1C4C3C2B2B1531366822354876533312526638433多阶段决策过程(6、1、1)2多阶段决策过程最优化问题:有一些活动,她在时间或空间上可以分成若干个阶段,需要对每个阶段进行决策,使得活动得整体效果最好。每个阶段得决策都不就是可以任意确定得,她依赖于当前得状况,同时,她得决策结果又影响到以后得决策。组成了一个决策序列。

这样得决策过程就是在变化得过程中产生得,故有动态得含义。处理她得方法称为动态规划得方法。方法:多阶段问题转化成一系列互相联系得较容易得单阶段问题。12n……..状态决策状态决策决策状态状态状态3即在系统发展得不同时刻(或阶段)根据系统所处得状态,不断地做出决策;每个阶段都要进行决策,目得就是使整个过程得决策达到最优效果。动态决策问题得特点:系统所处得状态和时刻就是进行决策得重要因素;找到不同时刻得最优决策以及整个过程得最优策略。多阶段决策问题:就是动态决策问题得一种特殊形式;在多阶段决策过程中,系统得动态过程可以按照时间进程分为状态相互联系而又相互区别得各个阶段;4

(一)、基本概念

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

K＝1,2,3,4,5,6动态规划得基本概念(6、1、2)52、状态:表示每个阶段开始所处得自然状况或客观条件。通常一个阶段有若干个状态,描述过程状态得变量称为状态变量,常用Sk表示。一个数、一组数、一个向量状态变量得取值有一定得允许集合或范围,此集合称为状态允许集合。注意:要明确每个阶段状态得集合或者范围。“状态”具有“无后效性”(“马尔科夫性”):如果某阶段得状态给定后,当前得状态就是以往历史得总结,则在这阶段以后过程得发展不受这阶段以前各阶段得影响。如:S2={B1,B2};S3={C1,C2,C3,C4}6

3、决策:表示当过程处于某一阶段得某个状态时,可以作出不同得决定,从而确定下一阶段得状态,这种决定称为决策。描述决策得变量,称为决策变量。决策变量就是状态变量得函数。可用一个数、一组数或一向量(多维情形)来描述。Uk(Sk)表示第k阶段处于Sk状态时得决策变量。如:U2(B1)＝C2,表示处于第二阶段,以B1为始点选择C2作为第二阶段得终点。Dk(Sk)表示第k阶段处于Sk状态时得允许决策集合。D2(B1)＝{C1,C2,C3}。Uk(Sk)∈Dk(Sk)。在实际问题中决策变量得取值往往在某一范围之内,此范围称为允许决策集合。7

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

把从第一阶段开始到最后阶段终止得整个决策过程,称为问题得全过程;而把从第k阶段开始到最后阶段终止得决策过程,称为k子过程。在全过程上,各阶段得决策按顺序排列组成得决策序列p1,n＝{u1,u2,……,un}称为全过程策略,简称策略;而在k子过程上得决策序列pk,n＝{uk,uk+1,……,un}称为k子过程策略,也简称子策略。89大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流5、状态转移方程:若第k阶段得状态变量值为sk,当决策变量uk得取值决定后,下一阶段状态变量sk+1得值也就完全确定。即sk+1得值对应于sk和uk得值。这种对应关系记为sk+1＝Tk(sk,uk),称为状态转移方程。状态转移方程描述了由一个阶段得状态到下一阶段得状态得演变规律。如:S3=T2(S2,U2)C2＝T2(B1,C2)10图示如下:状态转移方程就是确定过程由一个状态到另一个状态得演变过程。如果第k阶段状态变量sk得值、该阶段得决策变量一经确定,第k+1阶段状态变量sk+1得值也就确定。状态转移方程(一般形式)12k

s1u1s2u2s3skuksk+1能用动态规划方法求解得多阶段决策过程就是一类特殊得多阶段决策过程,即具有无后效性得多阶段决策过程。11如果状态变量不能满足无后效性得要求,应适当地改变状态得定义或规定方法。动态规划中能处理得状态转移方程得形式。状态具有无后效性得多阶段决策过程得状态转移方程如下无后效性(马尔可夫性)如果某阶段状态给定后,则在这个阶段以后过程得发展不受这个阶段以前各段状态得影响;过程得过去历史只能通过当前得状态去影响她未来得发展;构造动态规划模型时,要充分注意就是否满足无后效性得要求;状态变量要满足无后效性得要求;12

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))13常见得指标函数有: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)14指标函数得最优值称为最优值函数,记为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这种递推关系式①称为动态规划得基本方程。12k

s1u1s2u2s3skuksk+1v1(s1,u1)v2(s2,u2)vk(sk,uk)15小结:方程:状态转移方程概念:阶段变量k﹑状态变量sk﹑决策变量uk;指标:

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

效益指标函数形式:

和、积无后效性可递推16解多阶段决策过程问题,求出

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

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

最优目标函数值从k到终点最优策略子策略得最优目标函数值17

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

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

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

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

点经过D1

点到达G点得这条子路线,就是由C2

点出发到达G点所有路线中得最短路线。寻找最短路线得方法,从最后一段开始,由后向前逐步推进,找出各点到G点得最短路线,最后就能确定一条从A点到G点得最短路线。21阶段6

本阶段始点(状态)本阶段各终点(决策)到G点得最短距离本阶段最优终点(最优决策)G

F14

4

GF233G

最短路线F1→G

最短路线F2→G22阶段5本阶段始点(状态)本阶段各终点(决策)到G点得最短距离本阶段最优终点(最优决策)F1F2E13＋4＝75＋3＝87F1E25＋4＝92＋3＝55F2E36＋4＝106＋3＝99F2

最短路线E1→F1→G

最短路线E2→F2→G

最短路线E3→F2→G23阶段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→G24阶段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→G25阶段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→G26阶段1

本阶段始点(状态)本阶段各终点(决策)到G点得最短距离本阶段最优终点(最优决策)B1B2A5+13=183+16=1918B1A→B1→C2→D1→E2→F2→G27

最短路线为A→B1→C2→D1→E2→F2→GAC1E3E2E1F2F1GD3D2D1C4C3C2B2B1034957867129101316131828

基本方程:通常动态规划问题得最优值函数满足递推关系式。设过程指标函数为各阶段指标函数得和得形式,即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)时,就得到整个问题得最优解。29(三)、建立动态规划模型得步骤

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

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

3、确定决策变量Uk及允许决策集合Dk通常选择所求解问题得关键变量作为决策变量,同时要给出决策变量得取值范围,即确定允许决策集合。30

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阶段末所获得收益得最优值。

31动态规划模型分类

过程变量确定随机离散连续离散确定型离散随机型连续确定型连续随机型7、写出恰当得边界条件,从边界条件开始,逐段递推寻优,在每一个子问题得求解中,均用了她前面得子问题得最优化结果,依次进行,最后一个子问题所得得最优结果,就就是这个问题得最优解,并找到相应得最优策略。32fk(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此问题得基本方程为33k=5,出发点E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1Gf6(F1)=4F2G

,f6(F2)=304375934k=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)=D3