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

?fn(sn)?max?g(un)?h(sn?un)?0?un?sn???g(uk)?h(sk?uk)?fk?1?auk?b(sk?uk)?? ?fk(sk)?0max?uk?sk? k?n?1,?,2,1??最后求出f1(s1)即为所求问题的最大总收入。

例2 机器负荷分配问题。某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入生产的机器数量，年完好率a=0。7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0。9。

假定开始生产时完好的机器数量s1=1000台，试问每年如何安排机器在高、低负荷下的生产，使在五年内生产的产品总产量最高。

构造这个问题的动态规划模型： 设阶段序数k表示年度。

状态变量sk为第k年度初拥有的完好机器数量，同时也是第k?1年度末时的完好机器数量。 决策变量uk为第k年度中分配高负荷下生产的机器数量，于是sk?uk为该年度中分配在低负荷下生产的机器数量。

这里sk和uk均取连续变量，它们的非整数值可以这样理解，如sk=0。6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0。3，就表示一台机器在该年度只有3/10的时间能在高负荷下工作。

bks?u)s?u), k? ?1 ,2,状态转移方程为 sk?1?auk?(k?0.7uk?0.9(kkk段允许决策集合为 Dk(sk)??uk0?uk?sk? 设vk(sk,uk)为第k年度的产量，则

,5vk?8uk?5(sk?uk)

故指标函数为

V1,5??vk(sk,uk)

k?15令最优值函数fk(sk)表示由资源量sk出发，从第k年开始到第5年结束时所生产的产品的总产量最大值。因而有逆推关系式：

?f(s)?066???8uk?5(sk?uk)?fk?1?0.7uk?0.9(sk?uk)?? ?fk(sk)?umaxk?Dk(sk)??? k?1,2,3,4,5

从第5年度开始，向前逆推计算。

当k=5时，有f5(s5)?max8u5?5(s5?u5)?f6?0.7u5?0.9(s5?u5)?

0?u5?s5???max?8u5?5(s5?u5)??max?3u5?5s5?

0?u5?s50?u5?s5因f5是u5的线性单调增函数，故得最大解u5?s5，相应的有f5(s5)?8s5。

当k=4时，有f4(s4)?max8u4?5(s4?u4)?f5?0.7u4?0.9(s4?u4)?

0?u4?s4????max?8u4?5(s4?u4)?8?0.7u4?0.9(s4?u4)??0?u4?s4?max?13.6u4?12.2(s4?u4)??max?1.4u4?12.2s4?0?u4?s40?u4?s4

故得最大解，u4=s4，相应的有f4(s4)?13.6s4。依此类推，可求得

*?u3?s3, 相应的 f3(s3)?17.5s3?*?u2?0, 相应的 f2(s2)?20.8s2 ?*?u1?0, 相应的 f1(s1)?23.7s1?因s1=1000，故f1(s1)?23700（台）。

计算结果表明：最优策略为u1?0,u2?0,u3?s3,u4?s4,u5?s5，即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。

在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计算出每年年初完好机器数。已知s1=1000台，于是可得

*****s2?0.7u1*?0.9(s1?u1*)?0.9s1?900(台)**s3?0.7u2?0.2(s2?u2)?0.9s2?810(台)**s4?0.7u3?0.9(s3?u3)?0.7s3?567(台) **s5?0.7u4?0.9(s4?u4)?0.7s4?397(台)**s6?0.7u5?0.9(s5?u5)?0.7s5?278(台)下面讨论始端固定、终端自由的一般情形。

设有n个年度，在高、低负荷下生产的产量函数分别为g?cu1,h?du2，其中c、d>0，c>d。年回收率分别为a和b，0

sk?1?auk?b(sk?uk), k?1,2,?,n

k段的指标函数为

vk?cuk?b(sk?uk), k?1,2,?,n

令fk(sk)表示由状态sk出发，从第k年至第n年末时所生产的产品的总产量最大值。

可写出逆推关系式为：

?f(s)?0n?1n?1???cuk?d(sk?uk)?fk?1?auk?b(sk?uk)??(9?2) ?fk(sk)?0max?uk?sk??? k?1,2,?,n我们知道，在低负荷下生产的时间愈长，机器完好率愈高，但生产产量少。而在高负荷下生产产量会

增加，但机器损坏大。这样，即使每台产量高，总起来看产量也不高。

从前面的数字计算可以看出，前几年一般是全部用于低负荷生产，后几年则全部用于高负荷生产，这样才产量最高。如果总共为n年，从低负荷转为高负荷生产的是第t年，1≤t≤n。即是说，从1至t?1年在低负荷下生产，t至n年在高负荷下生产。现在要分析t与系数a、b、c、d是什么关系。

从回收率看，(b ? a)值愈大，表示在高负荷下生产时，机车损坏情况比在低负荷时严重得多，因此t值应选大些。从产量看，(c ? d)值愈大，表示在高负荷下生产较有利，故t应选小些。下面我们从(9-2)式这一基本方程出发来求出t与(b ? a)、(c ? d)的关系。

令?k?uksk。则在低负荷生产时有?k?0，高负荷生产时有?k?1。对第n段，有

fn(sn)?max?cun?d(sn?un)??max?(c?d)un?dsn??max?(c?d)?n?d?sn

0?un?sn0?un?sn0??n?1由于c＞d，所以?n应选1才能使fn(sn)最大。也就是说，最后一年应全部投入高负荷生产。故fn(sn)?csn

对n-1段，根据(9-2)式有

fn?1(sn?1)?maxun?10?un?1?sn?1?cun?1?d(sn?1?un?1)?fn(sn)??max?cun?1?d(sn?1?un?1)?csn??max?cun?1?d(sn?1?un?1)?c?aun?1?b(sn?1?un?1)??un?1

?max??(c?d)?c(b?a)?un?1?(d?cb)sn?1?un?1?max??(c?d)?c(b?a)??n?1?(d?cb)?sn?1?n?1(9?3)因此，欲要满足上式极值关系的条件是当

c?d?c(b?a)*(9?4)

*时，应取?n?1?1，即n ? 1年仍应全部在高负荷下生产。否则，当(9-4)式不满足时，应取?n?1?0，即n ? 1年应全部投入低负荷生产。 由前面知道，只要在第k年投入低负荷生产，那么递推计算结果必然是从第1年到第k年均为低负荷生产，即有?1??2????k?0。可见，算出?k?0后，前几年就没有必要再计算了。故只需研究哪一年由低负荷转入高负荷生产，即从?那一年开始变为1就行。根据这点，现只分析满足(9-4)式的情况。由于 …… 此处隐藏：1220字，全部文档内容请下载后查看。喜欢就下载吧 ……