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

《动态规划的基本概念和基本定.ppt》由会员分享，可在线阅读，更多相关《动态规划的基本概念和基本定.ppt（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 运筹学 引言引言引言引言 动态规划动态规划动态规划动态规划(Dynamic ProgrammingDynamic Programming)是解决是解决是解决是解决多阶段决策多阶段决策多阶段决策多阶段决策问题问题问题问题 最优化的一种数学方法最优化的一种数学方法最优化的一种数学方法最优化的一种数学方法.19511951年年年年,美国数学家美国数学家美国数学家美国数学家贝尔曼贝尔曼贝尔曼贝尔曼(R.Bellman)(R.Bellman)等人提出了等人提出了等人提出了等人提出了“最优最优最优最优 化原理化原理化原理化原理”,把把把把多阶段决策多阶段决策多阶段决策多阶段决策问题问题问题问题变换为变换

2、为变换为变换为一系列相互联系的一系列相互联系的一系列相互联系的一系列相互联系的单阶单阶单阶单阶 段决策段决策段决策段决策问题，逐阶段加以求解问题，逐阶段加以求解问题，逐阶段加以求解问题，逐阶段加以求解,创建了创建了创建了创建了动态规划方法动态规划方法动态规划方法动态规划方法.名著名著名著名著动态规划动态规划动态规划动态规划于于于于19571957年出版年出版年出版年出版,是该领域的第一本著作是该领域的第一本著作是该领域的第一本著作是该领域的第一本著作.动态规划应用广泛动态规划应用广泛动态规划应用广泛动态规划应用广泛.如求解最短路问题、生产计划问题、存如求解最短路问题、生产计划问题、存如求解最短

3、路问题、生产计划问题、存如求解最短路问题、生产计划问题、存 储问题、资源分配问题、推销商问题等储问题、资源分配问题、推销商问题等储问题、资源分配问题、推销商问题等储问题、资源分配问题、推销商问题等.第第11章章 动态规划的基本概念和基本定理动态规划的基本概念和基本定理1 1 运筹学 动态决策问题分类动态决策问题分类动态决策问题分类动态决策问题分类 1.1.按按按按数据给出的形式数据给出的形式数据给出的形式数据给出的形式分为：分为：分为：分为：离散型离散型离散型离散型动态决策问题动态决策问题动态决策问题动态决策问题 连续型连续型连续型连续型动态决策问题动态决策问题动态决策问题动态决策问题 2.2

4、.按按按按决策过程演变的性质决策过程演变的性质决策过程演变的性质决策过程演变的性质分为：分为：分为：分为：确定型确定型确定型确定型动态决策问题动态决策问题动态决策问题动态决策问题 随机型随机型随机型随机型动态决策问题动态决策问题动态决策问题动态决策问题引言引言引言引言第第11章章 动态规划的基本概念和基本定理动态规划的基本概念和基本定理2 2 运筹学 A AB B1 1B B2 2B B3 3C C1 1C C2 2C C3 3D D1 1D D2 2E E2 24 43 39 95 52 23 35 51 17 71 15 53 36 64 42 27 75 511.2 动态规划的基本概念和

5、模型构成动态规划的基本概念和模型构成一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念 以求以求以求以求最短路最短路最短路最短路为例为例为例为例1.1.阶段阶段阶段阶段（stagestage）通常根据通常根据通常根据通常根据时间顺序时间顺序时间顺序时间顺序或或或或空间特征空间特征空间特征空间特征把所给问题的全过程恰当地分把所给问题的全过程恰当地分把所给问题的全过程恰当地分把所给问题的全过程恰当地分 为若干个相互联系的阶段为若干个相互联系的阶段为若干个相互联系的阶段为若干个相互联系的阶段,以便按阶段的次序逐段解决整个以便按阶段的次序逐段解决整个以便按阶段的次

