第8章动态规划.ppt

《第8章动态规划.ppt》由会员分享，可在线阅读，更多相关《第8章动态规划.ppt（40页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第8章章 动态规划动态规划v 多阶段决策问题多阶段决策问题v 动态规划的基本概念和最优化原理动态规划的基本概念和最优化原理v 离散确定性动态规划问题的求解离散确定性动态规划问题的求解v 一般数学规划问题的动态规划解法一般数学规划问题的动态规划解法1.多阶段决策问题多阶段决策问题v所谓多阶段决策问题是指决策过程可以分为若干所谓多阶段决策问题是指决策过程可以分为若干个互相联系的阶段，在每一阶段分别对应着一组个互相联系的阶段，在每一阶段分别对应着一组可以选取的决策，当每个阶段的决策选定之后，可以选取的决策，当每个阶段的决策选定之后，过程也就随之确定。过程也就随之确定。v把各个阶段的决策综合起来，构

2、成一个决策序列，把各个阶段的决策综合起来，构成一个决策序列，称为称为策略策略。不同策略带来不同的效果。不同策略带来不同的效果。v多阶段决策问题就是要在所有可能采取的策略中多阶段决策问题就是要在所有可能采取的策略中间选取一个最优策略，使在预定的标准下取得最间选取一个最优策略，使在预定的标准下取得最好的效果。好的效果。【例例】最短路线问题。设有一个旅行者从最短路线问题。设有一个旅行者从A点出发，途中要点出发，途中要经过经过B、C、D等处，最后达到终点等处，最后达到终点E。从。从A到到E有很多条路有很多条路线可以选择，各点之间的距离如图中所示，问该旅行者应选线可以选择，各点之间的距离如图中所示，问该

3、旅行者应选择哪一条路线，使从择哪一条路线，使从A到达到达E的总路程为最短。的总路程为最短。AB1B2B3C1C2C3D1D2E25375632451514633334AB1B2B3C1C2C3D1D2E25375632451514633334（1）如果处在状态）如果处在状态D1，则该阶段的最优决策必然为，则该阶段的最优决策必然为D1E：距离距离 ；而；而 。如果处在状态如果处在状态D2，则该阶段的最优决策必然为，则该阶段的最优决策必然为D2E：距离距离 ；而；而 。AB1B2B3C1C2C3D1D2E25375632451514633334（2）如果处在状态）如果处在状态C1，需要在，需要在C

4、1D1和和C1D2两条路中选两条路中选择：择：应该选择应该选择C1D1，即从，即从C1到到E的最短路线为的最短路线为C1D1E。AB1B2B3C1C2C3D1D2E25375632451514633334（2）如果处在状态）如果处在状态C2，需要在，需要在C2D1和和C2D2两条路中选两条路中选择：择：应该选择应该选择C2D2，即从，即从C2到到E的最短路线为的最短路线为C2D2E。AB1B2B3C1C2C3D1D2E25375632451514633334（2）如果处在状态）如果处在状态C3，需要在，需要在C3D1和和C3D2两条路中选两条路中选择：择：应该选择应该选择C3D1，即从，即从C

5、3到到E的最短路线为的最短路线为C3D1E。AB1B2B3C1C2C3D1D2E25375632451514633334从从C1到到E：C1D1E从从C2到到E：C2D2E从从C3到到E：C3D1EB1C1D1EB2C1D1EB3C2D2EAB1B2B3C1C2C3D1D2E25375632451514633334B1C1D1EB2C1D1EB3C2D2EAB3C2D2E2.动态规划的基本概念动态规划的基本概念1.阶段阶段：通常按照所需决策的情况来进行阶段划分，需要：通常按照所需决策的情况来进行阶段划分，需要做几次决策划分成几个阶段。描述阶段的变量称为做几次决策划分成几个阶段。描述阶段的变量称

