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

运筹学动态规划第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
运筹学课件

m[4][m5][=3]m[4[4]+][m4][+5]m[5[5]+][5P]3+P5PP46P=5P160=0100+*52*02*02*52=55=0305000}
m=
0 15750 7875 9735 11875 15125
0 2625 4375 712510500
0 750 2500 5375 0 1000 3500
的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出 比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐 步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
(2)子问题的重叠性质:每次产生的子问题并不都是新的子问题，有些子问题 被反复计算多次,这种性质称为子问题的重叠性质。
7
7.1 一般方法和基本要素
例2:多段图问题:求从s到t的一条长度最短的路径
(3)多段图的向前递推关系式
cost(k,t) 0 cost(i, j) min {c( j, p) cost(i 1, p)} 1 i k 1
jVi, pVi1 j, pE
其中,cost(i,j)是从i阶段状态j到t的最短路径的长度,i是阶段编号,j 是第i阶段的一个状态编号.
在s[i][j]中记录使得下式取得最小值的k.
m[i, j] min {m[i, k] m[k 1, j] pi pk1p j1}
ik j

7.3 矩阵连乘 A0 A1 A2 A3 A4 A5 3035 3515 155 510 1020 2025
7.3.2 动态规划法求解
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中， 当再次需要解此子问题时，只是简单地用常数时间查看一下结果。