18.3.1 离散动态决策模型

很大一类优化问题可以用动态规划法求解. 我们把这样的优化问题看作自然地或形式上按时间行进的过程, 并且它由依赖时间的决策所控制. 如果这一过程可以分解成有穷或可数无穷多步,则它称为离散动态规划. 本节仅讨论 $n$ 级离散过程.

18.3.1.1 $n$ 级决策过程

一个 $n$ 级过程 $P$ 从 0 级初始状态 ${\underset{―}{x}}_{a} = {\underset{―}{x}}_{0}$ 开始,通过中间状态 ${\underset{―}{x}}_{1}, {\underset{―}{x}}_{2}, \dots$ , ${\underset{―}{x}}_{n - 1}$ 直到进入最终状态 ${\underset{―}{x}}_{n} = {\underset{―}{x}}_{e} \in X_{e} \subseteq R_{m}$ . 状态向量 ${\underset{―}{x}}_{j}$ 在状态空间 $X_{j} \subseteq R_{m}$ 中. 为了将状态 ${\underset{―}{x}}_{j - 1}$ 驱动到状态 ${\underset{―}{x}}_{j}$ ,要求找一个决策 ${\underset{―}{u}}_{j}$ . 在状态 ${\underset{―}{x}}_{j - 1}$ 处所有可能的决策向量 ${\underset{―}{u}}_{j}$ 构成决策空间 $U_{j} ({\underset{―}{x}}_{j - 1}) \subseteq R^{s}$ . 从 ${\underset{―}{x}}_{j - 1}$ 出发,可以通过如下变换得到下一个状态 ${\underset{―}{x}}_{j}$ (图 18.14):

\begin{matrix} (18.125) & {\underset{―}{x}}_{j} = g_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j}), j = 1 (1) n . \end{matrix}

01936af3-1230-7a0e-9a4a-8542777881ce_46_378_1498_884_176_0.jpg

18.3.1.2 动态规划问题

我们的目的是确定一个策略 $({\underset{―}{u}}_{1}, \dots, {\underset{―}{u}}_{n})$ 使得过程从初始状态 ${\underset{―}{x}}_{a}$ 驱动至状态 ${\underset{―}{x}}_{e}$ ,并考虑到所有的约束,使得目标函数或费用函数 $f (f_{1} ({\underset{―}{x}}_{0}, {\underset{―}{u}}_{1}), \dots, f_{n} ({\underset{―}{x}}_{n - 1},$ ${\underset{―}{u}}_{n})$ 达到极小. 函数 $f_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j})$ 称作阶段费用函数. 动态规划问题的标准形是

OF: $f (f_{1} ({\underset{―}{x}}_{0}, {\underset{―}{u}}_{1}), \dots, f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n})) \to min$ !(18.126a)

\begin{matrix} (18.126b) & \begin{array}{lll} CT: & {\underset{―}{x}}_{j} = g_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j}), & j = 1 (1) n, \\ {\underset{―}{x}}_{0} = {\underset{―}{x}}_{a}, {\underset{―}{x}}_{n} = {\underset{―}{x}}_{e} \in X_{e}, {\underset{―}{x}}_{j} \in X_{j} \subseteq R^{m}, & j = 1 (1) n, \\ {\underset{―}{u}}_{j} \in U_{j} ({\underset{―}{x}}_{j - 1}) \subseteq R^{m}, & j = 1 (1) n . \end{array}} \end{matrix}

第一种类型的约束 ${\underset{―}{x}}_{j}$ 称作动态约束,而其余约束 ${\underset{―}{x}}_{0}, {\underset{―}{u}}_{j}$ 则称作静态约束. 类似于 (18.126a), 也可以考虑极大问题. 满足所有约束条件的策略称作可行约束. 如果目标函数满足某些附加要求 (参见第 1227 页 18.3.3), 则可以应用动态规划法.

18.3.1 离散动态决策模型 ​

18.3.1.1 n 级决策过程 ​

18.3.1.2 动态规划问题 ​

18.3.1 离散动态决策模型

18.3.1.1 $n$ 级决策过程

18.3.1.2 动态规划问题