文档介绍：动态规划CONTENTSPARTONEPARTTWO动态规划的发展动态规划的基本组成PARTTHREEMatlab 算法PARTFOUR库存管理发展动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),即把求解在整个时间段上一个全局解的问题能化解为一系列在各个时间段上的局部优化问题。把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。发展运用动态规划可将多阶段最优决策问题(DOP)分解为一系列单阶段最优决策问题,从而使问题的求解计算量得到极大的降低。相比其它解法,动态规划总是提供一个反馈控制策略。而这在有扰动或在随机情况下是至关紧要的。在应用动态规划求解以上单目标多阶段最优决策问题时,问题(DOP)的目标函数必须是可分的,且具有单调性。而在实际复杂决策问题中,目标函数往往不具备可分性结构。另外在现实生活中,彼此冲突的多目标属性常常无法用一个目标函数统一度量。发展动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。?举例:线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;区域动规:石子合并,加分二叉树,统计单词个数,炮兵布阵等;树形动规:贪吃的九头龙,二分查找树,数字三角形等;背包动规:01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题等;?应用实例:最短路径问题,库存管理,网络流优化等。CONTENTSPARTONEPARTTWO动态规划的发展动态规划的基本组成PARTTHREEMatlab 算法PARTFOUR库存管理动态规划?动态规划基本组成(1)阶段整个问题的解决可分为若干个阶段依次进行,描述阶段的变量称为阶段变量,记为k。(2)状态状态表示每个阶段开始所处的自然状况或客观条件,它描述了研究问题过程的状况。各阶段状态通常用状态变量描述,用x(k) 表示第k阶段状态变量,n个阶段决策过程有n+1个状态。(3)决策从一确定的状态作出各种选择从而演变到下一阶段某一状态,这种选择手段称为决策。描述决策的变量称为决策变量,决策变量限制的取值范围称为允许决策集合。用uk(xk) 表示第k阶段处于状态x(k)时的决策变量,它是xk 的函数。用Dk(xk) 表示 xk 的允许决策集合。?动态规划基本组成(4)策略每个阶段的决策按顺序组成的集合称为策略。由第k阶段的状态xk开始到终止状态的后部子过程的策略记为{uk(xk),uk+1(xk+1),…,un(xn)}。可供选择的策略的范围称为允许策略集合,允许策略集合中达到最优效果的策略称为最优策略。从初始状态x1(=x1*)出发,过程按照最优策略和状态转移方程演变所经历的状态序列{x1*,x2*,…,xn*, xn+1* }称为最优轨线。(5)状态转移方程如果第k 个阶段状态变量为xk,作出的决策为uk,那么第k+1阶段的状态变量xk+1也被完全确定。用状态转移方程表示这种演变规律,记为 xk+1=T(xk , uk) 。动态规划?动态规划基本组成(6)指标函数指标函数是系统执行某一策略所产生结果的数量表示,是衡量策略优劣的数量指标,它定义在全过程和所有后部子过程上,用fk(xk) 表示。过程在某阶段j 的阶段指标函数是衡量该阶段决策优劣数量指标,取决于状态xj和决策uj,用vj(xj,uj) 表示。动态规划?动态规划逆序求解的基本方程:动态规划