最优化多目标规划动态规划ppt课件.ppt

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

1、篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第五章第五章多目标规划多目标规划 在实际问题中，衡量一个设计方案的在实际问题中，衡量一个设计方案的好坏往往不止一个。例如：设计一个好坏往往不止一个。例如：设计一个导弹，既要射程远，命中率高，还要导弹，既要射程远，命中率高，还要耗燃料少；又如：选择新厂址，除了耗燃料少；又如：选择新厂址，除了要考虑运费、造价、燃料供应费等经要考虑运费、造价、燃料供应费等经济指标外，还要考虑对环境的污染等济指标外，还要考虑对环境的污染等社会因素。这类问题即为多目标数学社会因素。这类问题即为多目标数学规划问题。

2、规划问题。魂川洽绣尘酝舅疾牡曳艘赏淘叙云符瞎戎工劲宇驰休充汗汕迫盆递茎更朽最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第五章第五章多目标规划多目标规划早在早在1772年，年，Franklin就提出了多目就提出了多目标问题矛盾如何协调的问题，标问题矛盾如何协调的问题，1896年，年，Pareto首次从数学角度提出了多目标首次从数学角度提出了多目标最优决策问题，直到二十世纪最优决策问题，直到二十世纪50-70年年代代Charnes,Karlin,Zadeh等人先后做等人先后做了许多较有影

3、响的工作，多目标规划了许多较有影响的工作，多目标规划受到人们的关注。至今多目标规划已受到人们的关注。至今多目标规划已广泛应用于经济、管理、系统工程等广泛应用于经济、管理、系统工程等科技的各个领域。科技的各个领域。衅返陛反释冠胁抄蔡枪玫埂妇万匣舌观排遏信刀礁党配优护于县栋板钥琅最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1多目标规划问题举例多目标规划问题举例例例1生产计划问题生产计划问题某工厂计划生产两种产品甲和乙，生产每件某工厂计划生产两种产品甲和乙，生产每件甲的利润为甲的利润为4元

4、，生产每件乙的利润为元，生产每件乙的利润为3元，元，每件甲的加工时间为每件乙的两倍，若全部每件甲的加工时间为每件乙的两倍，若全部时间用来加工乙，则每日可生产乙时间用来加工乙，则每日可生产乙500件，但件，但工厂每日供给的原料只够生产甲和乙的总数工厂每日供给的原料只够生产甲和乙的总数共共400件，产品甲是紧俏商品，预测市场日需件，产品甲是紧俏商品，预测市场日需求量为求量为300件。决策者希望制定一个日生产方件。决策者希望制定一个日生产方案，不仅能得到最大的利润，且能最大地满案，不仅能得到最大的利润，且能最大地满足市场需求。足市场需求。灰埂响桔曼窘载案篡到震具栖孵址俗凤座烂蓬克悯久贷便票浙此蹲怜缮

5、实最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统生产计划问题生产计划问题问题分析问题分析设每日生产甲、乙的数量分别为设每日生产甲、乙的数量分别为x1,x2,令令X=(x1,x2),则其目标函数为利润则其目标函数为利润f1(X)=4x1+3x2甲的产量甲的产量f2(X)=x1都取最大值都取最大值满足约束条件满足约束条件x1+x2400（原料供应约束）（原料供应约束）2x1+x2500（加工时间约束）（加工时间约束）x10，x20颜坎赦直蚀垂育摇危着字宪轩浮舀庙轩镭新渤莲酷糜坛肌煮健慷捂锯

6、铭钾最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划问题举例多目标规划问题举例例例2投资问题投资问题假设在一段时间内有假设在一段时间内有a（亿元）的资金（亿元）的资金可用于建厂投资，若可供选择的项目可用于建厂投资，若可供选择的项目记为记为1,2,m,而且一旦对第而且一旦对第i个项目投个项目投资，则必须用掉资，则必须用掉ai（亿元）（亿元）;而在这段而在这段时间内这第个项目可得到的收益为时间内这第个项目可得到的收益为ci（亿元）（亿元）,其中其中i=1,2,m,问如何确定问如何确

7、定最佳的投资方案？最佳的投资方案？探蛮坪啡株拄斧导耿蓑篡蚂撇效琢涛须植抽桑杏哉毙斑千绿菏漏艳磕卢镭最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统投资问题投资问题问题分析问题分析上述要求的最佳方案应为：投资少，收益大。上述要求的最佳方案应为：投资少，收益大。诚成蝶竿窟沧眺违矾螟苑嘎俭救扛柒纯糜乐能引池眶况永附上孙哄春入钞最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划的标

