多目标决策简介3127.pdf

《多目标决策简介3127.pdf》由会员分享，可在线阅读，更多相关《多目标决策简介3127.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十一章多目标决策(Multi-objective Decision-making)主要参考文献 68,111 11.1 序言 MA：评估与排序 MCDP MO：数学规划 一、问题的数学表达 N 个决策变量=,n 个目标函数(x)=(x),(x),(x)m个约束条件x即:(x)0 k=1,m x0(1)不失一般性，MODP可表示成：P1 Max f1(x),f2(x),fn(x)s.t.x 这是向量优化问题，要在可行域 X 中找一，使各目标值到达极大。通常xS并不存在，只能找出一集非劣解(2)假如能找到价值函数 v(f1(x),f2(x),fn(x)如此MODP可表示成：P2 Max v(f1

2、(x),f2(x),fn(x)s.t.x 这是纯量优化问题，困难在于 v 如何确定。二、最优调和解(Best Compromise Solution)P3 DR(f1(x),f2(x),fn(x)s.t.x 即根据适当的 Decision Rule 在 X 中寻找 BCS 常用的 Decision Rule:max V maxEU min(f-)求 BCS 必须引入决策人的偏好 三、决策人偏好信息的获取方式 1.在优化之前，事先一次提供全部偏好信息 如：效用函数法，字典式法，满意决策，目的规如此 2.在优化过程中：逐步索取偏好信息 如：STEM SEMOP Geoffrion,SWT 3.在优

3、化之后：事后索取偏好，由决策人在非劣解集中选择 i，算法复杂，决策人难理解，ii,计算量大，iii,决策人不易判断各种方式的利弊比拟 黄庆来111的分类表:11.2 目的规划法 适用场合：决策人愿意并且能用 优先级 P(Preemptive priority)权 W (Weight)目的f (Goal)来表示偏好 理想点(Ideal)一、距离测度的选择 =范数 p 的意义和作用 p=1 绝对值范数 p=2 欧几里德范数 p=契比 E 夫范数 在上图中，B、C 点到 A 的距离 f1 f2 AB 间的距离 0 6 6 6 6 6 AC 间的距离 5 4 9 6.4 5.74 5 p 从 1时最大

4、偏差所起作用越来越大，二、目的规划问题的表述 mindf xfp()=|()|wfxfjjjpp1 s.t.x即:gk(x)0 k=1,m x0 三、分类 1.线性目的规划 p=1,gk为线性;x连续;w,f事先给定 2.整数目的规划除x各分量为整数外，均同线性目的规划 (例：人才规划)3.非线性目的规划：p=1，w,f事先给定 fj,gk为非线性，X 为凸集，x连续 4.调和规划和移动理想点法:1 pw 事先给定 f=f*是移动的理想点 5.字典序法 p=1 f=f*P1?P2?PL 6.STEM法 P=f=f*为理想点，权由计算得出 7.SEMOP 目的标定为区间，不是固定点 四、例：某车

5、间生产甲、乙两种产品，产量分别为x1和x2，产品甲每单位需 2 个单位的劳动力和 3 个单位 原料,利润为 2；生产产品乙需 3 个单位劳动力和 1.5 个单位原料,利润为 3。在下一方案期间车间有 12 单劳动力 12单位原料。假定车间主任有如下目标：(1)利润至少为 6 个单位，(2)两种产品产量经尽可能保持x1：x2=3：2，(3)劳动力充分利用 解：按传统的线性规划，使利润最大：max 2x1+3x2 s.t.2x1+3x212 (劳力约束)3x1+1.5x212 (原料约束)x1,x20 用图解法可得x1=3,x2=2 时,利润最大为 12.五、例(续上例)条件中产品甲利润改为 4,

6、其余均不变。车间主任希望改为:最低利润 12 单位(2)产量比例为 1,即x1=x2;(3)充分利用原料 解:新的目标为 4x1+3x212 (最低限度利润)x1-x2=0 (产量比例)3x1+1.5x2=12 (材料充分利用)设定偏差变量d1:利润d2:产量比例d3:原料:劳动力 利用正、负偏差变量可得：min P1d1+P2(d2+d2)+P3d3 s.t.4x1+3x2-d1+d112 (利润目标)x1-x2-d2+d2=0 (产量比例)3x1+1.5x2+d3 =12 (材料充分利用)2x1+3x2+d4 =12 (劳动力约束)此题可以用改良的单纯形法求解(见 pp217-221),也

7、可用图解法求解:解得=(2.4,2.4),d1=d2=d2=d4=0 ,d3=1.2,d4=4.8 11.3 字典序法 第一步，由决策人给出 n，按重要性由高到低排成,第二步，用适当方法估计各属性的偏好(效用或价值)函数(y1),(y2),(yn)第三步，依次求解如下问题，进展筛选 问题 P1 解为 问题 P2 解为 问题 Pj 直到 a)问题 Pj 只有唯一解,如此该解为最优解 b)n 个问题全部解过：决策人用其他准如此从中选择一个方案。11.4 逐步进展法(STEP Method)特点：P=只有最大偏差起作用 属于 Min max 决策规如此 算法步骤 对多目标决策问题 max=Cx s.

8、t.Axb x0 记作 第一步 求解 n 个单目标优化问题 j=1,n 解为得=理想点f*=(,)列出支付表使决策人对取不同的xj*时各目标的值有直观认识f1 f1 fj fn f1*xj*fj*fn*第二步 由=max 求解 min df xf()*s.t.等价于解 min入 s.t.wffxjjj()*j=1,n 0 其中 j=1,n 式中从支付表中获得 解(2)得与 j=1,n 第三步由决策人判断 降低某个太好的目标，下降再修改约束条件，使 Axb x0:=fxl()1-fl fxj()1 j=1,n j 以X2取代X1，令=0 重复第二步 三、优缺点：直观;修改有针对性;fl较难定 1

9、1.5 调和解(Compromise solution)和移动理想点法 一、根本概念(思路)1.调和解 在求解 MODP:时 f*(或f),W,p 要由决策人确定 其中由单调性假设，f=fxj()j=1,n 可以求得 W 可由决策人设定 而 P 如此很难设定 因此，给定权向量 W，定义调和解集 =|x是给定 W 时minx X|()|wfxfjjjpp1的解 它是非劣解的子集,即XWC 2.各目标偏差的标准化 记=minx Xfxj()用使偏差无量纲、归一化，否如此dp量纲、单位的选取有关 二、求解步骤 第一步由决策人估计权 W 第二步fj0=minx Xfxj()f*=maxx Xfxj()

10、第三步构造调和集 求解minx Xdf xfp()*p=1,2,其中ffxffjjjj*()0 ffxffjjjj*()0 第四步 假如能从XWC中找出 BCS，如此完毕 第五步寻找新的理想点 令X2=XWC返回第二步.11.6 SEMOP(多目标问题的序贯解法)一、思路与记号 目的为区间 目的类型 目的表达式 偏差测度 有上界 fxj()fxj()/bj 有下界 fxj()aj/fxj()给定值 fxj()=区间内 ajfxj()bj 区间外 fxj()aj,fxj()bj n 个目标分为两类:：加约束的 r 个目标的下标集合；=JIq J=1,2,n ：X 中的子集，其中的x使jIq,fx

11、j()在标定区间内 求解 min s.t.将解与 j=1,n 送决策人判断 为了向决策人提供必要信息需解(n-r)个辅问题 min s.t.其中,l=1,n-r p 是Jq中第l个元素在 J 中的序号 是 jIq以及 j=p 的fxj()均严格处于标定的目的区间内 二、解题步骤 第一步由决策人确定 r 个应严格限定值域的目标，并给出这 r 个目标的目的区间，这 r 个目标的序号构成集合Iq 第二步 i,解主问题 minSdqjqj Jq s.t.xXq ii,解 n-r 个辅问题 minSdlqjj Jjpq,s.t.xXpq 得出xq与fxjq()j=1,n 和与 j=1,n l=1,n-r

12、 第三步由决策人对第二步结果作判断 基对xq满意如此停止 假如不满意如此 q=q+1 返回第一步 三、优缺点 1.可用于非单调区间 2.容易反映目标间的矛盾关系 3.非线性规划问题求解困难,没有标准化的步骤保证收敛 11.7Geoffrion 法 一、思路 用 Frank-Wolfe 法解线性约束的非线性规划问题 max v(f x()(0)s.t.xX 是在处，以一阶 Taylor 展开线性逼接 v(f x()记作v(x):()v x=v(x0)+(x-x0)(1)求(1)的极大值等价于求解线性规划问题 maxx Xxv x()0Tx (2)令(2)的最优解为，如此 i,假如 xv x()0

13、T(y0-x0)是(2)的最优解，迭代停止；ii,假如xv x()0T(y0-x0)0,如此从x0出发沿y0-x0方向作一维搜索 即求v(x0+(y0-x0)的最优解t0 只要t00 足够小,必有 v(x1)v(x0)式中x1=x0+t0(y0-x0)对，重复上述步骤，可得原问题(0)的最优解 xv x()0虽属未知，但xv x()0=除以,得xjfx()0其中，-j=1,n 二、求解步骤 三、优缺点 1.只要决策者心目中的效用函数确实存在，并能给出各点的边际置换率，不必给出具体的 效用函数值。2.只适用于线性约束的多目标规划 3.每次迭代都有所增加，收敛性有保证 但在实际上所得到的解的优劣取

14、决于决策人提供的局部偏好信息的准确性。11.8 代理值置换法(Surrogate worth Trade-off Method)一、思路：置换率：在某个非劣点处假如要提高某一目标值一个单位，必须使另一目标降低多少，(设 其他目标函数值不变)置换率给出了非常有用的信息:如决策人愿意进展这种置换，说明该方向上有决策人更喜爱的非劣解。二、求解步骤 第一步：产生非劣解的有代表性的子集 任选一种方法去求得非劣解的有代表性的子集。不失一般性，选作为参考目标，构成不等式约束问题:min fxn()(1)s.t.i=1,m j=1,n-1 其中,为了便于比拟，最好选用重要目标或其计量单位是决策人所熟悉的目标作

15、为目标 n。第二步：获得置换信息 在求解(1)时，可以得到 j=1,n-1 其中是(1)的解，是(1)的 Kuhn-Tucker 乘子，就是在x0处的置换率 第三步：了解决策人的偏好 把第二步计算结果递交给决策人，要决策人答复是否愿意进展这种调整，愿意到何种程度，并据以构造代用值函数 j=1,n-1 +10 非常愿意增加njx()0个单位的减去一个单位的fj-10 非常愿意减少njx()0个单位的fn以提高fj一个单位 第四步：寻求最优调和解 当某个x*使=0 j=1,n-1 时,x*为最优调和解.假如在第一步生成的非劣点中不包含x*，可用多元回归法构造代理值函数令wnj()=0 即=0 求解联列方程得 可用这组代入(1)求得x*.内容总结 （1）第十一章多目标决策(Multi-objective Decision-making)主要参考文献 68,111 11.1 序言 MA：评估与排序 MCDP MO：数学规划 一、问题的数学表达 N个决策变量=,（2）生产产品乙需 3 个单位劳动力和 1.5 个单位原料,利润为 3