6、为阶段阶段变量变量，常用，常用k表示。表示。2.状态状态：每个阶段开始都具有一些与该阶段有关的状态，：每个阶段开始都具有一些与该阶段有关的状态，它反映了前面各个阶段决策的结果，又是当前阶段决策它反映了前面各个阶段决策的结果，又是当前阶段决策的出发点。通常利用状态变量的出发点。通常利用状态变量s来描述。第来描述。第k阶段的状态阶段的状态变量变量 包含了该阶段之前决策过程的全部信息，做到从包含了该阶段之前决策过程的全部信息，做到从该阶段后作出的决策同之前的状态和决策无关，即无后该阶段后作出的决策同之前的状态和决策无关，即无后效性。效性。3.决策决策：某某阶阶段初从段初从给给定的状定的状态态出出发发

7、，决策者需要从若干，决策者需要从若干不同的方案中作出不同的方案中作出选择选择。决策。决策变变量量 表示第表示第k阶阶段初段初状状态为态为 时时所作决策。决策所作决策。决策变变量的取量的取值值往往受到某些限往往受到某些限制，用制，用 表示第表示第k阶阶段初状段初状态为态为 时时决策的取决策的取值值范范围围，显显然有然有 。4.策略策略：动态规动态规划划问题问题各各阶阶段决策构成的序列称段决策构成的序列称为为策略。策略。具有具有n个个阶阶段的段的动态规动态规划划问题问题的策略可表示的策略可表示为为：5.子策略子策略：从中从中间阶间阶段开始到段开始到过过程程结结束的决策构成的序列束的决策构成的序列称

8、称为为子策略。从第子策略。从第k阶阶段起的子策略可表示段起的子策略可表示为为 6.状态转移方程状态转移方程（状态转移律）：（状态转移律）：状状态转态转移方程用于确定移方程用于确定从上一从上一阶阶段的某个状段的某个状态态到下一到下一阶阶段某个状段某个状态态的的转转移移过过程。程。若若给给定第定第k阶阶段状段状态变态变量量 的取的取值值，以及，以及该阶该阶段决策段决策变变量量 的取的取值值，那么第，那么第k+1阶阶段状段状态变态变量量 的的值值也就随也就随之确定。利用函数关系来表示，之确定。利用函数关系来表示，记为记为 7.指标函数指标函数：用来衡量某用来衡量某阶阶段或者策略段或者策略优优劣的数量

9、指劣的数量指标标，称称为为指指标标函数。可分函数。可分为阶为阶段指段指标标函数和函数和过过程指程指标标函数。函数。阶段指标函数阶段指标函数：用来度量从某：用来度量从某阶阶段的状段的状态态出出发发采取的采取的单单阶阶段决策的段决策的优优劣，可用劣，可用 表示。表示。过程指标函数过程指标函数：用于度量策略或者子策略的：用于度量策略或者子策略的优优劣劣，常用，常用 表示，表示，即从第即从第k阶阶段状段状态态 出出发发的子策略的的子策略的优优劣度量劣度量值值：过过程指程指标标函数可以表示成各函数可以表示成各阶阶段指段指标标函数的函数。常函数的函数。常见见的形式如下：的形式如下：8.最优值函数最优值函数

10、：指指标标函数的最函数的最优值优值称称为为最最优值优值函数，表示函数，表示为为 。它表示从第。它表示从第k阶阶段的状段的状态态 开始到决策开始到决策过过程程结结束，采取最束，采取最优优策略得到的指策略得到的指标标函数函数值值。即。即AB1B2B3C1C2C3D1D2E25375632451514633334v美国数学家美国数学家Richard E.Bellman的的最优化原理最优化原理：v作为整个过程的最优策略具有这样的性质，无论过去的状作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对于先前决策所形成的状态而言，余下的态和决策如何，对于先前决策所形成的状态而言，余下的诸决策必

