20100720动态规划.ppt

动态规划
(Dynamic programming)
动态规划的基本思想
最短路径问题
投资分配问题
背包问题
动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于,它可以把一个n 维决策问题变换为几个一维最优化问题,从而一个一个地去解决。
主要应用于:
最优路径问题、资源分配问题、
投资决策问题、生产计划与库存问题、
货物装载问题、生产过程中的最优控制问题。
返回
前一页
后一页
注意:动态规划是求解某类问题的一种方法,是考察
问题的一种途径,而不是一种算法。必须对具
体问题进行具体分析,运用动态规划的原理和
方法,建立相应的模型,然后再用动态规划方
法去求解。
线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念,应用动态规划方法加以解决。
返回
前一页
后一页
例1、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站,两点之间的连线上的数字表示距离,如图所示。问应该选择什么路线,使总距离最短?
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
最短路径问题
返回
前一页
后一页
方法一:穷举
A到D共6条路,求出所有路长后取最短者即为最佳。
返回
前一页
后一页
工作量大!
方法二:
1、分成三个阶段
2、从第三阶段反推。
方法一共做了12次加法,
而方法二只做了8次加法!
例2最短路问题:给定一个交通网络图如下,其中两点之间的数字表示距离(或花费),试求从A点到E点的最短距离(总费用最小)。
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
5
3
1
3
6
8
7
6
3
6
8
5
3
3
8
4
3
3
5
2
5
6
6
4
返回
前一页
后一页
动态规划的特点:
1、把整个问题分阶段考虑,变成几个子问题。
第三阶段到终点作为第一个子问题,
第二、三阶段与终点组成第二个子问题,
第一、二、三阶段与终点构成第三个子问题。
而第三个子问题就是原来的问题。
2、一个子问题的解决借助它所包含的子问题的解答,
逐级推算。
3、动态规划中运用的原理:
最优路线的一部分也是最优的。
----Bellman最优性原理
(一) 基本概念
1、阶段: 把一个问题的过程,恰当地分为若干个相互联系的阶段,以便于按一定的次序去求解。
2、状态:表示每个阶段开始所处的自然状况或客观条件。第k阶段的终点又是第k+1阶段的起点,记做,称为状态变量或状态。
第k阶段所有可能的状态用状态集合来描述。如例1中四个状态集合为:
一、动态规划的基本思想
返回
前一页
后一页
例1中第三阶段的状态为:
3、决策:表示当处于某一阶段的某个状态时,作出决定从而确定下一阶段的状态,这种决定称为决策。
返回
前一页
后一页
用表示处于状态时的决策,称为决策变量。
例1中
4、状态转移方程:在动态规划中,如果给定了第k阶段的起始状态与决策变量,则第k+1阶段的状态也就确定了,这种关系可用公式

来表示。它表示从K到k+1阶段状态转移的规律,被称为状态转移方程。
例1中的状态转移方程为:
5、策略:对于一个含N个阶段的决策问题,任何一个由初始状态到终止状态的选择称为全过程策略,简称策略。任何一个策略都是由N个决策组成的决策序列。
例1
各阶段的决策为:
策略
从k阶段状态到终止阶段状态的选择称为子过程策略,简称子策略。
记做
是一个子策略
例1