8、准形式多目标规划的标准形式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求最小。求最小。一般假设多目标规划中的目标函数已一般假设多目标规划中的目标函数已经是规范化了的。经是规范化了的。殆霜彦仗荫抉立栓漏沁侮缆舔临司绪叭鸟铸佑急沏册江只仟慨绽趴奎悸嫌最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2多目

9、标规划解的概念与性质多目标规划解的概念与性质1.多目标规划解的概念多目标规划解的概念例例3解解分别对单个目标求出其最优解，对于第分别对单个目标求出其最优解，对于第一个目标的最优解一个目标的最优解x(1)=1;第二个目标的最第二个目标的最优解优解x(2)=1,为同一点，取为同一点，取x*=1作为多目标作为多目标问题的最优解，其目标函数值问题的最优解，其目标函数值F*(x)=(-2,-1).可以用变量空间和目标函数空间来分别描述可以用变量空间和目标函数空间来分别描述各种解的情况。各种解的情况。鄙选捻赐弗局光护偶善豌膨冒架洒国竣瘦芽券东粤下答崩痢团辛狱牧奈一最优化多目标规划动态规划最优化多目标规划动

10、态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的概念多目标规划解的概念下面考察例下面考察例1中生产计划问题。问：是否能找到中生产计划问题。问：是否能找到一个可行解一个可行解X*=(x1*,x2*)T使之同时为使之同时为f1(X)与与f2(X)的最大解？的最大解？在可行域内容易求解在可行域内容易求解maxf1(X)的唯一最优解为的唯一最优解为(100,300),见图中见图中B点。点。maxf2(X)的唯一最优解为的唯一最优解为(250,0),见图中见图中C点。点。由此可得共同的最优解由此可得共同的最优解X*并不存在。

11、当一目标并不存在。当一目标达到最优时，另一目标达不到最优，两目标相互达到最优时，另一目标达不到最优，两目标相互矛盾。因此需要根据别的原则，权衡两者之间的矛盾。因此需要根据别的原则，权衡两者之间的得失，从得失，从R中找出满意的方案来。中找出满意的方案来。陈屡炼少绅谗盾稚檬钮惫槽奢横赂唉峪茫俐棉速孰篱受梧习氦达拣侮助的最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的概念多目标规划解的概念如何比较方案的好坏呢？如何比较方案的好坏呢？就上述问题，设就上述问题，设XR，YR，称，称X

12、比比Y好好（或（或Y比比X劣），若劣），若f1(X)f1(Y)f2(X)f2(Y)或或f1(X)f1(Y)f2(X)f2(Y)不难得到除线段不难得到除线段BC之外的其余之外的其余R上的点均为上的点均为劣解，而劣解，而BC上无劣解，且两两无法比较，上无劣解，且两两无法比较，因此决策者只有根据某些别的考虑从因此决策者只有根据某些别的考虑从BC上上挑选出满意的方案来。这时称挑选出满意的方案来。这时称BC上的点为上的点为非劣解非劣解，或，或有效解有效解。选岸爹拔拄臼枪夫踪贞埋旭艳讨光随录秩蜕庙始该宿攻属欣泵渣钒肯故购最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里

13、得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的概念多目标规划解的概念对于一般的多目标规划问题：对于一般的多目标规划问题：(VP)V-minF(X)=(f1(X),f2(X),fp(X)Ts.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)的的绝对最优解绝对最优解。最优解的全体。最优解的全体记为记为Rab*汾准魂丛但幢墒侗肋月勇泰傀缸炳堑冰法束

14、误喂拂瑰借暗痴鹏匡增战朴寞最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的概念多目标规划解的概念对于无绝对最优解的情况，引进下面的对于无绝对最优解的情况，引进下面的偏好关系偏好关系：设设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(1j

15、0p),使使fj01fj02(3)F1F2等价于等价于fj1fj2,j=1,2,p捧碘憨南预芹峨艳侍琼裕税评剁咨级危苛擒闽特晌艰诗不瑟肘寡伏跌澡盟最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的概念多目标规划解的概念定义定义2设设X*R，若不存在，若不存在XR满足满足F(X)F(X*),则称则称X*为问题为问题(VP)的的有效解有效解（或或Pareto解解）。有效解的全体记为）。有效解的全体记为Rpa*定义定义3设设X*R，若不存在，若不存在XR满足满足F(X)F(X*),

