运筹学 动态规划.ppt

动态规划是一种研究多阶段决策问题的理论和方法。这种方法把一个多阶段决策问题转化成一系列相互联系的单阶段决策问题来求解。
动态规划主要应用于最短路问题、装载问题、库存问题、资源分配、生产过程最优化问题。
动态规划模型可以分为离散确定性、离散随机性、连续确定性、连续随机性四种决策过程。其中最基本的是离散确定性过程。
第6章动态规划
第6章动态规划
§1 多阶段的决策问题
§2 最优化原理与动态规划的数学
模型
§3 动态规划应用举例
§1 多阶段的决策问题
多阶段决策问题:可以分为若干个互相联系的阶段,在每个阶段分别对应着一组可以选取的决策,当每个阶段的决策选定以后,过程也就随之确定。
多阶段决策问题,就是要在所有可能采取的策略中间选取一个最优的策略,是在预定的标准下得到最好的效果。
[例1] 最短路线问题。设有一旅行者从下图中的A点出发,途中要经过B、C、D等处,最后到达终点E。从A到E有很多条路可以选择,各点之间的距离如图所示,问该旅行者应选择哪一条路线,使从A到E的总路程最短?
A
B3
B2
B1
C3
C2
C1
D2
D1
E
2
2
3
5
1
5
3
5
6
5
7
6
3
3
4
1
4
3
4
3
用穷举法的计算量:
如果从A到E的站点有k个,除A、E之外每站有3个位置则
总共有3k-1×2条路径;
计算各路径长度总共要进行(k+1) 3k-1×2次加法以及3k-
1×2-1次比较。随着 k 的值增加时,需要进行的加法和比较的
次数将迅速增加;
例如当 k=20时,加法次数为 ×1015 次,
比较 ×1014 次。若用1亿次/秒的计算机计算
需要约508天。
[例2] 设有某种机器设备,,若以数量xk用于A,余下的(sk-xk)用于工作B,则该年的预期收入为g(xk)+h(sk-xk).这里g(xk)和h(sk-xk)是已知函数,且g(0)=h(0)=,设机器用于工作A时,一年后能继续使用的完好机器数占年初投入量的a%;若用于B项工作时,一年后能继续使用的完好机器数占年初投入量的b%,即下一年初能继续用于完成这两项工作的设备数为sk+1=axk+b(sk-xk).设第一年初完好的机器总数为s0,问在连续三年内每年应如何分配用于A、B两项工作的机器数,使三年的总收益最大?
[例3] 将一个数c(c>0)分成n个部分c1,c2,...,cn之和,且ci>0(i=1,...,n),问应如何分割使其乘积 为最大?
§2 最优化原理与动态规划的数学模型
动态规划问题的解题思路
动态规划的基本概念
最优化原理与动态规划的数学模型
逆序解法与顺序解法
动态规划模型的分类
动态规划问题的解题思路
基本思路:是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题,从而简化计算过程。
在例1中,这种转化的实现是从终点E出发一步步进行反推,这种算法称为逆序算法。