多目标决策方法课件

1、多目标决策方法1第1页，共50页。1 分量加权和方法 考虑多目标规划： 其中可行集 假定多目标函数 中的各个分量fi(x),(1jp)具有相同的度量单位，那就可以按照一定的规则加权后，再按某种方式求和，构成评价函数。然后，再对评价函数求单目标极小化。对于权系数的不同处理和求和方式的不同，可有下列不同方法。2第2页，共50页。1.1 线性加权和法 分别给多目标函数F(x)的第j个分量fj(x)赋以权系数 , 作线性加权和评价函数： 把求解多目标问题(P0)转化成求解单目标问题(P1): 3第3页，共50页。 s.t. xX只要可行集X是凸集，目标函数fj(x)都是X上的凸函数(1j0);如果对于

2、给定的权系数 ,问题（P1）的最优解x*(w)是唯一解，那么x*(w)一定是问题(P0)的非劣解；或者给它的权系数 ,那么问题(P1)的最优解x*(w)也一定是问题(P0）的非劣解。4第4页，共50页。 例1 求解 这里：f1(x)=(x1-1)2+(x2-1)2 f2(x)=(x1-2)2+(x2-3)2 f3(x)=(x1-4)2+(x2-2)2 X=xR2/x1+2x210，x24，x10，x20 X是凸集，f1(x),f2(x),f3(x)都是X上的凸函数。5第5页，共50页。 定义权系数wi0(j=1,2,3), w1+w2+w3=1. 构造评价函数 求解单目标最优目标问题： 显然，

3、对于不同的权系数，最优解x*(w)是不同的，但是它们都是原多目标问题的非劣解，下面给出几组权系数及其对应的最优解（表1）.6第6页，共50页。 可以证明，这个问题的全部非劣解为： 其中： w=(w1,w2,w3)0序w=(w1,w2,w3)X(w)=(x1,x2)F1=(f1,f2,f3)12345(1, 0, 0)(0, 1, 0)(0, 0, 1)(1/3, 1/3, 1/3)(3/6, 2/6, 1/6)(1, 1)(2, 3)(4, 2)(7/3, 2)(11/6, 11/6)(0, 5, 10)(5, 0, 5 )(10, 5, 0)(25/9, 10/9, 25/9)(25/18,

4、 25/18, 85/18)表1 线性加权法的最优解7第7页，共50页。1.2 平方加权和法 先求各分量的最优值 分别赋以权系数wj ,再作平方加权和评价函数： 8第8页，共50页。1.3 一法 先对P个分量fj(x)求极小化 , 假设得到P个相应的极小点xj ，然后把这个P个极小点分别依次代入各个目标函数，就能得到P2个值。 然后，作线性方程组 其中是待定常数，由此可以解出权系数 9第9页，共50页。例2 用法求本节例1的权系数。 从表1可知，3个单目标分量单独求极小化，所得3个极小点是：， 3个极小点依次代入3个目标函数后，可以构造线性方程组如下： 不难解出，这个方程组有唯一解：， ， ，

5、 ， 其相应的线性加权和问题（P1）的最优解为 ，它也是多目标问题（P0）的非劣解，这时 。10第10页，共50页。1.4 统计加权和法 这是用统计方法处理权系数，同时进行方案比较的方法，1976年同B. A. By等人提出。首先，由l个老手（专家）各自独立地提出一个权系数方案（见表3.2所示），所以这个方法又称“老手法”。权系数老 手w1w2wjwp1w11w12w13w1pkwk1wk2wk3wkplwl1wl2wljw1p均 值表3.2 权系数方案11第11页，共50页。 在对在均值偏差太大的权系数进行适当协商和调整之后，求出各个权系数wj的平均值： 然后构造统计加权和评价函数: 因为这

6、时把权系数wj看成是一个随机数，因此在比较两个方案x1和x2的优劣时，不能直接比较 和 的大小，而只能按统计方法进行比较，例如利用假设检验的方法来确定不同方案的优劣。12第12页，共50页。1.5 变动权系数法 让线性加权和评价函数 中的各权系数wj(1jp)按一定规则变动，再求解问题（P1），就能得到多目标决策问题（P0）的全部非劣解。例3 求解双目标决策问题：13第13页，共50页。 作评价函数 求解 令 ，得 最优解为： 当w从1变动到5，x*由0变到2， 当w从1/5变动到0，x*由2变到+，但是这些解不可行，不予考虑。 所以这个例子的非劣解集是X*=0，2。 但是，变动权系数法对于较

7、大的n和p,以及复杂的分量函数，求解是很困难的，怎样不断变动权系数还是一个问题。14第14页，共50页。2 确定加权系数的方法2.1 法 考虑多目标数学规划问题：其中X=x|gi(x)0, 1im, xRn，法的核心是以理想点P*为标准来确定各目标的权系数。15第15页，共50页。1双目标决策问题（p=2） 先依次求解单目标最优化问题：分别得到最优解x1和x2； 相对应的目标函数值为：16第16页，共50页。 目标空间中的几何图形见图3.3所示。图3.3 法几何说明17第17页，共50页。 记理想点 求解单目标最优化问题 设其最优解为x0，记 。18第18页，共50页。 则从几何意义上易见，F

8、0恰是以理想点F*的圆心所作圆与目标集F(X)相切的切点，连接F*与F0两点，直线F0F*的斜率为： 设与直线F0F*垂直的直线方程为：1f1+2f2= （1） 其中 0i2） 设 （i=1, 2, , P） 记理想点 ，并假定F*不在目标集F(X)中，求解单目标最优化问题： 设其最优解为x0，目标函数21第21页，共50页。 在P维空间中，连接F0和F*两点的联线方程为： 其方向向量为：易见 。所以， 与方向相同。22第22页，共50页。 在P维空间上作超平面 ，使其法向量恰为0，而这个超平面方程的法向量为1，2，P，所以有： （k=1, 2, , P） 而且满足 这样求出的k就是目标fk的

9、权系数，（k=1, 2, , P）23第23页，共50页。2.2 环比评分法 假定多目标决策问题共有P个目标f1, f2, , fP。先把目标依次一对一对进行比较，先确定两个目标之间重要性的比率。等全部对比好之后，再以最末一个目标当作1，循序向上环比，算出全部目标间重要性比率，最后再算出权系数。24第24页，共50页。 例 一个多目标决策问题有6个目标，目标间的比率及对应权系数如表3.3所示表3.3 环比评分表 其中f1的权系数 ，其它依此类推。目 标两个之间比率 六个之间比率权 系 数f127.500.4236f213.750.2143f333.750.2143f451.250.0714f5

10、0.250.250.0143f61 1.000.0571=17.50=1.0025第25页，共50页。 2.3 二项系数加权法 设多目标决策问题共有P个目标f1, f2, , fP。假定经过专家组评定和比较，已经定性地给这P个目标排列了一个重要性的优先序，不失一般性，不妨记为： 我们可按对称方式，将上列优先序重新调整，使得最中间位置的目标最重要，同时重要性分别向两边递减。 当P=2K时，排序为： 当P=2K+1时，排序为：26第26页，共50页。 当我们对这P个决策目标很不熟悉，缺乏确定优先权的经验时，可以直接采用二项式展开的各项系数作为这P个目标的权系数。按照上述从左向右的优先序排列分配给相

11、应的目标。由于共有P个目标，所以宜采用P-1次幂的二项展开式： 展开式中，共有P项系数，从左向右，它们依次是：1， ， ， ，1。 若在二项展开式中令b=1，则有：27第27页，共50页。 所以，可以如下定义P个目标的权系数 （1）当P=2K+1时，令 ， ， 。 （2）当P=2K时，令 ， ， 。 不难看出，这样定义的权系数满足条件：28第28页，共50页。 这种二项系数加权法特别适用于决策者毫无赋权经验的问题，而且适宜于计算机求解。而且，当目标个数P很大时，各个目标在给出的重要性排序下，其对决策者所起作用（重要程度）大小的分布可看成具有某种概率分布的随机变量分布；由于各自的重要程度受到大量

12、微小的、独立的因素影响的结果，因此按照概率论中心极限定理，这种分布近似服从正态分布，而二项式系数的大小正好与此吻合。所以，二项系数加权法是比较接近实际的。29第29页，共50页。 2.4 倒数法 假定多目标决策问题的P个目标都是求最大值，而且 （k=1, 2, , P）。这里： （k=1, 2, , P）如果构造“线性加权和”评价函数 ，则可以定义这P个目标的加权系数为： （k=1, 2, , P）30第30页，共50页。 必须指出，“倒数法”于1971年提出来时，加权系数定义为：（k=1, 2, , P） 这样定义加权系数，有时候会得出错误结果。下面给出2个反例。 反例1 求解 这里：可行集

13、X由下列约束条件构成： 0 x118, x22, x1-x2-131第31页，共50页。 求单目标最优化问题： ，得最优解x1=(1, 2)， 。 ，得最优解x2=(1, 2)， 。 显然，多目标问题的最优解x*就是(1, 2)，即 x*=（x1，x2）=(1, 2), F*=( , )=(-5, -4)。32第32页，共50页。 但是，如果用“线性加权和”法来求解这个问题，则令： ， 。则U(x)=1f1(x)+2f2(x) 求解 ，得x*=(18, 19)，相应的F*=(-56, -55)。 这个结果显然是错误的。33第33页，共50页。 反例2 求解： 其中：X=x|3x1+x250,

14、x10, x20 求解单目标最优化问题： ，得最优解x1=(0, 25)， 。 ，得最优解x2=(0, 50)， 。34第34页，共50页。 再令： ， 。 用“线性加权和”法求解： 这个线性规划问题无解（最优解无界）。但是这个结论显然也是错误的，因为各个单目标规划都存在最优解时，那么不论用什么方法，至少应该找到多目标规划的一个有效解。换言之，这个问题因为2个单目标规划都存在最优解，所以求解“线性加权和”问题，至少存在一个最优解，它就是原多目标问题的有效解。35第35页，共50页。 原因分析 分析这2个反例产生错误的原因，都是因为所求出的 和 是负值，而f1(x)和f2(x)中所有系数也都是负

15、值。因此，作“线性加权和”评价函数时，U(x)中的系数就都变成了正值。对线性函数而言，这些系数恰是该函数梯度的各分量。因此，由于 和 的负值，改变了系数符号，因而也就改变了梯度的方向。于是，求最大值问题变成了求最小值问题，这是导致错误的根本原因。36第36页，共50页。 如果采用“线性加权和”法构造评价函数时，定义加权系数k= ，就能防止发生上述错误。 反例1中，令 ， 。 求解 ，得到最优解x*=(1, 2)，目标值向量F*=(-5, -4)，这个结果是正确的。37第37页，共50页。 反例2中，令 求解 ，得到最优解x*= ，目标值向量F*= ，这也就是原多目标规划的有效解。38第38页，

16、共50页。3 分量最优化方法3.1 主要目标法 从多目标函数F(x)的P个分量中选出一个最重要的fs(x)作为主要目标。同时，对于其余P-1个分量fj(x)（1jP, js）估计出其上限和下限。（1jP，js） 这样就把多目标问题转化成求解单目标最优化问题：39第39页，共50页。3.2 恰当等约束法（PEC法） PEC法于1976年由J. G. Lin提出。 从多目标函数F(x)的P个分量中选定一个fs(x)作为目标，同时，对其它P-1个分量恰当地选取一个相应的常数Cj，使fj(x)=Cj，（1jP，js）才可能是原多目标问题的非劣解。 具体求解时，每一步都要按照一些判别条件，逐步去掉一些劣

17、解，最后留下非劣解集。40第40页，共50页。 3.3 分量轮换法 分量轮换法于1971年由R. L. Fox提出，又称“协调研究法”。 首先对多目标函数F(x)的P个分量fj(x)分别估计其上限 （1jP），于是有： （1jP） 然后，我们构造P个单目标最优化问题： （k=1, 2, , P）41第41页，共50页。 这就是把F(x)中的P个分量轮流取其中一个作目标函数，其余P-1个分量进入约束条件，构成单目标最优化问题。 依次求解这P个单目标最优化问题，得到最优解 （k=1, 2, , P）。假定开始时，这些上限值 （1kP）选取得当，求出的 就是原多目标决策问题的非渐解，所有 值能为决策

18、者提供很多有用的信息。42第42页，共50页。3.4 恰当不等式约束法 从多目标函数F(x)的P个分量中选择一个合适的作为目标函数，为方便起见，不妨就选第一个，即f1(x)。同时，对于其余的P-1个分量恰当地选取一个常数Cj，使得fj(x)Cj，j=2, 3, , P），然后求解单目标问题。 只要常数Cj取得恰当，（j=2, 3, , P）这样求出的最优解x*(C)就是原多目标决策问题的非劣解。43第43页，共50页。 例1 求解： 其中：44第44页，共50页。 解 构造单目标最优化问题： 应用Kuhn-Tucker最优性必要条件，可以求出最优解x*(C)，而且只要C选取“恰当”它也就是原多

19、目标问题的非劣解。 。 要使x*(C2)是非劣解，C2的“恰当”范围是1，4。45第45页，共50页。 最优目标值向量为： 假定一开始选取C2=1，单目标问题是： 那么它的最优解恰是x*=0，F*=(1, 16)，这是原多目标问题的非劣解。46第46页，共50页。例2 求解 其中：47第47页，共50页。 构造单目标最优化问题： 应用Kuhn-Tucker条件求解这个问题，可得最优解为：48第48页，共50页。 其中C2、C3必须满足条件：2C2-C30，C3-C20 只要C2、C3选取得“恰当”，x*(C)就是原多目标决策问题的非劣解。 例如，下面给出了一些“恰当”非劣解： C2=1，C3=

20、2 x*=(0, 1) F*=(10, 1, 2) C2=1.5，C3=2 x*=(1, 0.5) F*=(6.25, 1.5, 2) C2=2，C3=3 x*=(1, 1) F*=(5, 2, 3)49第49页，共50页。1、不是井里没有水，而是你挖的不够深。不是成功来得慢，而是你努力的不够多。2、孤单一人的时间使自己变得优秀，给来的人一个惊喜，也给自己一个好的交代。3、命运给你一个比别人低的起点是想告诉你，让你用你的一生去奋斗出一个绝地反击的故事，所以有什么理由不努力!4、心中没有过分的贪求，自然苦就少。口里不说多余的话，自然祸就少。腹内的食物能减少，自然病就少。思绪中没有过分欲，自然忧就

21、少。大悲是无泪的，同样大悟无言。缘来尽量要惜，缘尽就放。人生本来就空，对人家笑笑，对自己笑笑，笑着看天下，看日出日落，花谢花开，岂不自在，哪里来的尘埃!25、你不能拼爹的时候，你就只能去拼命！26、如果人生的旅程上没有障碍，人还有什么可做的呢。27、我们无法选择自己的出身，可是我们的未来是自己去改变的。励志名言：比别人多一点执着，你就会创造奇迹28、伟人之所以伟大，是因为他与别人共处逆境时，别人失去了信心，他却下决心实现自己的目标。29、人生就像一道漫长的阶梯，任何人也无法逆向而行，只能在急促而繁忙的进程中，偶尔转过头来，回望自己留下的蹒跚脚印。30、时间，带不走真正的朋友；岁月，留不住虚幻的

22、拥有。时光转换，体会到缘分善变；平淡无语，感受了人情冷暖。有心的人，不管你在与不在，都会惦念；无心的情，无论你好与不好，只是漠然。走过一段路，总能有一次领悟；经历一些事，才能看清一些人。31、我们无法选择自己的出身，可是我们的未来是自己去改变的。32、命好不如习惯好。养成好习惯，一辈子受用不尽。33、比别人多一点执着，你就会创造奇迹。50、想像力比知识更重要。不是无知，而是对无知的无知，才是知的死亡。51、对于最有能力的领航人风浪总是格外的汹涌。52、思想如钻子，必须集中在一点钻下去才有力量。53、年少时，梦想在心中激扬迸进，势不可挡，只是我们还没学会去战斗。经过一番努力，我们终于学会了战斗，

23、却已没有了拼搏的勇气。因此，我们转向自身，攻击自己，成为自己最大的敌人。54、最伟大的思想和行动往往需要最微不足道的开始。55、不积小流无以成江海，不积跬步无以至千里。56、远大抱负始于高中，辉煌人生起于今日。57、理想的路总是为有信心的人预备着。58、抱最大的希望，为最大的努力，做最坏的打算。59、世上除了生死，都是小事。从今天开始，每天微笑吧。60、一勤天下无难事，一懒天下皆难事。61、在清醒中孤独，总好过于在喧嚣人群中寂寞。62、心里的感觉总会是这样，你越期待的会越行越远，你越在乎的对你的伤害越大。63、彩虹风雨后，成功细节中。64、有些事你是绕不过去的，你现在逃避，你以后就会话十倍的精

24、力去面对。65、只要有信心，就能在信念中行走。66、每天告诉自己一次，我真的很不错。67、心中有理想 再累也快乐68、发光并非太阳的专利，你也可以发光。69、任何山都可以移动，只要把沙土一卡车一卡车运走即可。70、当你的希望一个个落空，你也要坚定，要沉着！71、生命太过短暂，今天放弃了明天不一定能得到。72、只要路是对的，就不怕路远。73、如果一个人爱你、特别在乎你，有一个表现是他还是有点怕你。74、先知三日，富贵十年。付诸行动，你就会得到力量。75、爱的力量大到可以使人忘记一切，却又小到连一粒嫉妒的沙石也不能容纳。1、这世上，没有谁活得比谁容易，只是有人在呼天抢地，有人在默默努力。2、当热诚

25、变成习惯，恐惧和忧虑即无处容身。缺乏热诚的人也没有明确的目标。热诚使想象的轮子转动。一个人缺乏热诚就象汽车没有汽油。善于安排玩乐和工作，两者保持热诚，就是最快乐的人。热诚使平凡的话题变得生动。3、起点低怕什么，大不了加倍努力。人生就像一场马拉松比赛，拼的不是起点，而是坚持的耐力和成长的速度。只要努力不止，进步也会不止。4、如果你不相信努力和时光，那么时光第一个就会辜负你。不要去否定你的过去，也不要用你的过去牵扯你的未来。不是因为有希望才去努力，而是努力了，才能看到希望。5、人生每天都要笑，生活的下一秒发生什么，我们谁也不知道。所以，放下心里的纠结，放下脑中的烦恼，放下生活的不愉快，活在当下。人

26、生喜怒哀乐，百般形态，不如在心里全部淡然处之，轻轻一笑，让心更自在，生命更恒久。积极者相信只有推动自己才能推动世界，只要推动自己就能推动世界。6、人性本善，纯如清溪流水凝露莹烁。欲望与情绪如风沙袭扰，把原本如天空旷蔚蓝的心蒙蔽。但我知道，每个人的心灵深处，不管乌云密布还是阴淤苍茫，但依然有一道彩虹，亮丽于心中某处。7、每个人的心里，都藏着一个了不起的自己，只要你不颓废，不消极，一直悄悄酝酿着乐观，培养着豁达，坚持着善良，只要在路上，就没有到达不了的远方！8、不要活在别人眼中，更不要活在别人嘴中。世界不会因为你的抱怨不满而为你改变，你能做到的只有改变你自己！9、欲戴王冠，必承其重。哪有什么好命天赐，不都是一路披荆斩棘才换来的。10、放手如拔牙。牙被拔掉的那一刻，你会觉得解脱。但舌头总会不由自主地往那个空空的牙洞里舔，一天数次。不痛了不代表你能完全无视，留下的那个空缺永远都在，偶尔甚至会异常挂念。适应是需要时间的，但牙总是要拔，因为太痛，所