运筹学课件第七章动态规划

运筹学动态规划第7章动态规划动态规划是Bellman 在1957年提出的解多阶决策问题的方法，在那个时期，线性规划很流行，它是研究静态问题的，而Bellman 提出的解多阶决策问题的方法适用于动态问题，相对于线性规划研究静态问题，取名动态规划。

动态规划方法应用范围非常广泛，方法也比较简单。

动态规划是将一个多阶决策问题分解为一系列的互相嵌套的一步决策问题，序贯求解使问题得到简化。

动态规划问题按照问题的性质可以分为确定性的和随机性的，按决策变量的和状态变量的取值可以分为离散型的和连续型的。

此外还有依据时间变量连续取值还是离散取值又分为连续时间动态规划问题和离散时间动态规划问题。

本章重点讨论离散时间确定性动态规划问题，包括状态变量和决策变量连续取值和离散取值两种情况。

7.1解多阶决策问题的动态规划法1.多阶决策问题的例(1)最优路径问题—多阶决策问题的例为了直观，先从最优路径问题谈起，它可以看作一个多阶决策过程。

通过最优路径问题的解可以看到用动态规划法解多阶决策问题的基本思想。

考虑图7-1所示的最优路径问题。

一汽车由S 点出发到终点F ，P 和Q 是一些可以通过的点。

图中两点间标出的数字是汽车走这一段路所需的时间(单位为小时)。

最优路径问题是确定一个路径，使汽车沿这条路径由S 点出发达到F 点所用时间最短。

最优路径问题可以看作一个多阶决策问题，由S 到城市甲是第1个阶段，第1个结点P 1或第2个结点Q 1做为第1阶段可以通过的两个站点，由城市甲到城市乙是第2阶段，这个阶段是从P 1或Q 1到P 2或Q 2，由城市乙到城市丙是第3阶段，这个阶段是从P 2或Q 2到P 3或Q 3，由城市丙的P 3或Q 3到F 做为第四阶段。

（2）最优路径问题的解对最优路径问题，存在一个非常明显的原理，即最优路径的一部分还是最优路径。

换句话说，如果SQ P Q F 123是所求的最优路径，那么，汽车从这一路径上的任何一点，例如P 2，出发到F 的最优路径必为P Q F 23。

第七章 动态规划法
计算机科学与技术学院
通过应用范例学习动态规划算法设计策略。
（1）矩阵连乘问题； （2）最长公共子序列； （3）0/1背包问题； （4）流水作业调度；
第七章 动态规划法
是另一种求解最优化问题的算法设计策略 适合求解的问题(多阶段决策问题):
问题的活动过程可以分成若干个阶段,每个阶段包含一 个或多个状态，在任一阶段的决策仅依赖与该阶段的状 态，与该阶段之前的过程如何达到这种状态的方式无关， 这类问题的解决是多阶段的决策过程.
}
7.3 矩阵连乘
穷举法 动态规划法
分析最优解的结构 递归定义最优解的值 自底向上计算最优解的值
对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同
子 在递问归题计的算个时数，最许多多只有子问题n2被 重n 复 计(n算2)。多次。这也是该问题可用动
m[4][m5][=3]m[4[4]+][m4][+5]m[5[5]+][5P]3+P5PP46P=5P56*=1100**2200=*12050=05}000
m=
0 15750 7875 9735 11875 15125
0 2625 4375 712510500
0 750 2500 5375 0 1000 3500
所以，不能在某个阶段直接做出决策
再看一例：
最优子结构：
如果ABEG是A 到G的最短路径，那 么ABE也是A到E的 最短路径。
第七章 动态规划法
例2.数塔问题:设有一个三角形数塔，求一自塔顶到塔底的 路径,且该路径上结点的值的和最大.择12方向还是选择 15方向,取决于分别从12和15出发的两 条子路径上的最大路径值，设他们分别

J 表示留在左岸的仆人人数
初始状态s1是T(3,3)
结束状态sn是 T(0,0)
可达状态有哪些?(3,J) (2,2) (1,1) (0,J) J 3 2 1 0
2013-6-9
A
1
运筹学课件
2
3
I
阶段指标——每阶段选定决策xk后所产生的效益，记
vk= vk(Sk， xk)。
指标函数——各阶段的总效益，记相应于Pkn的指标函数
2013-6-9 运筹学课件
动态规划模型的分类： 以“时间”角度可分成：
离散型和连续型。
从信息确定与否可分成：
确定型和随机型。
从目标函数的个数可分成： 单目标型和多目标型。
2013-6-9 运筹学课件
8.2基本概念与方程
1.基本概念
阶段（Stage）——分步求解的过程，用阶段变量k表示，k=1，，n 状态（State）——每阶段初可能的情形或位置，用状态变 量Sk表示。 按状态的取值是离散或连续，将动态规划问题分为
当 k 3，f Max f v
3 0
3 3
3
4
Max 3x 5s 13.6(0.9s 0.2x )
0
3 3
3
3
3
3
Max 0.28x 17.24s
0
3 3
3
3

x s , f 17.52s ,即第3年初将全部完好机器都 投入高负荷。
指标函数vkn=
v

5
表示第k至5年的总产量；
1
递推公式：f Max f v
6

f 0, k 5, ,1
2013-6-9
运筹学课件

多阶段决策过程图示
决策 决策
决策
第第
第
1
2
n
阶阶
阶
段段
段
动态规划的基本概念
C1 5
2
8 D1 3
4
A
B1 3
4
6
C2
5
58
3
5 6 D2 2
E1 4 3
F
B2 7 C3 4
1
E2
7
8
D3 3
C4 4
1
2
3
4
5
阶段: k=1,2,3,4,5
基本概念（续一）
C1 5
2
8 D1 3
B1 3
4
4
A
6
C2
第七章 动态规划
动态规划简介
多阶段决策过程最优化
多阶段决策过程，是指一类特殊的过程， 它们可以按时间顺序分解成若干个相互联 系的阶段，称为“时段”，在每个时段都 要做决策，全部过程的决策是一个决策序 列。多阶段决策问题也称为序贯决策问题。 多阶段决策问题的目标是要达到整个活动 过程的总体最优。在每个阶段进行决策时 不应仅考虑本阶段最优，尤其应考虑对最 终目标的影响，从而做出对全局来说最优 的决策。 动态规划是符合这种要求的一种决策方法。
C1 5
2
8 D1 3
4
A
B1 3
4
6
C2
5
58
3
5 6
D2
2
E1 4 3
F
B2 7 C3 4
1
E2
7
8
D3 3
C4 4
第二步，k=4，状态变量s4可以取三个值D1，D2，D3。于是
f