动态规划汇总课件

*动态规划DP一、概述二、DP的基本原理(最优化原理)与方法三、DP基本概念及方程四、动态规划的数学模型和求解方法*动态规划DP一、概述*动态规划DP一、概述(一)什么是DPDP:解决多阶段决策的一种方法多阶段决策过程:根据问题的空间或时间特性将过程分为若干阶段,而在每一阶段中都需作出决策,并且一个阶段的决策将影响下阶段的状态。所有阶段决策构成一个决策序列，称为策略，每个策略对应一个效果。所选择的策略应使整个过程获得最优效果。DP是按照上述思路寻求问题最优解的工具。*动态规划DP一、概述*

动态系统:当所解决多阶段决策过程优化问题处于一个含时间变量或与时间变量有关的系统中,且系统现在的状态与过去与未来的状态有关时,这个系统称为动态系统.

如以灌溉或发电为主要目标的水库调度问题就是一个多阶段决策过程。一年可以按时间分成若干阶段。每个阶段，以水库蓄水量或水位为状态变量，以放水量为决策变量，把灌溉效益或发电量最大为目标函数。在满足约束条件下确定各时段放水量，即组成一个决策序列。如果所选定的各时段放水量能使全年灌溉或发电效益最大，这就是一个最优策略，即最优调度方案。由于各阶段决策与时间进程有关，故为DP。*动态系统:当所解决多阶段决策过程优化问题处于一个含*(二)DP适用范围DP不仅能解决与时间有关的优化问题，而且也能解决与时间无关的静态问题。例如，资源分配、投资分配、最优线路、结构优化问题等。只要能把问题分成多个阶段或步骤进行决策，就可用DP寻求最优解。广义:工农业生产,资源开发管理,经济社会,环境水利等系统狭义:①变量连续或离散,可微或不可微.②LP,NLP③变量是确定性或随机性④单变量或多变量(三)DP优缺点优:①可以把一个n维优化问题变为n个一维问题求解②能找出全局最优③适用难度较大的复杂问题④简单易懂缺:①存在”维数灾”②计算程序通用性差.

*(二)DP适用范围*二、DP的基本原理(最优化原理)与方法基本原理:一个决策过程的最优策略具备这样的性质,即形成的状态并作为初始状态的过程而言,余下的诸决策必须构成最优策略.12tt+1n-1n最优余留期例:AB1B2C1C2D1D2E456645132443(14,B2)(9,C1)(6,D1)(3,E)(11,C1)(5,D1)(4,E)①穷举法:2×2×2=8条路径,最优策略:AB2C1D1E,min为14②标号法*二、DP的基本原理(最优化原理)与方法12t*③公式法di(·)—第i阶段的费用Fi(·)—i~n阶段的总最小费用i=4D→Ef4(D1)=4f4(D2)=3i=3

f3(C1)=min[d3(C1,D1)+f4(D1),d3(C1,D2)+f4(D2)]=min[1+4,3+3]=5(C1,D1,E)f3(C2)=min[d3(C2,D1)+f4(D1),d3(C2,D2)+f4(D2)]=min[2+4,4+3]=6(C2,D1,E)i=2f2(B1)=min[d2(B1,C1)+f3(C1),d2(B1,C2)+f3(C2)]=min[6+5,6+6]=11(B1,C1,D1E)f2(B2)=min[d2(B2,C1)+f3(C1),d2(B2,C2)+f3(C2)]=min[4+5,5+6]=9(B2,C1,D1E)i=1f1(A)=min[d1(A,B1)+f2(B1),d1(A,B2)+f2(B2)]=min[4+11,5+9]=14(A,B2,C1,D1E)最优路线AB2C1D1E*③公式法*三、DP基本概念及方程(一)概念1.多阶段决策过程是把整个过程按时间或空间分成若干阶段,各阶段首尾相连,但不重复,闭合.2.多阶段过程具有性质:当前阶段以前的各阶段的决策和状态,对后面各阶段的决策,相当于一个初始条件,并不影响后面过程的最优策略.3.DP对多阶段最优决策过程是一个有效方法,可大大减少计算工作量.4.DP法丰富了计算结果.5.DP一般采用”逆序决策过程”*三、DP基本概念及方程*(二)DP的要素意义1.阶段:指研究对象在发展中所处的时段或空间中所处的部位,常用阶段变量k描述.2.状态:系统在某阶段中,过程演变的各种可能发生情况或所处状态.Sk为第k阶段的状态变量。如上例S2={B1,B2}

状态无后效性：过程的过去历史只通过面临阶段的状态去影响未来的发展，而与未来过程无直接联系。*(二)DP的要素意义*3.决策:某阶段给定,从该阶段状态演变到下一阶段某状态应做的决定(选择),描述决策的变量称决策变量。Uk(sk)为第k阶段状态处于变量Sk时的决策变量，是Sk的函数。U2(B1)=c14.策略:第k阶段开始到终止状态为止的过程，每段决策按顺序排列组成的决策函数序列{Uk(sk),Uk+1(sk+1)…,Un(sn)}记为Pk,n(Sk)*3.决策:某阶段给定,从该阶段状态演变到下一阶段某状态应做*5.状态转移方程:由一个状态到另一个状态的演变过程。SK+1=TK(Sk,uk)

