动态规划应用举例 - 图文(3)

*?n?1?1，故(9-3)式变为

****

fn?1(sn?1)?(c?ca)sn?1?c(1?a)sn?1

又由于sn?1?aun?2?b(sn?2?un?2)，将它代入上式得

fn?1(sn?1)?c(1?a)?(a?b)un?2?bsn?2?

对n-2段，由(9-2)式有

fn?2(sn?2)?maxun?20?un?2?sn?2?cun?2?d(sn?2-un?2)?fn?1(sn?1)?

?max?cun?2?d(sn?2?un?2)?c(1?a)?(a?b)un?2?bsn?2???max??(c?d)?c(1?a)(b?a)?un?2??d?c(1?a)b?sn?2?un?2?max??(c?d)?c(1?a)(b?a)??n?2?d?cb(1?a)?sn?2?n?2由此可知，只要满足极值条件式c?d?c(1?a)(b?a) 就应选?n?2?1，否则为0，即应继续在高负荷下生产。

依次类推，如果转入高负荷下生产的是第t年，则由

*ft(st)?max?cut?d(st?ut)?ft?1(st?1)?

ut可以推出，应满足极值关系的条件必然是：

2n?(t?1)?)(b?a)?c?d?c(1?a?a???a?2n?t??c?d?c(1?a?a???a)(b?a)(9?5)

相应的有最优策略

?n*??n*?1????t*?1???????*1*2*t?1?0

它就是例2在始端固定终端自由情况下最优策略的一般结果。

从这个例子看到，应用动态规划，可以在不求出数值解的情况下，确定最优策略的结构。 可见，只要知道了a，b，c，d四个值，就总可找到一个t值，满足(9-5)式，且1?t?n?1

例如题中给定的a?0.7,b?0.8,c?8,d?5，代入(9-5)式，应有

c?dc(b?a)?1?d/cb?a?1?5/80.9?0.7?31.6?1.875?(1?a)?1?0.7

可见n?t?1?5?t?1?1，所以t=3，即从第三年开始将全部机器投入高负荷生产，五年内总产量最高。

上面的讨论表明：当x在［0，s1］上离散地变化时，利用递推关系式逐步计算或表格法而求出数值解。当x在［0，s1］上连续地变化时，若g(x)和h(x)是线性函数或凸函数时，根据递推关系式运用解析法不难求出fk(x)和最优解；若g(x)和h(x)不是线性函数或凸函数时，一般来说，解析法不能奏效，那

只好利用递推关系式(9-1)求其数值解。首先要把问题离散化，即把区间［0，s1］进行分割，令x=0，Δ，2Δ，…，mΔ=s1。其Δ的大小，应根据计算精度和计算机容量等来确定。然后规定所有的fk(x)和决策变量只在这些分割点上取值。这样，递推关系式(9-1)便可写为

?fn(i?)?max?g(j?)?h(i??j?)?0?j?i???g(j?)?h(i??j?)?fk?1?a(j?)?b(i??j?)?? ?fk(i?)?max0?j?i? k?n?1,?,2,1??对i?0,1,?,m依次计算，可逐步求出fn(i?),fn?1(i?),?,f1(i?)及相应的最优决策，最后求得

f1(m?)?f1(s1)就是所求的最大总收入。这种离散化算法可以编成程序在计算机中计算。

1。2 二维资源分配问题

设有两种原料，数量各为a和b单位，需要分配用于生产n种产品。如果第一种原料以数量xi为单位，第二种原料以数量yi为单位，用于生产第i种产品，其收入为gi(xi,yi)。问应如何分配这两种原料于n种产品的生产使总收入最大?

此问题可写成静态规划问题：

?max?g1(x1,y1)?g2(x2,y2)???gn(xn,yn)???x1?x2???xn?a ?y?y???y?b2n?1?x?0,y?0, (i?1,2,?,n)且为整数i?i用动态规划方法来解，状态变量和决策变量要取二维的。

设状态变量(x，y):

x——分配用于生产第k种产品至第n种产品的第一种原料的单位数量。 y——分配用于生产第k种产品至第n种产品的第二种原料的单位数量。

决策变量(xk,yk)：

xk——分配给第k种产品用的第一种原料的单位数量。 yk——分配给第k种产品用的第二种原料的单位数量。 ??x?x;状态转换关系：xk??和?y?y?yk，式中xy分别表示用来生产第k+1种产品至第n种产品

的第一种和第二种原料的单位数量。

允许决策集合： Dk(x,y)??uk0?xk?x;0?yk?y?

fk(x,y)表示以第一种原料数量为x单位，第二种原料数量为y单位，分配用于生产第k种产品至第