建模：-动态规划.ppt

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

1、主要内容:§6.1多阶段决策过程的最优化§6.2动态规划的基本概念和基本原理§6.3动态规划方法的基本步骤§6.4动态规划应用举例第六章动态规划§6.1多阶段决策过程的最优化动态规划是解决多阶段最优决策的方法,由美国数学家贝尔曼(R.Bellman)于1951年首先提出;1957年贝尔曼发表动态规划方面的第一部专著“动态规划”,标志着运筹学的一个新分支的创立。例6.1求解最短路问题动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的;动态规划的各个决

2、策阶段不但要考虑本阶段的决策目标,还要兼顾整个决策过程的整体目标,从而实现整体最优决策.动态规划的分类:离散确定型离散随机型连续确定型连续随机型动态规划的特点:动态规划没有准确的数学表达式和定义精确的算法,它强调具体问题具体分析,依赖分析者的经验和技巧。与运筹学其他方法有很好的互补关系,尤其在处理非线性、离散性问题时有其独到的特点。通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适

3、合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。具有无后效性的多阶段决策过程的特点是系统过去的历史，只能通过现阶段的状态去影响系统的未来，当前的状态就是后过程发展的初始条件。动态规划的应用动态规划在工程技术,企业管理,军事部门有广泛的应用;可解决资源分配,生产调度,库存管理,路径优化,设备更新,投资规划,排序问题和生产过程的最优控制等问题;拾火

4、柴游戏:桌子上放30根火柴,每人一次可拾起1－3根,谁拾起最后一根火柴谁输,如果你先选择,如何保证你能赢得游戏？29－25－21－17－13－9－5－1动态规划与倒推求解:使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式,要涉及以下概念:(1)阶段(2)状态(3)决策与策略(4)状态转移(5)指标函数§6.2动态规划的基本概念和基本思想一、基本概念(1)划分阶段把一个复杂决策问题按时间或空间特征分解为若干(n)个相互联系的阶段(stage),以便按顺序求解;阶段变量描述当前所处的阶段位置，一般用下标k

5、表示;每阶段有若干状态(state),表示某一阶段决策面临的条件或所处位置及运动特征的量,称为状态。反映状态变化的量叫作状态变量。k阶段的状态特征可用状态变量sk或xk描述;状态有起始、中间、最终状态之分，每一阶段的全部状态构成该阶段的状态集合Sk，并有skSk或xkSk。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段的初始状态记作sk，终止状态记为sk+1(2)确定状态(3)决策、决策变量所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的

6、选择。用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述．也可以是状态变量的函数，记以，表示于k阶段状态sk时的决策变量．决策变量的取值往往也有一定的容许范围，称之允许决策集合．决策变量uk(sk)的允许决策集用UK(SK)表示，uk(sk)DK(SK),允许决策集合实际是决策的约束条件。(4)策略和允许策略集合策略(Policy)也叫决策序列．策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为。从k阶段

7、到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为，显然当k=1时的k部子策略就是全过程策略。(5)状态转移方程状态转移确定从一个状态到另一个状态的转移过程,由状态转移方程描述:sk+1=T(sk,uk);状态转移方程在大多数情况下可以由数学公式表达,如:sk+1=uk(sk)；(6)指标函数用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。用gk(sk,

8、uk)表示第k段处于状态sk且所作决策为uk时的指标，则它就是第k段指标函数，简记为gk。用RK(sk,uk)表示第k子过程的指标函数。表示处于第k段sk状态且所作决策为uk时，从sk点到终点的距离。由此可见，RK(sk,uk)不仅跟当前状态sk有关，还跟2）过程指标函数（也称目标函数）1