状态转移规律，状态转移方程

TK状态转移函数。上例SK+1=Uk(sk)，Vt+1=Vt+Qt-qt6.指标函数和最优值函数:指标函数:各阶段效益vk总和

Vk,n=Vk,n(SK,uk,Sk+1,uk+1,…Sn+1),k=1,2,…nVk,n应具有可分离性,并满足递推关系:

Vk,n(Sk,uk,Sk+1,uk+1,…Sn+1)=Vk(Sk,uk)+VK+1,n(SK+1,uk+1…Sn+1)]最优值函数:指标函数的最优值，记为fk(sk).表示从第k阶段的状态SK开始到第n阶段的终止状态的过程，采取最优策略得到的指标函数值。

fk(sk)=optVk,n(SK,uk,Sk+1,…Sn+1)

*5.状态转移方程:由一个状态到另一个状态的演变过程。SK+*综上，多阶段决策过程具有如下性质：（1）在多阶段决策过程中，任一阶段都是以若干状态来表征，其中任一状态的变化，都将使该阶段决策发生变化。（2）在每一阶段，都可对每个状态选择一种决策，决策的结果就是状态的转移。（3）阶段n+1的状态sn+1是由阶段的状态和决策所决定，而与以前的各阶段状态无关。这表明，多阶段决策过程存在着马尔可夫单链性质，这是无后效性的重要特性。（4）过程的决策序列可能有多个，但只有使目标函数获得最优值的策略才是要选择的最优策略。*综上，多阶段决策过程具有如下性质：*

设多阶段决策过程如下图，阶段变量、状态变量、决策变量分别用k、s和u表示。系统的实际运动方向为1----n，阶段的编码次序与实际运动方向一致，即1----N，递推计算时采用的系统状态转移方向也与实际运动方向一致sn---sn+1（三）DP的基本方程(递推方程)*设多阶段决策过程如下图，阶段变量、状态变量、决策变量*2….kk+1….nn+1123…N-1N时刻阶段Vk(sk,uk)Fk+1(sk+1)Fk(sk)状态s1s2….sk

…..

snsn+1uk系统实际运动方向逆序递推*2….k*根据Bellman最优原理:Vk,n=Vk(sk,uk)+VK+1,,n[sk+1,…,sn+1]，若用pk,n(sk)表示k~n阶段的策略,则:Vk,n(sk,pk,n)=vk(sk,uk)+Vk+1[sk+1,pk+1,n]

当最优策略记为p*k,n(sk)，则最优函数值fk(sk)DP递推方程为:**上式的推导中，阶段变量按顺序编码，且阶段号码与阶段初编号一致，系统状态转移方向也与实际运动方向一致，而递推计算次序与实际运动方向相反，即由系统实际的终端向始端递推，故称这种计算为逆序递推，又称向后计算法。许多问题可以令系统状态转移方向与系统实际运动方向相反，系统实际的始端变为计算用的终端，递推计算要从这个终端开始，这样递推计算次序与实际运行方向一致，称这顺序递推，又叫向前计算法。下图为顺序递推示意图。设阶段变量按顺序编码，且阶段号码与阶段末编号一致，用上述同样方法可推导出顺序递推的递推方程。*上式的推导中，阶段变量按顺序编码，且阶段号码与阶段初编号一*01….K-1k….N-1N12k…N-1N时刻阶段Vk(sk,uk)Fk-1(sk-1)Fk(sk)状态s0s1….sk

…..

Sn-1snuk系统实际运动方向顺序递推*01….K-1*

由最优化原理和递推方程可以看出DP具有如下基本性质：(1)DP的基本内容，实际上是把原问题分成许多相互联系的子问题，而每个子问题是一个比原问题简单得多的优化问题，且在每一个子问题的求解中，均利用它的一个后部子问题（余留过程）的最优化结果，依次进行，最后一个子问题所得的最优解，即为原问题的最优解。DP就是将一个决策序列问题转化为多个阶段求单阶段决策问题；每一个单阶段决策问题可看成原问题的一个子问题。现以一个简单情况为例说明，如果原问题划分为N个阶段，并且每个阶段只有一个决策变量，则DP就将一个N维决策的原问题转化成只有一维决策的N个子问题。*由最优化原理和递推方程可以看出DP具有如下基本性*(2)从递推方程中看出，在任一阶段n选用一个决策后，它有两方面的影响：其一，它直接影响面临阶段的费用；其二，它也影响其后子过程的初始状态，因而影响到后边各阶段的最小总费用。全过程最优策略的选择是根据两者统一考虑的结果确定的。所以，在多阶段决策过程中，DP是既把面临阶段与未来阶段分开，又把当前费用和未来费用结合起来考虑的一种最优化方法。*(2)从递推方程中看出，在任一阶段n选用一个决策后，它有两*(3)由于用DP求解问题只需考虑相邻两个阶段，就使得DP的计算量远远小于枚举法的计算量。对于一个N阶段问题，如果始端状态只有一个，其他各阶段状态点数有T个，每个状态下有T个决策，则枚举法需计算TN个方案，而DP只需计算T+(N-1)T2个方案。(4)对系统方程、目标函数、约束条件的函数性质无严格要求，线性、非线性均可，甚至用表格表示某些变量之间关系，都可用DP求解，它也不要求决策空间为凸的，故DP是一种相当灵活的方法。*(3)由于用DP求解问题只需考虑相邻两个阶段，就使得DP的*（四）动态规划的数学模型和求解方法1、DP的数学模型

