动态规划的基本概念和基本定

《动态规划的基本概念和基本定》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、引言动态规划(DynamicProgramming)是解决多阶段决策问题最优化的一种数学方法.1951年,美国数学家贝尔曼(R.Bellman)等人提出了“最优化原理”,把多阶段决策问题变换为一系列相互联系的单阶段决策问题，逐阶段加以求解,创建了动态规划方法.名著《动态规划》于1957年出版,是该领域的第一本著作.动态规划应用广泛.如求解最短路问题、生产计划问题、存储问题、资源分配问题、推销商问题等.第11章动态规划的基本概念和基本定理1动态决策问题分类1.按数据给出的形式分为：离散型动态决策问题连续型动态决策问题2.按决策过

2、程演变的性质分为：确定型动态决策问题随机型动态决策问题引言第11章动态规划的基本概念和基本定理2AB1B2B3C1C2C3D1D2E243952351715364275§11.2动态规划的基本概念和模型构成一、动态规划的基本概念以求最短路为例1.阶段（stage）通常根据时间顺序或空间特征把所给问题的全过程恰当地分为若干个相互联系的阶段,以便按阶段的次序逐段解决整个过程的优化问题.3AB1B2B3C1C2C3D1D2E243952351715364275一、动态规划的基本概念以求最短路为例1.阶段（stage）通常根据时间顺序或

3、空间特征把所给问题的全过程恰当地分为若干个相互联系的阶段,以便按阶段的次序逐段解决整个过程的优化问题.描述阶段的变量称为阶段变量,通常用k表示,k=1,…,n4一、动态规划的基本概念1.阶段（stage）通常根据时间顺序或空间特征把所给问题的全过程恰当地分为若干个相互联系的阶段,以便按阶段的次序逐段解决整个过程的优化问题.描述阶段的变量称为阶段变量,用k表示,k=1,…,n2.状态（state）描述每个阶段开始时所处的自然状况或客观条件.描述状态的变量称为状态变量,用xk表示第k阶段的状态变量.第k阶段所有状态的集合称为第k阶段可达

4、状态的集合,用Xk表示.如X3={C1,C2,C3}5一、动态规划的基本概念1.阶段（stage）2.状态（state）描述每个阶段开始时所处的自然状况或客观条件.描述状态的变量称为状态变量,用xk表示第k阶段的状态变量.第k阶段所有状态的集合称为第k阶段可达状态集合,用Xk表示.如X3={C1,C2,C3}3.决策（decision）决策的实质是关于状态的选择,是从一个阶段某状态演变到下一个阶段某状态的选择.决策变量—uk(xk),如u2(B1)=C26一、动态规划的基本概念1.阶段（stage）2.状态（state）3.决策（d

5、ecision）决策的实质是关于状态的选择,是从一个阶段某状态演变到下一个阶段某状态的选择.4.策略（policy）策略也叫决策序列.从第1阶段至第n阶段的一个策略称为全过程子策略,简称策略,记作p1,n(x1).从第k阶段至第n阶段的一个策略称为后部子策略,记作pk,n(xk).7一、动态规划的基本概念1.阶段（stage）2.状态（state）3.决策（decision）4.策略（policy）全过程子策略,简称策略,记作p1,n(x1).后部子策略,记作pk,n(xk).5.指标函数（objectivefunction）用来衡

6、量决策或策略效果的某种数量指标,称为指标函数.第k阶段的指标函数记作vk(xk,uk,).从第k阶段至第n阶段的指标函数记作Vk,n(xk,pk,n).从第1阶段至第n阶段的指标函数记作V1,n(x1,p1,n).8一、动态规划的基本概念1.阶段（stage）2.状态（state）3.决策（decision）4.策略（policy）5.指标函数（objectivefunction）用来衡量决策或策略效果的某种数量指标,称为指标函数.第k阶段的指标函数记作vk(xk,uk,).从第k阶段至第n阶段的指标函数记作Vk,n(xk,pk,n

7、).从第1阶段至第n阶段的指标函数记作V1,n(x1,p1,n).指标函数的最优值称为最优指标函数,记作fk(xk)或f1(x1).9二、动态规划的模型构成1.正确选择阶段变量k;2.正确选择状态变量xk——要保证无后效性,即某阶段的状态一旦确定,则此后过程的演变不受此前各状态及决策的影响;3.正确选择决策变量uk;4.列出状态转移方程xk+1=Tk(xk,uk);5.列出指标函数Vk,n——要满足按阶段可分性,并满足递推关系Vk,n=Vk,n(xk,pk,n)=vk(xk,uk,)+Vk+1,n(xk+1,pk+1,n)10§11

8、.3基本理论和基本方程一、最优化原理最优策略的任一后部子策略都是最优的.二、基本方程1.逆序递推的基本方程(以求min为例)x11u1x2u22x3...xkukkxk+1...xnunnxn+1f1(x1)f2(x2)fk(xk)f