6、序逐段解决整个以便按阶段的次序逐段解决整个 过程的优化问题过程的优化问题过程的优化问题过程的优化问题.3 3 运筹学 A AB B1 1B B2 2B B3 3C C1 1C C2 2C C3 3D D1 1D D2 2E E2 24 43 39 95 52 23 35 51 17 71 15 53 36 64 42 27 75 5一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念 以求以求以求以求最短路最短路最短路最短路为例为例为例为例1.1.阶段阶段阶段阶段（stagestage）通常根据通常根据通常根据通常根据时间顺序时间顺序时间顺序时间顺序或或或或

7、空间特征空间特征空间特征空间特征把所给问题的全过程恰当地分把所给问题的全过程恰当地分把所给问题的全过程恰当地分把所给问题的全过程恰当地分 为若干个相互联系的阶段为若干个相互联系的阶段为若干个相互联系的阶段为若干个相互联系的阶段,以便按阶段的次序逐段解决整个以便按阶段的次序逐段解决整个以便按阶段的次序逐段解决整个以便按阶段的次序逐段解决整个过程的优化问题过程的优化问题过程的优化问题过程的优化问题.描述阶段的变量称为描述阶段的变量称为描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量阶段变量阶段变量,通常用通常用通常用通常用 k k 表示表示表示表示,k=1,n,k=1,n4 4 运筹学 一、动

8、态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念1.1.阶段阶段阶段阶段（stagestage）通常根据通常根据通常根据通常根据时间顺序时间顺序时间顺序时间顺序或或或或空间特征空间特征空间特征空间特征把所给问题的全过程恰当地分把所给问题的全过程恰当地分把所给问题的全过程恰当地分把所给问题的全过程恰当地分 为若干个相互联系的阶段为若干个相互联系的阶段为若干个相互联系的阶段为若干个相互联系的阶段,以便按阶段的次序逐段解决整个以便按阶段的次序逐段解决整个以便按阶段的次序逐段解决整个以便按阶段的次序逐段解决整个过程的优化问题过程的优化问题过程的优化问题过程的优化问题.

9、描述描述描述描述阶段阶段阶段阶段的变量称为的变量称为的变量称为的变量称为阶段变量阶段变量阶段变量阶段变量,用用用用 k k 表示表示表示表示,k=1,n,k=1,n2.2.状态状态状态状态（statestate）描述每个阶段开始时所处的自然状况或客观条件描述每个阶段开始时所处的自然状况或客观条件描述每个阶段开始时所处的自然状况或客观条件描述每个阶段开始时所处的自然状况或客观条件.描述描述描述描述状态状态状态状态的变量称为的变量称为的变量称为的变量称为状态变量状态变量状态变量状态变量,用用用用 x xk k表示第表示第表示第表示第 k k 阶段的状态变阶段的状态变阶段的状态变阶段的状态变 量量量

10、量.第第第第 k k 阶段所有状态的集合称为第阶段所有状态的集合称为第阶段所有状态的集合称为第阶段所有状态的集合称为第 k k 阶段阶段阶段阶段可达状态的集合可达状态的集合可达状态的集合可达状态的集合,用用用用 X Xk k表示表示表示表示.如如如如X X3 3=C C1 1,C,C2 2,C,C3 3 5 5 运筹学 一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念1.1.阶段阶段阶段阶段（stagestage）2.2.状态状态状态状态（statestate）描述每个阶段开始时所处的自然状况或客观条件描述每个阶段开始时所处的自然状况或客观条件描述每个阶

11、段开始时所处的自然状况或客观条件描述每个阶段开始时所处的自然状况或客观条件.描述描述描述描述状态状态状态状态的变量称为的变量称为的变量称为的变量称为状态变量状态变量状态变量状态变量,用用用用 x xk k表示第表示第表示第表示第 k k 阶段的状态变阶段的状态变阶段的状态变阶段的状态变 量量量量.第第第第 k k 阶段所有状态的集合称为第阶段所有状态的集合称为第阶段所有状态的集合称为第阶段所有状态的集合称为第 k k 阶段阶段阶段阶段可达状态集合可达状态集合可达状态集合可达状态集合,用用用用 X Xk k表示表示表示表示.如如如如X X3 3=C C1 1,C,C2 2,C,C3 3 3.3.

