最优化多目标规划动态规划.pptx

《最优化多目标规划动态规划.pptx》由会员分享，可在线阅读，更多相关《最优化多目标规划动态规划.pptx（141页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章多目标规划 在实际问题中，衡量一个设计方案的好坏往往不止一个。例如：设计一个导弹，既要射程远，命中率高，还要耗燃料少；又如：选择新厂址，除了要考虑运费、造价、燃料供应费等经济指标外，还要考虑对环境的污染等社会因素。这类问题即为多目标数学规划问题。第五章多目标规划早在1772年，Franklin就提出了多目标问题矛盾如何协调的问题，1896年，Pareto首次从数学角度提出了多目标最优决策问题，直到二十世纪50-70年代Charnes,Karlin,Zadeh等人先后做了许多较有影响的工作，多目标规划受到人们的关注。至今多目标规划已广泛应用于经济、管理、系统工程等科技的各个领域。1多目标规

2、划问题举例例1生产计划问题某工厂计划生产两种产品甲和乙，生产每件甲的利润为4元，生产每件乙的利润为3元，每件甲的加工时间为每件乙的两倍，若全部时间用来加工乙，则每日可生产乙500件，但工厂每日供给的原料只够生产甲和乙的总数共400件，产品甲是紧俏商品，预测市场日需求量为300件。决策者希望制定一个日生产方案，不仅能得到最大的利润，且能最大地满足市场需求。生产计划问题 问题分析设每日生产甲、乙的数量分别为x1,x2,令X=(x1,x2),则其目标函数为利润f1(X)=4x1+3x2甲的产量f2(X)=x1都取最大值满足约束条件x1+x2400（原料供应约束）2x1+x2500（加工时间约束）x1

