18.3.6 泛函方程方法的应用例子

18.3.6.1 最优购买策略

1. 问题的提法

从第 1226 页 18.3.2.1 中的最优买入策略问题

OF: $f\left(u_1,\cdots ,u_n\right)=\sum _{j=1}^n{c}_j{u}_j\to min!$(18.142a)

$$\begin{array}{}\text{(18.142b)}& \begin{array}{ccc}\text{ CT: }& x_j=x_{j-1}+u_j-v_j,& j=1\left(1\right)n,\\ & x_0=x_a,0\le j\le K,& j=1\left(1\right)n,\\ & U_j\left(x_{j-1}\right)=\{u_j:max\left\{0,v_j-x_{j-1}\right\}& \\ & \le u_j\le K-x_{j-1}\},& j=1\left(1\right)n\end{array}\}\end{array}$$

导出泛函方程

$$\begin{array}{}\text{(18.143)}& {\varphi }_{n+1}\left(x_n\right)=0,\end{array}$$$$\begin{array}{}\text{(18.144)}& {\varphi }_j\left(x_{j-1}\right)=\underset{u_j\in U_j\left(x_{j-1}\right)}{max}\left(c_j{u}_j+{\varphi }_{j+1}\left(x_{j-1}+u_j-v_j\right)\right),j=1\left(1\right)n.\end{array}$$

2. 数值例子

$$n=6,K=10,x_a=2.\begin{array}{l}{c}_1=4,c_2=3,c_3=5,c_4=3,c_5=4,c_6=2,\\ v_1=6,v_2=7,v_3=4,v_4=2,v_5=4,v_6=3.\end{array}$$

后向计算 对于状态 $x_{j-1}=0,1,\cdots ,10$ 分别确定函数值 ${\varphi }_j\left(x_{j-1}\right)$ . 现在只需对于 $u_j$ 的整数值进行极小搜索.

$$j=6:{\varphi }_6\left(x_5\right)=\underset{u_6\in U_6\left(x_5\right)}{min}{c}_6{u}_6=c_{6}max\left\{0,v_6-x_5\right\}=2max\left\{0,3-x_5\right\}.$$

根据贝尔曼泛函方程方法的方式 2,只要将 ${\varphi }_6\left(x_5\right)$ 的值写在最后一行中. 例如,确定 ${\varphi }_4\left(0\right)$ 为

${\varphi }_4\left(0\right)=\underset{2\le u_4\le 10}{min}\left(3u_4+{\varphi }_5\left(u_4-2\right)\right)=min\{28,27,26,25,24,25,26,27,30\}=24.$

	$x_j=0$	1	2	3	4	5	6	7	8	9	10
$j=1$			75
2	59	56	53	50	47	44	41	38	35	32	29
3	44	39	34	29	24	21	18	15	12	9	6
4	24	21	18	15	12	9	6	4	2	0	0
5	22	18	14	10	6	4	2	0	0	0	0
6	6	4	2	0	0	0	0	0	0	0	0

前向计算

$${\varphi }_1\left(2\right)=75=\underset{4\le u_1\le 8}{min}\left(4u_1+{\varphi }_2\left(u_1-4\right)\right).$$

于是得到 $u_1^{\ast }=4$ 作为极小点,因此 $x_1^{\ast }=x_0^{\ast }+u_1^{\ast }-v_1=0$ . 对于 ${\varphi }_2\left(0\right)$ 以及后面各级重复此方法, 得到最优策略:

$$\left(u_1^{\ast },u_2^{\ast },u_3^{\ast },u_4^{\ast },u_5^{\ast },u_6^{\ast }\right)=\left(4,10,1,6,0,3\right).$$

18.3.6.2 背包问题

1. 问题的提法

考虑第 1226 页 18.3.2.2 中给出的问题:

$$\begin{array}{}\text{(18.145a)}& \text{:}f\left(u_1,\cdots ,u_n\right)=\sum _{j=1}^n{c}_j{u}_j\to max\text{!}\end{array}$$

CT:

$$\begin{array}{}\text{(18.145b)}& \begin{array}{ll}{x}_j=x_{j-1}-w_j{u}_j,& j=1\left(1\right)n,\\ x_0=W,0\le x_j\le W,& j=1\left(1\right)n,\\ u_j\in \{0,1\},x_{j-1}\ge w_j,& \\ u_j=0,x_{j-1}<w_j,& j=1\left(1\right)n.\end{array}\}\end{array}$$

