跳转至

动态规划⚓︎

约 1716 个字 预计阅读时间 6 分钟

6.1 多阶段决策问题⚓︎

  • 各阶段的方案选择称为决策；
  • 各个阶段的决策确定后，就构成一个决策序列，也就是策略；
  • 由于可选决策的不唯一性，这些相互联系的决策构成的策略就不止一个，这些策略构成一个集合，称策略集合；

  • 在策略集合中选一个策略使得在预定的约束下达到最好的效果，这样的策略就是最优策略。

  • 例题：

    • 速运公司配送路线选择
    • 资源分配问题
    • 物流配送装箱问题

6.2.2 动态规划的基本概念和基本方程⚓︎

阶段(Stage)⚓︎

  • 把一个决策问题分为若干相互联系的阶段，称为”阶段变量“
  • 从第\(k\)个阶段到最后一个阶段的过程被称为\(k\)的后部子过程；

状态(State)⚓︎

  • 状态：表示每个阶段开始时系统面临的自然状况和客观条件，是由系统本身决定的，反映系统的具体特征，描述过程的具体演变；
  • 状态变量：
  • 状态集合：
  • 作为动态规划的状态变量具有如下重要性质：既能描述过程演变特征，还能满足无后效性，马尔可夫性。

决策(Decision)⚓︎

  • 某个阶段的状态给定后往往可以做出不同的决定，使过程依不同的方式转移到下一阶段的某个状态，这种决定称为决策；
  • 描述决策的变量称为决策变量，第k个阶段的决策变量 \(u_k(s_k)\)；
  • 决策变量集合

状态转移函数⚓︎

  • 多阶段决策过程：序贯决策，如果给定第\(k\)个阶段的状态变量\(s_k\)，则在该阶段的决策变量确定之后，第\(k+1\)个阶段的状态\(s_{k + 1}\)也就随之确定，可以把\(s_{k + 1} = T_k (s_k, u_k)\)
  • 如果状态转移函数是确定的，就是确定性多阶段决策过程；如果这种转移关系是通过某种概率实现的，就称为随机性多阶段决策过程。

指标函数(Stage Indicator)和最优值函数⚓︎

  • 用来衡量所实现过程优劣的数量指标，以便对策略进行评价：指标函数。
  • 阶段指标函数
  • 过程指标函数
    • 所包含的阶段指标函数的“积”
    • \(V_{k, n} = V_{k,n}(s_k, u_k, s_{k+1}, u_{k+1},...,s_n, u_n)\)
    • \(V_{k,n} = v_k(s_k,u_k) + V_{k+1,n}\)，第\(k\)阶段的决策指标 \(+\) 自\(k+1\)阶段的向后决策指标；
\[f_k(s_k) = \mathop{opt} \limits_{P_{k,n} \in P_{k,n} (s_k)} V_{k,n}(s_k, u_k, s_{k+1}, u_{k+1},...,s_n, u_n )\]

6.2.2 动态规划的基本方程⚓︎

  1. 将实际问题划分为多个阶段，根据时间和空间的自然特性来划分；
  2. 正确选择状态变量\(s_k\)，满足无后效性；
  3. 确定决策变量\(u_k\) 以及每个阶段的允许决策集合 \(U_k(s_k)\)
  4. 写出状态转移方程\(s_{k + 1} = T_k(s_k, u_k)\)
  5. 正确写出指标函数\(V_{k,n}\)
\[f_k(s_k) = \mathop{opt} \limits_{P_{k,n} \in P_{k,n} (s_k)} \{ v_k(s_k, u_k) + f_{k+1}(s_{k+1}) | k = n,n-1,...,1 \}\]
  • 也可以逆向推导
  • 初始状态给定，用逆序的方法比较好；当终止状态给定，用顺序的方式比较好；

6.3 最优化原理和最优性定理⚓︎

  • 最优化原理：作为整个决策过程最优策略，具有如下性质：无论过去的决策状态如何，对于前面形成的状态而言，余下的策略必须构成最优策略。也就是“最优策略的子策略也必须是最优的”。

  • 动态规划的最优性定理：考虑阶段数是n的多阶段决策过程，其阶段编号为 \(k = 0,1,..,n - 1\)，其可行策略 \(p^{*}_{0, n - 1} = (x^{*}_0, x^{*}_1, ..., x^{*}_{n-1}, )\) 是最优策略的充分必要条件是对于任意满足 \(0 < k < n - 1\)的\(k\)和\(s_0 \in S_0\)，有：

