第八章 动态规划.ppt

文档介绍：第八章动态规划
第一节动态规划原理和模型
第二节一维动态规划求解方法
第三节动态规划在经济和管理中的应用
第一节动态规划原理和模型
一、引例与动态规划的基本概念
二、动态规划的原理
三、动态规划模型的建立
“最优化原理”基础上建立起来的。
动态规划是将一个较复杂的多阶段决策问题分解为若干相互关联的较容易求解的子决策问题,而每一个子决策问题都有多种选择,并且当一个子决策问题确定以后,将影响另一个子决策问题,从而影响到整个问题的决策。
一、动态规划的基本概念
动态规划模型分为(1)离散模型;(2)连续模型。本章只讨论与离散模型有关原理和方法。这对连续模型也适用。
下面通过一个多阶段决策过程的例子引入动态规划的基本概念、原理和方法。
.(最短路问题)某运输公司拟将一批货物从A地运往E地,其间的交通系统网络如图8-1所示。图上节点表示地点,边表示两地之间的道路,边上的数字表示两地间的运输费用,求运输费用最低的运输路线。
相关的概念:
A
B1
B2
B3
C1
C2
C3
D1
D2
E
第2阶段
第3阶段
第4阶段
第1阶段
5
4
12
3
3
11
3
6
4
4
4
1
6
5
7
9
8
(1) 阶段
将所给问题的过程,按时间或空间特征分解成若干互相联系的阶段,按次序去求每阶段的解,用字母k表示阶段变量。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
第2阶段
第3阶段
第4阶段
第1阶段的状态
第2阶段的状态
第1阶段
5
4
12
3
3
11
3
6
4
4
4
1
6
5
7
9
s1状态A ,s2?
S1={A},S2={B1、B2、B3},S3={C1、C2、C3},S4={D1、D2}。
8
(2)状态
状态就是阶段的起始位置。通常一个阶段包含若干个状态。第k阶段的状态就是该阶段所有始点的集合。描述各阶段状态的变量称为状态变量。常用sk表示第k阶段的状态变量。状态变量的取值集合称为状态集合,用Sk表示。
3)决策
决策是某阶段状态给定之后,从该状态演变到下一阶段某一状态的选择。表示决策的变量称为决策变量,用uk(sk)表示第阶段,状态为sk时的决策变量,它是状态变量的函数。实际问题中,决策变量的选取往往受到某些条件的影响而限制于某一范围,此范围称为允许决策集合。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
第2阶段
第3阶段
第4阶段
第1阶段的状态
第2阶段的状态
第1阶段
5
4
12
3
3
11
3
6
4
4
4
1
6
5
7
9
,u2(B1)就表示第2阶段状态为B1时的决策变量(它或等于C1或等于C3),即,从第2阶段的状态B1出发,可到达下一阶段的C1或者C3,所以这一阶段的允许决策集D2(B1)={C1,C3}。
8
4)策略
各阶段决策确定后,组成的一个有序的决策序列就构成了一个策略。
称为全过程的一个策略,简称策略。
称为由第k阶段开始到最后阶段止的一个子策略,简称后部子策略。
使整个问题到达最优效果的策略称为最优策略。
动态规划方法就是要从允许策略集中找出最优策略。