3、0，x20多目标规划问题举例例2投资问题假设在一段时间内有a（亿元）的资金可用于建厂投资，若可供选择的项目记为1,2,m,而且一旦对第i个项目投资，则必须用掉ai（亿元）;而在这段时间内这第个项目可得到的收益为ci（亿元）,其中i=1,2,m,问如何确定最佳的投资方案？投资问题 问题分析 上述要求的最佳方案应为：投资少，收益大。多目标规划的标准形式V-minF(X)=(f1(X),f2(X),fp(X)Ts.t.gi(X)0,i=1,2,m其中X=(x1,x2,xn)T,p2这里V-min是指对向量形式的p个目标(f1(X),f2(X),fp(X)T求最小。一般假设多目标规划中的目标函数已经是

4、规范化了的。2多目标规划解的概念与性质 1.多目标规划解的概念例3 解分别对单个目标求出其最优解，对于第一个目标的最优解x(1)=1;第二个目标的最优解x(2)=1,为同一点，取x*=1作为多目标问题的最优解，其目标函数值F*(x)=(-2,-1).可以用变量空间和目标函数空间来分别描述各种解的情况。多目标规划解的概念下面考察例1中生产计划问题。问：是否能找到一个可行解X*=(x1*,x2*)T使之同时为f1(X)与f2(X)的最大解？在可行域内容易求解maxf1(X)的唯一最优解为(100,300),见图中B点。maxf2(X)的唯一最优解为(250,0),见图中C点。由此可得共同的最优解X

5、*并不存在。当一目标达到最优时，另一目标达不到最优，两目标相互矛盾。因此需要根据别的原则，权衡两者之间的得失，从R中找出满意的方案来。多目标规划解的概念如何比较方案的好坏呢？就上述问题，设X R，Y R，称X比Y好（或Y比X劣），若f1(X)f1(Y)f2(X)f2(Y)或f1(X)f1(Y)f2(X)f2(Y)不难得到除线段BC之外的其余R上的点均为劣解，而BC上无劣解，且两两无法比较，因此决策者只有根据某些别的考虑从BC上挑选出满意的方案来。这时称BC上的点为非劣解，或有效解。多目标规划解的概念对于一般的多目标规划问题：(VP)V-minF(X)=(f1(X),f2(X),fp(X)Ts.

6、t.gi(X)0,i=1,2,m其中X=(x1,x2,xn)T,p2设R=X|gi(X)0,i=1,2,m定义1设X*R，若对任意j=1,2,p,以及任意X R均有fj(X)fj(X*),j=1,2,p则称X*为问题(VP)的绝对最优解。最优解的全体记为Rab*多目标规划解的概念对于无绝对最优解的情况，引进下面的偏好关系：设F1=(f11,f21,fp1)T,F2=(f12,f22,fp2)T(1)F1F2意味着F1每个分量都严格小于F2的相应分量，即fj1fj2,j=1,2,p(2)F1F2等价于fj1fj2,j=1,2,p，且至少存在某个j0(1j0p),使fj01fj02(3)F1F2等

7、价于fj1fj2,j=1,2,p多目标规划解的概念定义2设X*R，若不存在X R满足F(X)F(X*),则称X*为问题(VP)的有效解（或Pareto解）。有效解的全体记为Rpa*定义3设X*R，若不存在X R满足F(X)F(X*),则称X*为问题(VP)的弱有效解（或弱Pareto解）。弱有效解的全体记为Rwp*多目标规划解的性质记Rj*为单目标问题(Pj)minfj(X)s.t.gi(X)0,i=1,2,m的最优解集合，j=1,2,p，可见而R，Rab*，Rpa*，Rwp*，R1*,Rp*之间的关系有下列图示。并有下列定理。多目标规划解的性质多目标规划解的性质定义4如果f1(X),f2(X

8、),fp(X)和g1(X),g2(X),gm(X)均为凸函数，则称多目标数学规划（VP）为凸多目标数学规划。一般来说，即使（VP）为凸多目标数学规划，Rwp*和Rpa*也不一定为凸集。多目标规划解的性质 2.多目标规划问题的像集在（VP）中，取定一可行解X0R，可得到其相应的目标函数值F(X0)=(f1(X0),fp(X0)T此为EP空间中的一个点，从而确定了从X到F(X)的一个映射，即FXF(X)集合F(R)=F(X)|X R称为约束集合R在映射F之下的像集。多目标规划解的性质一般来说，即使（VP）是凸多目标规划，像集F(R)也不一定为凸集（见例3）。但是，当目标函数f1(X),f2(X),

9、fp(X)为线性函数，约束集合R为凸多面体时，可以证明：像集F(R)为EP中的凸多面体。多目标规划解的性质对于像集F(R)，还可以定义有效点及弱有效点。定义5设F*F(R)，若不存在F F(R)，满足FF*则称F*为像集F(R)的有效点，有效点的全体记为Epa*.定义6设F*F(R)，若不存在F F(R)，满足FF*则称F*为像集F(R)的弱有效点，弱有效点的全体记为Ewp*.多目标规划解的性质类似地可证明：像集F(R)的有效点一定是弱有效点，即通过在像集F(R)上寻找有效点（或弱有效点），就可以确定约束集合R上的有效解（或弱有效解）。对此，有如下的定理。多目标规划解的性质定理4在像集F(R)

10、上，若Epa*已知，则在约束集合R上，有定理5在像集F(R)上，若Ewp*已知，则在约束集合R上，有另外通过对像集的研究，可以更直观地认识问题，并且可以提供一些处理多目标规划的方法。3处理多目标规划的一些方法在2中，注意到，要使多目标规划（VP）中所有子目标同时实现最优经常是不可解的，那么如何制定比较标准在（弱）有效解集中找到满意解呢？处理多目标规划的一些方法3.1约束法（主要目标法）在目标函数f1(X),f2(X),fp(X)中，选出其中的一个作为主要目标，如f1(X),而其它的目标f2(X),fp(X)只要满足一定的条件即可。处理多目标规划的一些方法如fj(X)fj0,j=2,p，处理多目

11、标规划的一些方法 3.2分层序列法把（VP）中的p个目标f1(X),f2(X),fp(X)按其重要性排一个次序；分为最重要目标、次要目标等等。不妨设p个目标责任制的重要性序列为f1(X),f2(X),fp(X)首先求第一个目标f1(X)的最优解(P1)minf1(X)X R设其最优值为f1*，再求第二个目标的最优解处理多目标规划的一些方法(P2)minf2(X)X R1其中R1=RX|f1(X)f1*其最优值为f2*，然后求第三个目标的最优解(P3)minf3(X)X R2其中R2=R1X|f2(X)f2*求得最优值为f3*,，最后求第p个目标的最优解(Pp)minfp(X)X Rp-1其中R

12、p-1=Rp-2X|fp-1(X)fp-1*处理多目标规划的一些方法此时求得最优解X*，最优值为fp*，则X*就是多目标问题(VP)在分层序列意义下的最优解。进一步有下列定理。定理6设X*是由分层序列法所得到的最优解，则X*Rpa*.处理多目标规划的一些方法 证明用反证法证明。假设X*不Rpa*，则必存在Y R，使F(Y)F(X*)下面分两种情形讨论：(1)若f1(Y)f1(X*),而f1(X*)=f1*,故得(P1)的可行解Y满足f1(Y)f1(X*)=f1*此与f1*=minf1(X)相矛盾。X R处理多目标规划的一些方法(2)若fj(Y)=fj(X*),j=1,2,j0-1但fj0(Y)

13、fj0(X*)2j0p此时必有fj(Y)=fj(X*)fj*,j=1,2,j0-1因此，Y是问题(Pj0)minfp(X)X Rj0-2X|fj0-1(X)fj0-1*的可行解，又由fj0(Y)fj0(X*)fj0*此与fj0*是问题(Pj0)的最优值相矛盾。综合(1)(2),定理得证。处理多目标规划的一些方法 3.3评价函数法直接求解多目标规划问题是比较困难的，有一类方法是通过构造一个评价函数（或效用函数）U(F(X)将多目标规划问题(VP)转化为单目标规划问题minU(F(X)X R然后求解该问题，并将其最优解X*作为(VP)的最优解。由于构造评价函数的多种多样，也就出现了多种不同的评价函

14、数方法。处理多目标规划的一些方法 1.线性加权和法对(VP)中的p个目标f1(X),f2(X),fp(X)按其重要程度给以适当的权系数j0(j=1,2,p),且j=1，然后构造评价函数目标函数是一种和的形式，这里要求所有应具有相同量纲，若量纲不同，必须进行统一量纲或无量纲化处理。处理多目标规划的一些方法问题的难点是如何确定合理的权系数。(1)“老手法”(2)-方法处理多目标规划的一些方法2.平方和加权法对单目标规划问题(Pj)minfj(X)j=1,2,pX R求出一个尽可能好的下界f10,fp0（可看成是规定值），minfj(X)fj0j=1,2,pX R处理多目标规划的一些方法构造评价函数

15、然后求minU(F(X)X R求得最优解X*作为多目标规划的解。处理多目标规划的一些方法 3.理想点法（虚拟点法）先求p个单目标规划问题的最优解，记fj*=fj(X(j)=minfj(X)j=1,2,pX R若所有X(j)(j=1,2,p)都相同，设为X*，则X*为多目标函数的绝对最优解，但一般不易达到，因此向量F*=(f1*,f2*,fp*)只是一个理想点。处理多目标规划的一些方法C（1975）提出的理想点，其中心思想是定义一个模，在这个模的意义下，找一个点尽量接近理想点F*，即求minU(F(X)=min|F(X)-F*|X RX R处理多目标规划的一些方法 一般定义处理多目标规划的一些方

16、法例4设f1(X)=3x1-2x2,f2(X)=-4x1-3x2,约束集R=X|2x1+3x218,2x1+x210,x10,x20试用理想点法求解V-minF(X)=(f1(X),f2(X)TX R解先分别对单目标求出最优解X(1)=(0,6)T,X(2)=(3,4)T,对应的目标函数值为f1(X(1)=f1*=-12,f2(X(2)=f2*=-24,故理想点为F*=(f1*,f2*)T=(-12,-24)T处理多目标规划的一些方法取q=2,此时要求可解得最优解X*=(0.53,5.65)T,对应的目标函数值分别为f1*=-9.72,f2*=-19.06,其解空间、像空间如图。处理多目标规划

17、的一些方法 4.极小极大法（协调矛盾法）在对策论中，常常在作决策时要考虑：“在最不利情况下找出一个最有利”的策略，即所谓“min-max”，依此，令评价函数U(F(X)=maxfj(X)1jp然后求minU(F(X)的最优解，设为X*X R评价函数也可以采用赋权的形式，即令(Q)minU(F(X)=minmaxjfj(X)X RX R1jp其中j0(j=1,2,p)是一组权系数。处理多目标规划的一些方法 对于极小极大问题，可以用增加一个变量t及p个约束的方法将其化为通常的数学规划模型。有下面等价的定理。定理7设（X*，t*）为的最优解，则X*必为(Q)的最优解；反之，设X*为(Q)的最优解，令

18、t*=maxjfj(X*)，则(X*，t*）必为(Qt)的最优解。1jp处理多目标规划的一些方法 证明设(X*，t*）为(Qt)的最优解，则对(Qt)的任意可行解(X,t)有jfj(X*)t*t,(j=1,2,p)，由此maxjfj(X*)t*t1jp若取X R，t=maxjfj(X),易见(X,t)也是(Qt)的1jp可行解，将此t代入上式右端，得maxjfj(X*)maxjfj(X)对任意X R1jp1jp即X*为(Q)的最优解。处理多目标规划的一些方法 反之，设X*为(Q)的最优解，最小值为maxjfj(X*)t*1jp易见(X*,t*)是(Qt)的可行解。设(X,t)为(Qt)的任一可

19、行解，由jfj(X)t,j=1,2,p,X R知maxjfj(X)t对任意X R1jp由此t*=maxjfj(X*)maxjfj(X)t1jp1jp即t*为(Qt)的最小值，(X*，t*）为(Qt)的最优解。处理多目标规划的一些方法 5.乘除法（几何平均法）在(VP)中，设各目标函数值均有 fj(X)0,j=1,2,p不妨设其中k个f1(X),f2(X),fk(X)要求实现最小，其余fk+1(X),fp(X)要求实现最大，则可构造评价函数然后求minU(F(X)X R3.4评价函数的收敛性上节中，用不同的评价函数U(F(X)将多目标规划(VP)转化为单目标问题minU(F(X)X R来处理，并

20、将其解X*作为(VP)的解。而X*是否为(VP)的有效解或弱有效解呢？评价函数的收敛性定义7若对任意F,F Ep,当FF时，都有U(F)U(F)成立，则称U(F)是F的严格单调增函数。定义8若对任意F,F Ep,当FF时，都有U(F)U(F)成立，则称U(F)是F的单调增函数。评价函数的收敛性 定理8若对F Ep，U(F)是严格单调增函数，则单目标问题minU(F(X)X R的最优解X*Rpa*证明用反证法。若X*不Rpa*，即存在Y R，使F(Y)F(X*)由U(F)的严格单调性，有U(F(Y)U(F(X*)此与X*是minU(F(X)的最优解矛盾。X R评价函数的收敛性类似地可证得下面的定

21、理。定理9若对F Ep，U(F)是单调增函数，则单目标问题minU(F(X)X R的最优解X*Rwp*评价函数的收敛性针对3.3中使用的评价函数，由分析知均为严格单调函数或单调函数，从而由定理8和定理9知，求得的X*Rpa*或X*Rwp*评价函数的收敛性 1.线性加权和法j0，j=1,2,p,且j=1，此时U(F)为单调增函数。特别当j0，j=1,2,p时，U(F)为严格单调增函数。这是因为，若j0，j=1,2,p,且F0，于是j0fj0j0fj0相加得评价函数的收敛性特别当j0，j=1,2,p时，对FF，则jfjjfjj=1,2,p由FF，则至少存在某个j0(1j0p)，使fj0fj0从而j

22、0fj0j0fj0相加得评价函数的收敛性2.平方和加权法U(F)为F的严格单调增函数。评价函数的收敛性这是因为，若FF，由于FF0，FF0，故0fj-fj0fj-fj0j=1,2,p且至少存在某个j0(1j0p)，有fj-fj0fj-fj0从而j0fj0j0fj0故U(F)U(F)即U(F)为F的严格单调增函数。评价函数的收敛性3.理想点法式中fjfj*，j=1,2,p为F的严格单调增函数。可以仿照2的证法类似证明。评价函数的收敛性 4.极小极大法U(F)=maxjfj1jp为F的单调增函数。这里j0，j=1,2,p.这是因为，若FF，则对j=1,2,p,均有fjfj于是，若记j0fj0=ma

23、xjfj1jp则U(F)=maxjfj=j0fj0j0fj0maxjfj=U(F)1jp1jp评价函数的收敛性 5.乘除法且gj0,j=1,2,p可证U(G)为G的严格单调增函数。评价函数的收敛性这是因为，若GG，则由G0,G0及gjgjj=1,2,p且至少存在某个j0(1j0p)使gj0gj0则有评价函数的收敛性由上述讨论知：由方法1(j0),2,3,5求得的最优解X*Rpa*而由方法1(j0)，4得到的最优解X*Rwp*3.5逐步法（交替式对话方法）由于问题的复杂性，有时决策者所提供的信息不足以使分析者确定各目标函数之间的关系，因此需要在决策者和分析者之间建立一种交互式的对话方法（如Ste

24、pMethod,STEM,逐步法），分析者根据决策者提供的信息（经修改和补充后的）给出中间结果，决策者对中间结果发表意见，可根据中间结果进一步提供信息，让分析者重新计算，直到求得满意解为止。逐步法下面介绍多目标线性规划中的STEM步骤:求V-minF(X)=(f1(X),f2(X),fp(X)TX R逐步法 1.求p个线性规划的最优解minfi(X)=fi(X(i)=fi*i=1,2,pX R令fimaxmaxfi(X(j)i=1,2,p1jp显然fimaxfi*i=1,2,p不妨设不完全取等号。逐步法2.决策者不能给出加权系数，分析者只好根据函数fi(X)和R的性质给出一种算法：逐步法3.求

25、线性规划的最优解(X(0),t(0)逐步法 4.决策者对F(X(0)与F*=(f1*,fp*)T进行比较，若对X(0)比较满意，则迭代停止；否则，对最满意的fj0(X(0)提出允许变大的上限fj0,而对其它fi(X)(ij0)则不允许变大，因此把(P0)改成求的最优解(X(1),t(1)。逐步法若对X(1)仍不满意，则可用这种思想在(P1)中添加新的约束，或修改fj的值，再求新的解，这种交互式对话进行若干次，直到决策者满意为止。第六章动态规划动态规划（DynamicProgramming）是最优化的一个分支。1951年美国数学家R.Bellman（贝尔曼）等人根据一类多阶段决策问题的特性，提出

26、了解决这类问题的“最优性原理”，并研究了许多实际问题，从而建立了最优化的一个分支动态规划。动态规划 动态规划把比较复杂的问题划分成若干阶段，通过逐段求解，最终求得全局最优解。特别对于离散性问题，由于解析数学无法运用，动态规划就成为非常有效的工具。然而动态规划目前还存在以下弱点：1）动态规划没有一个统一的算法，它必须针对各种问题的性质，利用最优性原理得出函数方程后，再结合其它数学技巧来求解，而没有一种统一的处理方法，从而我们称动态规划是一种方法。2）当变数的个数（维数）太大时，这类问题虽可以用动态规划来描述，但由于计算机存贮容量和计算机速度的限制，使问题无法解决，此即所谓“维数障碍”。动态规划动

27、态规划根据多阶段决策过程的时间参量是离散的还是连续的和其决策过程的演变是确定性的还是随机的，可以分为离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。1多阶段决策问题及实例所谓多阶段决策问题，是指一类活动过程，它可以分为互相联系的若干个阶段，在每一阶段都需要作出决策，从而使整个过程达到最优的活动效果。因此，各个阶段决策的选取常依赖于当前面临的状态，又影响下一个阶段的决策，从而影响整个过程的活动路线，这种把一个问题看成一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称序贯决策过程。多阶段决策问题及实例各个阶段的决策确定以后就构成一个决策序列，称为一个策略。由于每一个阶段

28、可供选择的决策不止一个，因而对应于整个活动过程就有许多策略选择采用，从中选出一个效果最好的为最优策略。在多阶段决策问题中，既然引入了阶段的概念，也就与时间密不可分，决策过程从一个状态到另一个状态，随着时间的变化在变化，也就有了“动态”的含义。有一些问题表面上处来与时间无关，只要人为地引入“时间”因素，也可以变为下个多阶段决策问题，用动态规划方法来处理。多阶段决策问题及实例例1最短路线问题AB1B2C1C2C3C4D1E1F1GD2D3E2E3F2531368766835338422123335526643437597681310912131618多阶段决策问题及实例 例2多阶段资源分配问题 某

29、工厂生产A,B和C三种产品，都要使用某种原材料，原材料共有4吨。将不同数量的这种原料分配给各种产品时产生收益如下表（单位：万元），试确定使总收益最大的分配法。原料的分配量产品种类（吨）ABC000011068217171132018-2动态规划的基本概念一、最短路线问题的解首先讨论最短路线问题的求解方法解法一枚举法48条不同路线486=288步加法47次路线长度的比较最短路长为18最短路线问题的解 解法二共有6个阶段记f1(A)A到G的最短距离则f1(A)依赖于f2(B1),f2(B2),而f6(F1)=4,f6(F2)=3故由后向前写出相应公式的形式。解法二称为逆推解法（逆序解法）最短路线问

30、题的解上面的做法极其简单，从中我们可以处到这样一个规律，即最短路线必须且只能由最短子路线组成，在求A到G的最短路线时，附带求得了从所有中间顶点到G的最短路，它们是作为整个问题的子问题出现的，并且被嵌入较大问题之中，这常常是动态规划方法的一个特点。二、动态规划的基本概念(1)阶段(Stage)对所给问题的过程，根据时间和空间的自然特征，恰当地划分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，用k表示。动态规划的基本概念(2)状态(State)状态表示某阶段开始所处的自然状况（或条件），它既是本阶段的起始位置，又是上一阶段的终了位置，通常一个阶段包含若干个状态。描述

31、状态的变量称为状态变量，用sk表示第k个阶段的状态变量，用Sk表示所有可能状态的集合。状态的选择不是任意的，必须具有下列性质：若某阶段状态给定后，则在这阶段以后过程的发展不受这以前各阶段状态的影响，这个性质称为无后效性（即马尔科夫性）。动态规划的基本概念(3)决策(Decision)决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。在最优控制中也称为控制。描述决策的变量称为决策变量，常用uk(sk)表示第k个阶段当状态处于sk时的决策变量，它是状态变量的函数。决策变量的取值范围称为允许决策集合，常用Dk(sk)表示第k阶段从状态sk

32、出发的允许决策集合，有uk(sk)Dk(sk)。动态规划的基本概念(4)策略(Policy)策略是一个按顺序排列的决策序列，用pk,n(sk)=uk(sk),uk+1(sk+1),un(sn)表示从第k阶段sk状态开始到终止的决策序列，称为k子过程策略；当k=1时，即为全过程的一个策略，简称策略。动态规划的基本概念(5)状态转移方程状态转移方程是确定过程由一个状态到另一个状态的演变过程。在第k阶段当状态处于sk时，若该段的决策变量uk一经确定，则第k+1阶段的状态变量sk+1的值也就随之确定，从而sk+1的值随sk和uk的值变化而变化，记为sk+1=Tk(sk,uk)，称为状态转移方程。动态规

33、划的基本概念(6)指标函数和最优值函数指标函数是用以衡量多阶段决策过程实现效果的一种数量指标，用Vk,n表示，即Vk,n=Vk,n(sk,uk,sk+1,sn+1)，k=1,2,n指标函数应具有可分离性，并满足递推关系Vk,n(sk,uk,sk+1,sn+1)=k(sk,uk,Vk+1,n(sk+1,sn+1)指标函数的最优值，称为最优值函数，记为fk(sk)，即fk(sk)=OptimizationVk,n(sk,uk,sk+1,sn+1)uk,un3最优性原理和泛函方程一、动态规划的最优性原理20世纪50年代，R.Bellman等人根据研究一类多阶段决策问题，提出了最优性原理。动态规划的最

34、优性原理：一个（整个过程的）最优策略所具有的性质是，不论过去的状态和决策如何，其余下的诸决策必构成一个最优子策略。动态规划的最优性原理利用最优性原理，可以把多阶段决策问题的求解过程看成是一个连续的递推过程，由后向前逐步推算（因条件不同，也可能由前向后推算）。在求解时，各状态前面的状态和决策对其后面的子问题来说，只不过相当于其初始条件而已，并不影响后面过程的最优策略。为了利用最优性原理求解多阶段决策问题，还要导出一些递推公式，便于运算。二、泛函方程在最短路的计算中，若记fk(sk)表示第k阶段处于状态sk时到终点的最短距离，dk(sk,uk(sk)表示从状态sk到由决策uk(sk)所决定的状态s

35、k+1之间的距离，则有下列递推关系式fn+1(sn+1)=0fk(sk)=mindk(sk,uk(sk)+fk+1(sk+1)k=n,n-1,2,1ukDk(sk)泛函方程一般地，所有动态规划过程之间的相似性在于，构造一组特殊类型泛函方程，称为递推关系，这些递推关系使得我们能够以简单的方式从fk+1(sk+1)算出fk(sk)，典型的指标函数可以为“和”的形式或“积”的形式。上述递推关系式即为极小化的泛函方程，且指标函数为和的形式，当其中的加号改为乘号时，即转化为积的形式。三、动态规划的基本方法用动态规划求解实际问题时，为了遵循动态规划的最优性原理，需要将实际问题转化为动态规划的数学模型，一般

36、按下列步骤进行：(1)根据时间或空间的自然特征，将问题划分为恰当的阶段(2)正确选择状态变量sk，使其既能方便描述过程的演变，又能满足无后效性(3)确定决策变量uk及每个阶段的允许决策集合Dk(sk)(4)写出状态转移方程sk+1=Tk(sk,uk)动态规划的基本方法(5)正确写出指标函数Vk,n，其应满足下列三个性质a)是定义在全过程和所有后部子过程上的数量函数b)具有可分离性，并满足递推关系，即Vk,n(sk,uk,sk+1,sn+1)=k(sk,uk,Vk+1,n(sk+1,sn+1)c)函数k(sk,uk,Vk+1,n(sk+1,sn+1)对变量Vk+1,n要严格单调。4函数空间与策略

37、空间迭代法多阶段决策问题其阶段数有可能是固定的，也有可能不是固定的，此时可用泛函方程来求解。设有N个点，以1,2,N记之，任两点i,j之间的长度为Cij,当i,j间有一弧直接连接时，0Cij+,当i,j间不直接连接它们的弧时，Cij=+.今设N为终点，求任一点i至终点N的最短距离。函数空间与策略空间迭代法定义f(i)为由i点出发至终点N的最短距离，则由最优性原理可得f(i)=min(Cij+f(j),i=1,2,N-1f(N)=0这样的泛函方程不是递推方程，而且f(i)出现在方程的两边，不能通过简单的递推求得结果。下面用两种迭代法来求解。1、函数空间迭代法设fk(i)表示由i点出发向N走k步所

38、构成的所有路线中的最短距离。函数空间迭代法求解步骤如下：1f1(i)=CiN,i=1,2,N-1f1(N)=02fk(i)=min(Cij+fk-1(j),i=1,2,N-1jfk(N)=03反复迭代2直到fk(i)=fk+1(i)=f(i)为止，i=1,2,N函数空间迭代法可以证明：(1)由上述步骤确定的函数序列fk(i)不超过N-1步单调下降收敛于问题的最优函数f(i)(2)若0Cij+（i,j=1,2,N）,则收敛步骤P有下列估计：2、策略空间迭代法策略空间的迭代就是先给出初始策略u1(i)，然后按某种方式求得新策略u2(i),u3(i),，直至最终求出最优策略。其步骤如下：1选一无回路

39、的初始策略u1(i),i=1,2,N-1,u1(i)表示在此策略下由i点到达的下一个点。令k=1策略空间迭代法2在此策略下作方程组fk(i)=Ci,uk(i)+fkuk(i),i=1,2,N-1fk(N)=0求解fk(i)，这里Ci,uk(i)为已知值3由指标函数fk(i)求策略uk+1(i)，其中uk+1(i)是minCi,u+fk(u)的解。令k=k+14按2,3反复迭代，可逐次求得uk(i)和fk(i)，若对某一k，uk(i)=uk-1(i)对所有i成立，则称策略收敛，此时uk(i)就是最优策略，其相应的fk(i)为最优值。策略空间迭代法可以证明：若初始策略u1(i)不构成回路，则以后迭

40、代所得的策略uk(i)也不构成回路（即解是唯一的），且fk(i)一致收敛于泛函方程的解。函数空间与策略空间迭代法例3下图为一街区的单行道交通网络，分别用函数空间迭代法和策略空间迭代法求各点到顶点5的最短路线。2 6 3 1 2 3 3 4 5 2函数空间与策略空间迭代法解先用函数空间迭代法求解。为了便于运算，将距离Cij写成下列矩阵的形式，将fk(i)写成列向量的形式，利用函数空间迭代法求解，步骤迭代如下：iCijj12345f1(i)f2(i)f3(i)f4(i)u(i)1036877220224443310322222544055555553000005其中最后一列u(i)为i点的最优决策

41、，于是得到各点到顶点5的最短路线和最短距离如下表：函数空间与策略空间迭代法i点最短路线最短距离1235 7235 435 245 5函数空间与策略空间迭代法 再用策略空间迭代法求解。先选取一不构成回路的初始策略u1(i)：u1(1)=3，u1(2)=3，u1(3)=5，u1(4)=5然后根据策略空间迭代法步骤中的2,3,4，求得结果如下：iCijj12345u1(i)f1(i)u2(i)f2(i)u3(i)103638272202234343310325252544055555553050505其最短距离与最短路线与函数空间迭代法一致。函数空间与策略空间迭代法注意：在求解这类问题中，若网络中出

42、现负权边，由于有可能出现负圈，故上述方法不太适用。5动态规划的解法及应用举例5.1一维资源分配问题例1用逆推法解maxz=x1x22x3x1+x2+x3=C(C0)xi0,i=1,2,3动态规划的解法及应用举例例2用动态规划解下列问题（P332）maxz=8x1+7x22x1+x285x1+2x215x1,x2为非负整数动态规划的解法及应用举例 解用逆序解法，将问题分为两个阶段，对应 状态变量：vj,wj分别为第j阶段，第一、第二约束可供分配的右端数值 决策变量：x1,x2，于是 f2*(v2,w2)=max7x2=7minv2,w2/2 0 x2v2 0 2x2 w2 x2取整数 f1*(v

43、1,w1)=max8x1+f2*(v1-2x1,w1-5x1)02x1v1 0 5x1 w1 x1取整数 而v1=8,w1=15,所以动态规划的解法及应用举例 f1*(8,15)=max8x1+7min(8-2x1,(15-5x1)/2)02x18 0 5x1 15 x1取整数 由于x1 min(8/2,15/5)=3,因而 f1*(8,15)=max8x1+7min(8-2x1,(15-5x1)/2)x1=0,1,2,3=max8x1+7(15-5x1)/2=49 x1=0,1,2,3 x1*=0 由v2=v1-2x1=8,w2=w1-5x1=15,得 x2*=min8,15/2=7 最优解

44、为x1*=0,x2*=7,z*=49动态规划的解法及应用举例 1例2多阶段资源分配问题 某工厂生产A,B和C三种产品，都要使用某种原材料，原材料共有4吨。将不同数量的这种原料分配给各种产品时产生收益如下表（单位：万元），试确定使总收益最大的分配法。原料分配量产品种类（吨）ABC000011068217171132018-动态规划的解法及应用举例下面求1中的例2，将资源分配划分为三个阶段，分配给生产产品A，B，C的数量设为x1,x2,x3，其状态(资源剩余量)s1=4,s2=s1-x1,s3=s2-x2,sn+1=s4=0.现列表计算如下：动态规划的解法及应用举例由上述表知，最大总收益等于35，

45、最优决策序列是x1*=1,x2*=2,x3*=1动态规划的解法及应用举例例3资源连续分配问题：设有数量为s1的某种资源，可投入生产A和B两种产品，第一年若以数量u1投入生产A，剩下的s1-u1投入生产B，其收入为g(u1)+h(s1-u1)，这里g(0)=h(0)=0，在A、B生产后，资源的回收率分别为0a1,0b1,则在第一年生产后，回收的资源量合计为s2=au1+b(s1-u1);第二年将资源数量s2中的u2和s2-u2分别投入生产A和B，又得到收入为g(u2)+h(s2-u2)，如此继续进行n年，问如何决定每年投入A生产的资源量，才能使总的收入最大？动态规划的解法及应用举例此问题等价于下

46、列规划问题：maxZ=g(u1)+h(s1-u1)+g(u2)+h(s2-u2)+g(un)+h(sn-un)s2=au1+b(s1-u1)s3=au2+b(s2-u2)sn=aun-1+b(sn-1-un-1)0uisi,i=1,2,n动态规划的解法及应用举例下面用动态规划的方法来处理。设sk为状态变量，表示在第k阶段（第k年）可投入A、B两种生产的资源量。uk为决策变量，它表示在第k阶段用于A生产的资源量，则sk-uk表示用于B生产的资源量。状态转移方程为sk+1=auk+b(sk-uk)最优值函数fk(sk)表示当资源量为sk时，从第k阶段至第n阶段采取最优分配方案进行生产后所得到的最大

47、总收入。动态规划的解法及应用举例因此可写出动态规划的递推关系式为：fn(sn)=maxg(un)+h(sn-un)0unsnfk(sk)=maxg(uk)+h(sk-uk)+fk+1(auk+b(sk-uk),0ukskk=n-1,2,1最后求出f1(s1)即为所求问题的最大总收入。动态规划的解法及应用举例下面以简单的例子n=3,a=0.3,b=0.6,g(y)=0.8y,h(y)=0.5y来求解以说明递推求解的步骤。先计算f3(s3),得f3(s3)=max0.8u3+0.5(s3-u3)0u3s3=max0.3u3+0.5s3=0.8s30u3s3u3*=s3动态规划的解法及应用举例而f2

48、(s2)=maxg(u2)+h(s2-u2)+f3(au2+b(s2-u2)0u2s2=max0.98s2+0.06u2=1.04s20u2s2u2*=s2f1(s1)=maxg(u1)+h(s1-u1)+f2(au1+b(s1-u1)0u1s1=max1.124s1-0.012u1=1.124s10u1s1u1*=0动态规划的解法及应用举例上述结果可列表如下：实际阶段投入A的量投入B的量收入剩余量10s10.5s10.6s120.6s100.48s10.18s130.18s100.144s1总收入1.124s1动态规划的解法及应用举例上面的例子较简单，但当n很大时，且g(u),h(u)是复杂

49、函数时，问题的求解也是不容易的。当g(u),h(u)为凸函数，且h(0)=g(0)=0时，可以证明：在每个阶段上u(i)的最优决策总是取其上限或下限，因此，对于解的结构来说，它与g(u),h(u)是线性情况是类似的。动态规划的解法及应用举例5.2二维(两种)资源分配问题设有两种资源数量各为a和b，需要分配于n种生产，若第一种物资以数量xi，第二种以数量yi投入第i种生产时，得到的收益为gi(xi,yi)，问应如何分配这两种物资于n种生产使总收入最大？动态规划的解法及应用举例这个问题可化为下述数学规划问题：maxZ=g1(x1,y1)+g2(x2,y2)+gn(xn,yn)x1+x2+xn=ay

50、1+y2+yn=bxi0,yi0i=1,2,n动态规划的解法及应用举例用动态规划的方法求解。设状态变量为(Xk,Yk),Xk,Yk分别表示分配用于第k种生产至n种生产的两种物资的数量(资源剩余量)。决策变量为(xk,yk),xk,yk分别表示分配用于第k种生产的两种物资的数量。状态转移方程：Xk+1=Xk-xkYk+1=Yk-yk动态规划的解法及应用举例允许决策集合：Dk(Xk,Yk)=(xk,yk)|0 xkXk,0ykYk令fk(Xk,Yk)表示当状态为(Xk,Yk)时分别用于第k种生产到n种生产所得到的最大收入，则由最优性原理，得：fn(Xn,Yn)=g(Xn,Yn)fk(Xk,Yk)=