第10章--动态规划-(管理运筹学-第三版-课件--共17章-韩伯棠)

管理运筹学1第十章动态规划§1多阶段决策过程最优化问题举例§2基本概念、基本方程与最优化原理§3动态规划的应用(1)§4动态规划的应用(2)管理运筹学2§1多阶段决策过程最优化问题举例例1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC4123123123221647248386756110643751管理运筹学3§1多阶段决策过程最优化问题举例用穷举法的计算量:如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-1×2条路径；计算各路径长度总共要进行(k+1)3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.2550833966227×1015次，比较1.3726075472977×1014次。若用1亿次/秒的计算机计算需要约508天。管理运筹学4§1多阶段决策过程最优化问题举例讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；表10-1分析得知：从D1和D2到E的最短路径唯一。阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D210*6106EE管理运筹学5第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题：表10-2分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。§1多阶段决策过程最优化问题举例阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1管理运筹学6第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：表10-3分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。§1多阶段决策过程最优化问题举例阶段2本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C3管理运筹学7第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：表10-4最后，可以得到：从A到E的最短路径为AB4C3D1E§1多阶段决策过程最优化问题举例阶段1本阶段始点(状态)本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1412C2管理运筹学8以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC412312312332164724838675161060106121111121314144B127512§1多阶段决策过程最优化问题举例管理运筹学9一、基本概念：1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。§2基本概念、基本方程与最优化原理管理运筹学106、阶段指标函数vk(sk,xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1,…,xn)：从状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标。动态规划要求过程指标具有可分离性，即Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)+Vk+1(sk+1,xk+1,…,xn)称指标具有可加性，或Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)×Vk+1(sk+1,xk+1,…,xn)称指标具有可乘性。二、基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即)},({)(,,)(nkknksDxkkPsVsfoptkkk§2基本概念、基本方程与最优化原理管理运筹学11对于可加性指标函数，上式可以写为上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。nksfxsvsfkkkkksDxkkoptkkk,,2,1)}(),({)(11)(nksfxsvsfkkkkksDxkkoptkkk,,2,1)}(),({)(11)(§2基本概念、基本方程与最优化原理管理运筹学12三、最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。§2基本概念、基本方程与最优化原理管理运筹学13一、资源分配问题例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？表10-5盈利工厂设备台数甲厂乙厂丙厂000013542710639111141211125131112§3动态规划的应用(1)管理运筹学14解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3）。xk=分配给第k个设备台数。已知s1=5,并有从与的定义，可知以下我们从第三阶段开始计算。222223),(xsxsTskskx33xs§3动态规划的应用(1)111112),(xsxsTs管理运筹学15第三阶段:显然将台设备都分配给第3工厂时，也就是时，第3阶段的指标值（即第3厂的盈利）为最大，即由于第3阶段是最后的阶段，故有其中可取值为0,1,2,3,4,5。其数值计算见表10－6。)5,4,3,2,1,0(33ss).,(),(max)(333333333ssrxsrsfx3x),(),(max3333333ssrxsrx§3动态规划的应用(1)33xs管理运筹学16表10－601234500－－－－－001－4－－－－412－－6－－－623－－－11－－1134－－－－12－1245－－－－－121253x3s),(333xsr)(33sf3*x§3动态规划的应用(1)管理运筹学17其中表示取3子过程上最优指标值时的决策，例如在表10-6中可知当=4时，有有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。第二阶段：当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为3*x)(33sf3x3s;12)4,4(3r,12)4(3f43*x43s43x)5,4,3,2,1,0(22ss2s)](),([max)(33222222sfxsrsfx§3动态规划的应用(1)管理运筹学18因为上式也可写成其数值计算如表10－7所示。表10－7,223xss0123450－－－－－0010＋4－－－－5120＋65＋4－－－10230＋115＋611＋0－－14240＋1211＋411＋0－161,250＋125＋1211＋611＋411＋02122x2s)(),(233222xsfxsr)(22sf2*x00050104101156101110)(),(max)(223222222xsfxsrsfx§3动态规划的应用(1)管理运筹学19其中在的这一行里，当时，这里从表10－5中可知，把1台设备交给乙厂所得盈利数即可，知，这里从表10－6查即可知=11。同样可知当时，可知;当时，；当时，；当时，；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大即得，即有=16。在此行中我们在取最大值的上面加一横以示区别，也可知这时的最优决策为1或2。42s12x16115)3()1,4()14()1,4()(),(3232223222frfrxsfxsr)1,4(2r5)1,4(2r)3()14(33ff)3(3f)3(3f22x16610)2()2,4()24()2,4()(),(3232223222frfrxsfxsr02x12120)04()0,4(32fr32x411)34()3,4(32fr42x11011)44()4,4(32fr42s52x)54()5,4(32fr)4(2f)4(2f)(),(223222xsfxsr2x§3动态规划的应用(1)管理运筹学20第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表10－8表10-8然后按计算表格的顺序推算，可知最优分配方案有两个：1.由于，根据，查表10－7可知，再由，求得。即分配给甲厂0台，乙厂2台，丙厂3台。2.由于，根据，查表10－7可)5(11ss)],5(),5([max)5(111111xfxrfx1x01234553＋169+1012+513+0210,21x1s)5(),5(1211xfxr210147)(1xf1*x01*x5051*12xss02*x3252*23xss333*sx21*x3251*12xss§3动态规划的应用(1)管理运筹学21知，再由,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。22*x1232*23xss133*sx§3动态规划的应用(1)管理运筹学22二、背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i=1,2,…,n），背包中物品的总价值为z，则Maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn0且为整数。§3动态规划的应用(1)管理运筹学23下面用动态规划逆序解法求解它。设阶段变量k：第k次装载第k种物品（k=1,2,…,n）状态变量sk：第k次装载时背包还可以装载的重量；决策