动态规划建模题型

By Z.H. Fu https://fuzihaofzh.github.io/blog/

动态规划是一种强大的数学工具，它可以解决一系列看似复杂的优化问题。本篇博客文章将向你展示如何利用动态规划来解决各种类型的问题，包括资源分配、生产计划、不确定性采购、背包问题、复合系统可靠性、设备更新、旅行商问题和整数规划等。我们将从每个问题的静态规划模型开始，然后详细解释如何转化为动态规划模型，并给出求解的过程。希望这篇文章能帮助你更好地理解和应用动态规划，以解决实际中的问题。

一维资源分配

总原料$a$，生产$n$种产品，若分配数量$x_i$ 用于生产第 $i$ 种产 品,其收益为 $g_i ( x_i )$，求$x_i$的分配方式使得总收入最大。

静态规划：

$$\begin{aligned}\max ~ &z= \ \ \sum_{i=1}^n g_i(x_i) \\ s.t. \ \ \ &\sum x_i=a;x_i\ge 0 \end{aligned}$$

动态规划：

$$\begin{aligned} &f_k(s_k)=\max_{0\le x_k\le s_k}\{g_k(x_k)+f_{k+1}(s_k-x_k)\},\ \ k=n-1,\cdots,1;\\ &f_n(s_n)=\max_{x_n=s_n}g_n(x_n) \end{aligned}$$

$s_k$ 表示分配用于生产第 $k$ 种产品至第 $n$ 种产品的原料数量，最后求$f_1(a)$

资源连续分配问题

资源总量$s_1$，可投入A、B两种生产，第一年以$u_1$生产A，剩下$s_1-u_1$生产B，收入为$g(u_1)+h(s_1 -u_1)$。年终剩余资源再投入第二年生产$s_2 =au_1 +b(s_1 -u_1)$。决策变量$u_i$，求$n$年最大化收入。

静态规划:

$$\begin{aligned}\max &z= \ \ \sum_{i=1}^n g(u_i)+h(s_i-u_i)\\ s.t. \ \ \ &s_{i+1}=au_i+b(s_i-u_i),\ \ \ i=1,\cdots,n-1;\\ &0\le u_i \le s_i,\ \ \ i=1,\cdots,n\end{aligned}$$

动态规划：

$$\begin{aligned} &f_k(s_k)=\max_{0\le u_k\le s_k}\{g(u_k)+h(s_k-u_k)+f_{k+1}(au_k+b(s_k-u_k))\},\ \ k=n-1,\cdots,1;\\ &f_n(s_n)=\max_{0\le u_n\le s_n}\{g(u_n)+h(s_n-u_n)\} \end{aligned}$$

例如机器两个档的例题，$k=5,4,3,2,1$逐步往前推。每一步都能化简成max一个线性函数，因此若系数为正，就取决策变量的上界，系数为负就取下界。

二维资源分配

两种原料，数量为$a$和$b$，需要分配用于生产$n$种产品。如果以第一种原料$x_i$, 第二种原料$y_i$，生产第 $i$ 种产品, 其收入为$g_i ( x_i , y_i )$。分配$n$种产品，最大化收入。
静态规划：

$$\begin{aligned}\max z= \ \ \sum_{i=1}^n g_i(x_i,y_i)\\ s.t. \ \ \ \sum x_i=a;\\ \sum y_i=b\\ x_i,y_i\ge 0\end{aligned}$$

动态规划：

$$\begin{aligned} &f_k(x,y)=\max_{0\le x_k\le x;0\le y_k\le y}\{g_k(x_k,y_k)+f_{k+1}(x-x_k,y-y_k)\},\ \ k=n-1,\cdots,1;\\ &f_n(x,y)=g_n(x,y)\end{aligned}$$

$x,y$表示两种原料总量

固定资金分配

$n$种产品，两种资源$x,y$，价格限制$ax+by\le z$。求如何购买$x,y$
静态规划：$\max z= \ \ \sum_{i=1}^n r_i(x_i,y_i);$ s.t. $\ \ \ \sum x_i=x; \sum y_i=y; ax+by\le z;$
把二维转成一维。定义资金利润函数$R_k(x)=\max_{y_k=0,1,\cdots,(z/b)}\{r_k(\lfloor(z-by_k)/a\rfloor,y_k)\}$
动态规划：$f_k(z)=\max_{z_k=0,1,\cdots,z}[R_k(z_k) + f_{k+1}(z-z_k)];$ $f_n(z)=R_n(z)$

生产计划问题

$n$个阶段，第$k$个阶段需求$d_k$，产量$x_k$，$v_k$为$k$阶段结束时的库存量，每个阶段起步成本$K$，最大产量$m$，产品成本$ax_k$，$n$阶段借宿后库存为0。需最小化生产成本。
$c_k(x_k)=0,\ \ \ if~~x_k=0;~=K+ax_k,\ \ \ if~~x_k=1,2, \cdots,m; ~=\infty,\ \ \ if~~x_k>m$

