f2(S2)?max?45x2?35(s2?x2)?45?0.35x2?0.65(s2?x2)?)?max??3.5x2?64.25s2??64.25s2(x2?0)*
k=1时：
f1(S1)?max?45x1?35(s1?x1)?64.25?0.35x1?0.65(s1?x1)?)?max??9.275x1?76.7625s1??76.7625s1(x1?0)*
生产计划如下：
s1?100x1?0s2?65x2?0**
s3?42.25x3?42.25*
即前两年把所有机器投入B产品，最后一年全部投入A产品 最大收入：
f1(S1)=7676.25元
2.某工厂考虑设备n年的更新计划,在每年初需作出设备是更新还是继续使用的决策,设备使用一年产生的利润,设备使用一年的维修费,以及设备的更新费用都与设备已使用的年数(设备年龄t)有关.
设r(t)为t年龄设备使用一年的利润 u(t)为t年龄设备使用一年的维修费用 c(t)为t年龄设备当年更新的费用
用动态规划方法求出n年内每年的最佳决策而使n年总利润最大.试引入0-1变量表示决策变量,并由此统一表示动态规划有关的概念和式子(不必求解):阶段,状态变量,决策变量,状态转移,阶段指标.（2003）
解：⒉设阶段变量k=1,2?n,状态变量tk表示k年初设备的年龄 决策变量xk?0表示更新，xk?1表示继续使用 状态转移方程tk?xktk?1
阶段指标Vk(tk,xk)?r(tk)?u(tk)?(1?xk)c(tk)
?fk(tk)?max{r(tk)?u(tk)?(1?xk)c(tk)?fk?1(xktk?1)?递推方程?xk?0,1
?f(t)?0,k?1,2,?,n?n?1n?1 五、（10%）某厂计划用220万资金，购买生产同一种产品的四种型号的设备A、B、C、D，这四种型号的设备设计生产能力和价格如下表所示。每种型号的设备应购买过少台，使总生产能力最大。
设备型号 设计生产能力K（吨/台） i价格Pi（万元/台） A 150 70 B 180 75 C 200 80 D 210 85 建立该问题的动态规划模型：列出阶段变量、状态变量、决策变量、状态转移方程、阶段指标、递推方程（不解）。(2002)
解：五、阶段变量k=1,2,3,4 分别表示A,B,C,D四种型号的设备 状态变量：Sk表示在第k阶段还有Sk万元资金可供使用 决策变量：Xk表示购买k型号设备的台数
状态转移方程：Sk+1=Sk-CkXk(Ck为x型号设备的价格) 阶段指标：Vk(Xk,Sk)=RkXk(Rk为设备的设计生产能力) 递推方程：?
?fk(sk)?max?vk(xk,sk)?fk?1(sk?1)??max?Rkxk?fk?1(sk?ckxk)?
?f5(s5)?0,k?4,3,2,15．动态规划问题的研究对象是 b ，其求得的一般方法是 c 。(2001) （a）工程路线问题 （b）多段决策问题 （c）迭代求解 （d）单纯形法 解： 三、（12%）某瓷厂接受订制一个仿宋高级瓷瓶的任务，瓷瓶需要用电炉烧制，据技术分析，每个瓶出炉后合格率为1/2，各瓶合格与否相互独立（即一炉如装有n个瓷瓶，那么出炉后都不合格的概率为(1/2)n）。 制造一个瓷瓶的原料费为100元，烧一炉的费用为300元，现因厂中条件限制，只能烧3炉，每炉最多装四个瓷瓶，若3炉瓷瓶无1个合格，则因不能履行合同而被罚款1600元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。（2000）
解：阶段变量：k=1,2,3, 分别表示三次烧制过程。
状态变量：每次烧制前是否有合格品作为状态变量Sk，
?0,第k次烧制前有合格品 Sk??1,第k次烧制前无合格品?决策变量：Xk表示第次烧制的瓶数（0≤Xk≤4）。
?xk?3,xk?0阶段指标：Vk(xk,sk)??（百元为单位）
0,x?0k?
设fk(Sk)表示第k次烧制前的状态为Sk时，以后均采取最优策略的最低期望成本，则有fk(0) =0（k=1,2,3），f4(1) =16， 递推方程：
?fk(1)?minvk(xk,sk)?(0.5)xkfk?1(1)?minxk?3y?(0.5)xkfk?1(1)0?xk?40?xk?4,xk?My,y?0,1?? ?fk(0)?0,k?3,2,1?f(1)?16,4??当k=3时，f3(1)? x3 s3 0 1
当k=2时，f2(1)? x2 s2 0 1
0?x2?4,x2?My,y?0,10?x3?4,x3?My,y?0,1????min?x3?3y?(0.5)x3?16
?x3?3y?(0.5)x3?16 0 1 2 3 4 0 - - - - 16 12 9 8 8 minf3(s3) 0 8 x3 0 3或4 ?x2?3y?(0.5)x2?8?
x2?3y?(0.5)x2?8 0 1 2 3 4 0 - - - - 8 8 7 7 7.5 minf2(s2) 0 7 x2 0 2或3 当k=1时，f1(1)? x2 s2 1 0?x1?4,x1?My,y?0,1?x?3y?(0.5)1x1?7?
x1?3y?(0.5)x1?7 0 1 2 3 4 f2(s2) x2 7 7.5 6.75 6.875 7.4375 6.75 2 最优策略为第一阶段烧制2个，若无合格的第二阶段烧制2或3个，若还无合格的第三阶段烧制3或4个，最低期望成本为675元。
4．动态规划中的Bellman最优性原理是 。（1999） 解：4、对一个最优策略，无论前面的状态和决策如何，由前面决策所构成的状态，其后部子策略 是最优的。
三（12%）某大学生正在计划如何安排在7天时间里复习完4门考试课程，他要求每天只能安排一门课程的复习，每门课程至少需要复习一天。据他估计每门课程的复习时间与所能带来的成绩提高关系如下表。请在下面两小问众人选作一问。
(1) 用动态规划方法求出使其总成绩提高最多的复习天数安排计划。
(2) 不具体计算，但要写出本问题的阶段变量、状态变量、各阶段状态变量集（即状态变量取值范围）、决策变量、阶段指标、指标函数、基本方程（递推分式）。（1999）
估计的提高分数 1 2 3 4 1 4 3 5 2 2 4 5 6 4 3 5 6 8 7 4 8 7 8 8
解：三、阶段变量k=1,2,3,4,表给出课分配复习时间的过程
状态变量Sk表示第k天分配时间剩余的可利用天数 决策变量xk表经第k天分配的时间1≤xk≤Sk-(4-k) 阶段指标Vk（Sk，xk）（如表）
指标函数：Vkn=基本方程：
?Vk?knk
??fk(sk)?max?vk(xk,sk)?fk?1(sk?1)? ???f5(s5)?0,k?4,3,2,1状态变量集：5-k≤Sk≤7-(k-1) 5-k≤Sk≤8-k
k 4 sk 1 2 3 4 2 3 4 5 xk 1 2 3 4 1 1 2 1 2 3 1 2 3 4 1 1 2 1 2 vk 2 4 7 8 5 5 6 5 6 8 5 6 8 8 3 3 5 3 5 Vk+fk+1 2+0 4+0 7+0 8+0 5+2 5+4 6+2 5+7 6+4 8+2 5+8 6+7 8+4 8+2 3+7 3+9 5+7 3+12 5+9 fk(sk) 2 4 7 8 7 9 12 13 Pkn 1 2 3 4 1-1 1-2 1-3 1-4 2-3 3 2 3 4 5 10 12 15 1-1-1 1-1-2 2-1-1 1-1-3
6 3 1 2 3 4 6 3 5 6 7 6+7 3+13 5+12 6+9 7+7 17 2-1-3
k 1 sk 7 xk 1 2 3 4 vk 4 4 5 8 Vk+fk+1 fk 4+17 4+15 5+12 8+10 21 Pk 1-2
二（15%）某工厂欲对一新购置设备作一5年工作计划，决定每年初是继续使用还是更新该设备，以使5年的总收益最大。该设备工作的年收入，年维修费，更新费均与设备的年龄有关。设s表示设备年龄，R(s) ，U(s)和C(s)分别表示年收入，年维修费和更新费。
1) 用最短路模型来求解此问题（列出模型，不解）
2) 用动态规划模型来求解此问题（列出模型，不解）(1998)
解：二
最短路模型：
用点Vi表示第i年购进一台新设备，虚设一个点V6，表示第五年年底。 边 (Vi,Vj)表示第i年购进的设备一直使用到第j年年初（即第j-1年年底）。 边 (Vi,Vj)上的数字表示第i年初购进设备，一直使用到第j年年初所需支付的购买，维修的全部费用。
这样此设备更新问题就变为：求从V1到V6的最短路问题。 如图：