2019/1/12,运筹学 北京邮电大学,1,第九章 动态规划（续）,动态规划的基本原理 动态规划方法的基本步骤 动态规划方法应用举例,本章以下内容,2019/1/12,运筹学 北京邮电大学,2,最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：,动态规划的基本原理,则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为,2019/1/12,运筹学 北京邮电大学,3,3.动态规划方法的基本步骤,1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。 2正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：,2019/1/12,运筹学 北京邮电大学,4,3.动态规划方法的基本步骤,(1)要能够正确地描述受控过程的变化特征。 (2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。 (3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数而前者约束条件所表示的内容，常就是状态变量sk所代表的内容。,2019/1/12,运筹学 北京邮电大学,5,3.动态规划方法的基本步骤,3正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。 4. 能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk ,uk),2019/1/12,运筹学 北京邮电大学,6,3.动态规划方法的基本步骤,5根据题意,正确地构造出目标与变量的函数关系目标函数，目标函数应满足下列性质： (1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策 uk ,uk+1,un,就是说它是定义在全过程和所有后部子过程上的数量函数。 (2)要满足递推关系，即 (3)函数 对其变元Rk+1来说要严格单调。,2019/1/12,运筹学 北京邮电大学,7,6写出动态规划函数基本方程 例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成 ：,3.动态规划方法的基本步骤,2019/1/12,运筹学 北京邮电大学,8,学习方法建议： 第一步 先看问题，充分理解问题的条件、情况及求解目标。 第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。,4.动态规划方法应用举例,2019/1/12,运筹学 北京邮电大学,9,第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。 第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。 第五步 对照自己 的求解，分析成败。,4.动态规划方法应用举例,2019/1/12,运筹学 北京邮电大学,10,1.动态规划的四大要素 状态变量及其可能集合 xk Xk 决策变量及其允许集合 uk Uk 状态转移方程 xk+1= Tk (xk ,uk ) 阶段效应 rk ( xk , uk ),4.动态规划方法应用举例,2019/1/12,运筹学 北京邮电大学,11,2. 动态规划基本方程 fn+1(xn+1) = 0 (边界条件) fk(xk) = opt urk ( xk , uk ) + fk+1(xk+1) k = n,1,4.动态规划方法应用举例,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,13,求 最 短 路 径 例5.5,2019/1/12,运筹学 北京邮电大学,14,将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。,将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)=B3C1,B3C2,B3C3,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,15,最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为 f5(x5)=f5(E)=0 其含义是从E到E的最短路径为0。,第四阶段的递推方程为 :,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,16,其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。,由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,17,第三阶段的递推方程为：,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,18,由此得到f3(x3)的表达式：,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,19,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,20,由此得到f2(x2)的表达式：,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,21,第一阶段的递推方程为：,求 最 短 路 径,2019/1/12,运筹学 北京邮电大学,22,由此得到f1(x1)的表达式,求 最 短 路 径,资 源 分 配 问 题,2019/1/12,运筹学 北京邮电大学,24,例5.6: 有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：,求对三个项目的最优投资分配，使总投资效益最大。,资 源 分 配 问 题,2019/1/12,运筹学 北京邮电大学,25,阶段k：每投资一个项目作为一个阶段； 状态变量xk：投资第k个项目前的资金数； 决策变量dk：第k个项目的投资； 决策允许集合：0dkxk 状态转移方程：xk+1=xk-dk 阶段指标：vk(xk ,dk)见表中所示； 递推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1) 终端条件：f4(x4)=0,资 源 分 配 问 题,2019/1/12,运筹学 北京邮电大学,26,k=4，f4(x4)=0 k=3，0d3x3，x4=x3-d3,资 源 分 配 问 题,2019/1/12,运筹学 北京邮电大学,27,k=2，0d2x2，x3=x2-d2,资 源 分 配 问 题,2019/1/12,运筹学 北京邮电大学,28,k=1，0d1x1，x2=x1-d1,资 源 分 配 问 题,背 包 问 题,2019/1/12,运筹学 北京邮电大学,30,背 包 问 题,2019/1/12,运筹学 北京邮电大学,31,则 Max z= c1x1+c2x2+cnxn s.t. w1x1+w2x2+wnxnW x1,x2,xn为正整数,阶段k：第k次装载第k种物品（k=1,2,n） 状态变量xk：第k次装载时背包还可以装载的重量； 决策变量dk：第k次装载第k种物品的件数；,背 包 问 题,2019/1/12,运筹学 北京邮电大学,32,4. 决策允许集合： Dk(xk)=dk|0 dkxk/wk，dk为整数； 5. 状态转移方程：xk+1=xk-wkdk 6. 阶段指标：vk=ckdk 7. 递推方程 fk(xk)=maxckdk+fk+1(xk+1) =maxckdk+fk+1(xk-wkdk) 8. 终端条件：fn+1(xn+1)=0,背 包 问 题,2019/1/12,运筹学 北京邮电大学,33,例5.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及 W=5 用动态规划求解 f4(x4)=0 对于k=3,背 包 问 题,2019/1/12,运筹学 北京邮电大学,34,对于k =3,列出 f3(x3)的数值表如下：,2019/1/12,运筹学 北京邮电大学,35,对于k=2,列出f2(x2)的数值表,2019/1/12,运筹学 北京邮电大学,36,对于k=1,列出f1(x1)的数值表,2019/1/12,运筹学 北京邮电大学,37,机器负荷分配问题,2019/1/12,运筹学 北京邮电大学,39,2019/1/12,运筹学 北京邮电大学,40,构造动态规划模型如下： 阶段k：运行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，依次类推；k=6表示第五年末（即第六年初）。 状态变量xk：第k年初完好的机器数（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好机器数。 决策变量dk：第k年投入高负荷运行的机器数； 状态转移方程：xk+1=0.7dk+0.9(xk-dk) 决策允许集合：Dk(xk)=dk|0dkxk 阶段指标：vk(xk ,dk)=8dk+5(xk-dk) 终端条件：f6(x6)=0,机器负荷分配问题,2019/1/12,运筹学 北京邮电大学,41,递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1) dkDk(xk) = max8dk+5(xk- dk)+fk+10.7dk+0.9(xk-dk) 0dkxk,机器负荷分配问题,2019/1/12,运筹学 北京邮电大学,42,f5(x5)=max8d5+5(x5-d5)+f6(x6) 0d5x5 =max3d5+5x5=8x5, d5*=x5 0d5x5 f4(x4)=max8d4+5(x4-d4)+f5(x5) 0d4x4 =max8d4+5(x4-d4)+8x5 0d4x4 =max8d4+5(x4-d4)+80.7d4+0.9(x4-d4) 0d4x4 =max1.4d4+12.3x4=13.7x4, d4*=x4 0d4x4,机器负荷分配问题,2019/1/12,运筹学 北京邮电大学,43,f3(x3)=max8d3+5(x3-d3)+f4(x4) 0d3x3 =max8d3+5(x3-d3)+13.7x4 0d3x3 =max8d3+5(x3-d3)+13.70.7d3+0.9(x3-d3) 0d3x3 =max0.28d3+17.24x3=17.52x3, d3*=x3 0d3x3,机器负荷分配问题,2019/1/12,运筹学 北京邮电大学,44,f2(x2)=max8d2+5(x2-d2)+f3(x3) 0d