动态规划是一种将复杂问题转化为比较简单问题的最优 化方法，一些线性规划、非线性规划及整数规划都可以用 动态规划方法来求解。因此，动态规划在存贮控制、网络 流、作业安排、生产控制等方面都有所讨论，在工程技术、 工业生产、经济、军事以及自动控制等领域都有广泛的应 用，并获得了显著的效果。 #”但是动态规划不存在一种标准的数学形式，对于动态规 划方法的使用，有时可以说是一种艺术，它需要对动态规 划问题的一般结构有较深入的了解，：在一个具体问题中， 如何定义状态、“决策、阶段效应等，以及如何得到问题的 基本方程表达式，在很大程度上还有赖于分析者的经验、 洞察和判断能力。这就需要练习和实践，以及总结已有的 研究成果。本章通过一些典型的应用问题，介绍动态规划 的建模和基本解题方法
动态规划是一种将复杂问题转化为比较简单问题的最优 化方法，一些线性规划、非线性规划及整数规划都可以用 动态规划方法来求解。因此，动态规划在存贮控制、网络 流、作业安排、生产控制等方面都有所讨论，在工程技术、 工业生产、经济、军事以及自动控制等领域都有广泛的应 用，并获得了显著的效果。 但是动态规划不存在一种标准的数学形式，对于动态规 划方法的使用，有时可以说是一种艺术，它需要对动态规 划问题的一般结构有较深入的了解，在一个具体问题中， 如何定义状态、决策、阶段效应等，以及如何得到问题的 基本方程表达式，在很大程度上还有赖于分析者的经验、 洞察和判断能力。这就需要练习和实践，以及总结已有的 研究成果。本章通过一些典型的应用问题，介绍动态规划 的建模和基本解题方法
§1资源分配问题 给定一定数量的某种资源，例如人力、资金、设备、材料 将其投入多种活动，就会产生如何分配资源给各项活动， 使投放资源的总效果最优的问题，这就是资源分配问题。资源 分配是相当广泛的经济问题，我们前面介绍的线性规划、整数 规划、指派问题等都可以看作是求解资源分配的方法。这节介 绍的资源分配问题是用前述方法难以解决，但由于其自身特点 决定，可以用动态规划求解的实际问题。 现在设有某种资源（例如电、煤等）可用于项活动，假设资 源的数量为a,已知用于第项活动的资源数为×时，可以得到的收 益为g(×),=1,n。试确定资源的分配方案使总收益最大。 该问题的数学模型可以表示为： maxZ=g1.(X1)+g2（X2）+-.+gn(×n) s.t,X1tX2t+n）a X1,X2,…,X20 当g（×)是线性函数时，该问题是线性规划问题；当g(×)是非 线性函数时，是非线性规划问题，如果采用非线性规划方法去求解 是比较麻烦的。然而由于这类问题的特点，可以将它看成一个多阶 段决策问题，并利用动态规划方法求解
§1 资源分配问题 给定一定数量的某种资源，例如人力、资金、设备、材料 等，将其投入多种活动，就会产生如何分配资源给各项活动， 使投放资源的总效果最优的问题，这就是资源分配问题。资源 分配是相当广泛的经济问题，我们前面介绍的线性规划、整数 规划、指派问题等都可以看作是求解资源分配的方法。这节介 绍的资源分配问题是用前述方法难以解决，但由于其自身特点 决定，可以用动态规划求解的实际问题。 现在设有某种资源（例如电、煤等）可用于n项活动，假设资 源的数量为a，已知用于第i项活动的资源数为xi时，可以得到的收 益为gi（xi），i=1, …n。试确定资源的分配方案使总收益最大。 该问题的数学模型可以表示为： maxZ=g1（x1）+g2（x2）+ …… +gn（xn） s.t x1+x2+ …… + xn）≤a x1 ,x2 , ……,xn ≥0 当gi（xi）是线性函数时，该问题是线性规划问题；当gi（xi）是非 线性函数时，是非线性规划问题 ，如果采用非线性规划方法去求解 是比较麻烦的。然而由于这类问题的特点，可以将它看成一个多阶 段决策问题，并利用动态规划方法求解
在应用动态规划方法去处理这一类资源分配问题时，通常将 资源分给每项活动的过程看作一个阶段，每个阶段都要确定对一 种活动的资源投放量。 这时，状态变量x可选择k阶段初所拥有的资源量，即x是要 在第k项到第项活动间分配的资源量。 决策变量u,常常选对活动k的资源投放量，决策变量的允许 集合是：0≤u≤X 在选取上述状态变量和决策变量的情况下，状态转移方程是： Xk+1=Xk Uk 取投放资源时的效益为指标函数，则gk(uk)为阶段效益指标。 设东(xk)为k阶段到n阶段按最优分配方案获得的最大收益， 则动态规划基本方程是： 2u)+6】 Uf1(x1)=0.k=n,n-1,,1 按基本方程，逆序计算，就可求得这类资源分配问题的最优解
在应用动态规划方法去处理这一类资源分配问题时，通常将 资源分给每项活动的过程看作一个阶段，每个阶段都要确定对一 种活动的资源投放量。 这时，状态变量xk可选择k阶段初所拥有的资源量，即xk是要 在第k项到第n项活动间分配的资源量。 决策变量uk常常选对活动k的资源投放量，决策变量的允许 集合是： 0≤uk≤xk 在选取上述状态变量和决策变量的情况下，状态转移方程是： xk+1= xk-uk 取投放资源时的效益为指标函数，则gk（uk）为阶段效益指标。 设fk（xk）为k阶段到n阶段按最优分配方案获得的最大收益， 则动态规划基本方程是： fk（xk）= max｛gk（uk）+fk+1（xk+1）｝ 0≤uk≤xk fn+1（xn+1）=0 k=n,n-1, …,1 按基本方程，逆序计算，就可求得这类资源分配问题的最优解
例1某公司拟将5百万元资金投放下属的A、B、.C三个企业，各 企业获得资金后的收益如表所示，试确定总收益最大的投资分配方 案 投放资金（百万元） 012345 收 A 02233.3 益 B 001247 (百万元) "C.. 012:345 解：以分别向A、B、C三个企业分配资金为阶段，k=1,2,3。取 k阶段初拥有的资金数为状态变量x,决策变量u为分配给企业k的 资金数，则状态转移方程是：·+X 令人(Xk)为k企业至第三个企业按最优分配方案获得的最大收益， 则动态规划基本方程是： 数不 k-3,2,1 下面按基本方程具体求解：
例1 某公司拟将5百万元资金投放下属的A、B、C三个企业，各 企业获得资金后的收益如表所示，试确定总收益最大的投资分配方 案。 投放资金（百万元） 0 1 2 3 4 5 收 益 （百万元） A 0 2 2 3 3 3 B 0 0 1 2 4 7 C 0 1 2 3 4 5 解：以分别向A、B、C三个企业分配资金为阶段，k=1,2,3。取 k阶段初拥有的资金数为状态变量xk，决策变量uk为分配给企业k的 资金数，则状态转移方程是： xk+1=xk-uk 令fk（xk）为k企业至第三个企业按最优分配方案获得的最大收益， 则动态规划基本方程是： fk（xk）= max｛gk（uk）+fk+1（xk+1）｝ 0≤uk≤xk f4（x4）=0 k=3,2,1 下面按基本方程具体求解：
K=3X3=0,1,2,.3,4,5 5(0)=0,山(0)=0；5(1)=1，u3(1)=1; 5(2)2,u3(2)=2:5(3)=3,u3(3)=3; 5(4).=4,u山(4)=4：5(5)=5，u (5)=5 K=2X2=0,1,2,3,4,5 6(0)=0, 2.(0)=0 82 (0) 利 (1) 0+1 (1): =max 2 (1) (0) =max0+0=1,u2(1)=0; $ (2) 0+2 (2).=max =ma灯0+1 =2, 1+0 u2(2)-0; 0+3 (3),=max max J0+2 =3, 1+1 2+0 u2(3)=0;
K=3 x3 =0，1，2，3，4，5 f3（0）=0， u3（0）=0； f3（1）=1, u3（1）=1； f3（2）=2， u3（2）=2； f3（3）=3，u3（3）=3； f3（4）=4， u3（4）=4； f3（5）=5，u3（5）=5 K=2 x2 =0，1，2，3，4，5 f2（0）=0, u2（0）=0； g2（0）+f3（1） 0+1 f2（1）=max g2（1）+f3（0）=max 0+0 =1, u2（1）=0； g2（0）+f3（2） 0+2 f2（2）=max g2（1）+f3（1）=max 0+1 =2, g2（2）+f3（0） 1+0 u2（2）=0； g2（0）+f3（3） 0+3 f2（3）=max g2（1）+f3（2）=max 0+2 =3, g2（2）+f3（1） 1+1 g2（3）+f3（0） 2+0 u2（3）=0；
8 (0) +5(4) 0+4 g2(1) + (3) 0+3 (4)=max g2(2)+5(2)-max 1+2=4, 82 (3)+5(1) 2+1 (4)+5 (0) 4+0 u2:(4)=0或4 82 0)+5(5) 0+5 8 (1)+ .(4) 0+4 (5)=max g2(2)+5(3) =max. 1+3=7, (3)+5 (2》 2+2 (4) (1) 4+1 B2 (5) +f5 (0) 7+0 u2(5)=5; K=1.X1=5 81 (0) +5(5) 0+7 (1)+五 (4) 2+4 (5)=max 81(2)+月 (3) =max 2+3=7, g1(3)+五 (2) 3+2 g1(4)+5(1) 3+1 g1.(5)+6(0) 3+0 （5)=0. 至此， 算得本问题最大总收益7百方元，由u1(5).=0顺次可求得最优投资方案为： u1(5)=0:u2(5)=5;u3(0)=0 即将5百万元全部投放到企业B,届时可得收益7百万元
g2（0）+f3（4） 0+4 g2（1）+f3（3） 0+3 f2（4）=max g2（2）+f3（2）=max 1+2 =4, g2（3）+f3（1） 2+1 g2（4）+f3（0） 4+0 u2（4）=0或4； g2（0）+f3（5） 0+5 g2（1）+f3（4） 0+4 f2（5）=max g2（2）+f3（3）=max 1+3 =7, g2（3）+f3（2） 2+2 g2（4）+f3（1） 4+1 g2（5）+f3（0） 7+0 u2（5）=5； K=1 x1 =5 g1（0）+f2（5） 0+7 g1（1）+ f2（4） 2+4 f1（5）=max g1（2）+ f2（3）=max 2+3 =7, g1（3）+ f2（2） 3+2 g1（4）+ f2（1） 3+1 g1（5）+f2（0） 3+0 u1（5）=0. 至此，算得本问题最大总收益7百万元，由u1（5）=0顺次可求得最优投资方案为： u1（5）=0； u2（5）=5； u3（0）=0 即将5百万元全部投放到企业B，届时可得收益7百万元