最优化理论动态规划引言动态规划是解决多阶段决策过程最优化的一种方法。该方法是由美国数学家贝尔曼()等人在20世纪50年代初提出的。并成功地解决了生产管理、工程技术等方面的许多问题,从而建立了运筹学的一个新的分支,即动态规划。Bellman在1957年出版了《DynamicProgramming》一书,是动态规划领域中的第一本著作。§1动态规划问题实例例1给定一个线路网络,AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从A向F铺设一条输油管道,各点间连线上的数字表示距离,问应选择什么路线,可使总距离最短?动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问题是指这样的决策问题:其过程可分为若干个相互联系的阶段,每一阶段都对应着一组可供选择的决策,每一决策的选定即依赖于当前面临的状态,又影响以后总体的效果。ABCDE状态A状态B状态C状态D状态E状态F决策A决策D决策E当每一阶段的决策选定以后,就构成一个决策序列,称为一个决策B决策C策略,它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。§2动态规划的基本概念与原理一。基本概念阶段:是指问题需要做出决策的步数。阶段总数常记为n,相应的是n个阶段的决策问题。阶段的序号常记为k,称为阶段变量,k=1,2,…,,常用顺序编号。状态:各阶段开始时的客观条件,第k阶段的状态常用状态变量表示,状态变量取值的集合成为状态集合,用表示。例如,例1中,AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6决策:是指从某阶段的某个状态出发,在若干个不同方案中做出的选择。表示决策的变量,称为决策变量,用表示例如:表示走到C阶段,当处于C2路口时,,例如:状态转移方程:是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律,用表示。决策变量允许的取值范围称为允许决策集合,第k阶段状态为策略(Strategy)由过程的第一阶段开始到最后一阶段为止称为问题的全过程,由各阶段的决策构成的策略序列称为全过程策略,记为P1n。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643k=1k=2k=3k=4k=5k=6策略状态指标函数:分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段从状态出发,采取决策时的效益,用表示。而过程指标函数从第k阶段的某状态出发,采取子策略时所得到的阶段效益之和:最优指标函数:表示从第k阶段状态为时采用最佳策略到过程终止时的最佳效益。记为其中opt可根据具体情况取max或min。基本方程:此为逐段递推求和的依据,一般为:,例1的基本方程为:
最优化理论动态规划 来自淘豆网m.daumloan.com转载请标明出处.
