文档介绍：动态规划
多阶段决策问题与动态规划
动态规划的基本概念
动态规划的步骤
动态规划的应用
1 求解静态规划问题
2 资源分配问题
3 不确定性采购问题
4 排序问题
动态规划所研究的对象是多阶段决策问题。
所谓多阶段决策问题是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。
每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优。
多阶段决策问题与动态规划
安全过河问题
古代有3位商人各自带了一个仆人外出来到了一个渡口, 渡口只有一条小船每次只能乘2人,仆人私下约定只要岸上的仆人人数超过商人人数,.
问商人如何安全的渡过河去?
一、多阶段决策问题
1. 时间阶段的例子(机器负荷问题)
某厂有1000台机器,现需作一个五年计划,以决定每年安排多少台机器投入高负荷生产(产量大但损耗也大)可使五年的总产量最大。
1
2
3
4
5
S1=1000
x1
x2
x5
x4
x3
s5
v1
v2
v3
v4
v5
s2
s3
s4
多阶段决策问题与动态规划
2. 空间阶段的例子(最短路问题) 如图为一线路网络。现要从A点铺设一条管道到E点,图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路,使总距离最短。
A
E
B1
B2
B3
C1
C2
C3
D1
D2
2
9
5
3
12
2
5
1
5
6
4
6
8
10
13
12
11
14
10
阶段1 阶段2 阶段3 阶段4
动态规划
解决问题的基本特征
1. 动态规划一般解决最值(最优,最大,最小,最长……)问题;
2. 动态规划解决的问题一般是离散的,可以分解(划分阶段)的;
3. 动态规划解决的问题必须包含最优子结构,即可以由(n-1)的最优推导出n的最优
动态规划模型的分类:
以“时间”角度可分成:
离散型和连续型。
从信息确定与否可分成:
确定型和随机型。
从目标函数的个数可分成:
单目标型和多目标型。
阶段(Stage)——分步求解的过程,用阶段变量k表示,k=1,,n
状态(State)——每阶段初可能的情形或位置,用状态变量Sk表示。
按状态的取值是离散或连续,将动态规划问题分为
离散型和连续型。
决策( Decision )——每阶段状态确定后的抉择,即从该状态演变到下阶段某状态的选择,用决策变量xk表示。
状态转移——由Sk转变为Sk+1的规律,记Sk+1=T(Sk, xk)。
策略( Policy)——由各阶段决策组成的序列,记P1n={x1,…, xn},
称Pkn={xk,…, xn}为阶段k至n的后部子策略。
当前状态
以前状态
决策
显然,从上图可以看出,当前状态通过决策,。而以前状态也就决定了当前状态的情况。
K
Sk
Sk+1
Xk
Vk