\[V_{0,n-1}(s_0, p^{*}_{0,n-1}) = \mathop{opt}_{p_{0,k-1} \in P_{0, k-1}(s_0)} \{ V_{0,k-1}(s_0, p_{0,k-1}) +  \mathop{opt}_{p_{0,k-1} \in P_{0, k-1}(\tilde{s_k})} V_{k,n-1}( \tilde{s_k}, p_{k,n-1}) \}\]

其中\(p_{0,n-1} = (p_{0,k-1}, p_{k,n-1}); \tilde{s_k} = T_{k-1}(s_{k-1, x_{k-1}})\)，是由给定的初始状态和子策略p_{0,k-1}决定的第k阶段状态。

  • 推论 6.1 如果可行策略是最优策略，则对于任意满足\(0 < k < n-1\)的\(k\)，他的后部子策略对于由他的前部子策略所确定的第\(k\)阶段状态来说，一定是后面\(k\)到\(n-1\)阶段子过程的最优策略。

  • 推论 6.2 对任意满足\(0 \leq k \leq n-2\)的\(k\)，和以任意\(s_k \in S_k\) 为起点的后部子过程而言，可行子策略为最优策略的充分必要条件是：对满足 \(k < t < n\) 的任意整数，有：

【待补充】

满足后部子过程也是最优的。

  • 推论 6.3 对以任意\(s_k\) 为起点的后部子过程而言，函数序列分别是最优值函数序列和最优决策函数序列的充分必要条件是他们满足如下递推方程：

【待补充】

\[V_k = \varphi (s_k, x_k, V_{k+1})\]

6.4 离散确定性动态规划⚓︎

6.5 应用举例⚓︎

6.5.1 可回收资源的再分配问题⚓︎

  • 可回收资源的多期分配：

6.5.2 生产-存储问题⚓︎

  • 已知工厂未来几个月的需求，工厂每个月开工有固定成本，生产单位有一个产品成本；每个月的单位库存成本也已知，库存有上限，计划开始和结束时都有库存为0，制定生产计划使得总费用最小。

6.5.3 设备更新问题⚓︎

  • 设某台设备的年效益和年均维修费、更新净费用如下表所示，确定五年内的更新策略。
  • 每年的决策有两个：更新 / 不更新，状态就是机器“当前”的使用年限。

6.5.4 复合系统可靠性问题⚓︎

某个机器工作系统由n个不同的元件串联成，只要一个失灵，所有的都失灵：为了提高可靠性，每个部件上都有备用件，可以提高对应元件的可靠性，但是会导致成本上升。需要在成本上限的约束下，找到选用各种零件的最优个数，使得可靠性最高。

实例：3个零件，可靠性分别为：0.9，0.8，0.5， 单位成本分别为：30，15，20，成本约束是105，求可靠性最优的方案。

Notes

有多少个元件就有多少个决策阶段，所以\(k = 3\)个决策阶段，决策变量\(x_k\) 表示第k个元件的数量，\(f_k(s_k)\)表示\(k\)原件到\(n\)元件组成系统的最大可靠性。第一个阶段，决定装置1，：\(f_1(105) = \mathop{\max} \{ 0.9 * f(75), 0.99 * f(45) , 0.999 * f(15) \}\), 同理再计算f(75 )等等等，递推到找到最优结果。 这里的指标函数是连乘性的

6.5.5 生产排序问题⚓︎

6.5.6 背包问题🎒 🌟🌟⚓︎

0-1背包⚓︎

  • 固定的一个包，有n个物品，对应有重量和价值，问怎么装让总价值最大？

连续背包⚓︎

6.5.7 订购和销售问题⚓︎

  • 既要决定生产多少，还要决定销售多少。
Note

最终全部售出: \(f_5 (s_5) = 0\) 此前每一期，都需要考虑两个决策变量：订购数量和售出数量， \(f_k = \mathop{\max} p_k x_k - c_k y_k + f^{*}_{k+1}(s_{k+1})\)，这里的\(s_{k+1} = s_k - x_k + y_k\)