大学运筹学教程——动态规划.pptx

1最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：动态规划的基本原理动态规划的基本原理 则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为23.3.动态规划方法的基本步骤动态规划方法的基本步骤 1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。2正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：33.3.动态规划方法的基本步骤动态规划方法的基本步骤 (1)要能够正确地描述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。(3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数而前者约束条件所表示的内容，常就是状态变量sk所代表的内容。43.3.动态规划方法的基本步骤动态规划方法的基本步骤 3正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。4.能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk,uk)53.3.动态规划方法的基本步骤动态规划方法的基本步骤 5根据题意,正确地构造出目标与变量的函数关系目标函数，目标函数应满足下列性质：(1)可分性，即对于所有k后部子过程，其目 标 函 数 仅 取 决 于 状 态sk及 其 以 后 的 决 策 uk,uk+1,un,就是说它是定义在全过程和所有后部子过程上的数量函数。(2)要满足递推关系，即 (3)函数 对其变元Rk+1来说要严格单调。6 6写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成：3.3.动态规划方法的基本步骤动态规划方法的基本步骤7 学习方法建议：第一步 先看问题，充分理解问题的条件、情况及求解目标。第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。4.4.动态规划方法应用举例动态规划方法应用举例8 第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。第五步 对照自己 的求解，分析成败。4.4.动态规划方法应用举例动态规划方法应用举例11求 最 短 路 径12 求 最 短 路 径例5.513 将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是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)的表达式：求 最 短 路 径18求 最 短 路 径19由此得到f2(x2)的表达式：求 最 短 路 径20第一阶段的递推方程为：求 最 短 路 径21由此得到f1(x1)的表达式求 最 短 路 径22资资 源源 分分 配配 问问 题题23 例5.6:有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。资资 源源 分分 配配 问问 题题241.阶段k：每投资一个项目作为一个阶段；2.状态变量xk：投资第k个项目前的资金数；3.决策变量dk：第k个项目的投资；4.决策允许集合：0dkxk5.状态转移方程：xk+1=xk-dk6.阶段指标：vk(xk,dk)见表中所示；7.递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1)8.终端条件：f4(x4)=0资资 源源 分分 配配 问问 题题25k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3资资 源源 分分 配配 问问 题题26k=2，0d2x2，x3=x2-d2资资 源源 分分 配配 问问 题题27k=1，0d1x1，x2=x1-d1资资 源源 分分 配配 问问 题题28背 包 问 题29背 包 问 题30则 Max z=c1x1+c2x2+cnxn s.t.w1x1+w2x2+wnxnW x1,x2,xn为正整数1.阶 段k：第k次 装 载 第k种 物 品（k=1,2,n）2.状态变量xk：第k次装载时背包还可以装载的重量；3.决策变量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背 包 问 题33对于k=3列出列出 f3(x3)的数值表如下：的数值表如下：34对于k=2列出f2(x2)的数值表35对于k=1列出f1(x1)的数值表 3637 机器负荷分配问题机器负荷分配问题3839 构造动态规划模型如下：阶段阶段k k：运行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，依次类推；k=6表示第五年末（即第六年初状态变量状态变量x xk k：第k年初完好的机器数（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好机器数。决策变量决策变量d dk k：第k年投入高负荷运行的机器数；状态转移方程状态转移方程：xk+1=0.7dk+0.9(xk-dk)决策允许集合决策允许集合：Dk(xk)=dk|0dkxk 阶段指标阶段指标：vk(xk,dk)=8dk+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.9xk-dk)0dkxk 机器负荷分配问题机器负荷分配问题41f5(x5)=max8d5+5(x5-d5)+f6(x6)0d5x5 =max3d5+5x5=8x5,d5*=x5 0d5x5f4(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 机器负荷分配问题机器负荷分配问题42f3(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 机器负荷分配问题机器负荷分配问题43f2(x2)=max8d2+5(x2-d2)+f3(x3)0d2x2 =max8d2+5(x2-d2)+17.52x3 0d2x2 =max8d2+5(x2-d2)+17.520.7d2+0.9(x2-d2)0d2x2 =max-0.504d2+20.77x2=20.77x2,d2*=0 0d2x2 机器负荷分配问题机器负荷分配问题44f1(x1)=max8d1+5(x1-d1)+f2(x2)0d1x1 =max8d1+5(x1-d1)+20.77x2 0d1x1 =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.60 x4,d4*=x4wf5(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.2d5500d50 或 0d54.5x5-2500 容易想象，这时的最大产量将比x6是自由的情况下小。w 这个例子可以推广到一般情况。设高负荷生产时机器的完好率为k1，单台产量为p1；低负荷完好率为k2，单台产量为p2。若有t满足:机器负荷分配问题机器负荷分配问题48则从1t-1年，年初将全部完好机器投入低负荷运行，从tn年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。机器负荷分配问题机器负荷分配问题49生生 产产 库库 存存 问问 题题50 例例5.95.9：一个工厂生产某种产品,1-7月份生产成本和产品需求量的变化情 况如下表：生生 产产 库库 存存 问问 题题51w阶段k：月份，k=1,2,7,8；w状态变量xk：第k个月初（发货以前）的库存量；w决策变量dk：第k个月的生产量；w状态转移方程：xk+1=xk-rk+dk；w决策允许集合：wDk(xk)=dk|dk0,rk+1xk+1H =dk|dk0,rk+1xk-rk+dkH；w阶段指标：vk(xk,dk)=ckdk；w终端条件：f8(x8)=0,x8=0；生生 产产 库库 存存 问问 题题52递推方程：fk(xk)=minvk(xk,dk)+fk+1(xk+1)dkDk(xk)=minckdk+fk+1(xk-rk+dk)dkDk(xk)w对于k=7w因为 x8=0w有 d7=0w递推方程为wf7(x7)=minc7d7+f8(x8)=0 d7=0生生 产产 库库 存存 问问 题题53对于k=6因为d7=0，所以x7=r7=4而x6-r6+d6=x7=4因此有d6=x7+r6-x6=4+7-x6=11-x6也是唯一的决策。因此递推方程为：f6(x6)=minc6d6+f7(x7)d6=11-x6=10d6=10(11-x6)=110-10 x6生生 产产 库库 存存 问问 题题54对于对于k k=5=5f f5 5(x x5 5)=min)=minc c5 5d d5 5+f f6 6(x x6 6)d d5 5 D D5 5(x x5 5)=min20 =min20d d5 5+110-10+110-10 x x6 6 d d5 5 D D5 5(x x5 5)=min20 =min20d d5 5+110-10(+110-10(x x5 5-r r5 5+d d5 5)d d5 5 D D5 5(x x5 5)=min20 =min20d d5 5+110-10(+110-10(x x5 5-2+-2+d d5 5)d d5 5 D D5 5(x x5 5)=min10 =min10d d5 5-10-10 x x5 5+130+130 d d5 5 D D5 5(x x5 5)D D5 5(x x5 5)=)=d d5 5|d d5 5 0,0,r r6 6 x x5 5-r r5 5+d d5 5 H H =d d5 5|d d5 5 0,0,r r6 6+r r5 5-x x5 5 d d5 5 H H+r r5 5-x x5 5 =d d5 5|d d5 5 0,9-0,9-x x5 5 d d5 5 11-11-x x5 5 生生 产产 库库 存存 问问 题题55因为x5H=9，因此9-x50，决策允许集合可以简化为 D5(x5)=d5|9-x5d511-x5递推方程成为f5(x5)=min10d5-10 x5+130 9-x5d511x5 =10(9-x5)-10 x5+130 =220-20 x5 d5*=9-x5生生 产产 库库 存存 问问 题题56对于k=4f4(x4)=minc4d4+f5(x5)d4D4(x4)=min17d4+220-20 x5 d4D4(x4)=min17d4+220-20(x4-r4+d4)d4D4(x4)=min17d4+220-20(x4-3+d4)d4D4(x4)=min-3d4-20 x4+280 d4D4(x4)生生 产产 库库 存存 问问 题题57D4(x4)=d4|d40,r5x4-r4+d4H=d4|d40,r5+r4-x4d4H+r4-x4=d4|d40,5-x4d412x4=d4|max0,5-x4d412-x4 由于 在f4(x4)的表达式中d4的系数是-3，因此d4在决策允许集合中应取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280=-17x4+244生生 产产 库库 存存 问问 题题58对于k=3f3(x3)=min c3d3+f4(x4)d3D3(x3)=min 13d3+244-17x4 d3D3(x3)=min 13d3+244-17(x3-r3+d3)d3D3(x3)=min-4d3-17x3+329 d3D3(x3)D3(x3)=d3|d30,r4x3-r3+d3H=d3|d30,r4+r3-x3d3H+r3-x3=d3|d30,8-x3d314-x3=d3|max0,8-x3d314-x3由此 f3(x3)=-4(14-x3)-17x3+329 =-13x3+273,d3*=14-x3生生 产产 库库 存存 问问 题题59对于k=2f2(x2)=minc2d2+f3(x3)d2D2(x2)=min18d2+273-13x3 d2D2(x2)=min18d2+273-13(x2-r2+d2)d2D2(x2)=min18d2+273-13(x2-8+d2)d2D2(x2)=min5d2-13x2+377 d2D2(x2)D2(x2)=d2|d20,r3x2-r2+d2H=d2|d20,r3+r2-x2d2H+r2-x2 =d2|d20,13-x2d217-x2生生 产产 库库 存存 问问 题题60因为 13-x20所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377=-18x2+442,d2*=13-x2生生 产产 库库 存存 问问 题题61对于k=1f1(x1)=minc1d1+f2(x2)d1D1(x1)=min11d1+442-18x2 d1D1(x1)=min11d1+442-18(x1-r1+d1)d1D1(x1)=min11d1+442-18(x1-0+d1)d1D1(x1)=min-7d1-18x1+442 d1D1(x1)D D1 1(x x1 1)=)=d d1 1|d d1 1 0,0,r r2 2 x x1 1-r r1 1+d d1 1 H H =d d1 1|d d1 1 0,0,r r2 2+r r1 1-x x1 1 d d1 1 H H+r r1 1-x x1 1 =d d1 1|d d1 1 0,8-0,8-x x1 1 d d1 1 9-9-x x1 1 生生 产产 库库 存存 问问 题题62根据题意 x1=2所以 D1(x1)=d1|6d17由此 d1=7f1(x1)=-7d1-18x1+442=-77182442=357将以上结果总结成下表：生生 产产 库库 存存 问问 题题63设设 备备 更更 新新 问问 题题64 一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，设设 备备 更更 新新 问问 题题6566设设 备备 更更 新新 问问 题题67例5.10：设具体数据如下：设设 备备 更更 新新 问问 题题686970717273747576979777 由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。这两个决策是 设设 备备 更更 新新 问问 题题