管理运筹学课件—动态规划.ppt

1、1第九章 动态规划动态规划的基本原理动态规划方法的基本步骤动态规划方法应用举例本章以下内容2最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：动态规划的基本原理动态规划的基本原理)(),(,),(),()(221111nnkksususususp 则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为)(,),(),()(11nnkkkkkksusususp33.3.动态规划方

2、法的基本步骤动态规划方法的基本步骤 1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。2正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：43.3.动态规划方法的基本步骤动态规划方法的基本步骤 (1)要能够正确地描述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响。(3)要满足

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

4、k的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk,uk)63.3.动态规划方法的基本步骤动态规划方法的基本步骤 5根据题意,正确地构造出目标与变量的函数关系目标函数，目标函数应满足下列性质：(1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策 uk,uk+1,un,就是说它是定义在全过程和所有后部子过程上的数量函数。(2)要满足递推关系，即 (3)函数 对其变元Rk+1来说要严格单调。),(,),(111111,nkkkkknkkkknkssRussususR),(,111nkkkkkssRus7 6写出动态

5、规划函数基本方程例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成：3.3.动态规划方法的基本步骤动态规划方法的基本步骤nkiiiikkusgsR),()(),(iiiusg),(),(111nkkkkkkssRusgR8 1.动态规划的四大要素 状态变量及其可能集合 xk Xk 决策变量及其允许集合 uk Uk 状态转移方程 xk+1=Tk(xk,uk)阶段效应 rk(xk,uk)4.4.动态规划方法应用举例动态规划方法应用举例9 2.动态规划基本方程 fn+1(xn+1)=0 (边界条件)fk(xk)=opt urk(xk,uk)

6、+fk+1(xk+1)k=n,14.4.动态规划方法应用举例动态规划方法应用举例10求 最 短 路 径11BACBDBCDEC212312312511214106104131211396581052 阶段1 阶段2 阶段3 阶段4 阶段5 求 最 短 路 径例5.512 将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)=B3C1,B3C2,B3C3求 最 短 路 径13最优指标

7、函数fk(xk)表示从目前状态到E的最短路径。终端条件为f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。第四阶段的递推方程为:fxvxdfxdDx4444455444()min(,)()()从 f5(x5)到 f4(x4)的 递 推 过 程 用 下 表 表 示：x4D4(x4)x5v4(x4,d4)v4(x4,d4)+f5(x5)f4(x4)最优决策 d4*D1D1E E55+0=5*5D1ED2D2E E22+0=2*2D2E求 最 短 路 径14其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。由此得到f4(x4)的表达式。由于这是

8、一个离散的函数，取值用列表表示：f4(x4)的表达式 x4 f4(x4)最优决策 d4*D1 5 D1E D2 2 D2E 求 最 短 路 径15第三阶段的递推方程为：)(),(min)(44333)(33333xfdxvxfxDd 求 最 短 路 径16由此得到f3(x3)的表达式：x3 f3(x3)最 优 决 策d3*C1 8 C1D1 C2 7 C2D2 C3 12 C3D2 第 二 阶 段 的 递 推 方 程 为：)(),(min)(33222)(22222xfdxvxfxDd从f3(x3)到f2(x2)的递推过程用表格表示如下：求 最 短 路 径17x2 D2(x2)x3 v2(x2

9、,d2)v2(x2,d2)+f3(x3)f2(x2)最优决策 d2*B1 B1C1 B1C2 B1C3 C1 C2 C3 12 14 10 12+8=20*14+7=21 10+12=22 20 B1C1 B2 B2C1 B2C2 B2C3 C1 C2 C3 6 10 4 6+8=14*10+7=17 4+12=16 14 B2C1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+7=19*11+12=23 19 B3C2 求 最 短 路 径18由此得到f2(x2)的表达式：x2 f2(x2)最优决策d2*B1 20 B1C1 B2 14 B2C1

10、 B3 19 B3C2 求 最 短 路 径19第一阶段的递推方程为：)(),(min)(22111)(11111xfdxvxfxDd 从f2(x2)到f1(x1)的递推过程用表格表示如下：x1 D1(x1)x2 v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)最优决策 d1*A A B1 A B2 AB3 B1 B2 B3 2 5 1 2+20=22 5+14=19*1+19=20 19 A B 2 求 最 短 路 径20由此得到f1(x1)的表达式x1 f1(x1)最优决策 d1*A 19 A B2 从表达式f1(x1)可以看出，从A到E 的最短路径长度为 19。由f1(x1)