DP的数学模型一般由系统方程、目标函数、约束条件的边界条件等几部分组成。在建立模型时，首先将研究的问题根据其时间或空间特点划分阶段，形成多阶段决策过程，并相应地选取阶段变量、状态变量和决策变量。*（四）动态规划的数学模型和求解方法1、DP的数学模型*（一）系统方程系统方程即上面所说的状态转移方程，它是包括阶段变量、状态变量和决策变量三种变量的一组关系式。对于具有一个状态变量、一个决策变量的一维多阶段决策过程，系统方程可写成

n=1,2,…,N

式中，——阶段n的状态变量；

——阶段n的决策变量；

——状态转移函数。

*（一）系统方程*

例如，例5—1中的系统方程为单一水库优化调度问题的系统方程为式中，——n时段和n+1时段初水库蓄水量；

——n时段内水库来水量、放水量和蒸发渗漏损失量。对于具有m维状态向量、q维决策向量的系统方程可写成*例如，例5—1中的系统方程为*

﹕*﹕*

这可以4个水库联合运行为例加以说明。4个水库具有4个状态变量，故为四维（m=4）问题。由于每一个水库时段末的状态不仅和它自己时段初的状态、本时段的决策有关，而且和所有其他3个水库时段初状态的本时段决策有关。（二）目标函数

DP和其他数学规划方法一样，其数学模型同样要包括目标函数。目标函数的最优准则可以是效益最大化，也可以是费用最小化或其他指标。目标函数值决定于系统中的状态变量和决策变量，设以F表示目标函数，**

则

式中，L——每一阶段的费用（或效益）；

F——系统总费用（或总效益）。若为最小化目标函数，则写作

**（三）约束条件对状态变量和决策变量的约束可以根据实际限制条件给出。第n阶段的状态向量的约束于集合，记为

(5-22)

式中，——第n阶段的可行状态集合。在第n阶段状态时所采用的决策向量约束于集合，记为

(5-23)

式中，——在第n阶段状态的可行决策集合。*（三）约束条件*（四）边界条件指初始条件

或终末状态

式中，——已知常数。凡问题的初始状态已知，则称为初值问题；而终末状态已知的问题则称终值问题；如初始和终末状态均已知，则称边值问题。

DP就是要在系统方程、约束条件、边界条件约束下，寻求目标函数最优值和相应的最优决策序列。*（四）边界条件*2DP的求解方法求解DP数学模型，主要是反复使用递推方程进行择优计算，并由给定的初始状态开始反演，以确定最优策略。若实际问题中的阶段变量、状态变量和决策变量是离散的，就按原离散值计算；若这些变量是连续的，则可在其可行域内离散为有限个数值。设阶段变量离散为；任一阶段的状态离散为个点，记为,;状态上的决策离散为个值，记为,。*2DP的求解方法*（一）由最后阶段开始逐阶段进行递推计算在每个阶段，对每一个离散状态,都要使用所有的可行决策。对任何一个指定的离散状态，都须进行下列工作，以便选定最优决策。

1.由给定的和，求得相应的。

2.由该和,用系统方程计算，并求出由该状态开始的余留过程的最小总费用。*（一）由最后阶段开始逐阶段进行递推计算*

应当指出，若在给定的离散状态点上，则可以由阶段计算结果直接查到；若不在离散状态点上，则须进行内插。

3.由递推方程计算使用时的余留过程总费用，。当个决策都使用之后，将所有的进行比较，取其中最小者为该指定状态开始的余留过程的最小总费用，其相应的为最优决策。

*应当指出，若在给定的离散状态点上，则*

将记入计算机内存，供阶段计算使用；同时存贮，供决策反演时使用。至此，便结束这个离散化状态的计算。一个指定的算完后，接着依次进行其他离散状态点的计算。所有的都算完之后，阶段计算结束，随即转入阶段计算。**（二）由即定的初始状态开始进行决策反演，追寻最优策略

当递推计算至第1阶段后，由给定的初始状态开始，按系统方程和各状态下的最优决策进行反演，直到最后阶段，从而得到最优策略、最优轨迹和相应的最优目标函数值。若初始状态非唯一，则将推算的几个不同的初始状态的最小总费用进行比较，取其中最小者为最优目标函数值；并由它对应的初始状态开始反演求得最优策略和最优轨迹。一般讲来，当初始状态已知时，逆序递推较方便；当终末状已知时，顺序递推较方便*（二）由即定的初始状态开始进行决策反演，追寻最优策略*

开始

输入资料阶段计算；并放入内存状态决策由系统方程计算下一阶段状态计算由阶段优化结果求得存贮和由初始状态开始反演，追踪最优策略输入最优解

