动态规划

这是一篇关于动态规划的思维导图，主要内容包括：动态规划在经济管理中的应用，动态规划问题的求解方法，动态规划的基本原理，动态规划模型的建立，动态规划的基本概念，多阶段决策过程最优化问题。

动态规划

• 多阶段决策过程最优化问题
  • 多阶段决策过程是指这样一类特殊的 活动过程，他们可以按时间顺序分解成若干相 互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问題
    • 多阶段资源分配问题
    • 生产和存储控制问题
    • 运输网络问题
      • 动态规划方法导引：最短路问题
        • 全枚举法或穷举法
          • 列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案
        • 所谓“局部最优路径”法
        • 动态规划方法
          • 把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序 地求出各个子问题中所有可能状态的最优决策与最优路线值 ，然后再顺序地求出整个问题的最优策略和最优路线。 动态规划方法是从过程的最后阶段开始考虑，然后 逆着实际过程发展的顺序，逐段向前递推计算直至始点
• 动态规划的基本概念
  • 阶段
    • 把所给问题的过程，按时间或空间过程分解成若干互相联系的阶段，以便按照次序去求每阶段的解
  • 状态
    • 各阶段开始时的客观条件
  • 决策
    • 从某阶段的某个状态出发，在若干个不同方案中 做出的选择
      • 决策变量
        • 表示决策的变量
      • 允许决策范围
        • 决策变量允许的取值范围
  • 策略
  • 状态转移方程
    • 是从上一阶段的某一状态值转变为下一阶段 某一状态值的转移规律
  • 指标函数
    • 用于衡量所选定策略优劣的数量指标
      • 阶段指标函数
      • 过程指标函数
  • 最优指标函数
    • 最佳策略，最佳效益
  • 基本方程
    • 逐段递推求和的依据
• 动态规划的基本原理
  • 基本思想
    • 按多阶段决策过程划分阶段，恰当地选取状态变量，决策变量及定义最优指标函数，从而把问题化成同类型的子问题，然后逐个求解
    • 求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用前面求出的子问题的最优结果。最后一个子问题的最优解，就是整个问题的最优解
    • 动态规划问题最优决策选取从全局考虑
  • 最优化原理
    • 最优策略的任一后部子策略都是最优的。无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略
• 动态规划模型的建立
  • 确定各个变量及方程函数
    • 阶段变量
    • 状态变量
      • 能正确描述受控过程的演变特性
      • 满足无后效性
        • 无后效性：给定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响
    • 决策变量
    • 列出状态转移方程
    • 指标函数
• 动态规划问题的求解方法
  • 逆序法
    • 划分问题阶段，（k=n，...，1）
    • 稳定状态变量sk和决策变量uk
    • 写出状态转移方程s(k+1)=Tk(sk,uk)
    • 写出指标函数V(k,n)(sk)
    • 写出基本方程
    • 从k=n开始逆推，逐步求得各阶段的最优决策和相应的最优值，直到k=1时求得整个问题的全局最优决策和最优值
  • 顺序法
    • 划分问题阶段，（k=1，...，n）
    • 稳定状态变量sk和决策变量uk
    • 写出状态转移方程sk=Tk(s(k+1),uk)
    • 写出指标函数V(1,k)(sk)
    • 写出基本方程
    • 从k=1开始顺推，逐步求得各阶段的最优决策和相应的最优值，直到k=n时求得整个问题的全局最优决策和最优值
  • 区别
    • 求解的行进方向不同
    • 状态转移方式不同
    • 指标函数的定义不同
    • 基本方程形式不同
• 动态规划在经济管理中的应用
  • 背包问题
    • 一般的提法为：一旅行者携带背包去登山。已知他所能承受的背包重量的极限为a (千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为 ai(千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量xi的函数gi（xi）（i=1,2,3，...，n）。问旅行者如何选择携带物品的件数，以使总价值最大（该模型解决的是运输工具包括卫星的最优装载问题