管理运筹学 第五章 动态规划

主要内容

动态规划的举例
基本概念与原理
动态规划的应用
第一节 动态规划的举例
最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。
B 2 1 1 6 4 A 3 2 4 B3 7 3 5 1 8 C3 1 6 D 2 3 B2 7 2 C2 7 5 6 E C 1 6 D 1 10 8
（4） . 能够正确地写出状态转移方程，至少要能正确反映状态 转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变 量 uk 一经确定，第 k+1 段的状态变量 sk+1 的值也就完全确定，即 有sk+1=Tk(sk ,uk)
（ 5 ）．根据题意 , 正确地构造出目标与变量的函数关系 —— 目标 函数，目标函数应满足下列性质： 1) 可分性，即对于所有k 后部子过程，其目标函数仅取决于状 态sk及其以后的决策 uk ,uk+1,┈,un,就是说它是定义在全过程和 所有后部子过程上的数量函数。
阶段1 本阶段始 点(状态) A 本阶段各终点（决策） B1
4+12=16
B2
B3
B4
2+12=14
到E的最 短距离
14
本阶段最优终 点(最优决策) B4
3+13=16 3+14=17
最后，可以得到：从A到E的最短路径为A B4 C3 D1 E。
以上计算过程及结果，可用下图表示，可以看到，以上方法不 仅得到了从 A到E的最短路径，同时，也得到了从图中任一点到 E 的 最短路径。
比较 1.3726075472977×1014 次。 若用1亿次/秒的计算机计算需要约508天。
讨论： 1、以上求从 A到E 的最短路径问题，可以转化为四个性质完全 相同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短 路径问题。 第四阶段：两个始点D1和D2，终点只有一个； 阶段4 本阶段始点 本阶段各终点（决策） （状态） E 到E的最短距离 本阶段最优终点 （最优决策)
1)要能够正确地描述受控过程的变化特征。 2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以 后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无 后效性，就不能作为状态变量来构造动态规划的模型。 3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测 算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累 计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线 性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的

状态转移方程 sk+1=Tk(sk, xk)：某一状态以及该状态下的决策， 与下一状态之间的函数关系。

指标函数

阶段指标函数vk(sk, xk)：从状态sk出发，选择决策xk所产 生的第k阶段指标。
过程指标函数Vk,n(sk, xk, xk+1,…, xn)：从状态sk出发， 选择决策xk,xk+1, …, xn所产生的过程指标。
12 B1 14 A 3 2 4 3 B2 2 4 8 3 1 C3 1 11 6 12
2
6 1
C1 6 11 7 5
8
10 D1 10 0 E D2 6
13 4 7
C2
6
B3
14 7 5
B4
12
以上过程，仅用了22次加法，计算效率远高于穷举法。
从最后一个阶段开始，从终点向始点方向逐阶段逆推，找 出各点到终点的最短路，当逆推到始点时，也即找到了从始点 到终点的全过程的最短路，这种从后向前逆推的方法叫逆序解 法。
2.基本方程
最优指标函数f k(sk)：从状态sk出发，对所有的策略Pk,n，过程 指标Vk,n的最优值，即
f k (sk )
opt
xk Dk ( sk )
{Vk ,n ( s k , Pk ,n )}
对于可加性指标函数，上式可以写为
f k ( sk )
opt
xk Dk ( sk )
{vk ( sk , xk ) f k 1 ( sk 1 )}
阶段2 本阶段始点 （状态） B1 B2 B3 B4 本阶段各终点（决策） C1 2+12=14 4+12=16 4+12=16 7+12=19 C2 1+11=12 7+11=18 8+11=19 5+11=16 C3 6+11=17 2+11=13 3+11=14 1+11=12
到E的最 短距离
第二节 基本概念与原理

基本概念 基本方程 最优化原理 动态规划步骤
1.基本概念

