§3建立动态规划数学模型的步骤 “最优化原理”是动态规划的核心，所有动态规划问题 的递推关系都是根据这个原理建立起来的，并且根据递推关 系依次计算，最终可求得动态规划问题的解。 般来说，利用动态规划求解实际问题需先建立问题 的动态模型，具体步骤如下： 1.将问题按时间或空间次序划分成若干阶段。有些问 题不具有时空次序，也可以人为地引进时空次序，划分阶 段。 2.正确选择状态变量x。这一步是形成动态模型的关 键，状态变量是动态规划模型中最重要的参数。一般来说， 状态变量应具有以下三个特性： (1)要能够用来描述决策过程的演变特征。 (2)要满足无后效性。即如果某阶段状态已给定后，则 以后过程的进展不受以前各状态的影响，也就是说，过去 的历史只通过当前的状态去影响未来的发展。 (3)递推性。即由k阶段的状态变量x及决策变量u可以 计算出k+1阶段的状态变量1
§3 建立动态规划数学模型的步骤 “最优化原理”是动态规划的核心,所有动态规划问题 的递推关系都是根据这个原理建立起来的,并且根据递推关 系依次计算,最终可求得动态规划问题的解。 一般来说，利用动态规划求解实际问题需先建立问题 的动态模型，具体步骤如下： ⒈将问题按时间或空间次序划分成若干阶段。有些问 题不具有时空次序，也可以人为地引进时空次序，划分阶 段。 ⒉正确选择状态变量xk。这一步是形成动态模型的关 键，状态变量是动态规划模型中最重要的参数。一般来说， 状态变量应具有以下三个特性： ⑴要能够用来描述决策过程的演变特征。 ⑵要满足无后效性。即如果某阶段状态已给定后，则 以后过程的进展不受以前各状态的影响，也就是说，过去 的历史只通过当前的状态去影响未来的发展。 ⑶递推性。即由k阶段的状态变量xk及决策变量uk可以 计算出k+1阶段的状态变量xk+1
3.确定决策变量u及允许决策变量集合Dk()。 4.根据状态变量之间的递推关系，写出状态转移方程： Xk+I=T(xk uk(Xx)) 5.建立指标函数。一般用rk(X)描写阶段效应，五(xk) 表示k一n阶段的最优子策略函数。 6建立动态规划基本方程： f(Xk)=opt{K&,u4(X)》*人1(X+1）) u∈Dk(u) f+1（Xt1)=C k=n,n-1,..,1 以上是建立动态规划模型的过程，这个过程是正确求 解动态规划的基础。 在动态规划基本方程中，「k&,),+1=T(,)都是 已知函数，最优子策略人(xk)与+1(x1)之间是递推关 系，要求出(xk)及u(X),需要先求出五+1(xk+1)，这就 决定了应用动态规划基本方程求最优策略总是逆着阶段的 顺序进行的。由后向前逐步计算，最终可以算出全过程的 最优策略函数值及最优策略
⒊确定决策变量uk及允许决策变量集合Dk (uk )。 ⒋根据状态变量之间的递推关系，写出状态转移方程： xk+1=T(xk , uk (xk )) ⒌建立指标函数。一般用rk (xk , uk )描写阶段效应，fk（xk） 表示k—n阶段的最优子策略函数。 ⒍建立动态规划基本方程： fk（xk）= opt｛ rk (xk , uk (xk ))﹡fk+1（xk+1）｝ uk∈ Dk (uk ) fn+1（xn+1）=C k=n,n-1,…,1 以上是建立动态规划模型的过程，这个过程是正确求 解动态规划的基础。 在动态规划基本方程中， rk (xk , uk )， xk+1=T(xk , uk )都是 已知函数，最优子策略fk（xk）与fk+1（xk+1）之间是递推关 系，要求出fk（xk）及uk (xk )，需要先求出fk+1（xk+1），这就 决定了应用动态规划基本方程求最优策略总是逆着阶段的 顺序进行的。由后向前逐步计算，最终可以算出全过程的 最优策略函数值及最优策略
另一方面，由于k+1阶段的状态X+1=T(X,)是由前面 的状态x和决策u所形成的，在计算人+1(X+1)时还不能具 体确定X+1的值，所以，这就要求必须就k+1阶段的各个可 能状态计算人+1(x+1)，因此动态规划方法不但能求出整 个问题的最优策略和最优目标值，而且还能求出决策过程 中所有可能状态的最优策略及最优目标值。 下面就按上述步骤求解例2
另一方面，由于k+1阶段的状态xk+1=T(xk , uk )是由前面 的状态xk和决策uk所形成的，在计算fk+1（xk+1）时还不能具 体确定xk+1的值，所以，这就要求必须就k+1阶段的各个可 能状态计算fk+1（xk+1），因此动态规划方法不但能求出整 个问题的最优策略和最优目标值，而且还能求出决策过程 中所有可能状态的最优策略及最优目标值。 下面就按上述步骤求解例2
例2（带回收的资源分配问题）某厂新购某种机床125 台。据估计，这种设备5年后将被其它设备所代替。此机床 如在高负荷状态下工作，年损坏率为1/2，年利润为10万元： 如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。 问应如何安排这些机床的生产负荷，才能使5年内获得的利 润最大？ 解：以年为阶段，k=1,2,3,4,5 取k年初完好的机床数为状态变量x: 以k年初投入高负荷运行的机床数为决策变量u,则低 负荷运行机床数是x,于是状态转移方程为： Xk+1=1/2u+4/5(Xuk)-0.8x-0.3u4 以利润为目标函数，则k年利润为： 10u4+6(xku)=4uk+6x 记(xk)为k年至5年末最大总利润， 则动态规划基 本方程为： f(xk)=max{4u+6x+f+1(0.8x-0.3u))} 0≤uk≤Xk 6(x6)=0 k=5,4,3,2,1
例2（带回收的资源分配问题）某厂新购某种机床125 台。据估计，这种设备5年后将被其它设备所代替。此机床 如在高负荷状态下工作，年损坏率为1/2，年利润为10万元； 如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。 问应如何安排这些机床的生产负荷，才能使5年内获得的利 润最大？ 解：以年为阶段，k=1，2，3，4，5 取k年初完好的机床数为状态变量xk 以k年初投入高负荷运行的机床数为决策变量uk，则低 负荷运行机床数是xk-uk，于是状态转移方程为： xk+1=1/2uk+4/5（xk-uk）=0.8xk-0.3uk 以利润为目标函数，则k年利润为： 10uk+6（xk-uk）=4uk+6xk 记fk（xk）为k年至5年末最大总利润，则动态规划基 本方程为： fk（xk）= max｛ 4uk+6xk+fk+1（0.8xk-0.3uk）｝ 0≤uk≤xk f6（x6）=0 k=5,4,3,2,1
以上是建立动态模型的过程，下面具体求解。 注意动态规划基本方程为： 人(xk)=max( 4u+6x+f1(0.8x-03u)} 0≤uk≤Xk 所以，当k=5时，有 5(x5) =max{4u5+6x+6(x%)}=10x Us-X5 0≤u5X5 当k=4时 f(xa) =max{4u+6x4tf6(0.8x-0.3u)} 0≤u4X4 max {4u+6x+10(0.8x-0.3u4)} 0≤u4X max u4+14x4}=15x U4-X 0≤uX4 当k=3时 5(x3) max 4u+6xtf4(0.8x30.3u)) 0≤uX3 max 4u3+6x+15(0.8x3-0.3u3)} 0≤u3≤Xy 三 max{-0.5u+18x3}=18x 43=0 0≤u3X3
以上是建立动态模型的过程，下面具体求解。 注意动态规划基本方程为： fk（xk）= max｛ 4uk+6xk+fk+1（0.8xk-0.3uk）｝ 0≤uk≤xk 所以，当k=5时，有 f5（x5）= max｛ 4u5+6x5+f6（x6）｝=10x5 u5 =x5 0≤u5≤x5 当k=4时 f4（x4）= max｛ 4u4+6x4+f5（0.8x4-0.3u4）｝ 0≤u4≤x4 = max｛ 4u4+6x4+10（0.8x4-0.3u4）｝ 0≤u4≤x4 = max｛ u4+14x4｝=15x4 u4 =x4 0≤u4≤x4 当k=3时 f3（x3）= max｛ 4u3+6x3+f4（0.8x3-0.3u3）｝ 0≤u3≤x3 = max｛ 4u3+6x3+15（0.8x3-0.3u3）｝ 0≤u3≤x3 = max｛ -0.5u3+18x3｝=18x3 u3=0 0≤u3≤x3
动态规划基本方程为： 天(xk)=max{4u+6x+f+1(0.8x0.3u)} 0≤uk≤Xk 当k=2时 5(x2)=max{4u,+6x2+5(0.8x20.3u2)} 0≤u2≤X2 =max{4u2+6x2+18(0.8x2-0.3u2)} 0≤u2≤X2 =max{-1.4u2+20.4x2}=20.4x2 u2=0 0≤u2≤X2 当k=1时 f(x1)=max{4u1+6x+5(0.8x0.3u1)} 0≤u1X1 =max{4u+6x1+20.4(0.8x1-0.3u1)} 0<u1X1 =max{-2.12u1+22.32x1}=22.32x u1=0 0<u≤X1 =22.32×125=2790(万元) 至此已算得最大总利润2790万元，再按与计算过程相反的 顺序推回去，可得最优计划如下表所示：
动态规划基本方程为： fk（xk）= max｛ 4uk+6xk+fk+1（0.8xk-0.3uk）｝ 0≤uk≤xk 当k=2时 f2（x2）= max｛ 4u2+6x2+f3（0.8x2-0.3u2）｝ 0≤u2≤x2 = max｛ 4u2+6x2+18（0.8x2-0.3u2）｝ 0≤u2≤x2 = max｛-1.4u2+20.4x2｝=20.4x2 u2=0 0≤u2≤x2 当k=1时 f1（x1）= max｛ 4u1+6x1+f2（0.8x1-0.3u1）｝ 0≤u1≤x1 = max｛ 4u1+6x1+20.4（0.8x1-0.3u1）｝ 0≤u1≤x1 = max｛ -2.12u1+22.32x1｝=22.32x1 u1=0 0≤u1≤x1 =22.32×125=2790（万元） 至此已算得最大总利润2790万元，再按与计算过程相反的 顺序推回去，可得最优计划如下表所示：
年份 完好机床数 高负荷机床数 低负荷机床数 k X+10.8Xk0.3u Xk Uk 第一年 125 0 125 第二年 100 0 100 第三年 80 0 80 第四年 64 64 0 第五年 32 32 0
年份 k 完好机床数 xk+1=0.8xk-0.3uk 高负荷机床数 uk 低负荷机床数 xk-uk 第一年 125 0 125 第二年 100 0 100 第三年 80 0 80 第四年 64 64 0 第五年 32 32 0