结束

*开始输入资料阶段计算*DP和静态规划的关系及DP求解方法一,关系一般对LP,NLP问题可人为引入”时间”因素,用DP求状态转移方程:Sk+1=Tk(Sk,xk)V1n=v1(S1,x1)*v2(S2,x2)*…vn(Sn,xn)*表示”+”或”ⅹ”DP方法

LP静态数学规划NLP静态

DP与时间有关,多阶段阶段数n固定:公式法,列表法,标号法阶段数n不固定:函数迭代法,策略迭代法*DP和静态规划的关系及DP求解方法一,关系*例:Maxz=x1.x22.x3x1+x2+x3=c(c>0)xi≥0,i=1,2,3解:按变量个数划分为三个阶段i=1,2,3设状态变量为:sk(S1,S2,S3,S4)，代表第k个变量及以后变量之和，记S1=C，S4=0决策:x1,x2,x3状态转移:Sk+1=Sk-Xk,S4=S3-X3=0,∴S3=X3S3=S2-x2,,S2=S1-x1S1=C阶段效益:v1=x1v2=x22v3=x3F4(S4)=1*例:Maxz=x1.x22.x3F4(S4)=1*决策域:0≤x1≤S1=C,0≤x2≤S2,x3=S3递推:*决策域:0≤x1≤S1=C,0≤x2≤S2,x3=S3*例:MaxZ=x1·x22·x3x1+x2+x3=C(C>0)xi≥0,i=1,2,3*例:MaxZ=x1·x22·x3*****例:MaxF=4x12-x22+2x32+123x1+2x2+x3≤9xi≥0,i=1,2,3解:分三个阶段,设状态变量S0,S1,S2,S3≤9

决策变量:x1,x2,x3顺推解法:设S0=0,3x1=S1,S1+2x2=S2,S2+x3=S3≤9则:0≤x1≤1/3S1,0≤x2≤1/2S2,0≤x3≤S3阶段效益:v1=4x12

