运筹学与系统分析：第4章 动态规划

1、第四章 动态规划（Dynamic Programming） 动态规划是解决多阶段决策过程最优化问题的一种方法。用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序、生产过程最优控制等。动态规划模型分类：离散确定型离散随机型连续确定型连续随机型（最基本） 多阶段决策过程，是按时间顺序分解成若干相互联系的阶段（时段），每个阶段都要做出决策，形成一个决策序列。 多阶段决策过程最优化的目标是要达到活动过程的总体最优。每阶段决策时不仅要考虑本阶段最优，还应考虑对最终目标的影响。 动态规划就是符合这种要求的一种决策方法。4.1 多阶段决策过程的最优化多阶段决策问题举例：例1：最短路线问题。

2、如下图，给定一个线路网络图，要从A地向F地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？AB2B1C4C3C2C1D3D2D1E2E1F452368775845344835621343例2：投资决策问题。某公司有资金10万元，若投资项目i (i=1,2,3)的投资额为xi，其收益分别是g1(x1)=4x1, g2(x2)=9x2,g3(x3)=2x32, 问应如何分配投资数额才能使总收益最大？解：求x1,x2,x3，使本例可转化为3阶段的决策问题。4.2 动态规划的基本概念和基本原理一、动态规划的基本概念（1）阶段：将问题按时间或空间特征分解成若干相互联系的阶

3、段，常用k表示阶段变量。例1中A到F有5个阶段。（2）状态：各阶段开始时的条件为状态。常用sk表示状态，Sk表示状态集合。例1中，第1阶段状态为A，第2阶段有两个状态B1,B2，以此类推。 无后效性：某阶段状态确定后，其后面阶段状态的变化不受其前面各阶段状态的影响。 动态规划模型的状态变量必须具有无后效性。（3）决策和策略：当某阶段的状态取定后，可以作不同的决策（或选择），称为决策，从而确定下一阶段的状态。通常用uk(sk)表示第k阶段当状态为sk时的决策变量。Dk(sk)表示第k阶段从状态sk出发的允许决策集合。 例如，例1中D2(B1)=C1,C2,C3 各阶段策略确定后，整个问题的决策序

4、列构成一个策略，用p1,nu1(s1),u2(s2),un(sn)表示。（4）状态转移方程：若给定第k阶段的状态sk，且其决策为uk(sk)，则第k+1阶段的状态sk+1可用状态转移方程确定（5）指标函数：用于衡量所选定策略优劣的数量指标，分为阶段指标函数和过程指标函数。 阶段指标函数d(sk,uk):从状态sk出发采取uk策略时的效益。 过程指标函数V1,n(s1,p1,n):初始状态s1时采用策略p1,n时原过程的指标函数值。 后部子过程的指标函数值Vk,n(sk,pk,n)：指第k阶段，状态为sk时采用策略pk,n时，后部子过程的指标函数值。 最优指标函数fk(sk)：从第k阶段的状态s

5、k上采用最优策略p*k,n到过程终止时的最佳效益值。动态规划的最优解是最优策略P1,n，最优值是最优指标f1二、 动态规划的基本思想和最优化原理例：例1的最短路问题AB2B1C4C3C2C1D3D2D1E2E1F452368775845344835621343解：用逆序递推方法（逆序解法）求解（1）从k5开始，到终点的路长（2）k=4, 状态有3个D1,D2,D3，到终点的最短路长相应最优策略u*4(D1)=E1, 路径D1E1F相应最优策略u*4(D2)=E2, 路径D2E2F相应最优策略u*4(D3)=E1, 路径D3E1F类似地可得到k=3时，f3(C1)=12, u*3(C1)=D1

6、f3(C2)=10, u*3(C2)=D2 f3(C3)=8, u*3(C3)=D2 f3(C4)=9, u*3(C4)=D3k=2时，f2(B1)=13, u*2(B1)=C2 f2(B2)=15, u*2(B2)=C3k=1时，只有一个状态点A相应最优策略u*1(A)=B1, 最优路径AB1 C2 D2E2F最短路长17标号法：利用上述逆序递推方法计算完后，再利用如下图直观表示的方法。其中各点上数字表示该点到达终点的最短距离，这些数字对于许多实际问题而言是很有意义的。AB2B1C4C3C2C1D3D2D1E2E1F437553432143(4)(3)(7)(5)(5)(12)(10)(8)

7、(9)(15)(13)(17)分析：求解各阶段，都利用了如下第k与k+1阶段的关系此递推关系称为动态规划基本方程，f6(s6)=0为边界条件。总结：（1）动态规划恰当地选取状态变量、决策变量及定义最优指标函数，将问题化成一族同类型的子问题，逐个求解。（2）求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。每个子问题的求解都用到它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。（3）动态规划把当前阶段与未来各段分开，又把当前效益与未来效益结合起来考虑的一种最优方法。4.3 动态规划模型的建立与求解一、动态规划模型的建立 动态规划方法的关键在于识别问题的多阶段

8、特征，正确选择状态变量，使各阶段状态变量具有递推的状态转移关系sk+1=Tk(sk,uk)例：上述例2的投资决策问题。某公司有资金10万元，若投资项目i (i=1,2,3)的投资额为xi，其收益分别是g1(x1)=4x1, g2(x2)=9x2,g3(x3)=2x32, 问应如何分配投资数额才能使总收益最大？解：人为地赋予“阶段”的概念。将投资项目排序，依次对项目1、2、3进行投资，分为3个阶段，每阶段只决定对一个项目应投资的金额。 状态变量：设每阶段可供使用的资金为状态变量sk, s1=10 决策变量：设项目投资额为决策变量，即uk=xk, k=1,2,3k=1时:k=2时:一般地，第k阶段

9、:于是有：状态变量sk：第k阶段可以投资于第k项目至第3项目的资金决策变量xk：决定给第k个项目投资的资金状态转移方程：sk+1=sk-xk指标函数：最优指标函数fk(sk):当可投资金为sk时，投资第k项至第3项所 得最大收益建立起动态规划基本方程为： 用动态规划方法逐段求解，可得各项目最佳投资金额，以及投资的最大收益为f1(10) （求解过程略）二、顺序解法 与逆序解法相反，从第1阶段开始向后递推，后一阶段要用到前一阶段的求优结果。例：用顺序解法解例1的最短路问题AB2B1C4C3C2C1D3D2D1E2E1F452368775845344835621343k=0时，f0(s1)= f0(A)=0，这是边界条件解：设fk(sk+1)为从A点到第k阶段状态sk+1的最短距离k=1时，按f1(s2)的定义有k=2时,类似地可得到k=3时，f3(D1)=11, u3(D1)=C1或C2f3(D2)=12, u3(D2)=C2f3(D3)=14, u3(D3)=C3k=4时，f4(E1)=14, u4(E1)=D1f4(E2)=14, u4(E3)=D2k=5时，f5(F)=17, u5(F)=E2最短路长17，