文档介绍：该【运筹学第章动态规划 】是由【落意心】上传分享，文档一共【82】页，该文档可以免费在线阅读，需要了解更多关于【运筹学第章动态规划 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。运筹学第章动态规划
*
*
动态规划
模型分类
离散确定型
离散随机型
连续确定型
连续随机型
动态规划解决问题的思路独特,在处理某些优化问题时,,并能用创造性的技巧去求解。
其中离散确定性是最基本的,本章主要介绍这种类型的问题,介绍动态规划的基本思想、原理和方法.
*
*
本章主要内容
多阶段决策过程及其问题举例
最短路问题
动态规划的基本概念和基本方程
动态规划应用举例
资源分配问题
背包问题
生产库存问题
………
*
*
动态规划研究的问题-----多阶段决策问题(顺序决策问题)
研究的问题可以在时间或空间上划分为若干个相互联系阶段,称为”时段”。
在每一个时段都需要做出决策,每时段的决策将影响到下一时段的决策,因此决策者每段决策时,不仅要考虑本阶段目标最优,还应考虑最终目标的最优,最终达到整个决策活动的总体目标最优.
1
2
状态
状态
状态
n
…
状态
决策
决策
决策
状态
*
*
动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。
然而,它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。
*
*
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
例1最短路径问题
求从A到E的最短路径。
显然,这种运输网络问题是静态决策问题。但是,按照网络中点的分布,可以把它分为4个阶段,而作为多阶段决策问题来研究。
*
*
第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果,再对它们一一进行比较,求出最优方案。这里从A到E的路程共有3×3×2×1=18条可能的路线,分别算出各条路线的距离,最后进行比较,可知最优路线。显然,当组成交通网络的节点很多时,用穷举法求最优路线的计算工作量将会十分庞大,而且其中包含着许多重复计算.
第二种方法贪心算法,即所谓“局部最优路径”法,是说某人从k出发,他并不顾及全线是否最短,只是选择当前最短途径,“逢近便走”,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是
:1+11+8+5=25
*
*
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
第1阶段
第4阶段
第3阶段
第2阶段
状态
第三种方法是动态规划方法。
*
*
基本思想:如果起点A经过B1,C1,D1而到终点E,则由C1出发经D1到E点这条子路线,是从C1到E的最短路线。所以,寻找最短路线,应该从最后一段开始找,然后往前递推.
设sk:第k阶段初的状态(所处的结点);
xk(sk):在sk状态时第k阶段所作的决策,决定下一个状态的位置;
d(sk,xk):第k阶段,采取策略xk所发生的距离;
fk(sk):在第k阶段,由sk状态开始到终点E的最短距离.
*
*
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f3(C1)=8
f3(C2)=7