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

p13-1,引言,动态规划(Dynamic Programming)是解决多阶段决策问题 最优化的一种数学方法. 1951年, 美国数学家贝尔曼(R. Bellman)等人提出了“最优 化原理”,把多阶段决策问题变换为一系列相互联系的单阶 段决策问题，逐阶段加以求解, 创建了动态规划方法. 名著动态规划于1957年出版, 是该领域的第一本著作. 动态规划应用广泛. 如求解最短路问题、生产计划问题、存 储问题、资源分配问题、推销商问题等.,第11章 动态规划的基本概念和基本定理,p13-2, 动态决策问题分类 1. 按数据给出的形式分为： 离散型动态决策问题 连续型动态决策问题 2. 按决策过程演变的性质分为： 确定型动态决策问题 随机型动态决策问题,引言,第11章 动态规划的基本概念和基本定理,p13-3,11.2 动态规划的基本概念和模型构成,一、动态规划的基本概念 以求最短路为例,1. 阶段（stage） 通常根据时间顺序或空间特征把所给问题的全过程恰当地分 为若干个相互联系的阶段, 以便按阶段的次序逐段解决整个 过程的优化问题.,p13-4,一、动态规划的基本概念 以求最短路为例,1. 阶段（stage） 通常根据时间顺序或空间特征把所给问题的全过程恰当地分 为若干个相互联系的阶段, 以便按阶段的次序逐段解决整个过程的优化问题.,描述阶段的变量称为阶段变量, 通常用 k 表示, k = 1 , , n,p13-5,一、动态规划的基本概念,1. 阶段（stage） 通常根据时间顺序或空间特征把所给问题的全过程恰当地分 为若干个相互联系的阶段, 以便按阶段的次序逐段解决整个过程的优化问题.,描述阶段的变量称为阶段变量, 用 k 表示, k = 1 , , n,2. 状态（state） 描述每个阶段开始时所处的自然状况或客观条件. 描述状态的变量称为状态变量, 用 xk表示第 k 阶段的状态变 量. 第 k 阶段所有状态的集合称为第 k 阶段可达状态的集合, 用 Xk表示. 如X3= C1 ,C2 ,C3,p13-6,一、动态规划的基本概念,1. 阶段（stage）,2. 状态（state） 描述每个阶段开始时所处的自然状况或客观条件. 描述状态的变量称为状态变量, 用 xk表示第 k 阶段的状态变 量. 第 k 阶段所有状态的集合称为第 k 阶段可达状态集合, 用 Xk表示. 如X3= C1 ,C2 ,C3,3. 决策（decision） 决策的实质是关于状态的选择, 是从一个阶段某状态演变到 下一个阶段某状态的选择. 决策变量 uk(xk) , 如u2(B1) =C2,p13-7,一、动态规划的基本概念,1. 阶段（stage）,2. 状态（state）,3. 决策（decision） 决策的实质是关于状态的选择, 是从一个阶段某状态演变到 下一个阶段某状态的选择.,4. 策略（policy） 策略也叫决策序列. 从第1阶段至第n阶段的一个策略称为全过程子策略, 简称策略, 记作p1,n(x1). 从第k阶段至第n阶段的一个策略称为后部子策略, 记作pk,n(xk).,p13-8,一、动态规划的基本概念,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).,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).,二、动态规划的模型构成,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),p13-11,11.3 基本理论和基本方程,一、最优化原理 最优策略的任一后部子策略都是最优的.,二、基本方程 1. 逆序递推的基本方程(以求min为例),式中xk+1=Tk(xk, uk).,p13-12,11.3 基本理论和基本方程,一、最优化原理 最优策略的任一后部子策略都是最优的.,二、基本方程 2. 顺序递推的基本方程(以求min为例),式中xk=Tk(xk+1, uk).,p13-13,12.1 生产与存储问题,例 某厂生产某种产品，每千件的成本费为2千元；每季度开工的固定费用为3千元，第1、2、3季度市场对该产品的需求量分别为2、4、2千件，工厂每一季度的最大生产能力为6千件，设每季度每千件的存储费为1千元（按每季度初的库存量计算存储费），还规定年初和第3季度末无库存。问：如何安排各季度的产量，使全年的总费用最小？,p13-14,补充: 机器任务分配问题,例 某工厂有200台机器,拟分4个周期使用，在每一周期有两种 生产任务. 若机器投入第一种生产任