多目标决策方法.ppt

多目标决策方法 1分量加权和方法 考虑多目标规划 其中可行集假定多目标函数中的各个分量fi x 1 j p 具有相同的度量单位 那就可以按照一定的规则加权后 再按某种方式求和 构成评价函数 然后 再对评价函数求单目标极小化 对于权系数的不同处理和求和方式的不同 可有下列不同方法 1 1线性加权和法 分别给多目标函数F x 的第j个分量fj x 赋以权系数 作线性加权和评价函数 把求解多目标问题 P0 转化成求解单目标问题 P1 s t x X只要可行集X是凸集 目标函数fj x 都是X上的凸函数 1 j 0 如果对于给定的权系数 问题 P1 的最优解x w 是唯一解 那么x w 一定是问题 P0 的非劣解 或者给它的权系数 那么问题 P1 的最优解x w 也一定是问题 P0 的非劣解 例1 求解这里 f1 x x1 1 2 x2 1 2f2 x x1 2 2 x2 3 2f3 x x1 4 2 x2 2 2X x R2 x1 2x2 10 x2 4 x1 0 x2 0 X是凸集 f1 x f2 x f3 x 都是X上的凸函数 定义权系数wi 0 j 1 2 3 w1 w2 w3 1 构造评价函数求解单目标最优目标问题 显然 对于不同的权系数 最优解x w 是不同的 但是它们都是原多目标问题的非劣解 下面给出几组权系数及其对应的最优解 表1 可以证明 这个问题的全部非劣解为 其中 w w1 w2 w3 0 表1线性加权法的最优解 1 2平方加权和法 先求各分量的最优值分别赋以权系数wj 再作平方加权和评价函数 1 3 一法 先对P个分量fj x 求极小化 假设得到P个相应的极小点xj 然后把这个P个极小点分别依次代入各个目标函数 就能得到P2个值 然后 作线性方程组其中 是待定常数 由此可以解出权系数 例2 用 法求本节例1的权系数 从表1可知 3个单目标分量单独求极小化 所得3个极小点是 3个极小点依次代入3个目标函数后 可以构造线性方程组如下 不难解出 这个方程组有唯一解 其相应的线性加权和问题 P1 的最优解为 它也是多目标问题 P0 的非劣解 这时 1 4统计加权和法 这是用统计方法处理权系数 同时进行方案比较的方法 1976年同B A By 等人提出 首先 由l个老手 专家 各自独立地提出一个权系数方案 见表3 2所示 所以这个方法又称 老手法 表3 2权系数方案 在对在均值偏差太大的权系数进行适当协商和调整之后 求出各个权系数wj的平均值 然后构造统计加权和评价函数 因为这时把权系数wj看成是一个随机数 因此在比较两个方案x1和x2的优劣时 不能直接比较和的大小 而只能按统计方法进行比较 例如利用假设检验的方法来确定不同方案的优劣 1 5变动权系数法 让线性加权和评价函数中的各权系数wj 1 j p 按一定规则变动 再求解问题 P1 就能得到多目标决策问题 P0 的全部非劣解 例3 求解双目标决策问题 作评价函数求解令 得最优解为 当w从1变动到5 x 由0变到2 当w从1 5变动到0 x 由2变到 但是这些解不可行 不予考虑 所以这个例子的非劣解集是X 0 2 但是 变动权系数法对于较大的n和p 以及复杂的分量函数 求解是很困难的 怎样不断变动权系数还是一个问题 2确定加权系数的方法 2 1 法考虑多目标数学规划问题 其中X x gi x 0 1 i m x Rn 法的核心是以理想点P 为标准来确定各目标的权系数 1 双目标决策问题 p 2 先依次求解单目标最优化问题 分别得到最优解x1和x2 相对应的目标函数值为 目标空间中的几何图形见图3 3所示 图3 3 法几何说明 记理想点求解单目标最优化问题设其最优解为x0 记 则从几何意义上易见 F0恰是以理想点F 的圆心所作圆与目标集F X 相切的切点 连接F 与F0两点 直线F0F 的斜率为 设与直线F0F 垂直的直线方程为 1f1 2f2 1 其中0 i 1 i 1 2 1 2 1 2 由 1 式有 由两条垂直直线的斜率关系有 3 联立求解 2 3 可得 而且满足 1 2 1 1 2就是目标f1和f2的权系数 2 多目标决策问题 P 2 设 i 1 2 P 记理想点 并假定F 不在目标集F X 中 求解单目标最优化问题 设其最优解为x0 目标函数 在P维空间中 连接F0和F 两点的联线方程为 其方向向量为 易见 所以 与 方向相同 在P维空间上作超平面 使其法向量恰为 0 而这个超平面方程的法向量为 1 2 P 所以有 k 1 2 P 而且满足这样求出的 k就是目标fk的权系数 k 1 2 P 2 2环比评分法 假定多目标决策问题共有P个目标f1 f2 fP 先把目标依次一对一对进行比较 先确定两个目标之间重要性的比率 等全部对比好之后 再以最末一个目标当作1 循序向上环比 算出全部目标间重要性比率 最后再算出权系数 例 一个多目标决策问题有6个目标 目标间的比率及对应权系数如表3 3所示表3 3环比评分表其中f1的权系数 其它依此类推 2 3二项系数加权法 设多目标决策问题共有P个目标f1 f2 fP 假定经过专家组评定和比较 已经定性地给这P个目标排列了一个重要性的优先序 不失一般性 不妨记为 我们可按对称方式 将上列优先序重新调整 使得最中间位置的目标最重要 同时重要性分别向两边递减 当P 2K时 排序为 当P 2K 1时 排序为 当我们对这P个决策目标很不熟悉 缺乏确定优先权的经验时 可以直接采用二项式展开的各项系数作为这P个目标的权系数 按照上述从左向右的优先序排列分配给相应的目标 由于共有P个目标 所以宜采用P 1次幂的二项展开式 展开式中 共有P项系数 从左向右 它们依次是 1 1 若在二项展开式中令b 1 则有 所以 可以如下定义P个目标的权系数 1 当P 2K 1时 令 2 当P 2K时 令 不难看出 这样定义的权系数满足条件 这种二项系数加权法特别适用于决策者毫无赋权经验的问题 而且适宜于计算机求解 而且 当目标个数P很大时 各个目标在给出的重要性排序下 其对决策者所起作用 重要程度 大小的分布可看成具有某种概率分布的随机变量分布 由于各自的重要程度受到大量微小的 独立的因素影响的结果 因此按照概率论中心极限定理 这种分布近似服从正态分布 而二项式系数的大小正好与此吻合 所以 二项系数加权法是比较接近实际的 2 4倒数法 假定多目标决策问题的P个目标都是求最大值 而且 k 1 2 P 这里 k 1 2 P 如果构造 线性加权和 评价函数 则可以定义这P个目标的加权系数为 k 1 2 P 必须指出 倒数法 于1971年提出来时 加权系数定义为 k 1 2 P 这样定义加权系数 有时候会得出错误结果 下面给出2个反例 反例1 求解这里 可行集X由下列约束条件构成 0 x1 18 x2 2 x1 x2 1 求单目标最优化问题 得最优解x1 1 2 得最优解x2 1 2 显然 多目标问题的最优解x 就是 1 2 即x x1 x2 1 2 F 5 4 但是 如果用 线性加权和 法来求解这个问题 则令 则U x 1f1 x 2f2 x 求解 得x 18 19 相应的F 56 55 这个结果显然是错误的 反例2 求解 其中 X x 3x1 x2 50 x1 0 x2 0 求解单目标最优化问题 得最优解x1 0 25 得最优解x2 0 50 再令 用 线性加权和 法求解 这个线性规划问题无解 最优解无界 但是这个结论显然也是错误的 因为各个单目标规划都存在最优解时 那么不论用什么方法 至少应该找到多目标规划的一个有效解 换言之 这个问题因为2个单目标规划都存在最优解 所以求解 线性加权和 问题 至少存在一个最优解 它就是原多目标问题的有效解 原因分析 分析这2个反例产生错误的原因 都是因为所求出的和是负值 而f1 x 和f2 x 中所有系数也都是负值 因此 作 线性加权和 评价函数时 U x 中的系数就都变成了正值 对线性函数而言 这些系数恰是该函数梯度的各分量 因此 由于和的负值 改变了系数符号 因而也就改变了梯度的方向 于是 求最大值问题变成了求最小值问题 这是导致错误的根本原因 如果采用 线性加权和 法构造评价函数时 定义加权系数 k 就能防止发生上述错误 反例1中 令 求解 得到最优解x 1 2 目标值向量F 5 4 这个结果是正确的 反例2中 令求解 得到最优解x 目标值向量F 这也就是原多目标规划的有效解 3分量最优化方法 3 1主要目标法从多目标函数F x 的P个分量中选出一个最重要的fs x 作为主要目标 同时 对于其余P 1个分量fj x 1 j P j s 估计出其上限和下限 1 j P j s 这样就把多目标问题转化成求解单目标最优化问题 3 2恰当等约束法 PEC法 PEC法于1976年由J G Lin提出 从多目标函数F x 的P个分量中选定一个fs x 作为目标 同时 对其它P 1个分量恰当地选取一个相应的常数Cj 使fj x Cj 1 j P j s 才可能是原多目标问题的非劣解 具体求解时 每一步都要按照一些判别条件 逐步去掉一些劣解 最后留下非劣解集 3 3分量轮换法分量轮换法于1971年由R L Fox提出 又称 协调研究法 首先对多目标函数F x 的P个分量fj x 分别估计其上限 1 j P 于是有 1 j P 然后 我们构造P个单目标最优化问题 k 1 2 P 这就是把F x 中的P个分量轮流取其中一个作目标函数 其余P 1个分量进入约束条件 构成单目标最优化问题 依次求解这P个单目标最优化问题 得到最优解 k 1 2 P 假定开始时 这些上限值 1 k P 选取得当 求出的就是原多目标决策问题的非渐解 所有值能为决策者提供很多有用的信息 3 4恰当不等式约束法从多目标函数F x 的P个分量中选择一个合适的作为目标函数 为方便起见 不妨就选第一个 即f1 x 同时 对于其余的P 1个分量恰当地选取一个常数Cj 使得fj x Cj j 2 3 P 然后求解单目标问题 只要常数Cj取得恰当 j 2 3 P 这样求出的最优解x C 就是原多目标决策问题的非劣解 例1 求解 其中 解 构造单目标最优化问题 应用Kuhn Tucker最优性必要条件 可以求出最优解x C 而且只要C选取 恰当 它也就是原多目标问题的非劣解 要使x C2 是非劣解 C2的 恰当 范围是 1 4 最优目标值向量为 假定一开始选取C2 1 单目标问题是 那么它的最优解恰是x