运筹学课件动态规划.ppt

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

1、第十章动态规划（DP）DynamicProgramming§1多阶段决策过程最优化问题（掌握）§2基本概念、基本方程与最优化原理（掌握）§3动态规划应用（掌握）动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，可以把困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题，解决了这一系列较容易的单阶段问题，也就解决了这个困难的多阶段决策问题。每个阶段都要进行决策,目的是使整个过程的决策达到最优效果。多阶段决策问题：是动态决策问题的一种特殊形式；在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段

2、；需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。多阶段决策问题的典型例子：1.生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。12n状态决策状态决策状态状态决策2.航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使

3、之能最省燃料和实现目的（如软着落问题）。不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。3.最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643§1最短路径问题P201例1。§2基本概念、基本方程及最优化原理一、基本概念1、阶段（stage）指一个问题需要作出决策的步骤。通常按时间和

4、空间的自然特征划分阶段。如例1是按距A点距离划分的阶段。2、状态（state）--最关键参数指每个阶段初所处的自然状况或客观条件。它既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和依据。通常第k个阶段的有若干个状态，用状状态变量sk来描述。例1中某个阶段的状态就是所在的位置。通常状态数比阶段数多1。3、决策（decision）指某一阶段内的抉择，通常用决策变量xk(sk)表示第k阶段状态是sk时所做的选择，这个决策决定了第k+1阶段的状态。如：x2(B1)=C2表示第2阶段处于状态B1时选择了由B1到C2，即以C2做终点。又如：x3(C1)

5、=D24、策略（policy）由所有各阶段的决策组成的序列称为全过程策略，记作p1,n(s1)能够达到总体最优的策略叫做最优策略。从第k个阶段开始到最后阶段的决策组成序列称为k子过程策略简称K子策略（subpolicy）。记作pk,n(sk)5、指标函数指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。指标函数的最优值，称为最优值函数，记作f1(s1)或fk(sk)。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。fk(sk)就是指对某一确定状态选取最优策略后得到的指标函数值，即对某一最优子

6、策略的效益度量值。阶段指标函数：rk(sk,xk)表示在第k阶段的sk状态下做出xk决策时的指标值。6、状态转移方程（状态转移率）从sk的某一状态值出发，当决策变量xk（sk）的取值决定后，下一阶段状态变量sk+1的取值也随之确定。这种从上一阶段的某状态值到下阶段某状态值的转移的规律称为状态转移率，又叫状态转移方程。sk+1=Tk(sk,xk)图示：阶段kT(sk,xk)阶段k+1T(sk+1,xk+1)状态sk状态Sk+1状态Sk+2决策xk(sk)决策xk+1(sk+1)rk(sk,xk)rk+1(sk+1,xk+1)二、基本方程三、最优化原理

7、最优策略的性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。也就是说最优策略的任一个子策略也是最优的。小结:方程:状态转移方程概念:阶段变量k﹑状态变量sk﹑决策变量uk;指标:动态规划本质上是多阶段决策过程;效益指标函数形式:和、积无后效性可递推解多阶段决策过程问题，求出最优策略，即最优决策序列f1(s1)最优路线，即执行最优策略时的状态序列最优目标函数值从k到终点最优策略子策略的最优目标函数值§3动态规划的应用动态规划求解步骤：1、确定问题的阶段和编号2、确定状态变量sk3、确定决策变量xk

8、（用xk*表示该阶段的最优决策）4、确定状态转移方程5、确定指标函数例一、从A地到D地要铺设一条煤气管道,其中需经过两级中