4.2动态规划的基本原理.ppt

文档介绍：动态规划的
基本原理
对最短路问题:
来源于动态规划的最优化原理
最短路问题的基本方程:
k=4,3,2,1
由后向前迭代
递推公式
最优化原理:
一个过程的最优策略具有这样的性质,即无论初始状态及初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略
对最短路问题:
A
○
○
B1
○
F
○
B2
○
B3
○
C1
○
C2
○
C3
○
D2
○
D1
○
E2
○
E1
则不论前面A如何到达B,B又如何到达C1
上堂课的主要内容:
一、动态规划的基本概念
1、阶段:
指对整个过程的自然划分
,用k表示
2、状态变量sk
Sk ={sk}
第k阶段的状态集合
:第k阶段开始时所处的自然状况
3、决策变量:
当一个阶段的状态确定后,可以作出各种选
择从而演变到下一阶段的某个状态,这种选
择手段称为决策
4、状态转移方程
sk
第k阶段的状态变量
状态转移方程:
5、策略:
由各阶段的决策组成的序列称为策略
——允许策略集合
6、指标函数
用于衡量所选定的策略优劣的数量指标称为指标函数
最优策略
二、最优化原理:
一个过程的最优策略具有这样的性质,即无论初始状态及初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略
对最短路问题:
A
○
○
B1
○
F
○
B2
○
B3
○
C1
○
C2
○
C3
○
D2
○
D1
○
E2
○
E1
则不论前面A如何到达B,B又如何到达C1
对最短路问题:
○
C1
○
A
○
B1
○
E
○
B2
○
B3
○
C2
○
C3
○
D2
○
D1
8
4
5
8
9
6
1
6
10
9
6
7
7
3
8
4
2
3
最短路问题的基本方程:
k=4,3,2,1
例3(生产与存储问题)某工厂生产并销售某种产品。已知今四个月市场需求预测如下表,又每月生产j个单位产品的费用为


每月库存i个单位产品的费用E(i)=(千元),该厂最大库存容量为3个单位,每月最大生产能力为6个单位,计划开始和计划期末库存量都是零,试制定四个月的生产计划,在满足用户需求条件下,使总费用最小。
阶段k=1,2,3,4
状态变量sk=第k个月月初的库存量
i月
1
2
3
4
g(i)需求
2
3
2
4
状态转移方程:
当k=4时,
u4(s4)对应的总费用=生产费+库存费
i月
1
2
3
4
g(i)需求
2
3
2
4
库存费E(i)=,
最大库存容量为3个单位,
最大生产能力为6个单位,
计划开始和计划期末库存量为零
0
1
2
3
4
7
4
3

3
2
6
2
1

1