11、向 f4(x4)回朔，得到最短路径为：A B2 C1 D1 E求 最 短 路 径例：例：某公司从甲地向丁地运送物资，运送过程中先后需要经过乙、丙两个中转站，其中乙中转站某公司从甲地向丁地运送物资，运送过程中先后需要经过乙、丙两个中转站，其中乙中转站可以选择乙可以选择乙 1 1 和乙和乙 2 2 两个可选地点，丙中转站可以选择丙两个可选地点，丙中转站可以选择丙 1 1、丙、丙2 2 和丙和丙 3 3 三个可选地点，各三个可选地点，各相邻两地之间的距离如表所示，则甲地到丁地之间的最短距离为相邻两地之间的距离如表所示，则甲地到丁地之间的最短距离为：A A、64 64 B B、74 74 C C、76

12、 76 D D、6868【答案答案】：B B地点地点-距离距离-地点地点乙乙1 1乙乙2 2丙丙1 1丙丙2 2丙丙3 3丁丁甲甲26263030乙乙1 1181828283232乙乙2 2303032322626丙丙1 13030丙丙2 22828丙丙3 3222222资资 源源 分分 配配 问问 题题23 例5.6:有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：项目投入资金ABC1 万元15 万吨13 万吨11 万吨2 万元28 万吨29 万吨30 万吨3 万元40 万吨43 万吨45 万吨

13、4 万元51 万吨55 万吨58 万吨求对三个项目的最优投资分配，使总投资效益最大。资资 源源 分分 配配 问问 题题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-d3x3D3(x3)x4v3(x3,d3)v3(x

14、3,d3)+f4(x4)f3(x3)d3*00000+0=0000100+0=01101111+0=11*1110200+0=0111111+0=112203030+0=30*3020300+0=0121111+0=11213030+0=303304545+0=45*4530400+0=0131111+0=11223030+0=30314545+0=454405858+0=58*584资资 源源 分分 配配 问问 题题26k=2，0d2x2，x3=x2-d2x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=0000100+11=111101

15、313+0=13*1310200+30=30*111313+11=242202929+0=293000300+45=45*121313+30=43212929+11=403304343+0=434500400+58=58131313+45=58222929+30=59*314343+11=544405555+0=55592资资 源源 分分 配配 问问 题题27k=1，0d1x1，x2=x1-d1x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*0400+59=59131515+45=60*222828+30=58314040+13=534405151+0=

16、51601最优解为 x1=4,d1*=1,x2=x1-d1=3,d2*=0,x3=x2-d2*=3,d3=3,x4=x3-d3=0，即项目 A 投资 1 万元，项目 B 投资 0 万元，项目 C 投资 3 万元，最大效益为 60 万吨。资资 源源 分分 配配 问问 题题28背 包 问 题29 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi，每件价值ci。现有一只可装载重量为 W 的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设第i种物品取xi件（i=1,2,n，xi为非负整数），背包中物品的价值为z，则 背 包 问 题30则 Ma

17、x 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:对于

