数学模型动态规划.doc

羃动态规划蚁动态规划(dynamicprogramming)是运筹学的一个重要分支,(),《动态规划》一书,§1动态规划的概念与原理蒈一、动态规划的基本概念蒃引例:最短路线问题莂美国黑金石油公司(pany)最近在阿拉斯加(Alaska)的北斯洛波(NorthSlope)发现了大的石油储量。为了大规模开发这一油田,首先必须建立相应的输运网络,使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站(结点C)与装运港(结点P1、P2、P3)之间需要若干个中间站,中间站之间的联通情况如图1所示,图中线段上的数字代表两站之间的距离(单位:10千米)。试确定一最佳的输运线路,使原油的输送距离最短。蕿解:最短路线有一个重要性质,即如果由起点A经过B点和C点到达终点D是一条最短路线,则由B点经C点到达终点D一定是B到D的最短路(贝尔曼最优化原理)。此性质用反证法很容易证明,因为如果不是这样,则从B点到D点有另一条距离更短的路线存在,不妨假设为B—P—D;从而可知路线A—B—P—D比原路线A—B—C—D距离短,这与原路线A—B—C—D是最短路线相矛盾,性质得证。蚇根据最短路线的这一性质,寻找最短路线的方法就是从最后阶段开始,由后向前逐步递推求出各点到终点的最短路线,最后求得由始点到终点的最短路;即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法,将此过程划分为4个阶段,即阶段变量;取过程在各阶段所处的位置为状态变量,按逆序算法求解。肆膂蚀罿薆C袃P3蒈P2肇P1羅M11蚃M12蕿M21芆M22莄M23莃M31薁M32薈M33袄M34膄10莈12蚆8芃6袄9葿11聿10羇7莀6蒁9膇7莆5肁11芈4芆6螅8袁6荿4蚈3芅7薂7莁6螆5蚄3莂4膈k=1腿k=2肃k=3肂k=4芀图1芇螇螃莁莅膆薃膈螈蚆芃膀当时:袆由结点M31到达目的地有两条路线可以选择,即选择P1或P2;故:肅选择P2肄由结点M32到达目的地有三条路线可以选择,即选择P1、P2或P3;故:芁选择P2艿由结点M33到达目的地也有三条路线可以选择,即选择P1、P2或P3;故:蒄选择P3螄由结点M34到达目的地有两条路线可以选择,即选择P2或P3;故:肈选择P2莇当时:袄由结点M21到达下一阶段有三条路线可以选择,即选择M31、M32或M33;故:芁选择M32肀由结点M22到达下一阶段也有三条路线可以选择,即选择M31、M32或M33;故:蒅选择M32或M33莃由结点M23到达下一阶段也有三条路线可以选择,即选择M32、M33或M34;故:羁选择M33或M34膁当时:袈由结点M11到达下一阶段有两条路线可以选择,即选择M21或M22;故:肆选择M22螁由结点M12到达下一阶段也有两条路线可以选择,即选择M22或M23;故:罿选择M22羆当时:蒆由结点C到达下一阶段有两条路线可以选择,即选择M11或M12;故:蒂选择M11羀从而通过顺序(计算的反顺序)追踪(黑体标示)可以得到两条最佳的输运线路:C—M11—M22—M32—P2;C—M11—M22—M33—P3。最短的输送距离是280千米。莈一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。袅节1、阶段肁阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量,常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的,但要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用表示。蒇芅羂2、状态衿状态(state)表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性,即当某阶段的状态变量给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。衿描述状态的变量称状态变量(statevariable)。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用表示第阶段的状态变量,它可以是一个数或一个向量。用表示第阶段的允许状态集合。螄个阶段的决策过程有个状态变量,表示演变的结果。螃根据过程演变的具体情况,状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化;为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。羀羈3决策膃当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选择手段称为决策(decision),在最优控制问题中也称为控制(control)。蒃描述决策的变量称决策变量(decisionvariabl