动态规划建模题型

By Z.H. Fu
切问录 www.fuzihao.org

一维资源分配

总原料\(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)]\)