多目标决策方法.ppt

1,多目标决策方法,2,1 分量加权和方法,考虑多目标规划： 其中可行集 假定多目标函数 中的各个分量fi(x),[(1≤j≤p)具有相同的度量单位，那就可以按照一定的规则加权后，再按某种方式求和，构成评价函数然后，再对评价函数求单目标极小化对于权系数的不同处理和求和方式的不同，可有下列不同方法3,1.1 线性加权和法,分别给多目标函数F(x)的第j个分量fj(x)赋以权系数 , 作线性加权和评价函数： 把求解多目标问题(P0)转化成求解单目标问题(P1):,,,,4,s.t. xX只要可行集X是凸集，目标函数fj(x)都是X上的凸函数(1≤j≤0);如果对于给定的权系数 ,问题（P1）的最优解x*(w)是唯一解，那么x*(w)一定是问题(P0)的非劣解；或者给它的权系数 ,那么问题(P1)的最优解x*(w)也一定是问题(P0）的非劣解5,[例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={x∈R2/x1+2x2≤10，x2≤4，x1≥0，x2≥0} X是凸集，f1(x),f2(x),f3(x)都是X上的凸函数。

6,定义权系数wi≥0(j=1,2,3), w1+w2+w3=1. 构造评价函数 求解单目标最优目标问题： 显然，对于不同的权系数，最优解x*(w)是不同的，但是它们都是原多目标问题的非劣解，下面给出几组权系数及其对应的最优解（表1）.,,,7,可以证明，这个问题的全部非劣解为： 其中： w=(w1,w2,w3)≥0,表1 线性加权法的最优解,,,8,1.2 平方加权和法,先求各分量的最优值 分别赋以权系数wj ,再作平方加权和评价函数：,,,,,9,1.3 α一法,先对P个分量fj(x)求极小化 , 假设得到P个相应的极小点xj ，然后把这个P个极小点分别依次代入各个目标函数，就能得到P2个值 然后，作线性方程组 其中是待定常数，由此可以解出权系数,,,,,,10,[例2] 用法求本节例1的权系数 从表1可知，3个单目标分量单独求极小化，所得3个极小点是： ， ， 3个极小点依次代入3个目标函数后，可以构造线性方程组如下： 不难解出，这个方程组有唯一解： ， ， ， ， 其相应的线性加权和问题（P1）的最优解为 ，它也是多目标问题（P0）的非劣解，这时 。

11,1.4 统计加权和法,这是用统计方法处理权系数，同时进行方案比较的方法，1976年同B. A. ByНКИН等人提出首先，由l个老手（专家）各自独立地提出一个权系数方案（见表3.2所示），所以这个方法又称“老手法”表3.2 权系数方案,12,在对在均值偏差太大的权系数进行适当协商和调整之后，求出各个权系数wj的平均值： 然后构造统计加权和评价函数: 因为这时把权系数wj看成是一个随机数，因此在比较两个方案x1和x2的优劣时，不能直接比较 和 的大小，而只能按统计方法进行比较，例如利用假设检验的方法来确定不同方案的优劣13,1.5 变动权系数法,让线性加权和评价函数 中的各权系数wj(1jp)按一定规则变动，再求解问题（P1），就能得到多目标决策问题（P0）的全部非劣解 [例3] 求解双目标决策问题：,,,14,作评价函数 求解 令 ，得 最优解为： 当w从1变动到5，x*由0变到2， 当w从1/5变动到0，x*由2变到+∞，但是这些解不可行，不予考虑 所以这个例子的非劣解集是X*=[0，2] 但是，变动权系数法对于较大的n和p,以及复杂的分量函数，求解是很困难的，怎样不断变动权系数还是一个问题。

15,2 确定加权系数的方法,2.1 法 考虑多目标数学规划问题： 其中X={x|gi(x)0, 1im, xRn}，法的核心是以理想点P*为标准来确定各目标的权系数16,[1]．双目标决策问题（p=2） 先依次求解单目标最优化问题： 分别得到最优解x1和x2； 相对应的目标函数值为：,,,,17,目标空间中的几何图形见图3.3所示 图3.3 法几何说明,18,记理想点 求解单目标最优化问题 设其最优解为x0，记 19,则从几何意义上易见，F0恰是以理想点F*的圆心所作圆与目标集F(X)相切的切点，连接F*与F0两点，直线F0F*的斜率为： 设与直线F0F*垂直的直线方程为： 1f1+2f2= （1） 其中 0i1，（i=1, 2），1+2=1 （2）,,20,由（1）式有： 由两条垂直直线的斜率关系有： （3） 联立求解（2）、（3），可得： 而且满足1+2=1 1，2就是目标f1和f2的权系数21,[2]．多目标决策问题（P2） 设 （i=1, 2, …, P） 记理想点 ，并假定F*不在目标集F(X)中，求解单目标最优化问题： 设其最优解为x0，目标函数,,,,,22,在P维空间中，连接F0和F*两点的联线方程为： 其方向向量为： 易见 。

所以， 与方向相同23,在P维空间上作超平面 ，使其法向量恰为0，而这个超平面方程的法向量为1，2，…P，所以有： （k=1, 2, …, P） 而且满足 这样求出的k就是目标fk的权系数，（k=1, 2, …, P）,,,,24,2.2 环比评分法,假定多目标决策问题共有P个目标f1, f2, …, fP先把目标依次一对一对进行比较，先确定两个目标之间重要性的比率等全部对比好之后，再以最末一个目标当作1，循序向上环比，算出全部目标间重要性比率，最后再算出权系数25,[例] 一个多目标决策问题有6个目标，目标间的比率及对应权系数如表3.3所示 表3.3 环比评分表 其中f1的权系数 ，其它依此类推26,2.3 二项系数加权法,设多目标决策问题共有P个目标f1, f2, …, fP假定经过专家组评定和比较，已经定性地给这P个目标排列了一个重要性的优先序，不失一般性，不妨记为： 我们可按对称方式，将上列优先序重新调整，使得最中间位置的目标最重要，同时重要性分别向两边递减 当P=2K时，排序为： 当P=2K+1时，排序为：,,,,27,当我们对这P个决策目标很不熟悉，缺乏确定优先权的经验时，可以直接采用二项式展开的各项系数作为这P个目标的权系数。

按照上述从左向右的优先序排列分配给相应的目标由于共有P个目标，所以宜采用P-1次幂的二项展开式： 展开式中，共有P项系数，从左向右，它们依次是：1， ， ，…， ，1 若在二项展开式中令b=1，则有：,,,,,,28,所以，可以如下定义P个目标的权系数 （1）当P=2K+1时，令 ， ， （2）当P=2K时，令 ， ， 不难看出，这样定义的权系数满足条件：,,,,,,,,29,这种二项系数加权法特别适用于决策者毫无赋权经验的问题，而且适宜于计算机求解而且，当目标个数P很大时，各个目标在给出的重要性排序下，其对决策者所起作用（重要程度）大小的分布可看成具有某种概率分布的随机变量分布；由于各自的重要程度受到大量微小的、独立的因素影响的结果，因此按照概率论中心极限定理，这种分布近似服从正态分布，而二项式系数的大小正好与此吻合所以，二项系数加权法是比较接近实际的30,2.4 倒数法,假定多目标决策问题的P个目标都是求最大值，而且 （k=1, 2, …, P）这里： （k=1, 2, …, P） 如果构造“线性加权和”评价函数 ， 则可以定义这P个目标的加权系数为： （k=1, 2, …, P）,,,,,31,必须指出，“倒数法”于1971年提出来时，加权系数定义为： （k=1, 2, …, P） 这样定义加权系数，有时候会得出错误结果。

下面给出2个反例 [反例1] 求解 这里：可行集X由下列约束条件构成： {0x118, x22, x1-x2-1},,,32,求单目标最优化问题： ，得最优解x1=(1, 2)， ，得最优解x2=(1, 2)， 显然，多目标问题的最优解x*就是(1, 2)，即 x*=（x1，x2）=(1, 2), F*=( , )=(-5, -4)33,但是，如果用“线性加权和”法来求解这个问题，则令： ， 则 U(x)=1f1(x)+2f2(x) 求解 ，得x*=(18, 19)，相应的 F*=(-56, -55) 这个结果显然是错误的34,[反例2] 求解： 其中：X={x|3x1+x250, x10, x20} 求解单目标最优化问题： ，得最优解x1=(0, 25)， ，得最优解x2=(0, 50)， 35,再令： ， 用“线性加权和”法求解： 这个线性规划问题无解（最优解无界）但是这个结论显然也是错误的，因为各个单目标规划都存在最优解时，那么不论用什么方法，至少应该找到多目标规划的一个有效解换言之，这个问题因为2个单目标规划都存在最优解，所以求解“线性加权和”问题，至少存在一个最优解，它就是原多目标问题的有效解。

36,[原因分析] 分析这2个反例产生错误的原因，都是因为所求出的 和 是负值，而f1(x)和f2(x)中所有系数也都是负值因此，作“线性加权和”评价函数时，U(x)中的系数就都变成了正值对线性函数而言，这些系数恰是该函数梯度的各分量因此，由于 和 的负值，改变了系数符号，因而也就改变了梯度的方向于是，求最大值问题变成了求最小值问题，这是导致错误的根本原因37,如果采用“线性加权和”法构造评价函数时，定义加权系数k= ，就能防止发生上述错误 反例1中，令 ， 求解 ，得到最优解x*=(1, 2)，目标值向量F*=(-5, -4)，这个结果是正确的38,反例2中，令 求解 ，得到最优解x*= ，目标值向量F*= ，这也就是原多目标规划的有效解39,3 分量最优化方法,3.1 主要目标法 从多目标函数F(x)的P个分量中选出一个最重要的fs(x)作为主要目标同时，对于其余P-1个分量fj(x)（1jP, js）估计出其上限和下限 （1jP，js） 这样就把多目标问题转化成求解单目标最优化问题：,,,40,3.2 恰当等约束法（PEC法） PEC法于1976年由J. G. Lin提出。

从多目标函数F(x)的P个分量中选定一个fs(x)作为目标，同时，对其它P-1个分量恰当地选取一个相应的常数Cj，使fj(x)=Cj，（1jP，js）才可能是原多目标问题的非劣解 具体求解时，每一步都要按照一些判别条件，逐步去掉一些劣解，最后留下非劣解集41,3.3 分量轮换法 分量轮换法于1971年由R. L. Fox提出，又称“协调研究法” 首先对多目标函数F(x)的P个分量fj(x)分别估计其上限 （1jP），于是有： （1jP） 然后，我们构造P个单目标最优化问题： （k=1, 2, …, P）,,,,42,这就是把F(x)中的P个分量轮流取其中一个作目标函数，其余P-1个分量进入约束条件，构成单目标最优化问题 依次求解这P个单目标最优化问题，得到最优解 （k=1, 2, …, P）假定开始时，这些上限值 （1kP）选取得当，求出的 就是原多目标决策问题的非渐解，所有 值能为决策者提供很多有用的信息。