运筹学-第七章-动态规划

2019/12/1512019/12/151第七章动态规划DynamicProgramming，DP美国数学家贝尔曼(RichardBellman,1920～1984)创始时间上个世纪50年代创始人动态规划是运筹学的主要分支之一,是现代企业管理中的一种重要决策方法,它是解决多阶段决策过程的一种最优化方法2019/12/152本章主要内容多阶段决策过程及其问题举例最短路问题动态规划的基本概念和基本方程动态规划应用举例资源分配问题背包问题生产库存问题………2019/12/1537.1多阶段决策过程及其问题举例动态规划研究的问题—多阶段决策问题在时间或空间上可以划分为若干阶段，每一阶段都需要根据现阶段的情况做出决策决策者每段决策时，不仅要考虑本阶段目标最优，还应考虑之后各阶段的目标最优，最终达到整个决策活动的总体目标最优当各个阶段的决策确定后，就构成了一个决策序列各阶段的决策一般与时间有关，故称“动态”。但某些“静态”问题可通过引进“时间”因素，用动态规划方法来处理12状态状态状态n…状态决策决策决策状态2019/12/154动态规划分类：离散确定性动态规划离散随机性动态规划连续确定性动态规划连续随机性动态规划2019/12/155GD76543358109745EABCHF例1最短路径问题第一阶段第二阶段第三阶段第四阶段求从A到H的最短路径2019/12/1562019/12/156第一种方法称做枚举法（穷举法）：基本思想是列举出所有可能发生的方案和结果，再对它们进行比较，求出最优方案。这里，从A到H的路程共有7条可能的路线，分别算出各条路线的距离，最后进行比较，可得最优路线当节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算第二种方法熟称贪心算法，亦即“局部最优路径”法，只选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优。在这种想法指导下，所取决策必是A→C→G→H，距离为4+5+8=172019/12/157d(sk,uk)：第k阶段，采取策略uk所发生的距离fk(sk)：第k阶段，在sk状态时到终点H的最短距离动态规划的基本思想：如果起点A经过B,E而到H最优，则由B出发经E到H这条子路线，必为从B到H的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推假设sk：第k阶段初所处的节点uk(sk)：在sk状态时第k阶段所作的决定GD76543358109745EABCHF2019/12/158f4(H)=0GD76543358109745EABCHF2019/12/159f4(H)=0GD76543358109745EABCHFf3(E)=3343()()()303()fEdEHfHuEEH2019/12/1510f4(H)=0GD76543358109745EABCHFf3(E)=3f3(F)=5FHFuHfHFdFf)(505)()()(3432019/12/1511GHGuHfHGdGf)(508)()()(343f4(H)=0GD76543358109745EABCHFf3(E)=3f3(F)=5f3(G)=82019/12/1512f4(H)=0GD76543358109745EABCHFf3(E)=3f3(F)=5f3(G)=8f2(B)=13BEBuFfFBdEfEBdBf)(1359310min)(),()(),(min)(23322019/12/1513CECuGfGCdFfFCdEfECdCf)(10855637min)(),()(),()(),(min)(23332f4(H)=0GD76543358109745EABCHFf3(E)=3f3(F)=5f3(G)=8f2(B)=13f2(C)=102019/12/1514DFDuGfGDdFfFDdDf)(88453min)(),()(),(min)(2332f4(H)=0GD76543358109745EABCHFf3(E)=3f3(F)=5f3(G)=8f2(B)=13f2(C)=10f2(D)=82019/12/1515ACAuDfDAdCfCAdBfBAdAf)(1487104135min)(),()(),()(),(min)(12221f4(H)=0GD76543358109745EABCHFf3(E)=3f3(F)=5f3(G)=8f2(B)=13f2(C)=10f2(D)=8f1(A)=142019/12/1516f4(H)=0GD76543358109745EABCHFf3(E)=3f3(F)=5f3(G)=8f2(B)=13f2(C)=10f2(D)=8f1(A)=14状态最优决策状态最优决策状态最优决策状态A（AC）C（CE）E（EH）H从A到H的最短路径：距离为14，路线为A→C→E→H2019/12/15172019/12/1517多阶段决策过程及实例：标号法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643437597681310912131618第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段从G到A的解法称为逆序解法注：因为从A到G的最短路与从G到A的最短路是一样的，因此也可以从A出发来找。从A到G的解法称为顺序解法2019/12/15182019/12/1518综上可见，全枚举法虽可找出最优方案，但不是好算法；局部最优法则完全是个错误方法；只有动态规划方法属于科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题2019/12/15197.2动态规划的基本概念和基本方程(一)基本概念和基本方程(1)阶段：k=1,……,n(2)状态变量sk：第k阶段的自然状况(3)决策变量uk(sk)：第k阶段的决定Dk(sk)：决策变量的取值范围GD76543358109745EABCHF2019/12/1520(4)状态转移方程sk＋1＝T(sk,uk)：描述第k阶段与第k+1阶段的状态变量的关系(5)指标v(sk,uk)：第k阶段在状态sk下采取决策uk得到的结果（距离、得益、成本等）指标函数是指各阶段指标的累计。即V(sk,uk,…,sn,un,sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)…*vn(sn,un)它表示从第k阶段的状态sk开始到第n阶段的终止状态的指标累计。式中*表示某种运算符，一般为加法或乘积运算(6)最优指标函数fk(sk)：它表示从第k阶段的状态sk开始到第n阶段终止的过程中，采取最优策略得到的指标函数值),,,()(1,},{nkknkuukksusVOPTsfnk2019/12/15212019/12/1521逆推公式fk(sk)＝OPT{v(sk,uk)+fk+1(sk+1)}k=n,…1fn+1(sn+1)＝0或fk(sk)＝OPT{v(sk,uk)+fk+1(sk+1)}k=n-1,…1fn(sn)＝OPT{v(sn,un)}多阶段决策问题中，常见的目标函数形式之一是取各阶段效益之和的形式。有些问题，如系统可靠性问题，其目标函数是取各阶段效益的连乘积形式。总之，具体问题的目标函数表达形式需要视具体问题而定Max或Min2019/12/1522对例1(1)阶段：k＝1,2,3(2)状态变量sk：第k阶段初所处的位置,状态集合Sk,如S2={B,C,D}(3)决策变量uk：在第k段sk状态时的路径选择(4)状态转移方程：sk＋1＝uk(sk)2019/12/1523(5)指标：vk(sk，uk)为第k阶段采取决策uk时到下一状态的距离指标函数(6)最优指标函数：fk(sk)：第k阶段，在sk状态时到终点H的最短距离,(,)nknjijjkVvsufk(sk)＝min{vk(sk,uk)+fk+1(sk+1)}k=3,…1f4(s4)＝02019/12/15242019/12/1524（二）贝尔曼最优化原理最优策略具有这样的性质：不论初始状态与初始策略如何，对于先前决策所造成的状态而言，余下所有决策必构成最优决策。即：最优策略的子策略也是最优的！AⅠBMII’II2019/12/1525（三）解法步骤首先将问题划分为若干个阶段，然后选择状态变量与决策变量，并写出转移方程和指标函数，列出基本方程反向条件优化正向求最优解fk(sk)＝OPT{vk(sk,uk)+fk+1(sk+1)}k=n,…1fn+1(sn+1)＝0fk(sk)＝OPT{vk(sk,uk)×fk+1(sk+1)}k=n,…1fn+1(sn+1)＝12019/12/15267.3应用举例例2资源分配问题(Ⅰ)例3资源分配问题(Ⅱ)例4背包问题例5生产库存问题例6可靠性问题例7机器负荷分配问题……2019/12/1527例2资源分配问题(Ⅰ)某公司准备将5台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。问：如何分配这五台设备，才能使公司获得的收益最大？工厂盈利（万元）设备数工厂1工厂2工厂300001354271063101111412111251411122019/12/1528分析(1)阶段：k=1，2，3(3)决策变量uk：对第k阶段的分配数(2)状态变量sk：可分配给第k个至第3个企业的设备数（亦即第k阶段初可供分配的设备数）(4)状态转移方程：sk＋1＝sk-uk(5)指标函数gk(uk)：分配uk台设备给第k个工厂所产生的收益(6)最优指标函数fk(sk)：第k至第3阶段采取最优分配策略可产生的最大收益2019/12/1529fk(sk)＝max{gk(uk)+fk+1(sk+1)}（k=3,2,1）f4(s4)＝0逆推公式：其中()kkkuDs():0kkkkDsus2019/12/15302019/12/1530k=3,S3={0,1,2,3,4,5},f3(s3)＝max{g3(u3)+0}g3(u3)+0maxu3s3012345f3(s3)u3000010441204662304611113404611121245046111212124,5330su2019/12/15312019/12/1531k=2,S2={0,1,2,3,4,5},f2(s2)＝max{g2(u2)+f3(s3)}g2(u2)+f3(s3)max最优决策u2s2012345f2(s2)u200+000(0,0)10+45+051(1,0)20+65+410+0102(2,0)30+115+610+411+0142(2,1)40+125+1110+611+411+0161,2(1,3)(2,2)50+125+1210+1111+611+411+0212(2,3)S3=S2-u3220su2019/12/15322019/12/1532g1(u1)+f2(s2)max最优决策u1s1012345f1(s1)u150+213+167+1410+1012+514+0210,2(0,2,3)(2,2,1)k=1,S1={5},f1(s1)＝max{g1(u1)+f2(s2)}得到两种方案：u1*＝0，u2*＝2，u3*＝3:工厂1分配0台，工厂2分配2台，工厂3分配3台u1*＝2，u2*＝2，u3*＝1:工厂1分配2台，工厂2分配2台，工厂3分配1台总盈利均为21万元2*2u5052s21*f3*3u3253s同理得到另一组最优解0*1u51s110su2019/12/1533一般分配问题某种资源的总量为a，用于n种生产若分配uk于第k种生产时，收益为gk(xk)问：应如何分配才能使总收入最大？该问题的数学模型为M