【管理运筹学】第 8 章 | 动态规划（2，动态规划的基本思想）

系列文章

文章目录

系列文章
引言
写在最后

引言

承接前文，介绍完基本概念后，我们来学习动态规划的基本思想与模型求解，用上一篇文章的最短路问题来配合说明。

2.2 动态规划的基本思想

最短路问题中的网络如下图所示，从 A 到 E 可以分成 4 段，第一段从 A 到 B ，有两条路，如果选择去 B2 作为此阶段的决策，则下一阶段的起点就是 B2 ，此时又有两种选择，以此类推，可以求出一个决策序列。每一段选择不同，得到的序列便不同，我们希望求出一个最优决策，此决策对应的路线为 A 到 E 的最短路线。

在这里插入图片描述
显然，通过求出所有路线的距离进行比较，找出最短路对于本例是可行的，但是当路径数增加，这种穷举法的计算量会大大增加。下面介绍动态规划方法，可以帮助我们更好地求解该问题。

动态规划方法基于贝尔曼（R. Bellman）等人提出的最优化原理，这个最优化原理指出：一个过程的最优策略具有这样的性质，即无论初始状态或初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策须构成最优策略。

将该原理应用到最短路问题中，即从 A 到 E 的最短路线若经过 $s_k$ 点，则此路线由 $s_k$ 点到 E 的部分，必是由 $s_k$ 点到 E 点的最短路线。

如此，我们便可以从最后一个状态，即 $s_4$ 开始，向最初状态不断递推求解，最终得到从 A 到 E 的最短路线。

第一步： $k = 4$ ，此时状态变量集合为 $S_4=\{D1,D2,D3\}$ ，那么每个取值对应的指标函数分别为 $f_4(D1)=3,f_4(D2)=4,f_4(D3)=3$ 。

第二步： $k = 3$ ，此时状态变量可取值为 $S_3=\{C1,C2,C3,C4\}$ ，如果取 $C 1$ ，则其到终点有两条路线，需加以比较，有 $f_3(C1)=min$

{\begin{matrix} d (C 1, D 1) + f_{4} (D 1) \\ d (C 1, D 2) + f_{4} (D 2) \end{matrix}}

=min

{\begin{matrix} 5 + 3 \\ 6 + 4 \end{matrix}}

=8

f_{3} (C 1) = min {d (C 1, D 1) + f_{4} (D 1) d (C 1, D 2) + f_{4} (D 2)} = min {5 + 3 6 + 4} = 8

说明从 C1 到 E 最短距离为 8 ，路径为

C1\to D1 \to E

，此阶段决策为

u^*_3(C_1)=D1

。

若取 $C 2$ ，只有一条路径，即 $C_2\to D1\to E$ ，则 $f_3(C2)=d(C2,D1)+f_4(D1)=8$ ，相应决策为 $u^*_3(C2)=D1$ 。同理，可求出 $f_3(C3)=d(C3,D3)+f_4(D3)=11,u^*_3(C3)=D3$ $f_3(C4)=d(C3,D3)+f_4(D3)=6,u^*_3(C4)=D3$ 第三步： $k = 2$ ，此时状态变量集合 $S_2=\{B1,B2\}$ ，有 $f_2(B1)=min$

{\begin{matrix} d (B 1, C 1) + f_{3} (C 1) \\ d (B 1, C 2) + f_{3} (C 2) \\ d (B 1, C 3) + f_{3} (C 3) \end{matrix}}

=min

{\begin{matrix} 1 + 8 \\ 6 + 8 \\ 3 + 11 \end{matrix}}

=9,u^*_2(B1)=C1

f_{2} (B 1) = min ⎩ ⎨ ⎧ d (B 1, C 1) + f_{3} (C 1) d (B 1, C 2) + f_{3} (C 2) d (B 1, C 3) + f_{3} (C 3) ⎭ ⎬ ⎫ = min ⎩ ⎨ ⎧ 1 + 8 6 + 8 3 + 11 ⎭ ⎬ ⎫ = 9, u_{2}^{*} (B 1) = C 1