12、决策决策决策决策（decisiondecision）决策的决策的决策的决策的实质是关于实质是关于实质是关于实质是关于状态的选择状态的选择状态的选择状态的选择,是从一个阶段某状态演变到是从一个阶段某状态演变到是从一个阶段某状态演变到是从一个阶段某状态演变到 下一个阶段某状态的选择下一个阶段某状态的选择下一个阶段某状态的选择下一个阶段某状态的选择.决策变量决策变量决策变量决策变量 u uk k(x(xk k),),如如如如u u2 2(B(B1 1)=C)=C2 26 6 运筹学 一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念1.1.阶段阶段阶段阶段（st

13、agestage）2.2.状态状态状态状态（statestate）3.3.决策决策决策决策（decisiondecision）决策的决策的决策的决策的实质是关于实质是关于实质是关于实质是关于状态的选择状态的选择状态的选择状态的选择,是从一个阶段某状态演变到是从一个阶段某状态演变到是从一个阶段某状态演变到是从一个阶段某状态演变到 下一个阶段某状态的选择下一个阶段某状态的选择下一个阶段某状态的选择下一个阶段某状态的选择.4.4.策略策略策略策略（policypolicy）策略也叫策略也叫策略也叫策略也叫决策序列决策序列决策序列决策序列.从第从第从第从第1 1阶段阶段阶段阶段至至至至第第第第n n阶

14、段阶段阶段阶段的一个策略称为的一个策略称为的一个策略称为的一个策略称为全过程全过程全过程全过程子策略子策略子策略子策略,简称简称简称简称策略策略策略策略,记作记作记作记作p p1,n1,n(x(x1 1).).从第从第从第从第k k阶段阶段阶段阶段至至至至第第第第n n阶段阶段阶段阶段的一个策略称为的一个策略称为的一个策略称为的一个策略称为后部子策略后部子策略后部子策略后部子策略,记作记作记作记作p pk,nk,n(x(xk k).).7 7 运筹学 一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念1.1.阶段阶段阶段阶段（stagestage）2.2.

15、状态状态状态状态（statestate）3.3.决策决策决策决策（decisiondecision）4.4.策略策略策略策略（policypolicy）全过程全过程全过程全过程子策略子策略子策略子策略,简称简称简称简称策略策略策略策略,记作记作记作记作p p1,n1,n(x(x1 1).).后部子策略后部子策略后部子策略后部子策略,记作记作记作记作p pk,nk,n(x(xk k).).5.5.指标函数指标函数指标函数指标函数（objective functionobjective function）用来用来用来用来衡量衡量衡量衡量决策决策决策决策或或或或策略策略策略策略效果效果效果效果的某种

16、的某种的某种的某种数量指标数量指标数量指标数量指标,称为称为称为称为指标函数指标函数指标函数指标函数.第第第第k k阶段的指标函数记作阶段的指标函数记作阶段的指标函数记作阶段的指标函数记作 v vk k(x(xk k,u,uk k,).).从第从第从第从第k k阶段阶段阶段阶段至至至至第第第第n n阶段阶段阶段阶段的的的的指标函数记作指标函数记作指标函数记作指标函数记作 V Vk,nk,n(x(xk k ,p pk,nk,n).).从第从第从第从第1 1阶段阶段阶段阶段至至至至第第第第n n阶段阶段阶段阶段的的的的指标函数记作指标函数记作指标函数记作指标函数记作 V V1,n1,n(x(x1

17、1,p,p1,n1,n).).8 8 运筹学 一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念一、动态规划的基本概念1.1.阶段阶段阶段阶段（stagestage）2.2.状态状态状态状态（statestate）3.3.决策决策决策决策（decisiondecision）4.4.策略策略策略策略（policypolicy）5.5.指标函数指标函数指标函数指标函数（objective functionobjective function）用来用来用来用来衡量衡量衡量衡量决策决策决策决策或或或或策略策略策略策略效果效果效果效果的某种的某种的某种的某种数量指标数量指标数量指标数量指