11、构成最优策略。诸决策必构成最优策略。v根据这个原理给出求解动态规划问题的常用根据这个原理给出求解动态规划问题的常用递推关系式递推关系式称称为动态规划的为动态规划的基本方程基本方程。当当时，有时，有当当时，有时，有【例例】某一警卫部门共有某一警卫部门共有12支巡逻队，负责支巡逻队，负责4个要害部位个要害部位A、B、C、D的警卫巡逻，对每个部位可分别派出的警卫巡逻，对每个部位可分别派出24支巡逻队。支巡逻队。并且由于派出巡逻队数不同，各部位预期在一段时间内可能并且由于派出巡逻队数不同，各部位预期在一段时间内可能造成的损失有差别，如下表所示。问该警卫部门应往各部位造成的损失有差别，如下表所示。问该警

12、卫部门应往各部位分别派多少支巡逻队使总的预期损失为最小。分别派多少支巡逻队使总的预期损失为最小。ABCD218382434314352231410312125状态状态状态状态s s1 1状态状态状态状态s s2 2状态状态状态状态s s3 3状态状态状态状态s s4 4状态状态状态状态s s5 5A A A A部位部位部位部位B B B B部位部位部位部位C C C C部位部位部位部位D D D D部位部位部位部位1210988765465432432100 00 00 00 00 03431252525343125252534312525253431313134343424222124222

13、1242221242224464647474949555558583835313835313835318080848487871814109797解：解：阶段阶段决策变量决策变量 ：第：第k阶段派出的巡逻队数阶段派出的巡逻队数状态变量状态变量 ：第：第k阶段初可供派遣的巡逻队数阶段初可供派遣的巡逻队数状态转移方程状态转移方程：阶段指标函数阶段指标函数 ：第：第k阶段派出的巡逻队数为阶段派出的巡逻队数为 时，该部位的预期损失值时，该部位的预期损失值过程指标函数过程指标函数 ：最优值函数最优值函数 ：第：第k阶段初状态为阶段初状态为 ，以此，以此出发采用最优子策略到过程结束的预期损失值出发采用最优

14、子策略到过程结束的预期损失值当当k=4时时23426345343423431313343125254343125254343125254当当k=3时时2344856724+3458224+3122+3455224+2522+3121+3449224+2522+2521+3147324+2522+2521+25464当当k=2时时234810938+4935+5531+5887238+4735+4931+5584338+4635+4731+49804当当k=1时时2341218+8014+8410+8797412974810987284380448567582552492473464263453

15、42313254254254【例例】一项政府空间计划正在进行某项工程问题研究，这个问题必一项政府空间计划正在进行某项工程问题研究，这个问题必须在人们能够安全飞抵火星之前解决。三个科研小组目前正在尝试须在人们能够安全飞抵火星之前解决。三个科研小组目前正在尝试三种不同方法来解决这个问题。在这种情况下，估计各组（三种不同方法来解决这个问题。在这种情况下，估计各组（1组、组、2组、组、3组）不会成功的概率分别为组）不会成功的概率分别为0.4、0.6和和0.8。因而，目前所有。因而，目前所有这三组都失败的概率为这三组都失败的概率为0.40.60.8=0.192。因为目标是最小化失败。因为目标是最小化失败

16、概率，已有另外概率，已有另外2名顶级科学家将被分配到该工程项目中。下表中给名顶级科学家将被分配到该工程项目中。下表中给出了各组在有出了各组在有0名、名、1名、名、2名额外的科学家加入其组时，各小组会名额外的科学家加入其组时，各小组会失败的概率估计。只能考虑整数的科学家数目。问题是决定如何分失败的概率估计。只能考虑整数的科学家数目。问题是决定如何分配两位科学家以最小化所有组都失败的概率。配两位科学家以最小化所有组都失败的概率。新科学家新科学家小组小组1小组小组2小组小组300.40.60.810.20.40.520.150.20.3解：解：阶段阶段决策变量决策变量 ：第：第k阶段分配到小组阶段分

