动态规划(ppt).ppt

1、动态规划李孟涛动态规划是运筹学的一个分支，是求解多阶段决策过动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，我们首先要了解多阶段决策问题。学习动态规划，我们首先要了解多阶段决策问题。最短路径问题最短路径问题：给定一个交通网络图如下，其中两点之间：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从的数字表示距离（或运费），试求从A A点到

2、点到G G点的最短距离点的最短距离（总运输费用最小）。（总运输费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643背包问题背包问题 有一个徒步旅行者，其可携带物品重量的限度有一个徒步旅行者，其可携带物品重量的限度为为a a 公斤，设有公斤，设有n n 种物品可供他选择装入包中。已知每种种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？的物品（各几件），使所起作用（使用价值）最

3、大？物品物品 1 2 j n重量（重量（公斤公斤/件件）a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。生产决策问题生产决策问题：企业在生产过程中，由于需求是随时间变：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。机器负荷分配问题机器负荷分配问题：某种机器可以在高低两种不同的负荷：某种机器可以在高低

4、两种不同的负荷下进行生产。要求制定一个五年计划，在下进行生产。要求制定一个五年计划，在每年开始时，决每年开始时，决定如何重新分配定如何重新分配完好的完好的机器在两种不同的负荷下生产的数机器在两种不同的负荷下生产的数量量，使在五年内产品的总产量达到最高。，使在五年内产品的总产量达到最高。航天飞机飞行控制问题航天飞机飞行控制问题：由于航天飞机的运动的环境是不：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和

5、之能最省燃料和完成飞行任务完成飞行任务（如软着（如软着陆陆）。）。根据过程的特性可以将过程按空间、时间等标志分为根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。若干个互相联系又互相区别的阶段。在每一个阶段都需要做出决策，从而使整个过程达到在每一个阶段都需要做出决策，从而使整个过程达到最好的效果。最好的效果。各个阶段决策的选取不是任意确定的，它依赖于当前各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。面临的状态，又影响以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个

6、过程的一条活动路线，这样的一因而也就决定了整个过程的一条活动路线，这样的一个前后关联具有链状结构的多阶段过程就称为多阶段个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。决策问题。多阶段决策过程的特点：多阶段决策过程的特点：针对多阶段决策过程的最优化问题，美国数学家针对多阶段决策过程的最优化问题，美国数学家BellmanBellman等等人在人在2020世纪世纪5050年代初提出了著名的最优化原理，年代初提出了著名的最优化原理，把多阶段把多阶段决策问题转化为一系列单阶段最优化问题决策问题转化为一系列单阶段最优化问题，从而逐个求解，从而逐个求解，创立了解决这类过程优化问题的新方法：动态规划

7、。创立了解决这类过程优化问题的新方法：动态规划。对最佳路径（最佳决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，必定是该阶段始点到全过程终点的一切可能路径中的最佳路径（最优决策），这就是Bellman提出的著名的最优化原理。简言之，一个最优策略的子策略必然也是最优的。Bellman在在1957年出版的年出版的Dynamic Programming是动是动态规划领域的第一本著作。态规划领域的第一本著作。例1、从从A A 地到地到E E 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过三级其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。中间站，两点之间的连线上的

8、数字表示距离，如图所示。问应该选择什么路线，使总距离最短？问应该选择什么路线，使总距离最短？二.最短路径问题C1AB2B1B3C3D1D2E52141126101043121113965810521C2 解：解：整个计算过程分四个整个计算过程分四个阶段阶段，从最后一个阶段开始。，从最后一个阶段开始。第四阶段（第四阶段（D E）：D 有两条路线到终点有两条路线到终点E。显然有显然有AB2B1B3C1C3D1D2E52141126101043121113965810521C22)(;5)(2414 DfDf首先考虑经过首先考虑经过 的两条路线的两条路线第三阶段（第三阶段（C D）：C 到到D 有有

9、 6 条路线。条路线。(最短路线为最短路线为 )AB2B1B3C1C3D1D2E5214126101043121113965810521C282953min)(),()(),(min)(2421141113 DfDCdDfDCdCfEDC111CAB2B1B3C1C3D1D2E5214126101043121113965810521C272556min)(),()(),(min)(2422141223 DfDCdDfDCdCf(最短路线为最短路线为 )EDC22考虑经过考虑经过 的两条路线的两条路线2CAB2B1B3C1C3D1D2E5214126101043121113965810521C2

10、1221058min)(),()(),(min)(2423141333 DfDCdDfDCdCf(最短路线为最短路线为 )EDC23考虑经过考虑经过 的两条路线的两条路线3CAB2B1B3C1C3D1D2E5214126101043121113965810521C2201210714812min)(),()(),()(),(min)(33312321131112 CfCBdCfCBdCfCBdBf(最短路线为最短路线为 )EDCB111第二阶段（第二阶段（B C）：B 到到C 有有 9 条路线。条路线。首先考虑经过首先考虑经过 的的3条路线条路线1BAB2B1B3C1C3D1D2E521412

11、6101043121113965810521C21412471086min)(),()(),()(),(min)(34322422141222 CfCBdCfCBdCfCBdBf(最短路线为最短路线为 )EDCB112考虑经过考虑经过 的的3条路线条路线2BAB2B1B3C1C3D1D2E5214126101043121113965810521C2191211712813min)(),()(),()(),(min)(33332323131332 CfCBdCfCBdCfCBdBf(最短路线为最短路线为 )EDCB223考虑经过考虑经过 的的3条路线条路线3BAB2B1B3C1C3D1D2E5214126101043121113965810521C219191145202min)(),()(),()(),(min)(3232221211 BfBAdBfBAdBfBAdAf(最短路线为最短路线为 )EDCBA112第一阶段（第一阶段（A B）：A 到到B 有有 3 条路线。条路线。（最短距离为（最短距离为19）