阶段 k ：把所给问题的过程恰当地分成若干相互联系的段 落，以便按照一定次序求解，描述阶段的变量称为阶段变 量。表示决策顺序的离散的量，阶段可以按时间或空间划 分。

状态sk：能确定地表示决策过程当前特征的量。状态可以是数量， 也可以是字符，数量状态可以是连续的，也可以是离散的。也就 是每阶段初始的出发点，在最短路问题中，各个节点就是状态； 生产库存问题中，库存量是状态；物资分配问题中，剩余的物资 量是状态。
第三节 动态规划的应用

背包问题 资源分配问题 设备负荷分配问题


动态规划要求过程指标具有可分离性，
即： Vk,n(sk, xk, xk+1, …, xn) =
vk(sk,xk)+Vk+1(sk+1,xk+1, …, xn)
称指标具有可加性， 或 Vk,n(sk, xk, xk+1, …, xn) = vk(sk, xk)×Vk+1(sk+1, xk+1, …, xn) 称指标具有可乘性。
C1 C2 C3
8+10=18 7+10=17 1+10=11
6+6=12 5+6=11 6+6=12
12 11 11
D2 D2 D1
分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。
第二阶段：有 4 个始点 B1,B2,B3,B4 ，终点有 C1,C2,C3 。对始点 和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路 径问题：
k 1,2, , n
对于可乘性指标函数，上式可以写为
f k ( sk )
opt
xk Dk ( sk )
{vk ( sk , xk ) f k 1 ( sk 1 )}
k 1,2,, n
上式中“opt”表示“max”或“min”。 以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。
第六章 动态规划
动态规划是解决多阶段决策过程最优化问题的一种方法， 这种方法把困难的多阶段决策问题变换成一系列相互联系较 容易的单阶段问题，解决了这一系列较容易的单阶段问题， 也就解决了这个困难的多阶段决策问题。 用动态规划可以解决管理中的最短路问题、装载问题、库 存问题、资源分配问题、生产过程最优化问题等。 动态规划是求解一类问题的方法，是解决问题的原理，而 不是一种特殊的算法，故需要有丰富的想象去建模，创造性 地去求解。
12 13 14 12
本阶段最优终 点（最优决策) C2 C3 C3 C3
分析得知：如果经过B1，则走B1-C2-D2-E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。
第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和 终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：
2)要满足递推关系，即
Vk ,n ( sk , uk , sk 1, uk 1,, sn1 ) k [ s k , uk ,Vk 1 ( sk 1,, sn1 )]
3)函数 k [ s k , uk ,Vk 1 ( sk 1,, sn1 )] 对其变元Vk+1来说要严格单 调。
D1 D2
10 6
10 6
E E
分析得知：从D1和D2到E的最短路径唯一。
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题：
阶段3 本阶段始点 （状态） 本阶段各终点（决策） D1 D2 本阶段最优终点 到E的最短距离 （最优决策)
p1 ( s1 ) {u1 ( s1 ), u2 ( s2 ), , uk ( sk ), un ( sn )}
则对上述策略中所隐含的任一状态而言，第k子过程上对应于该 状态的最优策略必然包含在上述全过程最优策略p1*中，即为
pk ( s k ) {u k ( s k ), u k ( s ), , u 1 k 1 n ( s n )}
维数．而前者约束条件所表示的内容，常就是状态变量sk所代表的内
容。
（ 3 ）．正确地定义决策变量及各阶段的允许决策集合 Uk(sk) ， 根据经验，一般将问题中待求的量，选作动态规划模型中的决 划)转换为 动态规划模型时，常取前者的变量xj为后者的决策变量uk。
4
4
用穷举法的计算量:
如果从A到E的站点有k个，除A、E之外每站有3个位置则
总共有3k-1×2条路径； 计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及
3k-1×2-1次比较。随着 k 的值增加时，需要进行的加法和比 较的次数将迅速增加；
例如当 k=20时，加法次数为
4.2550833966227×1015 次，
4.动态规划步骤