多目标规划课件

1、第五章第五章 多目标规划多目标规划 在实际问题中，衡量一个设计方案的在实际问题中，衡量一个设计方案的好坏往往不止一个。例如：设计一个好坏往往不止一个。例如：设计一个导弹，既要射程远，命中率高，还要导弹，既要射程远，命中率高，还要耗燃料少；又如：选择新厂址，除了耗燃料少；又如：选择新厂址，除了要考虑运费、造价、燃料供应费等经要考虑运费、造价、燃料供应费等经济指标外，还要考虑对环境的污染等济指标外，还要考虑对环境的污染等社会因素。这类问题即为多目标数学社会因素。这类问题即为多目标数学规划问题。规划问题。第五章第五章 多目标规划多目标规划早在早在1772年，年，Franklin就提出了多目就提出了多

2、目标问题矛盾如何协调的问题，标问题矛盾如何协调的问题，1896年，年，Pareto首次从数学角度提出了多目标首次从数学角度提出了多目标最优决策问题，直到二十世纪最优决策问题，直到二十世纪50-70年年代代Charnes, Karlin, Zadeh等人先后做等人先后做了许多较有影响的工作，多目标规划了许多较有影响的工作，多目标规划受到人们的关注。至今多目标规划已受到人们的关注。至今多目标规划已广泛应用于经济、管理、系统工程等广泛应用于经济、管理、系统工程等科技的各个领域。科技的各个领域。1多目标规划问题举例多目标规划问题举例例例1生产计划问题生产计划问题 某工厂计划生产两种产品甲和乙，生产每件

3、某工厂计划生产两种产品甲和乙，生产每件甲的利润为甲的利润为4元，生产每件乙的利润为元，生产每件乙的利润为3元，元，每件甲的加工时间为每件乙的两倍，若全部每件甲的加工时间为每件乙的两倍，若全部时间用来加工乙，则每日可生产乙时间用来加工乙，则每日可生产乙500件，但件，但工厂每日供给的原料只够生产甲和乙的总数工厂每日供给的原料只够生产甲和乙的总数共共400件，产品甲是紧俏商品，预测市场日需件，产品甲是紧俏商品，预测市场日需求量为求量为300件。决策者希望制定一个日生产方件。决策者希望制定一个日生产方案，不仅能得到最大的利润，且能最大地满案，不仅能得到最大的利润，且能最大地满足市场需求。足市场需求。

4、生产计划问题生产计划问题问题分析问题分析 设每日生产甲、乙的数量分别为设每日生产甲、乙的数量分别为x1, x2, 令令X=(x1, x2), 则其目标函数为利润则其目标函数为利润 f1(X)=4x1 + 3x2 甲的产量甲的产量 f2(X)=x1 都取最大值都取最大值 满足约束条件满足约束条件 x1 + x2400（原料供应约束）原料供应约束） 2x1 + x2500（加工时间约束）加工时间约束） x10，x20多目标规划问题举例多目标规划问题举例例例2投资问题投资问题假设在一段时间内有假设在一段时间内有a（亿元）的资金亿元）的资金可用于建厂投资，若可供选择的项目可用于建厂投资，若可供选择的项

