运筹学 北京邮电大学.动态规划

《运筹学 北京邮电大学.动态规划》由会员分享，可在线阅读，更多相关《运筹学 北京邮电大学.动态规划（76页珍藏版）》请在金锄头文库上搜索。

1、第九章 动态规划（续 ）动态规划的基本原理 动态规划方法的基本步骤 动态规划方法应用举例本章以下内容1最优化原理 （贝尔曼最优化原理）作为一个全过程的最优策略具有这样 的性质：对于最优策略过程中的任意状 态而言，无论其过去的状态和决策如何 ，余下的诸决策必构成一个最优子策略 。该原理的具体解释是，若某一全过程 最优策略为：动态规划的基本原理则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中，即为23.动态规划方法的基本步骤1应将实际问题恰当地分割成n个 子问题(n个阶段)。通常是根据时间或空 间而划分的，或者在经由静态的数学规 划模型转

2、换为动态规划模型时，常取静 态规划中变量的个数n，即k=n。2正确地定义状态变量sk，使它既 能正确地描述过程的状态，又能满足无 后效性动态规划中的状态与一般控制 系统中和通常所说的状态的概念是有所 不同的，动态规划中的状态变量必须具 备以下三个特征：33.动态规划方法的基本步骤(1)要能够正确地描述受控过程的变化特征 。(2)要满足无后效性。即如果在某个阶段状 态已经给定，那么在该阶段以后，过程的发展 不受前面各段状态的影响，如果所选的变量不 具备无后效性，就不能作为状态变量来构造动 态规划的模型。(3)要满足可知性。即所规定的各段状态变 量的值，可以直接或间接地测算得到。一般在 动态规划模

3、型中，状态变量大都选取那种可以 进行累计的量。此外，在与静态规划模型的对 应关系上，通常根据经验，线性与非线性规划 中约束条件的个数，相当于动态规划中状态变 量sk的维数而前者约束条件所表示的内容， 常就是状态变量sk所代表的内容。43.动态规划方法的基本步骤3正确地定义决策变量及各阶段的允许 决策集合Uk(sk)，根据经验，一般将问题中 待求的量，选作动态规划模型中的决策变量 。或者在把静态规划模型(如线性与非线性规 划)转换为动态规划模型时，常取前者的变量 xj为后者的决策变量uk。4. 能够正确地写出状态转移方程，至少 要能正确反映状态转移规律。如果给定第k阶 段状态变量sk的值，则该段

4、的决策变量uk一 经确定，第k+1段的状态变量sk+1的值也就完 全确定，即有sk+1=Tk(sk ,uk)53.动态规划方法的基本步骤5根据题意,正确地构造出目标与变量 的函数关系目标函数，目标函数应满足 下列性质：(1)可分性，即对于所有k后部子过程，其 目标函数仅取决于状态sk及其以后的决策 uk ,uk+1,un,就是说它是定义在全过程和所 有后部子过程上的数量函数。(2)要满足递推关系，即(3)函数 对其变元Rk+1 来说要严格单调。66写出动态规划函数基本方程 例如常见的指标函数是取各段指标和的形 式其中 表示第i阶段的指标， 它显然是满足上述三个性质的。所以上 式可以写成 ：3.

5、动态规划方法的基本步骤7学习方法建议：第一步 先看问题，充分理解问题 的条件、情况及求解目标。第二步 结合前面讲到的理论和解 题过程，考虑如何着手进行求解该问题 的工作。分析针对该动态规划问题的“ 四大要素、一个方程”这一步在开 始时会感到困难，但是一定要下决心去 思考，在思考过程中深入理解前文讲到 的概念和理论。4.动态规划方法应用举例8第三步 动手把求解思路整理出 来，或者说，把该问题作为习题独立的 来做。第四步 把自己的求解放到一边 ，看书中的求解方法，要充分理解教材 中的论述。第五步 对照自己 的求解，分析成败。 4.动态规划方法应用举例91.动态规划的四大要素 状态变量及其可能集合

6、xk Xk 决策变量及其允许集合 uk Uk 状态转移方程 xk+1= Tk (xk ,uk ) 阶段效应 rk ( xk , uk ) 4.动态规划方法应用举例102. 动态规划基本方程 fn+1(xn+1) = 0 (边界条件)fk(xk) = opt urk ( xk , uk ) + fk+1(xk+1) k = n,14.动态规划方法应用举例11求 最 短 路 径12求 最 短 路 径 例5.513将问题分成五个阶段，第k阶段到 达的具体地点用状态变量xk表示，例 如：x2=B3表示第二阶段到达位置B3， 等等。这里状态变量取字符值而不是 数值。将决策定义为到达下一站所选择 的路径，

7、例如目前的状态是x2=B3，这 时决策允许集合包含三个决策，它们 是 D2(x2)=D2(B3)=B3C1,B3C2,B3C3求 最 短 路 径14最优指标函数fk(xk)表示从目前状态 到E的最短路径。终端条件为 f5(x5)=f5(E)=0 其含义是从E到E的最短路径为0。 第四阶段的递推方程为:求 最 短 路 径15其中*表示最优值，在上表中，由于决策允 许集合D4(x4)中的决策是唯一的，因此这个 值就是最优值。由此得到f4(x4)的表达式。由于这 是一个离散的函数，取值用列表表示：求 最 短 路 径16第三阶段的递推方程为：求 最 短 路 径17由此得到f3(x3)的表达式：求 最