由于这是一个极大问题, 故贝尔曼泛函方程现在是

$${\varphi }_{n+1}\left(x_n\right)=0,$$$${\varphi }_j\left(x_{j-1}\right)=\underset{u_j\in U_j\left(x_{j-1}\right)}{max}\left(c_j{u}_j+{\varphi }_{j+1}\left(x_{j-1}-w_j{u}_j\right)\right),j=1\left(1\right)n.$$

决策只可能是 0 和 1 , 故应用泛函方程方法的方式 1 是比较切合实际的. 对于$j=n,n-1,\cdots ,1:$

$${\varphi }_j\left(x_{j-1}\right)=\{\begin{array}{ll}{c}_j+{\varphi }_{j+1}\left(x_{j-1}-w_j\right),& \text{ 如果 }{x}_{j-1}\ge w_j,\\ c_j+{\varphi }_{j+1}\left(x_{j-1}-w_j\right)>{\varphi }_{j+1}\left(x_{j-1}\right),& \\ {\varphi }_{j+1}\left(x_{j-1}\right),& \text{ 否则,}\end{array}$$

$u_j\left(x_{j-1}\right)=\{\begin{array}{ll}1,& \text{ 如果 }{x}_{j-1}\ge w_j,c_j+{\varphi }_{j+1}\left(x_{j-1}-w_j\right)>{\varphi }_{j+1}\left(x_{j-1}\right),\\ 0,& \text{ 否则. }\end{array}$

2. 数值例子

$$W=10,n=6.\begin{array}{l}{c}_1=1,c_2=2,c_3=3,c_4=1,c_5=5,c_6=4,\\ w_1=2,w_2=4,w_3=6,w_4=3,w_5=7,w_6=6.\end{array}$$

由于权重 $w_j$ 是整数,故 $x_j$ 的可能值是 $x_j\in \{0,1,\cdots ,10\},j=1\left(1\right)n$ ,而 $x_0=$ 10. 下表中包含了每一级和每个状态 $x_{j-1}$ 下的函数值 ${\varphi }_j\left(x_{j-1}\right)$ 和实际的决策 $u_j\left(x_{j-1}\right)$ . 例如, ${\varphi }_6\left(x_5\right),{\varphi }_3\left(2\right),{\varphi }_3\left(6\right)$ 和 ${\varphi }_3\left(8\right)$ 的计算如下:

$${\varphi }_6\left(x_5\right)=\{\begin{array}{ll}0,& \text{ 如果 }{x}_5<w_6=4,\\ c_6=6,& \text{ 否则,}\end{array}{u}_6\left(x_5\right)=\{\begin{array}{ll}0,& \text{ 如果 }{x}_5<4,\\ 0,& \text{ 否则. }\end{array}$$

${\varphi }_3\left(2\right):x_2=2<w_3=3:{\varphi }_3\left(2\right)={\varphi }_4\left(2\right)=3,u_3\left(2\right)=0.$

${\varphi }_3\left(6\right):x_2>w_3,c_3+{\varphi }_3\left(x_2-w_3\right)=6+3<{\varphi }_4\left(x_2\right)=10:{\varphi }_3\left(6\right)=10,u_3\left(6\right)=0.$

${\varphi }_3\left(8\right):x_2>w_3,c_3+{\varphi }_3\left(x_2-w_3\right)=6+9>{\varphi }_4\left(x_2\right)=10:{\varphi }_3\left(8\right)=15,u_3\left(8\right)=1$ .

最优策略是

$$\left(u_1^{\ast },u_2^{\ast },u_3^{\ast },u_4^{\ast },u_5^{\ast },u_6^{\ast }\right)=\left(0,1,1,1,0,1\right),{\varphi }_1\left(10\right)=19.$$

	$x_j=0$	1	2	3	4	5	6	7	8	9	10
$j=1$											19;0
2	0;0	3;0	4;1	7;1	9;0	10;1	13;1	13;1	15;0	16;0	19;1
3	0;0	3;0	3;0	6;1	9;1	9;0	10;0	12;1	15;1	16;1	16;0
4	0;0	3;1	3;1	3;1	6;0	9;1	10;1	10;1	10;1	13;0	16;1
5	0;0	0;0	0;0	0;0	6;0	7;1	7;1	7;1	7;1	13;1	13;1
6	0;0	0;0	0;0	0;0	6;1	6;1	6;1	6;1	6;1	6;1	6;1

(冯德兴 译)