v2=-x22v3=2x32+12F0(S0)=0*例:MaxF=4x12-x22+2x32+12F0(*****2.列表法思路:首先把各阶段的状态变量Sk按计算精度ΔS离散为0,ΔS,2ΔS,…(m-1)ΔS,S0共有m+1个分点.先后用表格型式在离散点上求解递推方程,得最优策略.例:MaxF=x1+(x2-3)2+(4-x3)3

x1+x2+x3≤8xi≥0,i=1,2,3ε=1(精度)解:分三个阶段,设S0=0,状态空间为8是连续的

S1=S0+x1,S2=S1+x2,S3=S2+x3Sk=Tk(Sk-1,xk)阶段效益:v1=x1

v2=(x2-3)2v3=(4-x3)3把各Sk按ΔS=1离散顺推计算:

*2.列表法*第一阶段:设S1=x1F1(S1)=Max{v1(S1,x1)}=Max{x1}第二阶段:S2=S1+x2

S2={0…8}f2(S2)=Max{v2(S2,x2)+f1(S1)}S1

012345678f1(S1)

012345678X1*012345678

*第一阶段:设S1=x1S1*41014916250123456784101491625521251017632361176347854596510711

s1f2x2v2f10012345678*4101*f2(S2)s2v3x3f327810182764012345678361710910173673371811101118373819121112193920131213402114134122154223438901234567258

*f2(S2)s2v3x3f3278*把各阶段最优值汇总:Sf1x1f2x2f3x30009073011100740221107503312076044130770551407806615079077167或080088258890*把各阶段最优值汇总:Sf1*S2=S3-x3,S1=S2-x2当S0=8时，x1*=0,x2*=8,x3*=0,F=89当S0=7时,x1*=0,或7,x2*=7或0,x3*=0F=80当S0=6时,x1*=6x2*=0x3*=0F=79F(0,7,0)=x1+(x2-3)2+(4-x3)2=80F(7,0,0)=80结论：1）当问题的变量是离散时，所求解是精确的

2）当变量是连续的，可安精度要求得近似最优解。

3）DP离散方法，不用求导，计算简便，易于编程。*S2=S3-x3,S1=S2-x2*7.4二维及多维DPn维DP：状态变量n个，决策变量n个例：两个水库可供总水量分别为Z，Y联合向n个用水户供水，第i个用户从Z，Y取水xi,yi,得收益ri(xi,yi)求水资源系统最优分配方案？解：设水库A，B可用水量离散，用状态变量qi,Qi表示，则有DP递推方程：状态转移方程：qi+1=qi-xi0≤xi≤qi≤ZQi+1=QI-yi0≤yi≤Qi≤Y可用DP格点法求解

*7.4二维及多维DP*7.5随机DP简介1.分类：①各阶段是相互独立的，且有各自的概率分布②各阶段是有相关关系的，如存在马尔柯夫2.（MarkovChain）关系独立（有预报）相关（无预报）例：某室外工程，施工只需一天完成，要求在5天内完成。日程第1天雨情大雨小雨无P0.20.30.5

第2天大小无0.20.20.6

第3天大小无0.20.20.6

第4天大小无0.40.40.2

第5天大小无0.40.40.2*7.5随机DP简介日程第1天第2天*

雨情大雨小雨无雨施工费（元）800600500问该工程在哪一天施工最好？解：按天划分阶段，以Si,j表示第i天雨情，则相应概率Pij

Efi(Sij)=Min{ri(Sij,uj),Efi+1(Si+1,j)}

第5天无论什么天气均施工。rs*(Sij,usj)=rs(S5,j,u5)大雨:r5*(S51,u5)=800(元)，p51=0.4小雨：r5*(S52,u5)=600(元)，p52=0.4无雨：r5*(S53,u5)=500(元)，p53=0.2第4天：Ef5(S5j)=800╳0.4+600╳0.4+500╳0.2=660(元)f4(S4j)=Min{r4(S4j,u4j),Ef5(S5j)}f4*(S41,u41)=Min{800,660}=660大雨不施工f4*(S42,u42)=Min{600,660}=600小雨施工f4*(S43,u43)=Min{500,660}=500小雨施工

*雨情大雨小雨*第3天：f3*(S3j,u3j)=Min{r3(S3j,u3j),Ef4(S4j)}f3*(S31,u31)=Min{800,604}=604当天不施工f3*(S32,u32)=Min{600,604}=600当天施工f3*(S33,u33)=Min{500,604}=500当天施工第2天：Ef3*=541(元)f2*(S21,u21)=Min{800,541}=541当天不施工f2*(S22,u22)=Min{600,541}=541当天不施工f2*(S23,u23)=Min{500,541}=500当天施工第1天：Ef2*=516(元）f1*(S11,u11)=516=f1*(S12,u12)当天不施工f1*(S13,u13)=500当天施工最优策略：第1，2天：无雨施工，大小雨不施工第3，4天：无，小雨施工，大雨不施工第5天：无论什么天气都施工期望的施工最小费用：Ef1*=516╳0.2+516╳0.3+500╳0.5=508(元)*第3天：*动态规划DP一、概述二、DP的基本原理(最优化原理)与方法三、DP基本概念及方程四、动态规划的数学模型和求解方法*动态规划DP一、概述*动态规划DP一、概述(一)什么是DPDP:解决多阶段决策的一种方法多阶段决策过程:根据问题的空间或时间特性将过程分为若干阶段,而在每一阶段中都需作出决策,并且一个阶段的决策将影响下阶段的状态。所有阶段决策构成一个决策序列，称为策略，每个策略对应一个效果。所选择的策略应使整个过程获得最优效果。DP是按照上述思路寻求问题最优解的工具。*动态规划DP一、概述*

动态系统:当所解决多阶段决策过程优化问题处于一个含时间变量或与时间变量有关的系统中,且系统现在的状态与过去与未来的状态有关时,这个系统称为动态系统.

如以灌溉或发电为主要目标的水库调度问题就是一个多阶段决策过程。一年可以按时间分成若干阶段。每个阶段，以水库蓄水量或水位为状态变量，以放水量为决策变量，把灌溉效益或发电量最大为目标函数。在满足约束条件下确定各时段放水量，即组成一个决策序列。如果所选定的各时段放水量能使全年灌溉或发电效益最大，这就是一个最优策略，即最优调度方案。由于各阶段决策与时间进程有关，故为DP。*动态系统:当所解决多阶段决策过程优化问题处于一个含*(二)DP适用范围DP不仅能解决与时间有关的优化问题，而且也能解决与时间无关的静态问题。例如，资源分配、投资分配、最优线路、结构优化问题等。只要能把问题分成多个阶段或步骤进行决策，就可用DP寻求最优解。广义:工农业生产,资源开发管理,经济社会,环境水利等系统狭义:①变量连续或离散,可微或不可微.②LP,NLP③变量是确定性或随机性④单变量或多变量(三)DP优缺点优:①可以把一个n维优化问题变为n个一维问题求解②能找出全局最优③适用难度较大的复杂问题④简单易懂缺:①存在”维数灾”②计算程序通用性差.

*(二)DP适用范围*二、DP的基本原理(最优化原理)与方法基本原理:一个决策过程的最优策略具备这样的性质,即形成的状态并作为初始状态的过程而言,余下的诸决策必须构成最优策略.12tt+1n-1n最优余留期例:AB1B2C1C2D1D2E456645132443(14,B2)(9,C1)(6,D1)(3,E)(11,C1)(5,D1)(4,E)①穷举法:2×2×2=8条路径,最优策略:AB2C1D1E,min为14②标号法*二、DP的基本原理(最优化原理)与方法12t*③公式法di(·)—第i阶段的费用Fi(·)—i~n阶段的总最小费用i=4D→Ef4(D1)=4f4(D2)=3i=3

f3(C1)=min[d3(C1,D1)+f4(D1),d3(C1,D2)+f4(D2)]=min[1+4,3+3]=5(C1,D1,E)f3(C2)=min[d3(C2,D1)+f4(D1),d3(C2,D2)+f4(D2)]=min[2+4,4+3]=6(C2,D1,E)i=2f2(B1)=min[d2(B1,C1)+f3(C1),d2(B1,C2)+f3(C2)]=min[6+5,6+6]=11(B1,C1,D1E)f2(B2)=min[d2(B2,C1)+f3(C1),d2(B2,C2)+f3(C2)]=min[4+5,5+6]=9(B2,C1,D1E)i=1f1(A)=min[d1(A,B1)+f2(B1),d1(A,B2)+f2(B2)]=min[4+11,5+9]=14(A,B2,C1,D1E)最优路线AB2C1D1E*③公式法*三、DP基本概念及方程(一)概念1.多阶段决策过程是把整个过程按时间或空间分成若干阶段,各阶段首尾相连,但不重复,闭合.2.多阶段过程具有性质:当前阶段以前的各阶段的决策和状态,对后面各阶段的决策,相当于一个初始条件,并不影响后面过程的最优策略.3.DP对多阶段最优决策过程是一个有效方法,可大大减少计算工作量.4.DP法丰富了计算结果.5.DP一般采用”逆序决策过程”*三、DP基本概念及方程*(二)DP的要素意义1.阶段:指研究对象在发展中所处的时段或空间中所处的部位,常用阶段变量k描述.2.状态:系统在某阶段中,过程演变的各种可能发生情况或所处状态.Sk为第k阶段的状态变量。如上例S2={B1,B2}

状态无后效性：过程的过去历史只通过面临阶段的状态去影响未来的发展，而与未来过程无直接联系。*(二)DP的要素意义*3.决策:某阶段给定,从该阶段状态演变到下一阶段某状态应做的决定(选择),描述决策的变量称决策变量。Uk(sk)为第k阶段状态处于变量Sk时的决策变量，是Sk的函数。U2(B1)=c14.策略:第k阶段开始到终止状态为止的过程，每段决策按顺序排列组成的决策函数序列{Uk(sk),Uk+1(sk+1)…,Un(sn)}记为Pk,n(Sk)*3.决策:某阶段给定,从该阶段状态演变到下一阶段某状态应做*5.状态转移方程:由一个状态到另一个状态的演变过程。SK+1=TK(Sk,uk)

状态转移规律，状态转移方程

TK状态转移函数。上例SK+1=Uk(sk)，Vt+1=Vt+Qt-qt6.指标函数和最优值函数:指标函数:各阶段效益vk总和

Vk,n=Vk,n(SK,uk,Sk+1,uk+1,…Sn+1),k=1,2,…nVk,n应具有可分离性,并满足递推关系:

Vk,n(Sk,uk,Sk+1,uk+1,…Sn+1)=Vk(Sk,uk)+VK+1,n(SK+1,uk+1…Sn+1)]最优值函数:指标函数的最优值，记为fk(sk).表示从第k阶段的状态SK开始到第n阶段的终止状态的过程，采取最优策略得到的指标函数值。

fk(sk)=optVk,n(SK,uk,Sk+1,…Sn+1)

*5.状态转移方程:由一个状态到另一个状态的演变过程。SK+*综上，多阶段决策过程具有如下性质：（1）在多阶段决策过程中，任一阶段都是以若干状态来表征，其中任一状态的变化，都将使该阶段决策发生变化。（2）在每一阶段，都可对每个状态选择一种决策，决策的结果就是状态的转移。（3）阶段n+1的状态sn+1是由阶段的状态和决策所决定，而与以前的各阶段状态无关。这表明，多阶段决策过程存在着马尔可夫单链性质，这是无后效性的重要特性。（4）过程的决策序列可能有多个，但只有使目标函数获得最优值的策略才是要选择的最优策略。*综上，多阶段决策过程具有如下性质：*

设多阶段决策过程如下图，阶段变量、状态变量、决策变量分别用k、s和u表示。系统的实际运动方向为1----n，阶段的编码次序与实际运动方向一致，即1----N，递推计算时采用的系统状态转移方向也与实际运动方向一致sn---sn+1（三）DP的基本方程(递推方程)*设多阶段决策过程如下图，阶段变量、状态变量、决策变量*2….kk+1….nn+1123…N-1N时刻阶段Vk(sk,uk)Fk+1(sk+1)Fk(sk)状态s1s2….sk

…..

snsn+1uk系统实际运动方向逆序递推*2….k*根据Bellman最优原理:Vk,n=Vk(sk,uk)+VK+1,,n[sk+1,…,sn+1]，若用pk,n(sk)表示k~n阶段的策略,则:Vk,n(sk,pk,n)=vk(sk,uk)+Vk+1[sk+1,pk+1,n]

当最优策略记为p*k,n(sk)，则最优函数值fk(sk)DP递推方程为:**上式的推导中，阶段变量按顺序编码，且阶段号码与阶段初编号一致，系统状态转移方向也与实际运动方向一致，而递推计算次序与实际运动方向相反，即由系统实际的终端向始端递推，故称这种计算为逆序递推，又称向后计算法。许多问题可以令系统状态转移方向与系统实际运动方向相反，系统实际的始端变为计算用的终端，递推计算要从这个终端开始，这样递推计算次序与实际运行方向一致，称这顺序递推，又叫向前计算法。下图为顺序递推示意图。设阶段变量按顺序编码，且阶段号码与阶段末编号一致，用上述同样方法可推导出顺序递推的递推方程。*上式的推导中，阶段变量按顺序编码，且阶段号码与阶段初编号一*01….K-1k….N-1N12k…N-1N时刻阶段Vk(sk,uk)Fk-1(sk-1)Fk(sk)状态s0s1….sk

…..

Sn-1snuk系统实际运动方向顺序递推*01….K-1*

由最优化原理和递推方程可以看出DP具有如下基本性质：(1)DP的基本内容，实际上是把原问题分成许多相互联系的子问题，而每个子问题是一个比原问题简单得多的优化问题，且在每一个子问题的求解中，均利用它的一个后部子问题（余留过程）的最优化结果，依次进行，最后一个子问题所得的最优解，即为原问题的最优解。DP就是将一个决策序列问题转化为多个阶段求单阶段决策问题；每一个单阶段决策问题可看成原问题的一个子问题。现以一个简单情况为例说明，如果原问题划分为N个阶段，并且每个阶段只有一个决策变量，则DP就将一个N维决策的原问题转化成只有一维决策的N个子问题。*由最优化原理和递推方程可以看出DP具有如下基本性*(2)从递推方程中看出，在任一阶段n选用一个决策后，它有两方面的影响：其一，它直接影响面临阶段的费用；其二，它也影响其后子过程的初始状态，因而影响到后边各阶段的最小总费用。全过程最优策略的选择是根据两者统一考虑的结果确定的。所以，在多阶段决策过程中，DP是既把面临阶段与未来阶段分开，又把当前费用和未来费用结合起来考虑的一种最优化方法。*(2)从递推方程中看出，在任一阶段n选用一个决策后，它有两*(3)由于用DP求解问题只需考虑相邻两个阶段，就使得DP的计算量远远小于枚举法的计算量。对于一个N阶段问题，如果始端状态只有一个，其他各阶段状态点数有T个，每个状态下有T个决策，则枚举法需计算TN个方案，而DP只需计算T+(N-1)T2个方案。(4)对系统方程、目标函数、约束条件的函数性质无严格要求，线性、非线性均可，甚至用表格表示某些变量之间关系，都可用DP求解，它也不要求决策空间为凸的，故DP是一种相当灵活的方法。*(3)由于用DP求解问题只需考虑相邻两个阶段，就使得DP的*（四）动态规划的数学模型和求解方法1、DP的数学模型

DP的数学模型一般由系统方程、目标函数、约束条件的边界条件等几部分组成。在建立模型时，首先将研究的问题根据其时间或空间特点划分阶段，形成多阶段决策过程，并相应地选取阶段变量、状态变量和决策变量。*（四）动态规划的数学模型和求解方法1、DP的数学模型*（一）系统方程系统方程即上面所说的状态转移方程，它是包括阶段变量、状态变量和决策变量三种变量的一组关系式。对于具有一个状态变量、一个决策变量的一维多阶段决策过程，系统方程可写成

n=1,2,…,N

式中，——阶段n的状态变量；

——阶段n的决策变量；

——状态转移函数。

*（一）系统方程*

例如，例5—1中的系统方程为单一水库优化调度问题的系统方程为式中，——n时段和n+1时段初水库蓄水量；

——n时段内水库来水量、放水量和蒸发渗漏损失量。对于具有m维状态向量、q维决策向量的系统方程可写成*例如，例5—1中的系统方程为*

﹕*﹕*

这可以4个水库联合运行为例加以说明。4个水库具有4个状态变量，故为四维（m=4）问题。由于每一个水库时段末的状态不仅和它自己时段初的状态、本时段的决策有关，而且和所有其他3个水库时段初状态的本时段决策有关。（二）目标函数

DP和其他数学规划方法一样，其数学模型同样要包括目标函数。目标函数的最优准则可以是效益最大化，也可以是费用最小化或其他指标。目标函数值决定于系统中的状态变量和决策变量，设以F表示目标函数，**

则

式中，L——每一阶段的费用（或效益）；

F——系统总费用（或总效益）。若为最小化目标函数，则写作

**（三）约束条件对状态变量和决策变量的约束可以根据实际限制条件给出。第n阶段的状态向量的约束于集合，记为

(5-22)

式中，——第n阶段的可行状态集合。在第n阶段状态时所采用的决策向量约束于集合，记为

(5-23)

式中，——在第n阶段状态的可行决策集合。*（三）约束条件*（四）边界条件指初始条件

或终末状态

式中，——已知常数。凡问题的初始状态已知，则称为初值问题；而终末状态已知的问题则称终值问题；如初始和终末状态均已知，则称边值问题。

DP就是要在系统方程、约束条件、边界条件约束下，寻求目标函数最优值和相应的最优决策序列。*（四）边界条件*2DP的求解方法求解DP数学模型，主要是反复使用递推方程进行择优计算，并由给定的初始状态开始反演，以确定最优策略。若实际问题中的阶段变量、状态变量和决策变量是离散的，就按原离散值计算；若这些变量是连续的，则可在其可行域内离散为有限个数值。设阶段变量离散为；任一阶段的状态离散为个点，记为,;状态上的决策离散为个值，记为,。*2DP的求解方法*（一）由最后阶段开始逐阶段进行递推计算在每个阶段，对每一个离散状态,都要使用所有的可行决策。对任何一个指定的离散状态，都须进行下列工作，以便选定最优决策。

1.由给定的和，求得相应的。

2.由该和,用系统方程计算，并求出由该状态开始的余留过程的最小总费用。*（一）由最后阶段开始逐阶段进行递推计算*

应当指出，若在给定的离散状态点上，则可以由阶段计算结果直接查到；若不在离散状态点上，则须进行内插。

3.由递推方程计算使用时的余留过程总费用，。当个决策都使用之后，将所有的进行比较，取其中最小者为该指定状态开始的余留过程的最小总费用，其相应的为最优决策。

*应当指出，若在给定的离散状态点上，则*

将记入计算机内存，供阶段计算使用；同时存贮，供决策反演时使用。至此，便结束这个离散化状态的计算。一个指定的算完后，接着依次进行其他离散状态点的计算。所有的都算完之后，阶段计算结束，随即转入阶段计算。**（二）由即定的初始状态开始进行决策反演，追寻最优策略

当递推计算至第1阶段后，由给定的初始状态开始，按系统方程和各状态下的最优决策进行反演，直到最后阶段，从而得到最优策略、最优轨迹和相应的最优目标函数值。若初始状态非唯一，则将推算的几个不同的初始状态的最小总费用进行比较，取其中最小者为最优目标函数值；并由它对应的初始状态开始反演求得最优策略和最优轨迹。一般讲来，当初始状态已知时，逆序递推较方便；当终末状已知时，顺序递推较方便*（二）由即定的初始状态开始进行决策反演，追寻最优策略*

开始

输入资料阶段计算；并放入内存状态决策由系统方程计算下一阶段状态计算由阶段优化结果求得存贮和由初始状态开始反演，追踪最优策略输入最优解

结束

*开始输入资料阶段计算*DP和静态规划的关系及DP求解方法一,关系一般对LP,NLP问题可人为引入”时间”因素,用DP求状态转移方程:Sk+1=Tk(Sk,xk)V1n=v1(S1,x1)*v2(S2,x2)*…vn(Sn,xn)*表示”+”或”ⅹ”DP方法

LP静态数学规划NLP静态

DP与时间有关,多阶段阶段数n固定:公式法,列表法,标号法阶段数n不固定:函数迭代法,策略迭代法*DP和静态规划的关系及DP求解方法一,关系*例:Maxz=x1.x22.x3x1+x2+x3=c(c>0)xi≥0,i=1,2,3解:按变量个数划分为三个阶段i=1,2,3设状态变量为:sk(S1,S2,S3,S4)，代表第k个变量及以后变量之和，记S1=C，S4=0决策:x1,x2,x3状态转移:Sk+1=Sk-Xk,S4=S3-X3=0,∴S3=X3S3=S2-x2,,S2=S1-x1S1=C阶段效益:v1=x1v2=x22v3=x3F4(S4)=1*例:Maxz=x1.x22.x3F4(S4)=1*决策域:0≤x1≤S1=C,0≤x2≤S2,x3=S3递推:*决策域:0≤x1≤S1=C,0≤x2≤S2,x3=S3*例:MaxZ=x1·x22·x3x1+x2+x3=C(C>0)xi≥0,i=1,2,3*例:MaxZ=x1·x22·x3*****例:MaxF=4x12-x22+2x32+123x1+2x2+x3≤9xi≥0,i=1,2,3解:分三个阶段,设状态变量S0,S1,S2,S3≤9

决策变量:x1,x2,x3顺推解法:设S0=0,3x1=S1,S1+2x2=S2,S2+x3=S3≤9则:0≤x1≤1/3S1,0≤x2≤1/2S2,0≤x3≤S3阶段效益:v1=4x12

v2=-x22v3=2x32+12F0(S0)=0*例:MaxF=4x12-x22+2x32+12F0(*****2.列表法思路:首先把各阶段的状态变量Sk按计算精度ΔS离散为0,ΔS,2ΔS,…(m-1)ΔS,S0共有m+1个分点.先后用表格型式在离散点上求解递推方程,得最优策略.例:MaxF=x1+(x2-3)2+(4-x3)3

x1+x2+x3≤8xi≥0,i=1,2,3ε=1(精度)解:分三个阶段,设S0=0,状态空间为8是连续的

S1=S0+x1,S2=S1+x2,S3=S2+x3Sk=Tk(Sk-1,xk)阶段效益:v1=x1

v2=(x2-3)2v3=(4-x3)3把各Sk按ΔS=1离散顺推计算:

*2.列表法*第一阶段:设S1=x1F1(S1)=Max{v1(S1,x1)}=Max{x1}第二阶段:S2=S1+x2

S2={0…8}f2(S2)=Max{v2(S2,x2)+f1(S1)}S1

012345678f1(S1)

012345678X1*012345678

*第一阶段:设S1=x1S1*41014916250123456784101491625521251017632361176347854596510711

s1f2x2v2f10012