第七章动态规划.ppt

第七章动态规划.pptChapter 7 动态规划(Dynamic Programming)
多阶段决策问题
动态规划的基本概念
动态规划的求解步骤
动态规划模型的建立
运用动态规划求解实际问题
本章主要内容:
引言
动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。1951年,美国数学家贝尔曼( R . Bellman )等人,根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列相互联系的单阶段决策问题,然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之后,提出了解决这类问题的——所谓“最优性原理”,通常称为“贝尔曼最优化原理”,从而创建了解决最优化问题的一种新的方法——动态规划——(Dynamic Programming )。贝尔曼的名著《动态规划》于1957年出版,这成了动态规划的第一本著作。
引言
动态规划的方法,在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用,并且获得了显著的效果。在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等,它是现代企业管理中的一种重要的决策方法。
许多实际问题采用动态规划方法去处理,常比线性规划或非线性规划更加有效。特别对于离散性的问题,由于解析数学无法施展其术,而动态规划的方法就成为一种非常有效的工具。
引言
应特别指出的是,动态规划是解决某一类问题的一种方法,是分析问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习动态规划时,除了对基本概念和方法正确地理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。正如贝尔曼本人所说:“由于动态规划的最优化原理仅仅是一种基本原理,正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间!
本章我们在学习动态规划基本概念、理论和方法的基础上,在通过一些典型的应用问题来说明它的应用。
动态规划的基本概念和基本方法
多阶段决策过程
整个决策过程可按时间或空间顺序分解成若干相互联系的阶段,每一阶段都需作出决策,全部过程的决策是一个决策序列。
多阶段决策过程最优化的目标:
达到整个活动过程的总体效果最优,而非各单个阶段最优的简单总和。
请看如下典型案例——最短路线问题
动态规划的基本概念和基本方法
B1
A
C3
F2
F1
E3
E2
E1
D3
D2
D1
C4
C2
C1
B2
G
第一阶段
第二阶段
第三阶段
第四阶段
第五阶段
第六阶段
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6
6
4
3
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
该点到G点的最短距离
动态规划的基本概念和基本方法
动态规划方法的基本术语:
1、阶段和阶段变量
对整个决策过程的自然划分,通常根据时间顺序或空间特征来划分阶段,以便按阶段的次序逐段解决整个过程的优化问题。阶段变量通常用k表示(k=1,2,3,…,n)。
2、状态与状态变量
每个阶段开始时过程所处的自然状况或客观条件成为该阶段的状态。每个阶段的初始状况又是前一个阶段的终止状况(第一阶段除外)。因此,一旦各个阶段的状态确定之后,整个过程也完全确定。从这个意义上说,多阶段决策过程也是各个状态的演变过程。
动态规划的基本概念和基本方法
状态具有“无后效性”,即当前阶段状态给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关。
一般把描述阶段状态的变量称为状态变量。通常用sk表示第k阶段的状态。第k阶段状态变量的允许取值范围称为阶段k的状态集合。记作 Sk。
3、决策与决策变量
当一个阶段的状态确定后,可以作出不同的决定或选择,从而演变到下一阶段的某个状态,这种决定或选择称为决策。描述决策的变量称为决策变量,通常用uk表示,前面已经说过,决策要依据该阶段的状态,因此通常用uk(sk)表示第k阶段处于状态sk时的决策。决策变量的取值范围称为决策集合,表示为Dk(sk)。
动态规划的基本概念和基本方法
4、策略与子策略
一组有序的决策序列构成一个策略,从第k阶段至第n阶段的一个策略称为后部子策略记为 pk,n →(uk,uk+1,…,un)。
5、状态转移方程
在确定型多阶段决策过程中,一旦某阶段的状态和决策为已知,下一阶段的状态便完全确定,用状态转移方程反映这种状态间的演变规律,写作