18、一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5用动态规划求解 f4(x4)=0 对于k=330max)(max)(3/04433/033333333dxfdcxfwxdwxd列出f3(x3)的数值表 背 包 问 题3330max)(max)(3/04433/033333333dxfdcxfwxdwxd对于k=3列出列出 f3(x3)的数值表如下：的数值表如下：34对于k=2)3(80max)(max)(22323/03322/02222222dxfdxfdcxfxdwxd列出f2(x2)的数值表35对于k=1)2(65max)(max)(11212/0

19、2211/01111111dxfdxfdcxfxdwxd列出f1(x1)的数值表 36由题意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得：d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=x3-d3=0 即应取第一种物品 2 件,第三种物品 1 件,最高价值为 160 元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2 和W=1 时，相应的最优解立即可以得到。37 机器负荷分配问题机器负荷分配问题38 最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值。当状态变量和决策变量的取值范

20、围很大，或者这些变量是连续的，用列举的方法就比较困难或者根本不可能了。这就需要用连续变量的处理方法。例例 5 5.8 8:某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为 0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数 0.7 称为完好率。年初投入高负荷运行的u台机器的年产量为 8u吨。系数 8 称为单台产量。低负荷运行时，机器完好率为 0.9，单台产量为5 吨。设开始时有 1000 台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。39 构造动态规划模型如下：阶段阶段k

21、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(x

22、k,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*=x5 0d5x5f4(x4)=max8d4+5(x4-d4)+f5(x5)0d4x4 =max8d4+5(x4-d4)+8x5 0d4x4 =ma

23、x8d4+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(

24、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由此可以得到：w

25、f1(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

26、=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

27、，单台产量为p2。若有t满足:机器负荷分配问题机器负荷分配问题48则从1t-1年，年初将全部完好机器投入低负荷运行，从tn年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。tniitniikkkpppk0112121)1(01)(机器负荷分配问题机器负荷分配问题49设设 备备 更更 新新 问问 题题50 一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略

28、，设设 备备 更更 新新 问问 题题51阶段k：运行年份；状态变量xk：设备的役龄t；决策变量dk：继续使用更新)()(ReKeepKplaceRdk 状态转移方程：KdxRdxkkkk111 阶段指标：KdtCRdtSCPKdxCRdxSCPvkkkkkkk)()()0()()()0(52递推方程：KdtftCRdftSCPKdxfxCRdxfxSCPxfkkkkkkkkkkkkkk)1()()1()()0(min)()()()()0(min)(111111 终端条件：fn(t)=-R(t)设设 备备 更更 新新 问问 题题53例5.10：设具体数据如下：T 0 1 2 3 4 5 6 7

29、C(t)10 13 20 40 70 100 100-S(t)-32 21 11 5 0 0 0 R(t)-25 17 8 0 0 0 0 且 n=5，T=2，P=50 由上表开始，终端条件为：f6(1)=-25，f6(2)=-17，f6(3)=-8 f6(4)=f6(5)=f6(6)=f6(7)=0 设设 备备 更更 新新 问问 题题54 对于k=5:KdRdtftCftSCPtf55665)1()()1()()0(min)(KdfCfSCPf*5665,443min)17(13)25(321050min)2()1()1()1()0(min)1(KdfCfSCPf*5665,121214mi

30、n)8(20)25(211050min)3()2()1()2()0(min)2(55RdfCfSCPf*5665,244024min040)25(111050min)4()3()1()3()0(min)3(RdfCfSCPf*5665,307030min070)25(51050min)5()4()1()4()0(min)4(RdfCfSCPf*5665,3510035min0100)25(01050min)6()5()1()5()0(min)5(56RdfCfSCPf*5665,3510035min0100)25(01050min)7()6()1()6()0(min)6(KdRdtftCftS

31、CPtf44554)1()()1()()0(min)(RdfCfSCPf*4554,242524min1213)4(321050min)2()1()1()1()0(min)1(对于k=4:57RdfCfSCPf*4554,354435min2420)4(211050min)3()2()1()2()0(min)2(RdfCfSCPf*4554,457045min3040)4(111050min)4()3()1()3()0(min)3(58 RdfCfSCPf*4554,5110551min3570)4(51050min)5()4()1()4()0(min)4(RdfCfSCPf*5554,561

32、3556min35100)4(01050min)6()5()1()5()0(min)5(59 对于k=3:KdRdtftCftSCPtf33443)1()()1()()0(min)(KdfCfSCPf*3443,484852min351324321050min)2()1()1()1()0(min)1(60 RdfCfSCPf*3443,739173min514024111050min)4()3()1()3()0(min)3(RdfCfSCPf*3443,7912679min56702451050min)5()4()1()4()0(min)4(RdfCfSCPf*3443,636563min45

33、2024211050min)3()2()1()2()0(min)2(61 KdRdtftCftSCPtf22332)1()()1()()0(min)(RdKdfCfSCPf*2*2332,767676min631348321050min)2()1()1()1()0(min)1(或者 RdfCfSCPf*2332,879387min732048211050min)3()2()1()2()0(min)2(对于k=2:62RdfCfSCPf*2332,7311997min794048111050min)4()3()1()3()0(min)3(对于k=1:KdRdtftCftSCPtf11221)1()()1()()0(min)(RdfCfSCPf*1221,115117115min972076211050min)3()2()1()2()0(min)2(979763 由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。年年 份份 1 1 2 2 3 3 4 4 5 5 决决 策策 1 1 更更 新新 更更 新新 继继 续续 更更 新新 继继 续续 决决 策策 2 2 更更 新新 继继 续续 更更 新新 更更 新新 继继 续续 这两个决策是 设设 备备 更更 新新 问问 题题