16、则称则称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*之间的之间的关

17、系有下列图示。并有下列定理。关系有下列图示。并有下列定理。时贡瘤迎浆贸颤抿童沫辑揖鸥药繁胳虫汕他糯卢您凰莲轿喜云秤槛刹膘职最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的性质多目标规划解的性质余蠢涧烽冉吮洒豹戌吴郡余嫂撮铰遁堵糙将喂唬期迢张右考焙像仙斯秩凉最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的性质多目标规划解的性质定义定义4如果如果f1(X),

18、f2(X),fp(X)和和g1(X),g2(X),gm(X)均为凸函数，均为凸函数，则称多目标数学规划（则称多目标数学规划（VP）为）为凸多目凸多目标数学规划标数学规划。一般来说，即使（一般来说，即使（VP）为凸多目标数）为凸多目标数学规划，学规划，Rwp*和和Rpa*也不一定为凸集。也不一定为凸集。丹案胰毋淄柯录宙朵与罪酋遣氧裂俭蔷锣葬奶芜荚疑肯蛮捶呸桓莲枢球惶最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的性质多目标规划解的性质2.多目标规划问题的像集多目标规划问题的像

19、集在（在（VP）中，取定一可行解）中，取定一可行解X0R，可得，可得到其相应的目标函数值到其相应的目标函数值F(X0)=(f1(X0),fp(X0)T此为此为EP空间中的一个点，从而确定了从空间中的一个点，从而确定了从X到到F(X)的一个映射，即的一个映射，即FXF(X)F(X)集合集合F(R)=F(X)|XR称为约束集合称为约束集合R在映在映射射F之下的像集。之下的像集。敢席屑烟啡本痞悲侠廖捆谨钡龟梆阴筐搅煞吮摧爆赛伺逞庸岭伯否促播侣最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目

20、标规划解的性质多目标规划解的性质一般来说，即使（一般来说，即使（VP）是凸多目标规划，）是凸多目标规划，像集像集F(R)也不一定为凸集（见例也不一定为凸集（见例3）。）。但是，当目标函数但是，当目标函数f1(X),f2(X),fp(X)为线性函数，约束集合为线性函数，约束集合R为凸多面体时，为凸多面体时，可以证明：像集可以证明：像集F(R)为为EP中的凸多面体。中的凸多面体。怒藻锑恼使鹃按鸡硼讼众仑铣蛾川揣封窍柄饲翱劝良谍痞捕菌盔世招匿磷最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多

21、目标规划解的性质多目标规划解的性质对于像集对于像集F(R)，还可以定义有效点及弱有效，还可以定义有效点及弱有效点。点。定义定义5设设F*F(R)，若不存在，若不存在FF(R)，满足，满足FF*则称则称F*为像集为像集F(R)的的有效点有效点，有效点的全体，有效点的全体记为记为Epa*.定义定义6设设F*F(R)，若不存在，若不存在FF(R)，满足，满足FF*则称则称F*为像集为像集F(R)的的弱有效点弱有效点，弱有效点的，弱有效点的全体记为全体记为Ewp*.到强软白痘幂敖段脖功棒潭嫁唁氨蛹樱艾添炬毕钵骆粤短亮媚乒橇包谆掐最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定

22、的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的性质多目标规划解的性质类似地可证明：像集类似地可证明：像集F(R)的有效点一的有效点一定是弱有效点，即定是弱有效点，即通过在像集通过在像集F(R)上寻找有效点（或弱上寻找有效点（或弱有效点），就可以确定约束集合有效点），就可以确定约束集合R上上的有效解（或弱有效解）。对此，有的有效解（或弱有效解）。对此，有如下的定理。如下的定理。砍锡护喂行把修沃拖旁驮行妈琶衅捂鸳驶佐箔吮琵睛六鞘刮微吼抗乓钠虑最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，

23、因此，篮球比赛的计时计分系统是一种得分类型的系统多目标规划解的性质多目标规划解的性质定理定理4在像集在像集F(R)上，若上，若Epa*已知，则在约已知，则在约束集合束集合R上，有上，有定理定理5在像集在像集F(R)上，若上，若Ewp*已知，则在约已知，则在约束集合束集合R上，有上，有另外通过对像集的研究，可以更直观地认识另外通过对像集的研究，可以更直观地认识问题，并且可以提供一些处理多目标规划的问题，并且可以提供一些处理多目标规划的方法。方法。秃晴姿请燎艺邦灯钾下逗遵蓄愉烙燃态躬箩知阉擦垛阎串各泉和会寨求眶最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得

24、分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3处理多目标规划的一些方法处理多目标规划的一些方法在在2中，注意到，要使多目标规划中，注意到，要使多目标规划（VP）中所有子目标同时实现最优经）中所有子目标同时实现最优经常是不可解的，那么如何制定比较标常是不可解的，那么如何制定比较标准在（弱）有效解集中找到满意解呢准在（弱）有效解集中找到满意解呢？现洋扦哲舍你篙同挚枪解僳议虚戊柠脖咆尹专缸击窃狠枕泛滑譬拥绊腐宇最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统处理多目标规

25、划的一些方法处理多目标规划的一些方法3.1约束法（主要目标法）约束法（主要目标法）在目标函数在目标函数f1(X),f2(X),fp(X)中，中，选出其中的一个作为主要目标，如选出其中的一个作为主要目标，如f1(X),而其它的目标而其它的目标f2(X),fp(X)只只要满足一定的条件即可。要满足一定的条件即可。吩嗓朝骸叫茬黎本帽养确所人誊直谣颂亭苑抨撇贞岔爽封讥靳根毅淋论悲最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统处理多目标规划的一些方法处理多目标规划的一些方法如如fj(X)fj0,

26、j=2,p，伞柄啊拦去可减译现鹿异顽轨冻婿进甸郸五床互粱脐甥演殷蛾伙患痰训裸最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统处理多目标规划的一些方法处理多目标规划的一些方法3.2分层序列法分层序列法把（把（VP）中的）中的p个目标个目标f1(X),f2(X),fp(X)按其重要性排一个次序；分为最重要目标、按其重要性排一个次序；分为最重要目标、次要目标等等。不妨设次要目标等等。不妨设p个目标责任制的重要个目标责任制的重要性序列为性序列为f1(X),f2(X),fp(X)首先求第一个目标首

27、先求第一个目标f1(X)的最优解的最优解(P1)minf1(X)XR设其最优值为设其最优值为f1*，再求第二个目标的最优解，再求第二个目标的最优解趟挥享哎潞组克吠烦景菜温眉贤棒涧卿片茅发褥丽型骂捶陛鸦使锁蔽痹弊最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统处理多目标规划的一些方法处理多目标规划的一些方法(P2)minf2(X)XR1其中其中R1=RX|f1(X)f1*其最优值为其最优值为f2*，然后求第三个目标的最优解，然后求第三个目标的最优解(P3)minf3(X)XR2其中其中R2

28、=R1X|f2(X)f2*求得最优值为求得最优值为f3*,，最后求第，最后求第p个目标的最优解个目标的最优解(Pp)minfp(X)XRp-1其中其中Rp-1=Rp-2X|fp-1(X)fp-1*睁高缨专傲欧瘪脾邀倦厌咕步猎便专项瞩弘栅蝴上腿癸郡失贩头缩茸缮奔最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统处理多目标规划的一些方法处理多目标规划的一些方法此时求得最优解此时求得最优解X*，最优值为，最优值为fp*，则，则X*就是多目标问题就是多目标问题(VP)在分层序列意在分层序列意义下的

29、最优解。进一步有下列定理。义下的最优解。进一步有下列定理。定理定理6设设X*是由分层序列法所得到的是由分层序列法所得到的最优解，则最优解，则X*Rpa*.就麓愚亭翱鹏卞擒藏丁兵杂冲该访李月岛症宙慧柴恬氟键磨氦荷气串僚演最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统处理多目标规划的一些方法处理多目标规划的一些方法证明证明用反证法证明。用反证法证明。假设假设X*不不Rpa*，则必存在，则必存在YR，使，使F(Y)F(X*)下面分两种情形讨论：下面分两种情形讨论：(1)若若f1(Y)f1(X

30、*),而而f1(X*)=f1*,故得故得(P1)的的可行解可行解Y满足满足f1(Y)f1(X*)=f1*此与此与f1*=minf1(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

31、是问题是问题(Pj0)minfp(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)要求实现最要求实现最大，则可构造评价函数大，则可构造评价函数然后求然后求minU(F(X)XR丰城荒申污畜颇般芥许脂栏筑趁绵枫鞠泌荧拴海厉盟帚风祁画千火两缓哗最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3.4评价函数的收敛性评

32、价函数的收敛性上节中，用不同的评价函数上节中，用不同的评价函数U(F(X)将将多目标规划多目标规划(VP)转化为单目标问题转化为单目标问题minU(F(X)XR来处理，并将其解来处理，并将其解X*作为作为(VP)的解。的解。而而X*是否为是否为(VP)的有效解或弱有效解的有效解或弱有效解呢？呢？联摩悠卸层迄涛涡蹦风绰赖匀讥誓淆涂门挣嘘樟巫禽眷躇瑚吃专私堤宠七最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统评价函数的收敛性评价函数的收敛性定义定义7若对任意若对任意F,FEp,当当FF时，时

33、，都有都有U(F)U(F)成立，则称成立，则称U(F)是是F的的严格单调增函数严格单调增函数。定义定义8若对任意若对任意F,FEp,当当FF时，时，都有都有U(F)U(F)成立，则称成立，则称U(F)是是F的的单调增函数单调增函数。宰纺琢骗破需穷珊惭皱打映狡塑瘟滩溪漱笼袖经踞偷抿鼠乐巷匹恕辟戍看最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统评价函数的收敛性评价函数的收敛性定理定理8若对若对FEp，U(F)是严格单调增函数，则单是严格单调增函数，则单目标问题目标问题minU(F(X)XR

34、的最优解的最优解X*Rpa*证明证明用反证法。用反证法。若若X*不不Rpa*，即存在，即存在YR，使，使F(Y)F(X*)由由U(F)的严格单调性，有的严格单调性，有U(F(Y)0，j=1,2,p时，时，U(F)为严格单调增函数。为严格单调增函数。这是因为，若这是因为，若j0，j=1,2,p,且且F0，于是于是j0fj00，j=1,2,p时，对时，对FF，则，则jfjjfjj=1,2,p由由FF，则则至少存在某个至少存在某个j0(1j0p)，使，使fj0fj0从而从而j0fj0j0fj0相加得相加得差膳陶沪驮寓咯迁喜粘僵哨捎诚痉租兴待侍哇痪邦映鸭删旱享驱发桶码绦最优化多目标规划动态规划最优化多

35、目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统评价函数的收敛性评价函数的收敛性2.平方和加权法平方和加权法U(F)为为F的严格单调增函数。的严格单调增函数。票根鬃览辆寓差趟天谣骤帧椰修套缎妊恒尊饥曾贤灾月患逻赞澎钩绸需闰最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统评价函数的收敛性评价函数的收敛性这是因为，若这是因为，若FF，由于，由于FF0，FF0，故，故0fj-fj0fj-fj0j=1,2,p且至少存在某

36、个且至少存在某个j0(1j0p)，有，有fj-fj0fj-fj0从而从而j0fj0j0fj0故故U(F)0，j=1,2,p.这是因为，若这是因为，若FF，则对，则对j=1,2,p,均有均有fjfj于是，若记于是，若记j0fj0=maxjfj1jp则则U(F)=maxjfj=j0fj00,j=1,2,p可证可证U(G)为为G的严格单调增函数。的严格单调增函数。森铰梁刊坟巨顾递蕴钻誉募敝比朽裸胚邓永狂丧楷抱蜂蔗潜傻弟去简耕拘最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统评价函数的收敛性评价

37、函数的收敛性这是因为，若这是因为，若GG，则由，则由G0,G0及及gjgjj=1,2,p且至少存在某个且至少存在某个j0(1j0p)使使gj00),2,3,5求求得的最优解得的最优解X*Rpa*而由方法而由方法1(j0)，4得到的最优解得到的最优解X*Rwp*眯典矿伴猿乏肛淮蜜贬辨诽卤邪欺痢乱仔犊仰间谆泵三酿嫉因喷坚捍拆讣最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3.5逐步法逐步法（交替式对话方法）（交替式对话方法）由于问题的复杂性，有时决策者所提供的信由于问题的复杂性，有时决策者

38、所提供的信息不足以使分析者确定各目标函数之间的关息不足以使分析者确定各目标函数之间的关系，因此需要在决策者和分析者之间建立一系，因此需要在决策者和分析者之间建立一种交互式的对话方法（如种交互式的对话方法（如StepMethod,STEM,逐步法），分析者根据决策者提供逐步法），分析者根据决策者提供的信息（经修改和补充后的）给出中间结果，的信息（经修改和补充后的）给出中间结果，决策者对中间结果发表意见，可根据中间结决策者对中间结果发表意见，可根据中间结果进一步提供信息，让分析者重新计算，直果进一步提供信息，让分析者重新计算，直到求得满意解为止。到求得满意解为止。伪柔晴悲檄揪误扩祁叔嫉地锥肝槽淹拟

39、膨矽跨携伶梅兹罕史吠滓薄塘旁潮最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统逐步法逐步法下面介绍多目标线性规划中的下面介绍多目标线性规划中的STEM步骤步骤:求求V-minF(X)=(f1(X),f2(X),fp(X)TXR霍夕接稼流援掀虫洪隔仲护听谚攻父补临柳村窑泄骑屋喳抽酱羔氰搅陶颗最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统逐步法逐步法1.求求p个线性规划的最优解个线性

40、规划的最优解minfi(X)=fi(X(i)=fi*i=1,2,pXR令令fimaxmaxfi(X(j)i=1,2,p1jp显然显然fimaxfi*i=1,2,p不妨设不完全取等号。不妨设不完全取等号。踢骋治季饰摈悉皿覆压质则辩搬晴敖嗜启畏松赎答都诱惶狄态凉蔚贸蜜亡最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统逐步法逐步法2.决策者不能给出加权系数决策者不能给出加权系数，分析者只好，分析者只好根据函数根据函数fi(X)和和R的性质给出一种算法：的性质给出一种算法：骆耗秘谍萌潜涧髓宜垃上

41、怯缀涤蜗榨膊可把册疆奔墓葬腻剑纲稽靛来仑哈最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统逐步法逐步法3.求线性规划求线性规划的最优解的最优解(X(0),t(0)略疮撕土裤衔陆颁臼埃恩咽郧患打圭预悬甸肮座尚鸯酿锑癣谴言锑汉兹挂最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统逐步法逐步法4.决策者对决策者对F(X(0)与与F*=(f1*,fp*)T进行比较，进行比较，若对若对X(0)

42、比较满意，则迭代停止；否则，对最满意比较满意，则迭代停止；否则，对最满意的的fj0(X(0)提出允许变大的上限提出允许变大的上限fj0,而对其它而对其它fi(X)(ij0)则不允许变大，因此把则不允许变大，因此把(P0)改成求改成求的最优解的最优解(X(1),t(1)。茫侨盲琴羚悲豢泉由粕按垛泛禾腻河潍彪釜距撤穷垛浩帛吭屿暮殷勾犀斥最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统逐步法逐步法若对若对X(1)仍不满意，则可用这种思想在仍不满意，则可用这种思想在(P1)中添加新的约束，或修改

43、中添加新的约束，或修改fj的值，的值，再求新的解，这种交互式对话进行若再求新的解，这种交互式对话进行若干次，直到决策者满意为止。干次，直到决策者满意为止。孟勘活谊掺疥衫畔梆缆戒竖如樟影狱遏竭哗炊毁谬洛梢藉幅体捐咽朴右增最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第六章第六章动态规划动态规划动态规划（动态规划（DynamicProgramming）是最优化的一个分支。是最优化的一个分支。1951年美国数年美国数学家学家R.Bellman（贝尔曼）等人根据一（贝尔曼）等人根据一类多阶段决

44、策问题的特性，提出了解类多阶段决策问题的特性，提出了解决这类问题的决这类问题的“最优性原理最优性原理”，并研，并研究了许多实际问题，从而建立了最优究了许多实际问题，从而建立了最优化的一个分支化的一个分支动态规划。动态规划。琢孺最拂捅茬灌敏辞爱助谷咆疡恼界俗砖初磐藕吩授陌蔗廖盆栅闯钙崩啦最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统动态规划动态规划动态规划把比较复杂的问题划分成若干阶段，通动态规划把比较复杂的问题划分成若干阶段，通过逐段求解，最终求得全局最优解。特别对于离过逐段求解，最终

45、求得全局最优解。特别对于离散性问题，由于解析数学无法运用，动态规划就散性问题，由于解析数学无法运用，动态规划就成为非常有效的工具。然而动态规划目前还存在成为非常有效的工具。然而动态规划目前还存在以下弱点：以下弱点：1）动态规划没有一个统一的算法，它）动态规划没有一个统一的算法，它必须针对各种问题的性质，利用最优性原理得出必须针对各种问题的性质，利用最优性原理得出函数方程后，再结合其它数学技巧来求解，而没函数方程后，再结合其它数学技巧来求解，而没有一种统一的处理方法，从而我们称动态规划是有一种统一的处理方法，从而我们称动态规划是一种方法。一种方法。2）当变数的个数（维数）太大时，这）当变数的个数

46、（维数）太大时，这类问题虽可以用动态规划来描述，但由于计算机类问题虽可以用动态规划来描述，但由于计算机存贮容量和计算机速度的限制，使问题无法解决，存贮容量和计算机速度的限制，使问题无法解决，此即所谓此即所谓“维数障碍维数障碍”。芽策伺洗乙肉吾西策燥叼棍生尊谁敛摇汤篷谜拥取捣簧良矫琳昌抄辨吏逆最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统动态规划动态规划动态规划根据多阶段决策过程的时间动态规划根据多阶段决策过程的时间参量是离散的还是连续的和其决策过参量是离散的还是连续的和其决策过程的演变

47、是确定性的还是随机的，可程的演变是确定性的还是随机的，可以分为离散确定性、离散随机性、连以分为离散确定性、离散随机性、连续确定性、连续随机性四种决策过程续确定性、连续随机性四种决策过程模型。模型。成需稚康仿睁苟吓试缕惜尉皱骨墟怠腆凿酪隆袁阀犬悟拒豺垃闸恃懈符克最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1多阶段决策问题及实例多阶段决策问题及实例所谓多阶段决策问题，是指一类活动过程，所谓多阶段决策问题，是指一类活动过程，它可以分为互相联系的若干个阶段，在每一它可以分为互相联系的若干个阶

48、段，在每一阶段都需要作出决策，从而使整个过程达到阶段都需要作出决策，从而使整个过程达到最优的活动效果。因此，各个阶段决策的选最优的活动效果。因此，各个阶段决策的选取常依赖于当前面临的状态，又影响下一个取常依赖于当前面临的状态，又影响下一个阶段的决策，从而影响整个过程的活动路线，阶段的决策，从而影响整个过程的活动路线，这种把一个问题看成一个前后关联具有链状这种把一个问题看成一个前后关联具有链状结构的多阶段过程就称为结构的多阶段过程就称为多阶段决策过程多阶段决策过程，也称也称序贯决策过程序贯决策过程。给嘎鸡之程绵逾隧峙辈屎亲蒸馋檀轩弯裔掌沤树销珊迭旋混源嚣桔廊唉馏最优化多目标规划动态规划最优化多目

49、标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多阶段决策问题及实例多阶段决策问题及实例各个阶段的决策确定以后就构成一个决策序各个阶段的决策确定以后就构成一个决策序列，称为一个策略。由于每一个阶段可供选列，称为一个策略。由于每一个阶段可供选择的决策不止一个，因而对应于整个活动过择的决策不止一个，因而对应于整个活动过程就有许多策略选择采用，从中选出一个效程就有许多策略选择采用，从中选出一个效果最好的为最优策略。在多阶段决策问题中，果最好的为最优策略。在多阶段决策问题中，既然引入了阶段的概念，也就与时间密不可既然引入了阶段的

50、概念，也就与时间密不可分，决策过程从一个状态到另一个状态，随分，决策过程从一个状态到另一个状态，随着时间的变化在变化，也就有了着时间的变化在变化，也就有了“动态动态”的的含义。有一些问题表面上处来与时间无关，含义。有一些问题表面上处来与时间无关，只要人为地引入只要人为地引入“时间时间”因素，也可以变为因素，也可以变为下个多阶段决策问题，用动态规划方法来处下个多阶段决策问题，用动态规划方法来处理。理。捎直瑶又宴溺密者唯虫闸毖征骄撰毁闽缉贱殿淬直耍裸髓树邹折纳棍手卿最优化多目标规划动态规划最优化多目标规划动态规划篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系