17、配到小组k中的新科学家数目中的新科学家数目状态变量状态变量 ：第：第k阶段初能够被分配到剩余小组的新科阶段初能够被分配到剩余小组的新科学家的数目学家的数目状态转移方程状态转移方程：阶段指标函数阶段指标函数 ：第：第k阶段如果分配到阶段如果分配到 个科学个科学家时，小组家时，小组k的失败概率的失败概率最优值函数最优值函数 ：第：第k阶段初状态为阶段初状态为 ，以此，以此出发采用最优子策略到过程结束的失败概率出发采用最优子策略到过程结束的失败概率当当k=3时时0120120.80.800.80.50.510.80.50.30.32当当k=2时时0120120.60.80.4800.60.50.40

18、.80.3000.60.30.40.50.20.80.162当当k=1时时01220.40.160.0610.20.3 0.150.4801220.40.160.0610.20.3 0.150.480120120.60.80.4800.60.50.40.80.3000.60.30.40.50.20.80.1620120120.80.800.80.50.510.80.50.30.32【例例】用动态规划方法求解下述非线性规划问题用动态规划方法求解下述非线性规划问题解：阶段解：阶段k=1，2，3 决策变量决策变量状态变量状态变量状态转移方程：状态转移方程：决策变量取值范围：决策变量取值范围：当当k=

19、3时时当当k=2时时当当k=1时时解：状态变量为解：状态变量为k阶段初各约束条件右端阶段初各约束条件右端项的剩余值，用项的剩余值，用 表示表示状态转移方程：状态转移方程：指标函数：指标函数：当当k=2时时当当k=1时时当当k=2时时当当k=1时时即最优解为即最优解为【例例】某商店在未来的某商店在未来的4个月里，准备利用它的一个仓库来个月里，准备利用它的一个仓库来专门经销某种商品。仓库最大容量能储存这种商品专门经销某种商品。仓库最大容量能储存这种商品1000单位。单位。假定该商店每月只能卖出仓库现有的货。当商店在某月订购假定该商店每月只能卖出仓库现有的货。当商店在某月订购时，下月初才能到货。预测

20、该商店未来四个月买卖价格如下时，下月初才能到货。预测该商店未来四个月买卖价格如下表所示。假定商店在表所示。假定商店在1月开始经销时，仓库存有该商品月开始经销时，仓库存有该商品500单单位。试问若不计库存费用，该商店应如何制定位。试问若不计库存费用，该商店应如何制定1月至月至4月的订月的订购和销售计划，使预计获利最大。购和销售计划，使预计获利最大。月份月份购买单价（购买单价（ck）销售单价（销售单价（pk）110122983111341517解：按月份划分成解：按月份划分成4个阶段个阶段 k=1，2，3，4状态变量状态变量 ：第：第k月初时仓库中的存货量（含上月订货）月初时仓库中的存货量（含上月

21、订货）决策变量决策变量 ：第：第k月卖出的货物数量月卖出的货物数量 ：第：第k月订购的货物数量月订购的货物数量状态转移方程：状态转移方程：最优值函数最优值函数 ：第：第k月初存货量为月初存货量为 时，从第时，从第k月月到到4月末所获最大利润，则有月末所获最大利润，则有当当k=4时时当当k=3时时当当k=2时时当当k=1时时月份月份月初存货月初存货售出量售出量(xk)购进量购进量(yk)15005000200100031000100010004100010000【作业作业】某公司从银行获得贷款某公司从银行获得贷款400万元，现有万元，现有3个项目个项目A、B、C可供投资。投资不同项目所获收益如下表所示。试用可供投资。投资不同项目所获收益如下表所示。试用动态规划方法求解如下问题，公司如何分配这动态规划方法求解如下问题，公司如何分配这400万元资金万元资金用于三个项目，才能使公司总收益最大？用于三个项目，才能使公司总收益最大？0100200300400A0407090120B050100110120C04060110120