{\begin{matrix} d (B 2, C 2) + f_{3} (C 2) \\ d (B 2, C 4) + f_{3} (C 4) \end{matrix}}

第四步：

k = 1

，此时只有一个状态 A ，有

{\begin{matrix} d (A, B 1) + f_{2} (B 1) \\ d (A, B 2) + f_{2} (B 2) \end{matrix}}

即 A 到 E 的最短距离为 13 ，按照计算顺序反推可得到最优决策序列

{u^*_k\}

，为

u^*_1(A)=B2,u^*_2(B_2)=C4,u^*_3(C4)=D3,u^*_4(D3)=E

，则最优路线为

A\to B2 \to C4 \to D3 \to E

从上述求解过程中可以看出，第

k

阶段和第

k + 1

段都利用了如下关系

{\begin{cases} f_{k} (s_{k}) = m i n {d_{k} (s_{k}, u_{k}) + f_{k + 1} (s_{k + 1})}, & k = 4, 3, 2, 1 （ 1.1 ） \\ f_{5} (s_{5}) = 0 （ 1.2 ） \end{cases}

注：状态转移方程为

s_{k+1}=u_k

。

这种递推关系称为动态规划的基本方程，式（1.2）为边界条件。

因此，可总结出动态规划方法的基本思想总结为：

将多阶段问题决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化为一族同类型的子问题，然后逐个求解。
求解时从最后一个阶段开始，逆方向进行，逐段递推寻优。在每个子问题求解时，都要使用它前面已经求出的子问题的最优结果，最后一个子问题的最优解就是整个问题的最优解。
动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的决策选取都是从全局考虑的，与该段的最优选择一般不同。

2.3 动态规划模型及其求解

给一个实际问题建立动态规划模型，必须做到以下 5 点。

将问题按时空特性恰当地划分为若干个阶段。
正确地规定状态变量 $s_k$ ，使它既能描述过程的演变，又具有无后效性。
正确地规定决策变量 $u_k$ 及每阶段的允许决策集合 $D_k(s_k)$ 。
正确地写出状态转移方程 $s_{k+1}=g_k(s_k,u_k)$ 。
正确地定义各阶段的直接指标函数 $d_k(s_k,u_k)$ 和后部子过程的最优指标函数 $f_k(s_k)$ ，并写出其基本方程： ${\begin{cases} f_{k} (s_{k}) = o p t_{u_{k} \in D_{k} (s_{k})} {d_{k} (s_{k}, u_{k}) \oplus f_{k + 1} (g_{k} (s_{k}, u_{k}))}, & k = 1, 2, \dots, n \\ f_{n + 1} (s_{n + 1}) = 0 或 1 ，边界条件 \end{cases}$ 其中 $\oplus$ 为 $+$ 或 $\times$ ，当 $\oplus$ 为 $+$ 时，边界条件为 0 ；当 $\oplus$ 为 $\times$ 时，边界条件为 1 。
$o pt$ 为 min 或 max 。

以上 5 点也称为动态规划模型的 5 要素。

动态规划模型的求解，是从 $k = n$ 开始，逐步向前推进，依次求解第 $k$ 阶段的后部最优指标 $f_k(s_k)$ 和最优子策略 $p_{k,n}(u_k^*,\cdots,u^*_n)$ 。当 $k = 1$ 时，就求出了原过程的最优指标函数和最优策略。这种方法的递进求解过程和实际决策过程是相反的，故称为动态规划的逆序解法。

有些问题，也可以按照与实际决策过程相同的方向逐阶段递进，寻求最优策略，这称为动态规划的顺序解法。

当动态规划模型中的状态变量与决策变量只能取离散值时，则可采取分段穷举法，如上篇文章中的最短路问题，一般用表格形式展示。对于状态变量和决策变量取连续值时，需具体情况具体分析，灵活选取求解方法，如经典解析方法、线性规划方法、非线性规划方法和其他数值计算方法等。

下面用一个例子来说明经典解析法。

经典解析法算例

用动态规划方法求解下面的规划问题： $max{z}=4x_1+9x_2+2x_3^2$

{\begin{cases} x_{1} + x_{2} + x_{3} = 10 \\ x_{i} \geq 0, i = 1, 2, 3 \end{cases}

s . t . {x_{1} + x_{2} + x_{3} = 10 x_{i} \geq 0, i = 1, 2, 3

解：可以将问题分为三个阶段，用每个阶段开始时的资源剩余量（约束条件即可看作资源）作为状态变量

s_k

，决策变量可取静态规划模型中的

x_k(k=1,2,3)

。状态转移方程为

s_{k+1}=s_k-x_k

，每个阶段的收益函数分别为

g_1(x_1)=4x_1,g_2(x_2)=9x_2,g_3(x_3)=2x_3^2

。最优指标函数

f_k(s_k)

表示第

k

阶段状态为

s_k

时，从第

k

阶段到第 3 阶段的后部最佳收益，该问题的基本方程为

{\begin{cases} max {g_{k} (x_{k}) + f_{k + 1} (s_{k} - x_{k})}, k = 1, 2, 3 \\ f_{4} (s_{4}) = 0 \end{cases}

当

k = 3

时，决策变量

x_3

为连续变量，取值范围为

0,s_3]

，则

f_3(s_3)=\max\{2x_3^2\}

。这是一个一元函数求极值问题，可知当

x^*_3=s_3

时，取得极大值

2s_3^2

，即有

f_3(s_3)=2s_3^2

。

当 $k = 2$ 时，此时 $x_2\in [0,s_2]$ ，则 $f_2(s_2)=\max\{9x_2+2s_3^2\}=\max\{9x_2+2(s_2-x_2)^2\}$ 。记 $h(x_2)=9x_2+2(s_2-x_2)^2$ ，令 $dh/dx_2=9-4(s_2-x_2)=0$ ，得 $x_2=s_2-9/4$ ；又由 $d^2h/dx_2^2=4>0$ ，故 $x_2=s_2-9/4$ 为极小值点，极大值在端点处取得。

$h(0)=2s_2^2,h(s_2)=9s_2$ ，当 $2s_2^2 \geq 9s_2$ ，即 $s_2\geq9/2$ 时， $x_2^*=0$ ；当 $s_2<9/2$ 时， $x^*_2=s_2$ 。

当 $k = 1$ 时， $s_1=10,x_1\in [0,10]$ 。若当 $s_2<9/2$ 时， $f_2(s_2)=9s_2$ ，有 $f_1(s_1)=\max\{4x_1+9(10-x_1)\}=\max\{90-5x_1\}$ ，则 $x^*_1=0$ ，此时 $s_2=10>9/2$ ，与条件矛盾，故舍去。

则 $f_2(s_2)=2s_2^2,f_1(s_1)=\max\{4x_1+2(10-x_1)^2\}$ 。记 $u(x_1)=4x_1+2(10-x_1)^2$ ，令 $du/dx_1=4-(10-x_1)=0$ ，得 $x_1=9$ ，此时 $d^2u/dx_1^2=1>0$ ，故其为极小值点。应在端点处取极大值，有 $u (0) = 200, u (10) = 40 < 200$ ，故 $x_1^*=0$ 。

由转移方程进行回推，有 $s_2=10,x_2^*=0;s_3=10,x_3^*=s_3=10$ ，故原问题最优解为 $0,0,10)^T$ ，最优解值为 200 。

写在最后

那么以上就是动态规划的基本内容了，往后，我们将针对具体类型的问题来深入进行理解，包括资源分配、生产与储存和设备更新问题。

相关阅读:
搭建XSS 测试平台
【机器学习算法】支持向量机（support Vector Machine，SVM）
Threejs_05 几何体顶点索引
通过监控Nginx日志来实时屏蔽高频恶意访问的IP
事件的事后调查
面试：HTTP 的长连接和短连接
ubuntu20.04.5 LTS搭建高可用k3s集群
面向对象程序设计(C++)之 String 类
正则表达式绕过
多表查询_子查询

原文地址：https://blog.csdn.net/Douglassssssss/article/details/132978061