动态规划实例教学ppt课件.ppt

《动态规划实例教学ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划动态规划问题实例动态规划的基本概念与原理动态规划应用举例引言动态规划是解决多阶段决策过程最优化的一种方法。该方法是由美国数学家贝尔曼（R.E.Bellman)等人在20世纪50年代初提出的。并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。Bellman在1957年出版了《DynamicProgramming》一书，是动态规划领域中的第一本著作。§1动态规划问题实例例1给定一个线路网络，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从A向F铺设一条输油管道，各点间连线上的数字表示距离，问应选

2、择什么路线，可使总距离最短？动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。ABCDE状态A状态B状态C状态D状态E状态F决策A决策D决策E当每一阶段的决策选定以后，就构成一个决策序列，称为一个决策B决策C策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。§2动态规划的基本概念与原理一。基本概念阶段：是指问题需要做出决策的步数。阶段总数常记为n，相应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段变量，k=1,

3、2,…,n.k即可以是顺序编号也可以是逆序编号，常用顺序编号。状态：各阶段开始时的客观条件，第k阶段的状态常用状态变量表示，状态变量取值的集合成为状态集合，用表示。例如，例1中，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6决策：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为决策变量，用表示例如：表示走到C阶段,当处于C2路口时，下一步奔D1.时的允许决策集合记为，例如：状态转移方程：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移

4、规律，用表示。决策变量允许的取值范围称为允许决策集合，第k阶段状态为指标函数：分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段从状态出发，采取决策时的效益，用表示。而过程指标函数从第k阶段的某状态出发，采取子策略时所得到的阶段效益之和：最优指标函数：表示从第k阶段状态为时采用最佳策略到过程终止时的最佳效益。记为其中opt可根据具体情况取max或min。基本方程：此为逐段递推求和的依据，一般为：式中opt可根据题意取max或min.例如，例1的基本方程为：最优性原理：最优策略的子策略必为最优。不管过去的状态和决策如何，从眼下直到最后的诸决策必构成最优子策略。动态规划应用举例例1最短路线问题

5、AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143逆序递推方程：（1）k=5时，状态它们到F点的距离即为最短路。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4时，状态它们到F点需经过中途点E，需一一分析从E到F的最短路：先说从D1到F的最短路有两种选择：经过E1,E2,比较最短。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143这说明由D1到F的最

6、短距离为7，其路径为相应的决策为：这说明由D2到F的最短距离为5，其路径为相应的决策为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距离为5，其路径为相应的决策为：（3）k=3时，状态这说明由C1到F的最短距离为12，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的

7、最短距离为10，相应的决策为即由C3到F的最短距离为8，相应的决策为即由C4到F的最短距离为9，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态这说明由B1到F的最短距离为13，相应的决策为即由B2到F的最短距离为15，相应