文档介绍：第六章动态规划
Dynamic Programmlng
§ 基本概念和常用术语
一、什么是动态规划?
在日常生活和工程实践中,有很多问题是分阶段进行而达到预定目标的,在每个阶段中都要考虑选择进行的路线和方法,才能达到问题的最优解决方案,这就是所谓的多阶段决策过程的最优化问题,即人们要按某一预定目标实现某个过程,该目标是可以用某种数量来衡量的,该过程可分成若干阶段进行,每个阶段都可以有许多不同的决策,以使过程按不同的方式进行。问题就是要确定各个阶段的决策,使整个过程的实现达到预定的最优目标,即寻找实现该过程的最优总策略。动态规划是解决多阶段决策过程最优化问题的一种数学方法,是最优化的一个分支,它的中心思想是所谓的“最优化原理”,在此基础上提出了一系列的求解方法。
基本概念和常用术语
许多工程技术或经济管理中的问题常常既可以用动态规划方法解决,也可以用线性规划或非线性规划方法解决,有时用动态规划方法往往更为简便,特别是对于某些离散型的问题,近年来动态规划方法又广泛用于最优控制问题。
动态规划模型可根据其过程的时间参量是离散的还是连续的而分为离散决策过程和连续决策过程;又可根据决策过程的演变是确定性的还是随机性的而分为确定性决策过程和随机性决策过程。本章主要结合油气储运中的应用讨论离散确定性过程。
基本概念和常用术语
所谓“动态”意味着该问题可按时间的推移而分成若干个阶段,实际上很多问题中并没有时间因素,而是人为地分成逐步向前推进的各个阶段,即人为地引入一个“时段”的概念,以便使用动态规划的方法来求解。最典型的是最优路径问题,后面将给大家详细介绍。
二、基本概念和常用术语
1、阶段:把待求解的问题按其进行过程恰当地划分为若干个相互联系的阶段, 根据具体情况不同, 对某一问题可按时间的推移分成若干个阶段, 也可按其它情况划分阶段。
基本概念和常用术语
2、状态:一个阶段可以有若干个状态,每个阶段都有起始状态和终了状态,例如在管道选线问题中,常以一段管道作为一个阶段,该段管道的起始位置是该阶段的起始状态,也是上一段管道的终了状态。
表示状态的参数称为状态变量,常用x或y表示,通常都选各阶段相对应的点作为状态变量,各阶段的状态变量是相互联系的,如果把问题分成n个阶段,取各阶段的起点状态作为状态变量,如用xk表示第k阶段起点的状态,则该问题中各阶段的状态变量为xk(k=1~n)。每一阶段都有几个可能的起点状态,即每一阶段有一个状态变量的集合xk={xk1,xk2,…},在此集合中,只有一个状态变量是最优的。
基本概念和常用术语
3、决策:决策就是在某阶段的状态变量给定后,从该状态演变到下一阶段的某个状态所做的选择。
为了达到问题的最优解,在每一阶段都要选择一种方案,或称一个决策,以达到下一阶段。如管道选线问题中确定走哪条路线。用于表示这种决策的变量称为决策变量。
显然第k阶段选择什么样的决策是与该阶段的起始状态密切相关的,常用uk(xk)表示在第k阶段起始状态为xk时的决策变量。同样在某一阶段常有若干个可能的决策变量,其中只有一个是最优的,这些可能的决策变量常被限制在某一范围内,这些变量的集合称为允许决策集合,常用Uk(xk)表示。
基本概念和常用术语
4、状态转移方程:上、下两个阶段中的状态变量和决策变量之间的函数关系称为状态转移方程。
如对于第k阶段来说,在某一起点状态xk下,当选择某一决策变量uk后,其终了状态即下一阶段的初始状态xk+1就被确定了,可表示为:xk+1=Tk(uk,xk),此函数关系式即为状态转移方程。
5、策略:对于某一问题的某一解决方案,其各个阶段都会有一个相应的决策,才能构成一个解决方案,这些决策的集合称为这一方案的总策略。如果某一问题可分为n个阶段,某一方案的各阶段决策分别为:
u1(x1),u2(x2),…,un(xn)
则该方案的总策略为P1n(x1)={u1(x1), u2(x2), …, un(xn)},从第k阶段到最后的部分策略为Pkn(xk)={uk(xk), …, un(xn)},称为子过程策略。
基本概念和常用术语
对于某一问题,常有若干个解决方案,即由若干个总策略组成的集合,称为允许策略集合,在允许策略集合中达到最优效果的策略称为最优策略。
6、效益函数:又称代价函数,指用数量指标及函数关系表示的整个过程所要达到的效益或付出的代价。整个过程的效益或代价的大小与各个阶段的状态变量和决策变量的大小有关,可表示为:
Vk,n(xk)={xk,uk,xk+1, uk+1,…, xn+1, un+1}
研究整个问题的目的就是要找出效益函数为最优值时的总策略,最优的效益函数可表示为:opt Vk,n(xk),对于效益函数opt为max,对于代