资源描述：
《动态规划的应用实例.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第15卷综合刊云南财贸学院学报·经济管理版Vol.15,No52001年6月JournalofYunnanFinance&EconomicsUniversityJune2001动态规划的应用实例王刚(云南财贸学院基础部,云南昆明650221)有许多社会,经济,生物,生态和人口等问题广泛的应用。它将一个多级决策问题转化为了个可以描述成离散时间状态方程,例如,商品的生单级决策问题。产,销售,贮存和运输等的最优管理和控制问题,下面我们来看一个四级模型,须进行四项决自然资源,劳动力的合理利用和分配问题,人口增策d1,d2,d3,d4,假如某项确定的决策为对一特定
2、长局控制问题,以及积累与消耗的合理比例问题部门的投资额,与每一决策相对应的都有一个“序等。动态规划是贝尔曼(RichardBellman)在50年列”,我们假设:n级的盈利为Rn,且这一切利润只代提出的,它是用最优性原理解决多级决策过程与决策dn及n级“系统状态”有关。最优化的十分有效的方法,在许多领域中得到了我们要求“状态高量”xn包括前面那些级的第2,3和4级可达到的最高利润,其先决条件是所有有关的信息,比如,状态说明可以包括须保留从第2级开始尚有1000元可供使用。的,亦即尚需投资的部分。在应用动态规划时,必须求出每一级的函数图一即是这一模型的图示
3、,如果Rn为n级盈fn(xn),只是要从最后那一级开始,我们利用下面利,则我们的目的就是把下面的总额最大化:R1这一递推关系式就可得到函数:fn(xn)=max[Rnd(x1,d1)+R2(x2,d2)+⋯+R4(x4,d4)初始状态假n(xn,dn)+fn+1(xn+1)](1)设用x1来表示,这里似乎可以把它理解为开始时其中,xn+1=tn(xn,dn),这样,级决策变量dn的全所提供使用的资本额,在进行了全部投资决策后,经极状态x5就应表示尚可使用后资本额。部可行值都建立在最大化的基础上了。一个重要的假设是:实际状态xn和所属的决现在,原来确定4个
4、决策变量的最优值问题策dn借助于关于式xn+1=tn(xn,dn)应能很精确地就可以看成一个包括4个互相依存的最优化问题确定下一状态xn+1。这样,我们的投资问题即可的结果,而这4个问题中的每一个都只和唯一的由下面的变换所得:一个决策变量相关。这一分解作用即是动态规划xn+1=xn-dn问题的一个要点。这时可以借助于微分法,线性决策变量dn可能会受到一系列约束,比如:规则,列举所有给出的可能性成其它某项技术来投资额不准超过尚不使用的资本。着手一定级上的最优化。下面我们依据一个实例我们把fn(xn)定义为由n级直至最后一级取来对这种方法加以说明。得的最大盈
5、利(利润)。比如,假定f2(1000)为到实例:最优后运输路线·190·云南财贸学院学报·经济管理版第15卷增合刊一批货物准备从甲地到乙地,有如下可能的得到下面这一递推公式:运输路线供选择fn(xn)=min[Cxn1dn]+fn+1(xn+1)](2)dn其中xn+1=dn因为到达目的后就不再支付费用,故规定f5(x5)=0因为d4必定等于10,所以第4级很容易处理。状态高量x4可以取的值只能是8或9。相应下费用f4(8)=c8,10=10,f4(9)=c9,10=40第3级有许多选择,现有需要计算一下x3=5,6,7时f3(x3)的值:先来看f3(5
6、),如果运输处在正如图二所示,可以把这样一个问题看作是第3级的状态5,那么可以在d3=8及d3=9间选一个多级决策问题,是一个要作出4级决策的4择。余下的费用由csd+f4(d)即可得知,其中函数级问题。f4(d)(剩给第4级的费用)已经确定,比较好的决假定由a地到b地的费用cab由下表得出策是使这一数目最小化的那一个。如果决定x3=5时d=8,则余下的费用就等于C58+f4(8)=70+10=80。如果确定d3=9,那余下的费用就等于C59+f4(9)=50+40=90。所以我们的结论是:如果该批货物经过第5个城市,那么其下一个目的地应是第8个城市。下
7、面其它的路线就不再对需要加以考虑了。我们的部分结论是f3(5)=80及d3(5)=8;运用同样的方法借助于(2)就可确定f3的其余值为f3(6)=40,d3(6)=8,f3(7)=50;d3(7)=9现在我们来递推一下第2级,其后是第1级,计算情形在下表给出:第2级cxd+f3(x)需要求出的是从甲到乙费用最低的路线。这个问题可以这样来解决,就是把每一条可能路线x/d567f2(x)d2(x)的费用算一下,并判别出最便宜的路线。然而动2100+80120+40—1606350+80100+4070+50120⑦态规划却不需要将各条路线的全部费用算出就可4
8、—150+40130+501807以给出最化解。根据我们以前的论述,现在用fn(
