运筹学第八章-动态规划

第八章动态规划8.1动态规划的研究对象和特点8.2动态规划的基本概念与最优化原理8.3动态规划的求解与应用8.4随机动态规划Page18.1动态规划的研究对象和特点动态规划(DynamicProgramming)是一项重要的数量规划方法，由美国数学家贝尔曼(R..Bellman)和徳赖费斯（Dreyfus）等人在二十世纪中叶提出的。1957年，贝尔曼发表了动态规划方面的第一本著作〈〈DynamicProgramming〉〉,标志着运筹学的又一个分支动态规划的建立。动态规划被广泛应用于企业经营、工业工程、资源理论、最佳控制理论和商业决策理论中，并且取得了一定的经济效果。Page2一、动态规划的研究对象动态规划最初是根据多阶段决策问题的特点，由贝尔曼等人提出了解决此类问题的“最优化原理”，并且进一步成功地解决了许多实际问题，才得到大家的充分重视。1.多阶段决策又称序贯决策问题，通常它可以按时间顺序分成若干个相互联系的阶段，在每一个阶段都需要作出一个决策，每一个阶段作出的决策又称为子策略，每个阶段作出的子策略就组成此多阶段决策问题的策略集。实际工作中我们很难遇到不影响未来决策的当前决策，决策者经常面临的问题通常是要他们作出一系列决策，而这些决策中的每一个均依赖于先前决策的结果，动态规划就可被用来解决很多此类问题。2.动态规划也可以应用于解决某些与时间无关的问题。例如：把固定数量的几种资源在若干用途上进行配置，这个问题被划分成几个步骤来求解，用这种方法求最后的决策就好象它和时间有关似的，这就进一步扩大了动态规划解决问题的范围。Page3二、动态规划的特点1.动态规划根据问题的具体情况，把整个问题划分成数个阶段，而变成数个部分问题。当这些部分问题由阶段的顺序而贯通，则形成一项多重阶段的程序（过程）。2.动态规划对整个问题的求解，通常是从一个阶段的部分问题开始，逐个逆序向前推求解。对某些问题也可以反过来从最前一个阶段顺序向后推求解。但逆序求解是动态规划的一个显著特点。3.动态规划在每一个阶段求得自以往各阶段至本阶段的最佳解，并将此项最佳解带入次阶段。4.动态规划的目标是全局（系统）的最优化，而不仅是局部（本阶段）的优化。5.动态规划与运筹学的其它分支不同，它没有标准的数学表达式和解题规则，但却是更一般性的解题方法。一个动态规划问题公式的格式在性质上和复杂程度上会与其它动态规划问题大不一样，其差异取决于问题的结构。解题时要有丰富的想象力和创造性技巧。总之，应用动态规划可把一个复杂的难以下手的大问题变成一系列较易于各个解决的小问题，然后可以一个一个求解。所以许多问题用动态规划求解，常较运筹学的其它方法更有效果。Page4三、动态规划数学模型的类型动态规划分为离散确定性、离散随机性，连续确定性、连续随机性四种决策类型。本章主要研究离散型动态规划，这也正是动态规划的核心内容和特色所在Page5一、多阶段决策问题（漫游数学家问题）这是一个典型的多阶段决策问题，通过这个例子，有助于我们更好的理解动态规划的基本概念和基本思路。例8—1有一个智慧比金钱多的应用数学家渴望进行一次旅行。假设他住在城市1，而渴望到城市10（见图8-1表示可能的路线和花费）。这是一个长途的旅行，要求必须进行3次中间停留，中间站可以选择。他希望为这次旅行付出的花费最小，那么他将选择那些城市作为自己的中间站？Page7Page80站1站2站3站4站.图8-1684712441526381097413411369553分析：他可以采用枚举法，列出所有18种可能的路线来解决这个问题。是否有更好的方法？例如：假设我们在城市5，可通过城市8，也可通过城市9到达城市10，很明显我们会选城市9而不会选城市8。因为（8+3）＜（9+5）,即（5—9—10）这条路花费较少,由于可按三种不同的路线到达城市5，可以看出枚举法将做不少不必要的工作。这个相当简单的观察为我们提供了一种解题的思路。若我们处在第3站，可通过城市8或9到达城市10可用表8—1说明表8—1Page9第3站城市Min（f）最佳路径858-------10939-------10现在假定在第2站，并问哪一条路到城市10最近，花费最小。若在城市5，最小花费是11，即Min{9+5,8+3}=11，将选择路径（5—9—10）。同理若在城市6最小花费是12，Min{7+5,12+3}=12，将选择（6—8—10）。城市7最小费用8，Min{----,5+3}=8，将选择路径为（7—9—10），结果列于表8—2表8—2Page10第2站城市Min（f）最佳路径5115---9----106126---8----10787---9----10现在假定在第1站，用类似方法可知：由城市2到城市10的最小费用为Min{3+11,---,4+8}=12，路径为（2—5—9—10）。第一站计算结果为表8—3表8—3Page11第1站城市Min（f）最佳路径2122----7---9----103143-----7---9----104124----5---9----10最后假定在第0站即城市1也就是起点，那么由城市1到城市10最小花费的路线，应由城市1到第一站的哪个城市呢？由Min{4+12,3+14,11+12}=16可知花费最小的路线为（1—2—7—9—10），第0站计算结果见表8—4表8—4Page12第0站城市Min（f）最佳路径1161—2—7—9—10Page1352638109741341134697125534461812340531112812141216阶段和阶段变量.状态和状态变量.决策和决策变量.策略和最优策略.指标函数.状态转移方程.1.阶段（Stage）和阶段变量Page15把所给问题的过程，按照时间或空间恰当地划分为若干个相互联系的阶段，以便于求解。描述阶段的变量称为阶段变量，通常用K表示阶段变量。如例8-1可分为4个阶段，当K=2时，表示对第2阶段求解。2.状态（State）和状态变量状态表示某阶段的初始位置，它既是该段某支路的始点，同时也是前一阶段某支路的终点。通常一个阶段，包含若干个状态。描述过程状态的变量，称为状态变量，可用一个数、一组数或一个向量表示。用SK表示，如例8—1中，阶段2有三个状态。则状态变量S2可取{２，３，４}，S2=3表示第二阶段在状态3{城市3}处考虑问题．Page163.决策{Deciding}和决策变量决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量（它是改变状态变量的机会，可能以概率方式出现），常用XK(SK)表示第K阶段当状态为SK时的决策变量，它是状态SK的函数。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合，通常用DK(SK)表示第K阶段的关于SK状态的允许决策集合。显然有XK(SK)∈DK(SK)Page174．策略（Strategies）和最优策略由过程的第K阶段开始到终点为止的过程称为问题的后部子过程。由后部子过程的每个阶段的决策组成的决策函数序列{XK(SK)，XK+1(SK+1)―――――Xn(Sn)}就称为子过程的策略，简称子策略。并记为：PK..n(SK)={XK(SK)，XK+1(SK+1)......Xn(Sn)}当K=1时，则此决策函数序列就是全过程的一个策略，简称策略，记为P1..n(S1)。可供选择的策略范围，称为允许策略集合用P表示。使问题达到最优效果的策略，称为最优策略。例8—1中：{X1(1)=2,X2(2)=7,X3(7)=9,X4(9)=10}就是一个策略，且为最优策略。Page185．指标函数和最优指标函数值阶段指标函数是用来表示某阶段给定状态和决策取得效应的一种数量指标。它是定义在第K阶段上的一个数量函数。用vK..N表示：vK..N=vK..N(SK,XK)过程指标函数（简称指标函数；又称目标函数）是用来衡量所考查过程效应的一种数量指标。它是定义在从第K阶段到终点过程上的一个数量函数。用VK..N表示：VK..N=VK..N(SK,XK.SK+1,XK+1――――SN+1)(k=1,2――――N)当初始状态给定时过程的策略就确定了，因而指标也就确定了，所以指标函数又是初始状态和策略的函数即：VK..N=VK..N(SK，PK..N(SK))Page195．指标函数和最优指标函数值指标函数VK..N的最优值，称为相应的最优指标函数值记为：FK(SK)=optVKN(SK，PK..N(SK))式中opt是optimization(最优化)的缩写，根据问题不同取Max或Min。在不同问题中指标的涵义不同，可以是距离、费用、收益、产品产量、资源消耗等。从例8—1中：VK..N表示第k阶段的点SK到终点城市10的花费。FK(SK)=MinVK,N表示SK到城市10的最小花费。Page206.状态转移方程状态转移方程表示从阶段k到阶段k+1的状态转移规律的表达式。多级决策过程中，如给定了第K阶段的状态变量SK和决策变量XK(SK)，则下一阶段K+1阶段状态变量的值也就确定了。即SK+1=TK(SK,XK(SK))上式又称为状态转移函数。Page21三、动态规划数学模型的构造条件1.能够恰当地划分问题的阶段，把问题化为多阶段决策过程；2.正确地选择状态变量动态规划中的状态要能描述受控过程的演变特征：满足无后效性和可知性。Page22无后效性——如果过程某阶段的状态给定，则在这个阶段以后过程的发展不受前面各个阶段的影响，只和当前状态及今后的决策有关，过程前面的状态和决策只能通过形成的当前状态去影响过程未来的发展，即重要的是当前的状态和今后的决策而于过去的状态和决策无关。可知性—各阶段状态变量的值直接或间接均为已知。Page23Page243.能确定决策变量及各阶段的允许决策集合；4.能写出状态转移方程；5.根据实际问题，列出指标函数VK,N，要满足递推关系。VK,N(SK,XK,SK+1,XK+1,……SN+1)=Ψ[SK,XK,VK+1..N(SK+1,XK+1,……SN+1)]一般是求和或求积的关系。四、最优化原理和基本方程1.最优化原理最优策略具有这样的性质：无论过去状态和决策如何，对前面决策所形成的某一状态而言，余下的决策序列必须构成最优策略。Page25示意图解释：MBA2.动态规划的基本方程利用最优化原理，把多阶段决策问题的求解过程分解为一个连续的递推过程，由后向前逐步推算。求解时，各阶段以前的状态和决策，对后部子过程来说，只充当其初始条件，并不影响后面过程的最优策略。据此可得出动态规划的递推关系：为使关系式表达方便,可对问题增加第N+1阶段此时有：FN+1(SN+1)=ee为一常数FN+1(SN+1)=e又称为动态规划的边界条件。Page262.动态规划的基本方程对于任何第K阶段（1≤K≤N）当VK,N=∑vj(Sj,Xj)时则有FK(SK)=opt{vK(SK,XK)+Fk+1(SK+1)}XK(SK)∈DK(SK)sK∈SKPage272.动态规划的基本方程Page28又当VK,N=∏vj(Sj，Xj)时则有Fn+1(Sn+1)≠0Fk(Sk)=opt{Vk(Sk,Xk)Fk+1(Sk+1)}Xk(Sk)∈Dk(Sk)Sk∈Sk再有状态转移函数Sk+1=Tk(Sk,Xk(Sk))问题就可以求解啦例8—2：求X1、X2、X3在满足约束条件：X1+X2+X3=CXi≧0(i=1,2,3)之下，使函数F(X1、X2、X3)=X1•X2•X3→MaxK:按变量将问题划分为3个阶段，每个阶段只决定X1、X2、X3其中一个变量的值。SK:表示第K个阶段初尚未分配出的数值，S1=CXK：表示第K个阶段分配给的数值,0≤XK≤SK状态转移函数：Sk+1=SK—XK(K=1、2、3)各个阶段效益按乘积组合，所以基本方