5、目记为记为1,2,m, 而且一旦对第而且一旦对第i个项目投个项目投资，则必须用掉资，则必须用掉ai（亿元）亿元）; 而在这段而在这段时间内这第个项目可得到的收益为时间内这第个项目可得到的收益为ci（亿元）亿元）, 其中其中i=1,2,m, 问如何确定问如何确定最佳的投资方案？最佳的投资方案？投资问题投资问题问题分析问题分析上述要求的最佳方案应为：投资少，收益大。上述要求的最佳方案应为：投资少，收益大。 mixxaxaxcxxxfxaxxxfiixiimiiimiiimmiiimi,.,2,1,0)1(,),.,(,),.,(01112121211且且要要满满足足下下列列约约束束条条件件取取最最

6、大大而而最最小小问问题题即即求求个个项项目目不不投投资资若若对对第第个个项项目目投投资资若若决决定定对对第第设设多目标规划的标准形式多目标规划的标准形式V-min F(X)=(f1(X), f2(X),fp(X)T s.t. gi(X)0, i=1,2,m 其中其中X=(x1,x2,xn)T, p2 这里这里V-min 是指对向量形式的是指对向量形式的p个目个目标标(f1(X), f2(X),fp(X)T求最小。求最小。一般假设多目标规划中的目标函数已一般假设多目标规划中的目标函数已经是规范化了的。经是规范化了的。2 多目标规划解的概念与性质多目标规划解的概念与性质1. 多目标规划解的概念多目

7、标规划解的概念例例3解解分别对单个目标求出其最优解，对于第分别对单个目标求出其最优解，对于第一个目标的最优解一个目标的最优解x(1)=1; 第二个目标的最优第二个目标的最优解解x(2)=1, 为同一点，取为同一点，取x*=1作为多目标问题作为多目标问题的最优解，其目标函数值的最优解，其目标函数值F*(x) =(-2,-1). 可以用变量空间和目标函数空间来分别描可以用变量空间和目标函数空间来分别描述各种解的情况。述各种解的情况。RxxFVRxxxxxfxxxf )(min,2 , 0213210)(,42)(221求求设设多目标规划解的概念多目标规划解的概念下面考察例下面考察例1中生产计划问题

8、。问：是否能找到中生产计划问题。问：是否能找到一个可行解一个可行解X*=(x1*, x2*)T使之同时为使之同时为f1(X)与与f2(X)的最大解？的最大解？在可行域内容易求解在可行域内容易求解 max f1(X)的唯一最优解为的唯一最优解为 (100, 300), 见图中见图中B点。点。 max f2(X)的唯一最优解为的唯一最优解为 (250, 0), 见图中见图中C点。点。 由此可得共同的最优解由此可得共同的最优解X*并不存在。当一目标并不存在。当一目标达到最优时，另一目标达不到最优，两目标相互达到最优时，另一目标达不到最优，两目标相互矛盾。因此需要根据别的原则，权衡两者之间的矛盾。因此

9、需要根据别的原则，权衡两者之间的得失，从得失，从R中找出满意的方案来。中找出满意的方案来。多目标规划解的概念多目标规划解的概念 如何比较方案的好坏呢？如何比较方案的好坏呢？ 就上述问题，设就上述问题，设XR，YR，称，称X比比Y好好（或（或Y比比X劣），若劣），若 f1(X)f1(Y) f2(X) f2(Y) 或或 f1(X)f1(Y) f2(X) f2(Y) 不难得到除线段不难得到除线段BC之外的其余之外的其余R上的点均为上的点均为劣解，而劣解，而BC上无劣解，且两两无法比较，上无劣解，且两两无法比较，因此决策者只有根据某些别的考虑从因此决策者只有根据某些别的考虑从BC上上挑选出满意的方案来

10、。这时称挑选出满意的方案来。这时称BC上的点为上的点为非劣解非劣解，或，或有效解有效解。多目标规划解的概念多目标规划解的概念对于一般的多目标规划问题：对于一般的多目标规划问题： (VP) V-min F(X)=(f1(X), f2(X),fp(X)T s.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, 以及任意以及任意XR均有均有 fj(X)fj(X*), j=1,2,p 则称则称X*为问题为问题(VP)的的绝对最优解绝对最优解。最优解的全。最优解的全体记为体记为

11、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等价于等价于fj1fj2, j=1,2,p多目标规划解的概念多目标规划解的概念定义定义2 设设X*R，若不存在若

12、不存在XR满足满足F(X)F(X*), 则称则称X*为问题为问题(VP)的的有效解有效解（或或Pareto解解）。有效解的全体记为）。有效解的全体记为Rpa*定义定义3 设设X*R，若不存在若不存在XR满足满足F(X)F(X*), 则称则称X*为问题为问题(VP)的的弱有效解弱有效解（或弱或弱Pareto解解）。弱有效解的全体记为）。弱有效解的全体记为Rwp*多目标规划解的性质多目标规划解的性质记记Rj*为单目标问题为单目标问题(Pj) min fj(X) s.t. gi(X)0, i=1,2,m的最优解集合，的最优解集合，j=1,2,p，可见可见而而R，Rab*，Rpa*，Rwp*，R1*,

13、 Rp*之间的之间的关系有下列图示。并有下列定理。关系有下列图示。并有下列定理。*1*jpjabRR 多目标规划解的性质多目标规划解的性质*321paabwpjwppaRRRRRRR 定理定理定理定理定理定理多目标规划解的性质多目标规划解的性质定义定义4 如果如果f1(X), f2(X),fp(X)和和g1(X), g2(X),gm(X)均为凸函数，则称多目均为凸函数，则称多目标数学规划（标数学规划（VP）为为凸多目标数学规划凸多目标数学规划。一般来说，即使（一般来说，即使（VP）为凸多目标数为凸多目标数学规划，学规划，Rwp*和和Rpa*也不一定为凸集。也不一定为凸集。多目标规划解的性质多目

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

15、定为凸集（见例3）。）。但是，当目标函数但是，当目标函数f1(X), f2(X),fp(X)为为线性函数，约束集合线性函数，约束集合R为凸多面体时，可为凸多面体时，可以证明：像集以证明：像集F(R)为为EP中的凸多面体。中的凸多面体。多目标规划解的性质多目标规划解的性质 对于像集对于像集F(R)，还可以定义有效点及弱有效还可以定义有效点及弱有效点。点。定义定义5 设设F*F(R)，若不存在若不存在FF(R)，满足满足 FF* 则称则称F*为像集为像集F(R)的的有效点有效点，有效点的全体，有效点的全体记为记为Epa*.定义定义6 设设F*F(R)，若不存在若不存在FF(R)，满足满足 FF*

16、则称则称F*为像集为像集F(R)的的弱有效点弱有效点，弱有效点的，弱有效点的全体记为全体记为Ewp*.多目标规划解的性质多目标规划解的性质类似地可证明：像集类似地可证明：像集F(R)的有效点一的有效点一定是弱有效点，即定是弱有效点，即通过在像集通过在像集F(R)上寻找有效点（或弱上寻找有效点（或弱有效点），就可以确定约束集合有效点），就可以确定约束集合R上上的有效解（或弱有效解）。对此，有的有效解（或弱有效解）。对此，有如下的定理。如下的定理。*wppaEE 多目标规划解的性质多目标规划解的性质定理定理4 在像集在像集F(R)上，若上，若Epa*已知，则在约已知，则在约束集合束集合R上，有上，

17、有定理定理5 在像集在像集F(R)上，若上，若Ewp*已知，则在约已知，则在约束集合束集合R上，有上，有另外通过对像集的研究，可以更直观地认另外通过对像集的研究，可以更直观地认识问题，并且可以提供一些处理多目标规识问题，并且可以提供一些处理多目标规划的方法。划的方法。),(|*RXXFFXRpaEFpa ),(|*RXXFFXRwpEFwp 3处理多目标规划的一些方法处理多目标规划的一些方法在在2中，注意到，要使多目标规划中，注意到，要使多目标规划（VP）中所有子目标同时实现最优经中所有子目标同时实现最优经常是不可解的，那么如何制定比较标常是不可解的，那么如何制定比较标准在（弱）有效解集中找到

18、满意解呢？准在（弱）有效解集中找到满意解呢？处理多目标规划的一些方法处理多目标规划的一些方法3.1 约束法（主要目标法）约束法（主要目标法） 在目标函数在目标函数f1(X), f2(X),fp(X)中，选中，选出其中的一个作为主要目标，如出其中的一个作为主要目标，如f1(X), 而其它的目标而其它的目标f2(X),fp(X)只要满足一只要满足一定的条件即可。定的条件即可。处理多目标规划的一些方法处理多目标规划的一些方法如如fj(X)fj0, j=2,p， pjfXfmiXgXfmiXgXRXffjjiijRXj,.,2,)(,.,2 , 1, 0)()(min:,.,2 , 1, 0)(|)(

19、min010单单目目标标规规划划问问题题划划问问题题化化为为下下面面的的于于是是可可以以把把原原来来的的多多规规这这里里处理多目标规划的一些方法处理多目标规划的一些方法3.2 分层序列法分层序列法 把（把（VP）中的中的p个目标个目标f1(X), f2(X),fp(X)按按其重要性排一个次序；分为最重要目标、次其重要性排一个次序；分为最重要目标、次要目标等等。不妨设要目标等等。不妨设p个目标责任制的重要性个目标责任制的重要性序列为序列为 f1(X), f2(X),fp(X) 首先求第一个目标首先求第一个目标f1(X)的最优解的最优解 (P1) min f1(X) XR 设其最优值为设其最优值为

20、f1*，再求第二个目标的最优解再求第二个目标的最优解处理多目标规划的一些方法处理多目标规划的一些方法(P2) min f2(X) XR1 其中其中R1=RX |f1(X)f1* 其最优值为其最优值为f2*，然后求第三个目标的最优解然后求第三个目标的最优解 (P3) min f3(X) XR2 其中其中R2=R1X |f2(X)f2* 求得最优值为求得最优值为f3*,，最后求第最后求第p个目标的最优解个目标的最优解 (Pp) min fp(X) XR p-1 其中其中Rp-1=Rp-2X |fp-1(X)fp-1*处理多目标规划的一些方法处理多目标规划的一些方法此时求得最优解此时求得最优解X*，

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

22、此与f1*=min f1(X)相矛盾。相矛盾。 XR处理多目标规划的一些方法处理多目标规划的一些方法(2)若若fj(Y)= fj(X*), j=1,2,j0-1 但但fj0(Y)fj0(X*) 2j0p 此时必有此时必有fj(Y)= fj(X*)fj*, j=1,2,j0-1 因此，因此，Y是问题是问题 (Pj0) min fp(X) XRj0-2X |fj0-1(X)fj0-1* 的可行解，又由的可行解，又由 fj0(Y)0, j=1,2,p不妨设其中不妨设其中k个个f1(X), f2(X),fk(X)要求实现要求实现最小，其余最小，其余fk+1(X), ,fp(X)要求实现最大，要求实现最

23、大，则可构造评价函数则可构造评价函数然后求然后求min U(F(X) XR)().()().()()(121XfXfXfXfXfXFUpkk 3.4 评价函数的收敛性评价函数的收敛性上节中，用不同的评价函数上节中，用不同的评价函数U(F(X)将将多目标规划多目标规划(VP)转化为单目标问题转化为单目标问题 min U(F(X) XR 来处理，并将其解来处理，并将其解X*作为作为(VP)的解。的解。 而而X*是否为是否为(VP)的有效解或弱有效解的有效解或弱有效解呢？呢？评价函数的收敛性评价函数的收敛性定义定义7 若对任意若对任意F, FEp, 当当FF时，时，都有都有 U(F)U(F) 成立，

24、则称成立，则称U(F)是是F的的严格单调增函数严格单调增函数。定义定义8 若对任意若对任意F, FEp, 当当FF时，时，都有都有 U(F)U(F) 成立，则称成立，则称U(F)是是F的的单调增函数单调增函数。评价函数的收敛性评价函数的收敛性定理定理8 若对若对FEp，U(F)是严格单调增函数，则单是严格单调增函数，则单目标问题目标问题 min U(F(X) XR 的最优解的最优解X*Rpa*证明证明用反证法。用反证法。 若若X*不不Rpa*，即存在即存在YR，使使 F(Y)F(X*) 由由U(F)的严格单调性，有的严格单调性，有 U(F(Y)0，j=1,2,p时，时，U(F)为严格单调增函数

25、。为严格单调增函数。 这是因为，若这是因为，若j0，j=1,2,p, 且且F0，于于是是 j0fj00，j=1,2,p时，对时，对FF，则则 jfjjfj j=1,2,p 由由FF，则则至少存在某个至少存在某个j0(1j0p)，使使 fj0fj0 从而从而 j0fj0j0fj0 相加得相加得 ) ()(11FUffFUpjjjpjjj 评价函数的收敛性评价函数的收敛性2. 平方和加权法平方和加权法 U(F)为为F的严格单调增函数。的严格单调增函数。pjffffFUjjjpjjjpjjj,.,2 , 1, 0, 1)()(01201 这里这里评价函数的收敛性评价函数的收敛性这是因为，若这是因为，

26、若FF，由于由于FF0，FF0，故故 0fj-fj0fj-fj0 j=1,2,p 且至少存在某个且至少存在某个j0(1j0p)，有有 fj-fj0fj-fj0 从而从而 j0fj0j0fj0 故故U(F)0，j=1,2,p. 这是因为，若这是因为，若FF，则对则对j=1,2,p, 均有均有 fjfj 于是，若记于是，若记 j0fj0= max jfj 1jp 则则 U(F)=max jfj =j0fj00, j=1,2,p 可证可证U(G)为为G的严格单调增函数。的严格单调增函数。jpjjjjpkkgGUFUpjkfkjfgfffffFU1121)()(111.)( 化为化为则评价函数则评价函

27、数当当当当令令评价函数的收敛性评价函数的收敛性这是因为，若这是因为，若GG，则由则由G0, G0及及 gjgj j=1,2,p 且至少存在某个且至少存在某个j0(1j0p)使使 gj00),2,3,5求求得的最优解得的最优解 X*Rpa*而由方法而由方法1(j0)，4得到的最优解得到的最优解 X*Rwp*3.5 逐步法逐步法（交替式对话方法）（交替式对话方法）由于问题的复杂性，有时决策者所提供的由于问题的复杂性，有时决策者所提供的信息不足以使分析者确定各目标函数之间信息不足以使分析者确定各目标函数之间的关系，因此需要在决策者和分析者之间的关系，因此需要在决策者和分析者之间建立一种交互式的对话方

28、法（如建立一种交互式的对话方法（如Step Method, STEM, 逐步法），分析者根据决逐步法），分析者根据决策者提供的信息（经修改和补充后的）给策者提供的信息（经修改和补充后的）给出中间结果，决策者对中间结果发表意见，出中间结果，决策者对中间结果发表意见，可根据中间结果进一步提供信息，让分析可根据中间结果进一步提供信息，让分析者重新计算，直到求得满意解为止。者重新计算，直到求得满意解为止。逐步法逐步法下面介绍多目标线性规划中的下面介绍多目标线性规划中的STEM步骤步骤: 求求 V-min F(X)=(f1(X), f2(X),fp(X)T XR0,|,.,2 , 1,)(1 XbAXX

29、RpixcXfnjjiji设设逐步法逐步法1.求求p个线性规划的最优解个线性规划的最优解 min fi(X) = fi(X(i) = fi* i=1,2,p XR 令令 fimax max fi(X(j) i=1,2,p 1jp 显然显然 fimaxfi* i=1,2,p 不妨设不完全取等号。不妨设不完全取等号。逐步法逐步法2.决策者不能给出加权系数决策者不能给出加权系数，分析者只好分析者只好根据函数根据函数fi(X)和和R的性质给出一种算法：的性质给出一种算法： 0)(10)(1,.,2 , 1*12*max*12max*max12121injijiiiinjijiiiipjjiifcfff

30、fcfffpi当当当当其中其中令令 逐步法逐步法3. 求线性规划求线性规划 的最优解的最优解(X(0), t(0) RXpitfXftPiii,.,2 , 1)(min)(*0 逐步法逐步法4. 决策者对决策者对F(X(0)与与F*=(f1*,fp*)T进行比较，若进行比较，若对对X(0)比较满意，则迭代停止；否则，对最满意的比较满意，则迭代停止；否则，对最满意的fj0(X(0)提出允许变大的上限提出允许变大的上限fj0, 而对其它而对其它fi(X)(ij0)则不允许变大，因此把则不允许变大，因此把(P0)改成求改成求 的最优解的最优解(X(1), t(1)。 RXjipiXfXffXfXfj

31、ipitfXftPiijjjiii0)0(0)0(000*1,.,2 , 1)()()()(,.,2 , 1)(min)( 逐步法逐步法若对若对X(1)仍不满意，则可用这种思想在仍不满意，则可用这种思想在(P1)中添加新的约束，或修改中添加新的约束，或修改fj的值，的值，再求新的解，这种交互式对话进行若再求新的解，这种交互式对话进行若干次，直到决策者满意为止。干次，直到决策者满意为止。第六章第六章 动态规划动态规划 动态规划（动态规划（Dynamic Programming）是最优化的一个分支。是最优化的一个分支。1951年美国数年美国数学家学家R.Bellman（贝尔曼）等人根据一贝尔曼）等

32、人根据一类多阶段决策问题的特性，提出了解类多阶段决策问题的特性，提出了解决这类问题的决这类问题的“最优性原理最优性原理”，并研，并研究了许多实际问题，从而建立了最优究了许多实际问题，从而建立了最优化的一个分支化的一个分支动态规划。动态规划。动态规划动态规划 动态规划把比较复杂的问题划分成若干阶段，通动态规划把比较复杂的问题划分成若干阶段，通过逐段求解，最终求得全局最优解。特别对于离过逐段求解，最终求得全局最优解。特别对于离散性问题，由于解析数学无法运用，动态规划就散性问题，由于解析数学无法运用，动态规划就成为非常有效的工具。然而动态规划目前还存在成为非常有效的工具。然而动态规划目前还存在以下弱

33、点：以下弱点：1）动态规划没有一个统一的算法，它）动态规划没有一个统一的算法，它必须针对各种问题的性质，利用最优性原理得出必须针对各种问题的性质，利用最优性原理得出函数方程后，再结合其它数学技巧来求解，而没函数方程后，再结合其它数学技巧来求解，而没有一种统一的处理方法，从而我们称动态规划是有一种统一的处理方法，从而我们称动态规划是一种方法。一种方法。2）当变数的个数（维数）太大时，这）当变数的个数（维数）太大时，这类问题虽可以用动态规划来描述，但由于计算机类问题虽可以用动态规划来描述，但由于计算机存贮容量和计算机速度的限制，使问题无法解决，存贮容量和计算机速度的限制，使问题无法解决，此即所谓此

34、即所谓“维数障碍维数障碍”。动态规划动态规划 动态规划根据多阶段决策过程的时间动态规划根据多阶段决策过程的时间参量是离散的还是连续的和其决策过参量是离散的还是连续的和其决策过程的演变是确定性的还是随机的，可程的演变是确定性的还是随机的，可以分为离散确定性、离散随机性、连以分为离散确定性、离散随机性、连续确定性、连续随机性四种决策过程续确定性、连续随机性四种决策过程模型。模型。1多阶段决策问题及实例多阶段决策问题及实例所谓多阶段决策问题，是指一类活动过程，所谓多阶段决策问题，是指一类活动过程，它可以分为互相联系的若干个阶段，在每它可以分为互相联系的若干个阶段，在每一阶段都需要作出决策，从而使整个

35、过程一阶段都需要作出决策，从而使整个过程达到最优的活动效果。因此，各个阶段决达到最优的活动效果。因此，各个阶段决策的选取常依赖于当前面临的状态，又影策的选取常依赖于当前面临的状态，又影响下一个阶段的决策，从而影响整个过程响下一个阶段的决策，从而影响整个过程的活动路线，这种把一个问题看成一个前的活动路线，这种把一个问题看成一个前后关联具有链状结构的多阶段过程就称为后关联具有链状结构的多阶段过程就称为多阶段决策过程多阶段决策过程，也称，也称序贯决策过程序贯决策过程。多阶段决策问题及实例多阶段决策问题及实例各个阶段的决策确定以后就构成一个决策各个阶段的决策确定以后就构成一个决策序列，称为一个策略。由

36、于每一个阶段可序列，称为一个策略。由于每一个阶段可供选择的决策不止一个，因而对应于整个供选择的决策不止一个，因而对应于整个活动过程就有许多策略选择采用，从中选活动过程就有许多策略选择采用，从中选出一个效果最好的为最优策略。在多阶段出一个效果最好的为最优策略。在多阶段决策问题中，既然引入了阶段的概念，也决策问题中，既然引入了阶段的概念，也就与时间密不可分，决策过程从一个状态就与时间密不可分，决策过程从一个状态到另一个状态，随着时间的变化在变化，到另一个状态，随着时间的变化在变化，也就有了也就有了“动态动态”的含义。有一些问题表的含义。有一些问题表面上处来与时间无关，只要人为地引入面上处来与时间无

37、关，只要人为地引入“时间时间”因素，也可以变为下个多阶段决因素，也可以变为下个多阶段决策问题，用动态规划方法来处理。策问题，用动态规划方法来处理。多阶段决策问题及实例多阶段决策问题及实例例例1 最短路线问题最短路线问题AB1B2C1C2C3C4D1E1F1GD2D3E2E3F2531368766835338422123335526643437597681310912131618多阶段决策问题及实例多阶段决策问题及实例例例2 多阶段资源分配问题多阶段资源分配问题某工厂生产某工厂生产A, B和和C三种产品，都要使用某种原材三种产品，都要使用某种原材料，原材料共有料，原材料共有4吨。将不同数量的这种

38、原料分配吨。将不同数量的这种原料分配给各种产品时产生收益如下表（单位：万元），试给各种产品时产生收益如下表（单位：万元），试确定使总收益最大的分配法。确定使总收益最大的分配法。 原料的分配量原料的分配量 产品种类产品种类 （吨）（吨） A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 -2动态规划的基本概念动态规划的基本概念一、最短路线问题的解一、最短路线问题的解 首先讨论最短路线问题的求解方法首先讨论最短路线问题的求解方法 解法一解法一枚举法枚举法 48条不同路线条不同路线 486=2886=288步加法步加法 47次路线长度的比较次路线长度的比较 最短路长

39、为最短路长为18最短路线问题的解最短路线问题的解解法二解法二共有共有6个阶段个阶段 记记f1(A) A到到G的最短距离的最短距离 则则 f1(A)依赖于依赖于f2(B1), f2(B2), 而而f6(F1)=4, f6(F2)=3 故由后向前写出相应公式的形式。故由后向前写出相应公式的形式。 解法二称为逆推解法（逆序解法）解法二称为逆推解法（逆序解法）最短路线问题的解最短路线问题的解上面的做法极其简单，从中我们可以上面的做法极其简单，从中我们可以处到这样一个规律，即最短路线必须处到这样一个规律，即最短路线必须且只能由最短子路线组成，在求且只能由最短子路线组成，在求A到到G的最短路线时，附带求得

40、了从所有中的最短路线时，附带求得了从所有中间顶点到间顶点到G的最短路，它们是作为整的最短路，它们是作为整个问题的子问题出现的，并且被嵌入个问题的子问题出现的，并且被嵌入较大问题之中，这常常是动态规划方较大问题之中，这常常是动态规划方法的一个特点。法的一个特点。二、动态规划的基本概念二、动态规划的基本概念(1)阶段阶段(Stage) 对所给问题的过程，根据时间和空对所给问题的过程，根据时间和空间的自然特征，恰当地划分为若干个间的自然特征，恰当地划分为若干个相互联系的阶段，以便能按一定的次相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段序去求解。描述阶段的变量称为阶段变量，用变量，

41、用k表示。表示。动态规划的基本概念动态规划的基本概念(2)状态状态(State) 状态表示某阶段开始所处的自然状况状态表示某阶段开始所处的自然状况（或条件），它既是本阶段的起始位置，（或条件），它既是本阶段的起始位置，又是上一阶段的终了位置，通常一个阶段又是上一阶段的终了位置，通常一个阶段包含若干个状态。描述状态的变量称为状包含若干个状态。描述状态的变量称为状态变量，用态变量，用sk表示第表示第k个阶段的状态变量，个阶段的状态变量，用用Sk表示所有可能状态的集合。表示所有可能状态的集合。状态的选择不是任意的，必须具有下列性状态的选择不是任意的，必须具有下列性质：若某阶段状态给定后，则在这阶段以

42、质：若某阶段状态给定后，则在这阶段以后过程的发展不受这以前各阶段状态的影后过程的发展不受这以前各阶段状态的影响，这个性质称为响，这个性质称为无后效性无后效性（即马尔科夫（即马尔科夫性）。性）。动态规划的基本概念动态规划的基本概念(3)决策决策(Decision) 决策表示当过程处于某一阶段的某个状决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为从而确定下一阶段的状态，这种决定称为决策。在最优控制中也称为控制。描述决决策。在最优控制中也称为控制。描述决策的变量称为决策变量，常用策的变量称为决策变量，常用

43、uk(sk)表示第表示第k个阶段当状态处于个阶段当状态处于sk时的决策变量，它是状时的决策变量，它是状态变量的函数。决策变量的取值范围称为态变量的函数。决策变量的取值范围称为允许决策集合，常用允许决策集合，常用Dk(sk)表示第表示第k阶段从阶段从状态状态sk出发的允许决策集合，有出发的允许决策集合，有uk(sk)Dk(sk)。动态规划的基本概念动态规划的基本概念(4)策略策略(Policy)策略是一个按顺序排列的决策序列，用策略是一个按顺序排列的决策序列，用 pk,n(sk)=uk(sk), uk+1(sk+1), un(sn) 表示从第表示从第k阶段阶段sk状态开始到终止的决状态开始到终止

44、的决策序列，称为策序列，称为 k子过程策略；当子过程策略；当k=1时，时，即为全过程的一个策略，简称策略。即为全过程的一个策略，简称策略。动态规划的基本概念动态规划的基本概念(5)状态转移方程状态转移方程状态转移方程是确定过程由一个状态状态转移方程是确定过程由一个状态到另一个状态的演变过程。在第到另一个状态的演变过程。在第k阶段阶段当状态处于当状态处于sk时，若该段的决策变量时，若该段的决策变量uk一经确定，则第一经确定，则第k+1阶段的状态变量阶段的状态变量sk+1的值也就随之确定，从而的值也就随之确定，从而sk+1的值的值随随sk和和uk的值变化而变化，记为的值变化而变化，记为sk+1=T

45、k(sk, uk)，称为状态转移方程。称为状态转移方程。动态规划的基本概念动态规划的基本概念(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)指标函数的最优值，称为最优值函数，记为指标函数的最优值，

46、称为最优值函数，记为fk(sk)，即即 fk(sk)=OptimizationVk, n(sk, uk, sk+1,sn+1) uk, , un3最优性原理和泛函方程最优性原理和泛函方程一、动态规划的最优性原理一、动态规划的最优性原理 20世纪世纪50年代，年代，R.Bellman等人根据研究一等人根据研究一类多阶段决策问题，提出了最优性原理。类多阶段决策问题，提出了最优性原理。 动态规划的最优性原理动态规划的最优性原理：一个（整个过程的）一个（整个过程的）最优策略所具有的性质是，不论过去的状最优策略所具有的性质是，不论过去的状态和决策如何，其余下的诸决策必构成一态和决策如何，其余下的诸决策必

47、构成一个最优子策略。个最优子策略。动态规划的最优性原理动态规划的最优性原理利用最优性原理，可以把多阶段决策问题利用最优性原理，可以把多阶段决策问题的求解过程看成是一个连续的递推过程，的求解过程看成是一个连续的递推过程，由后向前逐步推算（因条件不同，也可能由后向前逐步推算（因条件不同，也可能由前向后推算）。在求解时，各状态前面由前向后推算）。在求解时，各状态前面的状态和决策对其后面的子问题来说，只的状态和决策对其后面的子问题来说，只不过相当于其初始条件而已，并不影响后不过相当于其初始条件而已，并不影响后面过程的最优策略。面过程的最优策略。为了利用最优性原理求解多阶段决策问题，为了利用最优性原理求

48、解多阶段决策问题，还要导出一些递推公式，便于运算。还要导出一些递推公式，便于运算。二、泛函方程二、泛函方程在最短路的计算中，若记在最短路的计算中，若记fk(sk)表示第表示第k阶段阶段处于状态处于状态sk时到终点的最短距离，时到终点的最短距离，dk(sk, uk(sk)表示从状态表示从状态sk到由决策到由决策uk(sk)所决定的状态所决定的状态sk+1之间的距离，则有下列递推关系式之间的距离，则有下列递推关系式 fn+1(sn+1)=0 fk(sk)=mindk(sk, uk(sk) + fk+1(sk+1) k=n,n-1,2,1 ukDk(sk) 泛函方程泛函方程一般地，所有动态规划过程之

49、间的相似性一般地，所有动态规划过程之间的相似性在于，构造一组特殊类型泛函方程，称为在于，构造一组特殊类型泛函方程，称为递推关系，这些递推关系使得我们能够以递推关系，这些递推关系使得我们能够以简单的方式从简单的方式从fk+1(sk+1)算出算出fk(sk)，典型的指典型的指标函数可以为标函数可以为“和和”的形式或的形式或“积积”的形的形式。式。 上述递推关系式即为极小化的泛函方程，上述递推关系式即为极小化的泛函方程，且指标函数为和的形式，当其中的加号改且指标函数为和的形式，当其中的加号改为乘号时，即转化为积的形式。为乘号时，即转化为积的形式。三、动态规划的基本方法三、动态规划的基本方法用动态规划

50、求解实际问题时，为了遵循动态规划用动态规划求解实际问题时，为了遵循动态规划的最优性原理，需要将实际问题转化为动态规划的最优性原理，需要将实际问题转化为动态规划的数学模型，一般按下列步骤进行：的数学模型，一般按下列步骤进行：(1)根据时间或空间的自然特征，将问题划分为恰根据时间或空间的自然特征，将问题划分为恰当的阶段当的阶段(2)正确选择状态变量正确选择状态变量sk，使其既能方便描述过程的使其既能方便描述过程的演变，又能满足无后效性演变，又能满足无后效性(3)确定决策变量确定决策变量uk及每个阶段的允许决策集合及每个阶段的允许决策集合Dk(sk)(4)写出状态转移方程写出状态转移方程sk+1=T

51、k(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 函数空间与策略空间迭代法函数空间与策略空间迭代法多阶段决策问题其阶段

52、数有可能是固多阶段决策问题其阶段数有可能是固定的，也有可能不是固定的，此时可定的，也有可能不是固定的，此时可用泛函方程来求解。用泛函方程来求解。设有设有N个点，以个点，以1, 2, , N记之，任两记之，任两点点 i, j之间的长度为之间的长度为Cij, 当当i, j间有一弧间有一弧直接连接时，直接连接时，0Cij+, 当当i, j间不直接间不直接连接它们的弧时，连接它们的弧时，Cij=+. 今设今设N为终为终点，求任一点点，求任一点i至终点至终点N的最短距离。的最短距离。函数空间与策略空间迭代法函数空间与策略空间迭代法定义定义f(i)为由为由i点出发至终点点出发至终点N的最短距的最短距离，则

53、由最优性原理可得离，则由最优性原理可得 f(i) = min(Cij + f(j), i=1,2,N-1 f(N)=0这样的泛函方程不是递推方程，而且这样的泛函方程不是递推方程，而且f(i)出现在方程的两边，不能通过简单出现在方程的两边，不能通过简单的递推求得结果。的递推求得结果。 下面用两种迭代法来求解。下面用两种迭代法来求解。1、函数空间迭代法、函数空间迭代法设设fk(i)表示由表示由i点出发向点出发向N走走k步所构成的所步所构成的所有路线中的最短距离。有路线中的最短距离。 函数空间迭代法求解步骤如下：函数空间迭代法求解步骤如下： 1f1(i) = CiN, i=1,2,N-1 f1(N)

54、=0 2fk(i) = min(Cij + fk-1(j), i=1,2,N-1 j fk(N)=0 3反复迭代反复迭代2直到直到fk(i) = fk+1(i) = =f(i) 为止，为止，i=1,2,N函数空间迭代法函数空间迭代法可以证明：可以证明： (1)由上述步骤确定的函数序列由上述步骤确定的函数序列fk(i) 不超过不超过N-1步单调下降收敛于问题的最步单调下降收敛于问题的最优函数优函数f(i) (2)若若0Cij0)xi0, i=1,2,3动态规划的解法及应用举例动态规划的解法及应用举例例例2用动态规划解下列问题（用动态规划解下列问题（P332） max z=8x1 + 7x2 2x

55、1 + x28 5x1 + 2x215 x1, x2为非负整数为非负整数动态规划的解法及应用举例动态规划的解法及应用举例解解用逆序解法，将问题分为两个阶段，对应用逆序解法，将问题分为两个阶段，对应状态变量：状态变量：vj, wj分别为第分别为第j阶段，第一、第二约束阶段，第一、第二约束可供分配的右端数值可供分配的右端数值决策变量：决策变量：x1,x2，于是，于是f2*(v2,w2)=max7x2=7minv2, w2/2 0 x2v2 0 2x2 w2 x2取整数取整数f1*(v1,w1)=max8x1+ f2*(v1-2x1,w1-5x1) 02x1v1 0 5x1 w1 x1取整数取整数而

56、而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,3x1*=0由由v2=v1-2x1=8, w2=w1-5x1=15, 得得x2*= min8, 15/2=7最优解为最优解为x1*=0, x2*= 7, z*=49

57、动态规划的解法及应用举例动态规划的解法及应用举例1例例2 多阶段资源分配问题多阶段资源分配问题某工厂生产某工厂生产A, B和和C三种产品，都要使用某种原材三种产品，都要使用某种原材料，原材料共有料，原材料共有4吨。将不同数量的这种原料分配吨。将不同数量的这种原料分配给各种产品时产生收益如下表（单位：万元），试给各种产品时产生收益如下表（单位：万元），试确定使总收益最大的分配法。确定使总收益最大的分配法。 原料分配量原料分配量 产品种类产品种类 （吨）（吨） A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 -动态规划的解法及应用举例动态规划的解法及应用举例下面

58、求下面求1中的例中的例2，将资源分配划分，将资源分配划分为三个阶段，分配给生产产品为三个阶段，分配给生产产品A，B，C的数量设为的数量设为x1,x2,x3，其状态其状态(资源剩资源剩余量余量)s1=4, s2=s1-x1, s3=s2-x2, sn+1=s4=0.现列表计算如下：现列表计算如下：动态规划的解法及应用举例动态规划的解法及应用举例由上述表知，最大总收益等于由上述表知，最大总收益等于35，最，最优决策序列是优决策序列是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, 0bai时时 t工件工件i-1t-ai+bi排序问题排序问题得到得到 记记Z