8、短 路 径18求 最 短 路 径19由此得到f2(x2)的表达式：求 最 短 路 径20第一阶段的递推方程为：求 最 短 路 径21由此得到f1(x1)的表达式求 最 短 路 径22资 源 分 配 问 题23例5.6: 有资金4万元，投资A、B、C三个项 目，每个项目的投资效益与投入该项目的 资金有关。三个项目A、B、C的投资效益（ 万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使 总投资效益最大。资 源 分 配 问 题24w阶段k：每投资一个项目作为一个阶段 ；w状态变量xk：投资第k个项目前的资金 数；w决策变量dk：第k个项目的投资；w决策允许集合：0dkxkw状态转移

9、方程：xk+1=xk-dkw阶段指标：vk(xk ,dk)见表中所示；w递推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)w终端条件：f4(x4)=0资 源 分 配 问 题25k=4，f4(x4)=0 k=3，0d3x3，x4=x3-d3资 源 分 配 问 题26k=2，0d2x2，x3=x2-d2资 源 分 配 问 题27k=1，0d1x1，x2=x1-d1资 源 分 配 问 题28背 包 问 题29背 包 问 题30则 Max z=c1x1+c2x2+cnxns.t. w1x1+w2x2+wnxnWx1,x2,xn为正整数w阶段k：第k次装载第k种物品（ k=1,2,

10、n）w状态变量xk：第k次装载时背包还 可以装载的重量；w决策变量dk：第k次装载第k种物品 的件数；背 包 问 题314. 决策允许集合： Dk(xk)=dk|0 dkxk/wk，dk为整数 ；5. 状态转移方程：xk+1=xk-wkdk6. 阶段指标：vk=ckdk7. 递推方程fk(xk)=maxckdk+fk+1(xk+1)=maxckdk+fk+1(xk-wkdk)8. 终端条件：fn+1(xn+1)=0背 包 问 题32例5.7:对于一个具体问题c1=65， c2=80，c3=30；w1=2，w2=3，w3=1；以 及W=5 用动态规划求解 f4(x4)=0 对于k=3背 包 问

11、题33对于k =3列出 f3(x3)的数值表如下：34对于k=2列出f2(x2)的数值表35对于k=1列出f1(x1)的数值表 3637机器负荷分配问题3839构造动态规划模型如下：阶段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)=8

12、dk+5(xk-dk)终端条件：f6(x6)=0机器负荷分配问题40递推方程： fk(xk)=maxvk(xk,dk)+fk+1(xk+1)dkDk(xk) = max8dk+5(xk- dk)+fk+10.7dk+0.9(xk-dk) 0dkxk机器负荷分配问题41f5(x5)=max8d5+5(x5-d5)+f6(x6)0d5x5=max3d5+5x5=8x5, d5*=x50d5x5 f4(x4)=max8d4+5(x4-d4)+f5(x5)0d4x4=max8d4+5(x4-d4)+8x50d4x4=max8d4+5(x4-d4)+80.7d4+0.9(x4-d4)0d4x4=max1

13、.4d4+12.3x4=13.7x4, d4*=x40d4x4机器负荷分配问题42f3(x3)=max8d3+5(x3-d3)+f4(x4)0d3x3 =max8d3+5(x3-d3)+13.7x40d3x3 =max8d3+5(x3-d3)+13.70.7d3+0.9(x3-d3)0d3x3 =max0.28d3+17.24x3=17.52x3, d3*=x30d3x3机器负荷分配问题43f2(x2)=max8d2+5(x2-d2)+f3(x3)0d2x2=max8d2+5(x2-d2)+17.52x30d2x2=max8d2+5(x2-d2)+17.520.7d2+0.9(x2-d2)0d

14、2x2=max-0.504d2+20.77x2=20.77x2,d2*=00d2x2机器负荷分配问题44f1(x1)=max8d1+5(x1-d1)+f2(x2)0d1x1=max8d1+5(x1-d1)+20.77x20d1x1=max8d1+5(x1-d1)+20.770.7d1+0.9(x1-d1)0d1x1=max-0.05d1+23.69x1=23.69x1,d1*=0 0d1x1机器负荷分配问题45由此可以得到：wf1(x1)=23.69x1,d1*=0wf2(x2)=20.77x2,d2*=0wf3(x3)=17.52x3,d3*=x3wf4(x4)=13.60x4,d4*=x4

15、wf5(x5)=8x5 d5*=x5 用x1=1000代入，得到五年最大产量为wf1(x1)=f1(1000)=23690机器负荷分配问题46每年投入高负荷运行的机器数以每年初完 好的机器数为：wx1=1000wd1*=0, x2=0.7d1+0.9(x1-d1)=900wd2*=0, x3=0.7d2+0.9(x2-d2)=810wd3*=x3=810, x4=0.7d3+0.9(x3-d3)=567wd4*=x4=567, x5=0.7d4+0.9(x4-d4)=397wd5*=x5=397, x6=0.7d5+0.9(x5-d5)=278机器负荷分配问题47在这个例子中，状态变量的终端值x6 是未加约束的，如果要求在第五年末（即 第六年初）完好的机器数不少于500台，这 时决策变量d5的决策允许集合将成为： D5(x5)=d5|0.7d5+0.9(x5-d5)500, d50 即 0.9x5-0.2d5500 d50 或 0d54.5x5-2500容易想象，这时的最大产量将比x6 是自由的情况下小。w 这个例子可以推广到一般情况。设 高