05 第五章 动态规划.pptx

第1页：第五章动态规划与§1引言

第五章 动态规划（Dynamic programming）　§1. 引言　研究多阶段决策问题。R.E.Bellman 于 1951 年提出动态规划，1957 年出版《Dynamic Programming》。

应用：最优调度、资源分配、最优路径、最优控制、设备更新、库存问题。

第2页：§2多阶段决策问题

§2. 多阶段决策问题　例　某产品从 A 城运至 F 城，其间要经过若干个城镇和若干条道路，路线结构如图所示，图中给出了每段道路的运费（元），试选择一条合理的运输路线，使总运费最小？

第3页：运输方案运费对比

分析：比较若干备选路线的总运费。

最优方案：方案③（总运费 18 元）。

第4页：阶段、阶段变量与状态

§3. 基本概念

1. 阶段和阶段变量

阶段：过程的划分，包括时间、空间的划分，阶段数为 n。阶段变量：描述阶段的变量，用 k 表示，k = 1,2,…,n。

2. 状态和状态变量

状态：描述过程的必要信息。状态应具有无后效性：若给定了某阶段状态，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。

第5页：状态变量

状态变量：描述状态的变量，用 s 表示。第 k 阶段的状态变量记为 s_k，其取值的集合称为状态集合 S_k。

第6页：决策与决策变量

3. 决策和决策变量　决策：决定（选择），从一个阶段的状态到下一个阶段状态的选择。决策变量：描述决策的变量，用 u 表示。

第7页：策略

4. 策略　策略：决策按顺序构成的序列，用 p 表示。从全过程看，策略是由各阶段决策依次排列组成的决策序列。

第8页：

第9页：

第10页：

第11页：多阶段过程

7. 多阶段过程　对于动态系统，过程按 1、2、…、k、…、n 依次推进，前一阶段的输出即为后一阶段的输入。

第12页：多阶段决策过程

8. 多阶段决策过程　多阶段决策过程就是在各个阶段都要进行决策（1、2、…、k、…、n 各阶段依次决策）。

第13页：多阶段过程的数学描述

数学描述：用状态转移方程 s_k+1 = T_k(s_k, u_k) 描述相邻阶段的关系，并给出全过程指标函数。

本页为公式页，源文件文字提取较少，建议对照原课件图片核对。

第14页：§4基本方程与最优性原理

§4 动态规划的基本方程　4.1 最优性原理：作为全过程的最优策略，其后部子过程所构成的子策略也必定是最优策略。

第15页：基本方程与指标函数

4.2 基本方程　设指标函数为各阶段指标函数的和（或积），由此建立动态规划的递推基本方程。

第16页：

第17页：

第18页：基本方程的解法

基本方程的解法：由最后一阶段开始，按基本方程逆序递推，逐段求出各阶段的最优决策与最优指标值。

第19页：动态规划求解步骤

求解步骤示意：划分阶段 → 逆推找决策 → 顺序定策略。

• 划分阶段：把全过程按 1、2、…、k、…、n 划分；
• 逆推找决策：从最后阶段逆序求各阶段最优决策；
• 顺序定策略：由起点开始顺序确定最优策略。

第20页：

第21页：

第22页：

第23页：

第24页：

第25页：§5资源分配问题

§5 资源分配问题　把数量为 a 的某种资源分配给 n 个使用者，使总收益最大，是动态规划的典型应用。

第26页：

第27页：资源分配的逆推求解

逆推求解：按基本方程从最后一个阶段逆序递推，求出各阶段的最优分配量与最优指标值，再顺序回代确定分配方案。

本页计算过程以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对。

第28页：

第29页：

第30页：