18、标,称为称为称为称为指标函数指标函数指标函数指标函数.第第第第k k阶段的指标函数记作阶段的指标函数记作阶段的指标函数记作阶段的指标函数记作 v vk k(x(xk k,u,uk k,).).从第从第从第从第k k阶段阶段阶段阶段至至至至第第第第n n阶段阶段阶段阶段的的的的指标函数记作指标函数记作指标函数记作指标函数记作 V Vk,nk,n(x(xk k ,p pk,nk,n).).从第从第从第从第1 1阶段阶段阶段阶段至至至至第第第第n n阶段阶段阶段阶段的的的的指标函数记作指标函数记作指标函数记作指标函数记作 V V1,n1,n(x(x1 1,p,p1,n1,n).).指标函数的指标函数

19、的指标函数的指标函数的最优值最优值最优值最优值称为称为称为称为最优指标函数最优指标函数最优指标函数最优指标函数,记作记作记作记作 f fk k(x(xk k)或或或或 f f1 1(x(x1 1).).9 9 运筹学 二、动态规划的模型构成二、动态规划的模型构成二、动态规划的模型构成二、动态规划的模型构成1.1.正确选择阶段变量正确选择阶段变量正确选择阶段变量正确选择阶段变量k;k;2.2.正确选择状态变量正确选择状态变量正确选择状态变量正确选择状态变量x xk k要保证要保证要保证要保证无后效性无后效性无后效性无后效性,即某阶段的状即某阶段的状即某阶段的状即某阶段的状 态一旦确定态一旦确定态

20、一旦确定态一旦确定,则此后过程的演变不受此前各状态及决策的则此后过程的演变不受此前各状态及决策的则此后过程的演变不受此前各状态及决策的则此后过程的演变不受此前各状态及决策的 影响影响影响影响;3.3.正确选择决策变量正确选择决策变量正确选择决策变量正确选择决策变量u uk k;4.4.列出状态转移方程列出状态转移方程列出状态转移方程列出状态转移方程x xk+1k+1=T=Tk k(x(xk k,u,uk k););5.5.列出指标函数列出指标函数列出指标函数列出指标函数V Vk,nk,n要满足要满足要满足要满足按阶段可分性按阶段可分性按阶段可分性按阶段可分性,并满足递推关并满足递推关并满足递推

21、关并满足递推关系系系系 V Vk,nk,n=V=Vk,nk,n(x(xk k,p,pk,nk,n)=)=v vk k(x(xk k,u,uk,k,)+)+V Vk+1,nk+1,n(x(xk+1k+1,p,pk+1,nk+1,n)1010 运筹学 11.3 基本理论和基本方程基本理论和基本方程一、最优化原理一、最优化原理一、最优化原理一、最优化原理 最优策略的任一后部子策略都是最优的最优策略的任一后部子策略都是最优的最优策略的任一后部子策略都是最优的最优策略的任一后部子策略都是最优的.二、基本方程二、基本方程二、基本方程二、基本方程 1.1.逆序逆序逆序逆序递推的基本方程递推的基本方程递推的基

22、本方程递推的基本方程(以求以求以求以求minmin为例为例为例为例)x1 1u1 x2 u2 2 x3 .xk uk k xk+1 .xn un n xn+1 f1(x1)f2(x2)fk(xk)fn(xn)式中式中式中式中x xk+1k+1=T=Tk k(x(xk k,u,uk k).).1111 运筹学 11.3 基本理论和基本方程基本理论和基本方程一、最优化原理一、最优化原理一、最优化原理一、最优化原理 最优策略的任一后部子策略都是最优的最优策略的任一后部子策略都是最优的最优策略的任一后部子策略都是最优的最优策略的任一后部子策略都是最优的.二、基本方程二、基本方程二、基本方程二、基本方程

23、 2.2.顺序顺序顺序顺序递推的基本方程递推的基本方程递推的基本方程递推的基本方程(以求以求以求以求minmin为例为例为例为例)式中式中式中式中x xk k=T=Tk k(x(xk+1k+1,u,uk k).).xk+1 x1 1u1 x2 u2 2 x3 .xk uk k.xn un n xn+1 f1(x2)f2(x3)fk(xk+1)fn(xn+1)1212 运筹学 12.1 12.1 生产与存储问题生产与存储问题生产与存储问题生产与存储问题例例例例 某厂生产某种产品，每千件的成本费为某厂生产某种产品，每千件的成本费为某厂生产某种产品，每千件的成本费为某厂生产某种产品，每千件的成本费为

24、2 2千元；每季千元；每季千元；每季千元；每季度开工的固定费用为度开工的固定费用为度开工的固定费用为度开工的固定费用为3 3千元，第千元，第千元，第千元，第1 1、2 2、3 3季度市场对该产季度市场对该产季度市场对该产季度市场对该产品的需求量分别为品的需求量分别为品的需求量分别为品的需求量分别为2 2、4 4、2 2千件，工厂每一季度的最大千件，工厂每一季度的最大千件，工厂每一季度的最大千件，工厂每一季度的最大生产能力为生产能力为生产能力为生产能力为6 6千件，设每季度每千件的存储费为千件，设每季度每千件的存储费为千件，设每季度每千件的存储费为千件，设每季度每千件的存储费为1 1千元千元千元

25、千元（按每季度初的库存量计算存储费），还规定年初和第（按每季度初的库存量计算存储费），还规定年初和第（按每季度初的库存量计算存储费），还规定年初和第（按每季度初的库存量计算存储费），还规定年初和第3 3季度末无库存。问：如何安排各季度的产量，使全年季度末无库存。问：如何安排各季度的产量，使全年季度末无库存。问：如何安排各季度的产量，使全年季度末无库存。问：如何安排各季度的产量，使全年的总费用最小？的总费用最小？的总费用最小？的总费用最小？1313 运筹学 补充补充补充补充:机器任务分配问题机器任务分配问题机器任务分配问题机器任务分配问题例例例例 某工厂有某工厂有某工厂有某工厂有200200台机

26、器台机器台机器台机器,拟分拟分拟分拟分4 4个周期使用，在每一周期有两种个周期使用，在每一周期有两种个周期使用，在每一周期有两种个周期使用，在每一周期有两种生产任务生产任务生产任务生产任务.若机器投入第一种生产任务，则在一个生产周期中若机器投入第一种生产任务，则在一个生产周期中若机器投入第一种生产任务，则在一个生产周期中若机器投入第一种生产任务，则在一个生产周期中机器作废的概率为机器作废的概率为机器作废的概率为机器作废的概率为1/31/3；若机器投入第二种生产任务；若机器投入第二种生产任务；若机器投入第二种生产任务；若机器投入第二种生产任务,则在一个则在一个则在一个则在一个生产周期中机器作废的概率为生产周期中机器作废的概率为生产周期中机器作废的概率为生产周期中机器作废的概率为1/10.1/10.如果完成第一种生产任务，如果完成第一种生产任务，如果完成第一种生产任务，如果完成第一种生产任务，每台机器可获益每台机器可获益每台机器可获益每台机器可获益1010千元千元千元千元,完成第二种生产任务完成第二种生产任务完成第二种生产任务完成第二种生产任务,每台机器可获益每台机器可获益每台机器可获益每台机器可获益7 7千元千元千元千元.问问问问:怎样分配机器任务怎样分配机器任务怎样分配机器任务怎样分配机器任务,才能使总收益最大才能使总收益最大才能使总收益最大才能使总收益最大.1414