运筹学第六章DP.ppt

第六章 动态规划(Dynamic programming) §1.引言 研究多阶段决策问题 R.E.Bellman 1951年提出动态规划。 1957年出版Dynamic Programming 应用：最优调度、资源分配 最优路径、最优控制 设备更新、库存问题 § 2.多阶段决策问题 例. 某产品从A城运至F城，其间要经过若干 个城镇和若干条道路，路线结构如图所示， 图中给出了每段道路的运费（元），试选 择一条合理的运输路线，使总运费最小？ § 3.基本概念 1.阶段和阶段变量 阶段：过程的划分，包括时间、空间的划分， 阶段数:n 阶段变量：描述阶段的变量用k 表示，k=1,2,…..,n 2.状态和状态变量 状态：描述过程的必要信息。 状态应具有无后效性: 若给定了某阶段状态，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响. 状态变量：描述状态的变量，用s表示。 3.决策和决策变量 决策：决定（选择），从一个阶段的状态到 下一个阶段状态的选择。 决策变量：描述决策的变量，用u表示. 4.策略 策略：决策按顺序构成的序列，用p表示。 7.多阶段过程 对于动态系统， 8.多阶段决策过程 多阶段决策过程就是在各个阶段都要进行决策。 数学描述 §4 动态规划的基本方程 4.1最优性原理 4.2基本方程 设指标函数为 基本方程的解法 ● 顺序解法 (1)基本方程 (2)顺序解法 例 将上例用顺序方程求解。 解 (1)问题的顺序方程 §5 资源分配问题 资源多段分配 分析：该问题的静态规划模型为 该问题的动态规划描述 逆推求解 小结一、基本概念 二、最优性原理三、基本方程 A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E * Operations Research * 1 2 3 4 分析：方案① ：A→B1→C1→E1→F 运费：26元 方案② : A→B3→C3→E3→F 运费：22元 方案③ : A→B2→C1→E2→F 运费：18元 最优方案：方案③ 1 2 k n 1 2 k n ······ 1 2 k n ······ 逆推找决策 划分阶段 顺序定策略 A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E A B3 B1 B2 C1 C2 E