静态规划：

$$\begin{aligned} \min &g=\sum_{k=1}^n[c_k(x_k)+h_k(v_k)],\\ s.t. &v_0=0,v_n=0;\\ &v_k=\sum_{j=1}^k(x_j-d_j)\ge0,k=2,\cdots,n-1;\\ &0\le x_k\le m,k=1,\cdots,n\end{aligned}$$

$x_k$ is integer

动态规划：

$x_k$为决策变量，$v_{k-1}$为状态变量，是$k$阶段开始时的库存量。有：$v_k=v_{k-1}+x_k-d_k$，$f_k(v_k)=\min_{0\le x_k\le \sigma_k}[c_k(x_k)+h_k(v_k)+f_{k-1}(v_{k-1})]$其中$\sigma_k=\min(v_k+d_k,m)$(生产上限是m，且$v_{k-1}=v_k+d_k-x_k\ge 0$)。边界条件$f_0(v_0)=0$。目标求$f_n(0)$

不确定性采购问题

一种商品的采购可以在n周内选一个时候买，每个阶段有价格和相应的概率（每周都相同）。求价格期望最小的采购方案。 状态变量$y_k$，$x_k$决策变量，$y_{kE}$第k周等待，以后采购的期望价格。
动态规划：$f_k(y_k)=\min\{y_k,y_{kE}\}$，$f_n(y_k)=y_n$（最后一周，不管什么价都必须买），$y_{kE}=Ef_{k+1}(y_{k+1})$。先算$k=5$。

背包问题

背包容量$w$，每件物品重$w_i$，每件物品价值$c_ix_i$，状态变量$w$，决策变量$x_k$
$f_1=\max_{x_1=0,1,\cdots,\lfloor w/w_1\rfloor} c_1(x_1)$，$f_k(w)=\max_{x_k=0,1,\cdots,\lfloor w/w_k\rfloor}\{c_k(x_k)+f_{k-1}(w-w_kx_k)\},2\le k\le n$

复合系统可靠性

目标函数是乘积。一个系统由n个模块串联，每个模块可以有$u_i$个备份，正常工作概率$p_i(u_i)$，每个模块单个备份重$w_i$，价格$c_i$，总费用限制$c$，总重量限制$w$。求最大化正常工作概率。

静态规划：

$$\begin{aligned}\max ~&P=\prod_{i=1}^n p_i(u_i),\\ s.t. &\sum_{i=1}^nc_iu_i\le c;\\&\sum_{i=1}^nw_iu_i\le w;\\ &u_i\ge 0\end{aligned}$$

动态规划：

用$x_k,y_k$表示$k$到$n$个部件剩余的总费用和总重量，状态转移方程$x_{k+1}=x_k-u_kc_k,y_{k+1}=y_k-u_kw_k$。

动态规划基本方程：

$$\begin{aligned} f_k(x_k,y_k)=\max_{0\le u_k \le \min(\lfloor x_k/c_k \rfloor, \lfloor y_k / w_k \rfloor)}[p_k(u_k)f_{k+1}(x_k-c_ku_k,y_k-w_ku_k)],\\k=n,n-1,\cdots, 1, f_{n+1}(x_{n+1},y_{n+1})=1\end{aligned}$$

设备更新问题

$I_j(t),O_j(t),C_j(t)$表示在第j年，役龄为t年的一台机器运行所得收入，运行费用，更新费用（若更新的话），$\alpha$为一年后的收入折现到现在的因子，$T$第一年时，机器已使用年数，$n$计划总年数，$g_j(t)$在第j年使用役龄为$t$的机器的最优收入，$x_j(t)$第$j$年的决策(保留或更新)

$$\begin{aligned} g_j(t)=&\max[I_j(0)-O_J(0)-C_j(t)+\alpha g_{j+1}(1),I_j(t)-O_j(t)+\alpha g_{t+1}(t+1)],\\ &(j=1,2,\cdots,n, t=1,2,\cdots,j-1,j+T-1);\\ &g_{n+1}(t)=0 \end{aligned}$$

TSP问题

记$f_k(i,S)$表示第一个城市到第i个城市的距离，$S$是途经城市的集合。$S\in N_i=\{2,3,\cdots,i-1,i+1,\cdots,n\}$，$f_k(i,S)=\min_{f\in S}[f_{k-1}(j,S \backslash \{j\})+d_{ji}]$，$f_0(i,\Phi)=d_{1i}$

解整数规划

$$\begin{aligned}\max &z=c^Tx \\ s.t.~ &a^Tx \le 10;b^Tx \le 13; \\&x_i\ge 0 \end{aligned}$$

状态$x,y$表示两个约束对$x_i,\cdots x_n$进行规划，$f_k(x, y)=\max_{0\le x_k \le \min(\lfloor x/a_k \rfloor, \lfloor x/b_k \rfloor)} [c_k x_k + f_{k+1}(x-a_kx_k,y-b_kx_k)]$