运筹学动态规划..ppt

运筹学—动态规划复合系统工作可靠性问题姓名:佘俊学号:20070150212内容动态规划的基本概念和基本原理动态规划模型的建立和求解动态规划在经济管理中的应用复合系统工作可靠性问题动态规划基本原理最优化原理“一个过程的最优策略具有这样的性质:即无论初始状态及初始决策如何,对于先前决策所形成的状态而言,其以后的决策应构成最优策略”。AMB内容1、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步,在确定多阶段特性后,按时间或空间先后顺序,将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念,以便划分阶段。2、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性,而且各阶段状态变量的取值能够确定。一般地,状态变量的选择是从过程演变的特点中寻找。3、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量,同时要给出决策变量的取值范围,即确定允许决策集合。动态规划模型的建立4、确定状态转移方程根据k阶段状态变量和决策变量,写出k+1阶段状态变量,状态转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数,建立动态规划基本方程阶段指标函数是指第k阶段的收益,最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值,最后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同,动态规划模型没有统一的模式,建模时必须根据具体问题具体分析,只有通过不断实践总结,才能较好掌握建模方法与技巧。动态规划的求解离散变量的分段穷举法连续变量的解法逆序解法顺序解法连续变量的离散化解法高维问题的降维法AB1B2C1C2C3D2433332111412ks1u1s2u2s3skuksk+112ks1u1s2u2s3skuksk+1××11