第3讲动态规划基本概念和基本定理

《第3讲动态规划基本概念和基本定理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第3讲动态规划基本概念和基本定理教学内容:教学日的:教学重点:教学难点:作业布置:确定性决策过程的定义；最优性定理的内容和证明过程；最优化原理的内容和意义；动态规划基本方程组的建立方法理解动态规划的基本概念，包括确定性决策过程、状态空I'可、决策空I'可、状态转移方程、报酬函数和目标函数；熟练掌握最优性定理的意义，他是分阶段解决问题的前提；熟练掌握动态规划的基本方程及利用动态规划方法解决问题的一般过程；深刻理解动态规划最优性原理的意义，对不同的动态规划模型，能够证明相应的最优性原理；熟练掌握根据最优化原理建立动态规划基本方程组，进而利用动态规划模型求解问题。适当的选取状态变暈，利用最优

2、化原理建立动态规划问题基本方程组。P25Z31)2)3)4)1)2)3)1)2)一、动态规划的基本概念定义由具有下述意义的五重组{X,U,Tk(xk,uk),vk(xk,uk),匕•，几V)}(简记为{X,U,7；y,V})构成的决策过程，称为确定性决策过程(亦称确定性动态规划)。(1)X为状态空I'可。笫R段状态集合为兀，其元素为无，即x,gX,cXo(2)U为决策空间。第殳段允许决策集合为DW其元素为uk(xk)，即uk(Xk)eDk(xk)uUo从耳出发全过程的允许策略为心(冷)={"。(兀)，络(西)，…，柿}，其允许策略集为(x0),即p0jV(x0)€An(%)okm子过程

3、的允许策略为Pwv(%*)={Uk(xk),...»%E_1)}，其允许策略集为(xk),即G心(檢)o(3)卩为状态转移方程：xk+[=Tk(xk,uk)o(4)为第k段处于状态忑釆取决策绚时所得的效果(所得的报酬)，称为报酬函数。它是定义在XxZ)±的函数。(5)目标函数：V0N(x0,Pg(心))=(兀，西，•…，xn)=(心,如,U]，.…,柿_1)%(檢,PkN(耳))=叭(母.，叫，%+l,NZN(&+J)这里，函数屮女对变元匕+川来说要严格单调。二、动态规划的基本定理(最优性定理)N7定理1设久N(x°))=工弓(~,竹)，则允许策略心是{XQ,7>,V}的最优策略的7=

4、0充要条件：对任意0v£vW和心wX。有%,2（兀‘Pon（勺））—OptW^k（兀‘Po&（心））+OptW取（无,PkN（忑））】｝兀g加说）证明必要性：设P；n（X°）是最优策略，则%”（兀0，Pon（兀0））=Opt1%”（兀o?Pon（兀o））】%N（心）—opt｛（兀0、Pok（X。））+Vg（兀，PkN（忑））｝%N代）—opt｛opt｛%衣（兀0‘卩0&（X（）））+%N（无9刃N（兀）｝｝A）/v（心）Pang）=Opt｛V（）k（x（）,PmUo））+opt%（xk,%（“））］｝上述第二行中，匕V（"，加（母））取决于母和pM（Xk）,而无是心及皿（如）决定的，因

5、而在P（）N（Xo）上求最优解，相当于将P（W（XO）分成两部分P（）A.（XO）与加（兀），先在/W母）上求最优值，然后再求这些子最优解在/也（兀）上的最优解，从而推得第三行。充分性：设〃:“（兀0）满足式（221）,贝g对任一加（兀0）丘氐（无）有%n（兀o‘Pon（兀o））=K*（人o‘Po*（珀）））+Vtv（耳,P册（耳））兰％（如，pok（%））+Op%（xk,%（xk））ptN（•*）OptWok（兀（），Pok（兀0））+OptWkN（林，PkN（无））］｝=（兀0、Pon（兀o））故必（心）是最优策略。三.最优化原理最优化原理设％”（无，皿（兀））二£号（9，勺），允

6、许策略几（如）是｛X,U,7>,V｝的最优7=0策略,则对任意R：o

7、））+Op%（兀;，Pw（兀：））ocopt｛v0k（和％（兀o））+optykN（兀,仏（兀））】｝(2.3.3)PZ；）加（忑）POA（凡）式（2.3.3）说明，根据充要条件得知讣“不是最优策略，这与题设矛盾，故得证。四*动态规划的基本方程N-1定理设V（｝N（x0,pQN（Aq））=21vj（xj对任意OSkSN-2»k〈S