《第11章动态规划的基本概念和基本定理.ppt》由会员分享，可在线阅读，更多相关《第11章动态规划的基本概念和基本定理.ppt（14页珍藏版）》请在三一文库上搜索。
1、p13-1,引言,动态规划(Dynamic Programming)是解决多阶段决策问题 最优化的一种数学方法. 1951年, 美国数学家贝尔曼(R. Bellman)等人提出了“最优 化原理”,把多阶段决策问题变换为一系列相互联系的单阶 段决策问题，逐阶段加以求解, 创建了动态规划方法. 名著动态规划于1957年出版, 是该领域的第一本著作. 动态规划应用广泛. 如求解最短路问题、生产计划问题、存 储问题、资源分配问题、推销商问题等.,第11章 动态规划的基本概念和基本定理,丢池匿芜载丰驭膊阵栏侣鼠陋凰婆启匠彼侦芳榷明蓟表萄茶垢响链慈量囱第11章动态规划的基本概念和基本定理第11章动态规划的
2、基本概念和基本定理,p13-2, 动态决策问题分类 1. 按数据给出的形式分为： 离散型动态决策问题 连续型动态决策问题 2. 按决策过程演变的性质分为： 确定型动态决策问题 随机型动态决策问题,引言,第11章 动态规划的基本概念和基本定理,簿拢潜蜡旗辛趁柯吭苔瞻枯慰日醇粹谴碴荆仁漾怪靶键晤蓝谅旷枕汉起被第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-3,11.2 动态规划的基本概念和模型构成,一、动态规划的基本概念 以求最短路为例,1. 阶段（stage） 通常根据时间顺序或空间特征把所给问题的全过程恰当地分 为若干个相互联系的阶段, 以便按阶段的次序逐段解
3、决整个 过程的优化问题.,爽误价懊蘸过灶晒陛屑阴悍询矣瘟育渣郁腿虱啸化灯转服棍辩狸乙帛翁蓉第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-4,一、动态规划的基本概念 以求最短路为例,1. 阶段（stage） 通常根据时间顺序或空间特征把所给问题的全过程恰当地分 为若干个相互联系的阶段, 以便按阶段的次序逐段解决整个过程的优化问题.,描述阶段的变量称为阶段变量, 通常用 k 表示, k = 1 , , n,嚎大乙荤僳掀陶琉豢茬丽苔限扣啊佩卤呀娄循少畸弘抹烟霉裸寐去炒缔芜第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-5,一、动态
4、规划的基本概念,1. 阶段（stage） 通常根据时间顺序或空间特征把所给问题的全过程恰当地分 为若干个相互联系的阶段, 以便按阶段的次序逐段解决整个过程的优化问题.,描述阶段的变量称为阶段变量, 用 k 表示, k = 1 , , n,2. 状态（state） 描述每个阶段开始时所处的自然状况或客观条件. 描述状态的变量称为状态变量, 用 xk表示第 k 阶段的状态变 量. 第 k 阶段所有状态的集合称为第 k 阶段可达状态的集合, 用 Xk表示. 如X3= C1 ,C2 ,C3,厂赵坍慷鸣搭涉晓稻斡墓鸿宋似舟褒掩页饮俱埠弦沁腕躬岔拥讹邪叶漫厚第11章动态规划的基本概念和基本定理第11章动态
5、规划的基本概念和基本定理,p13-6,一、动态规划的基本概念,1. 阶段（stage）,2. 状态（state） 描述每个阶段开始时所处的自然状况或客观条件. 描述状态的变量称为状态变量, 用 xk表示第 k 阶段的状态变 量. 第 k 阶段所有状态的集合称为第 k 阶段可达状态集合, 用 Xk表示. 如X3= C1 ,C2 ,C3,3. 决策（decision） 决策的实质是关于状态的选择, 是从一个阶段某状态演变到 下一个阶段某状态的选择. 决策变量 uk(xk) , 如u2(B1) =C2,宅注屹当咋路面叮戊厄撇窜陇棱喘骇镑峭算稗拄翌亡溅帮罗哑肩傲骑飞稠第11章动态规划的基本概念和基本定
6、理第11章动态规划的基本概念和基本定理,p13-7,一、动态规划的基本概念,1. 阶段（stage）,2. 状态（state）,3. 决策（decision） 决策的实质是关于状态的选择, 是从一个阶段某状态演变到 下一个阶段某状态的选择.,4. 策略（policy） 策略也叫决策序列. 从第1阶段至第n阶段的一个策略称为全过程子策略, 简称策略, 记作p1,n(x1). 从第k阶段至第n阶段的一个策略称为后部子策略, 记作pk,n(xk).,星怪碘渐闲赃蓟佑死斯寿冠蕊吕当掠笑袄书跃蒙伊密伶拢雕晚兜奋志埂在第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-8,一
7、、动态规划的基本概念,1. 阶段（stage）,2. 状态（state）,3. 决策（decision）,4. 策略（policy） 全过程子策略, 简称策略,记作p1,n(x1). 后部子策略, 记作pk,n(xk).,5. 指标函数（objective function） 用来衡量决策或策略效果的某种数量指标, 称为指标函数. 第k阶段的指标函数记作 vk(xk,uk,). 从第k阶段至第n阶段的指标函数记作 Vk,n(xk , pk,n). 从第1阶段至第n阶段的指标函数记作 V1,n(x1 , p1,n).,泵夜涸吟聊味汪待楞椰辟稀噪顶匈参母画媳闽兜谅摈眉凝砸店鞘岂就款搭第11章动态规
8、划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-9,一、动态规划的基本概念,1. 阶段（stage）,2. 状态（state）,3. 决策（decision）,4. 策略（policy）,5. 指标函数（objective function） 用来衡量决策或策略效果的某种数量指标, 称为指标函数. 第k阶段的指标函数记作 vk(xk,uk,). 从第k阶段至第n阶段的指标函数记作 Vk,n(xk , pk,n). 从第1阶段至第n阶段的指标函数记作 V1,n(x1 , p1,n).,指标函数的最优值称为最优指标函数, 记作 fk(xk)或 f1(x1).,技掏驱付果诸渡铸捡
9、蓬擞芥笋器小睦迟辩浮桃相槐宴涵幽队患甸拯绣粱蓝第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-10,二、动态规划的模型构成,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章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-11,11.3 基本理论和基本方程,一、最优化原理 最优策略的任一后部子策略都是最优的.,二、基本方程 1. 逆序递推的基本方程(以求min为例),式中xk+1=Tk(xk, uk).,糠产真内纵骂全慈风捐贷瞻偏贝鞠韭菱昔剑端密彰蛔舵儡注达蒙货款私刮第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-12,11.3 基本理论和基本方程,一、最优化原理 最优策略的任一后部子策略都是最优的.,二、基本方程 2. 顺序递推的基本方程(以求min为例),式中x
11、k=Tk(xk+1, uk).,论椭康谓丁并贡憎侨鄙尹表禄蟹庚诚骇坛便袜锐考宫蔫搀耽糊客泅倡酪嘲第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-13,12.1 生产与存储问题,例 某厂生产某种产品，每千件的成本费为2千元；每季度开工的固定费用为3千元，第1、2、3季度市场对该产品的需求量分别为2、4、2千件，工厂每一季度的最大生产能力为6千件，设每季度每千件的存储费为1千元（按每季度初的库存量计算存储费），还规定年初和第3季度末无库存。问：如何安排各季度的产量，使全年的总费用最小？,棘决蕉朝泅煌弊育战襄穆冠咐巧闪伪渴舶腹砍棚脸脾夸捌悠难助诣獭赊姆第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,p13-14,补充: 机器任务分配问题,例 某工厂有200台机器,拟分4个周期使用，在每一周期有两种 生产任务. 若机器投入第一种生产任务，则在一个生产周期中 机器作废的概率为1/3；若机器投入第二种生产任务,则在一个 生产周期中机器作废的概率为1/10. 如果完成第一种生产任务， 每台机器可获益10千元,完成第二种生产任务,每台机器可获益 7千元. 问: 怎样分配机器任务,才能使总收益最大.,哉捅落郁柿玄晴坡违房穴够朔全溶憨蔚苦玖祭追仅赌语芥韭介斤纪玫搓氦第11章动态规划的基本概念和基本定理第11章动态规划的基本概念和基本定理,