《多目标决策简单概述.doc》由会员分享，可在线阅读，更多相关《多目标决策简单概述.doc（18页珍藏版）》请在三一文库上搜索。
1、第十一章多目标决策(Multi-objective Decisio n-maki ng)主要参考文献68, 111§ 11.1序言MA :评估与排序MCDPMO :数学规划、问题的数学表达N个决策变量=,，,n 个目标函数 ()=(),(),()m个约束条件 三 即：()：0k=1,m0(1) 不失一般性，MODP可表示成：Pi Max (),(),()s.t. 三这是向量优化问题，要在可行域X中找一，使各目标值达到极大。通常并不存在，只能找出一集非劣解 若能找到价值函数 V(),(),()则MODP可表示成：P2 Max v (),(),()s.t. X、最佳调和解(Best Co
2、mpromise Solution)P3 DR ( fi(x), f2(X),，fn(X)s.t. x - xc即根据适当的 Decision Rule在X中寻找BCS X常用的 Decision Rule:max VmaxEUmin dp( f- f) *求BCS必须引入决策人的偏好三、决策人偏好信息的获取方式1在优化之前，事先一次提供全部偏好信息女口：效用函数法，字典式法，满意决策，目的规则2在优化过程中：逐步索取偏好信息女口： STEM SEMOP Geoffri on, SWT3在优化之后：事后索取偏好，由决策人在非劣解集中选择 i，算法复杂，决策人难理解，ii,计算量大，iii,决策
3、人不易判断各种方式的利弊比较黄庆来111的分类表§ 11.2目的规划法适用场合：决策人愿意并且能用优先级 P (Preemptive priority)权 W (Weight)目的f ( Goal)来表示偏好理想点f ( Ideal )一、距离测度的选择- " 1 'dp(f (x) - f) = C Wj| fj(R - fj|p p范数p的意义和作用p=1 绝对值范数p=2 欧几里德范数p = a契比E夫范数4A 6 6)r *C(hO)111:B6 0) r123456在上图中，B、C点到A的距离f1f2d1d2d3d OQAB间的距离066666AC间的距离
4、5496.45.745p从1m时最大偏差所起作用越来越大，二、目的规划问题的表述1 min dp(f(x)- f) = ' Wj|fj(x)- fj|p p * * *s. t. X即：gk(X):： 0k=1,mX 0三、分类1线性目的规划p = 1f j, gk为线性；X连续；w, f事先给定2整数目的规划 除X各分量为整数外，均同线性目的规划 （例：人才规划）3.非线性目的规划：p=1 , w, f事先给定fj, gk为非线性，X为凸集，X连续4调和规划和移动理想点法：1 < p乞:，w事先给定f = f*是移动的理想点5.字典序法 p = 14*f = fPiP2Pl 4
5、6.STEM法 P=s f = f 为理想点，权由计算得出7.SEMOP目的标定为区间，不是固定点四、例：某车间生产甲、乙两种产品，产量分别为x1和x2，产品甲每单位需 2个单位的劳动力和 3个单位原料，利润为2;生产产品乙需3个单位劳动力和1.5个单位原料，利润为3。在下一计划期间车间有12单劳动力12单位原料。假定车间主任有如下目标：(1) 利润至少为6个单位，(2) 两种产品产量经尽可能保持X1 : X2 = 3 : 2,(3) 劳动力充分利用解：按传统的线性规划，使利润最大：max 2 x1 + 3x2s. t. 2x1+ 3x2w 12(劳力约束)3x1+1.5 x2 w 12(原料
6、约束)X1,X2 > 0用图解法可得 X1=3, X2=2时，利润最大为12.原料约朿五、例（续上例）已知条件中产品甲利润改为4,其余均不变。车间主任希望改为：最低利润12单位产量比例为1,即Xi = X2；充分利用原料解：新的目标为4X3 x2 > 12（最低限度利润）x1 - x2 = 0（产量比例）3xi +1.5X2=12（材料充分利用）设定偏差变量d1：利润d2：产量比例d3：原料 d4：劳动力利用正、负偏差变量可得：min P1d1 + P2（d2 + d2 ）+ P3d3 -s. t. 4x1+3 x2 - d1 + d1 12（利润目标）X1-X2-d2 + d2
7、= 0（产量比例）3x1+1.5 x2 + d =12（材料充分利用）2X1+ 3X2 + d4 一 =12（劳动力约束）本题可以用改进的单纯形法求解（见pp217-221）,也可用图解法求解=4.8解得 x = (2.4, 2.4) , d1 _= d2 =d2 -=d4 _=0, d3 _=1.2 , d4§ 11.3字典序法第一步，由决策人给出n,按重要性由高到低排成yi,y2,yn第二步，用适当方法估计各属性的偏好(效用或价值)函数wi( yi),W2(y2),，Wn(yn)第三步，依次求解下列问题，进行筛选问题 Pi max w1(y1(x) 解为 X1 x次问题 P2 m
8、 axw2(y2(x)解为 X2x 4X问题Pj朋讐匕)直到a)问题Pj只有唯一解，则该解为最优解b) n个问题全部解过：决策人用其他准则从Xn中选择一个方案。§ 11.4 逐步进行法(STEP Method)特点：P=g只有最大偏差起作用属于Min max决策规则算法步骤对多目标决策问题 max f(x)=cxs. t. A x W b1x > 0 记作X第一步求解n个单目标优化问题maxfj(x)j=1,nxn j .J解为 X* 得 fj*= fj(x*) _ , » * * *理想点f =( fi，,fn)列出支付表使决策人对取不同的X*时各目标的值有直观认识
9、f1f1fjfn*fX1f1T1jT 1n*fXjfj1fjT jn*Xnfn1fnjfn第二步由d(f(X)一 f *)= maxwj(f； - fj(x) * *求解 min d(f(x)_f*)_ s. t. x X1等价于解 min入s. t入Wj(fj* f j (x)j=1,nx X1入0其中 Wj =j=1,ni牛j m|fj* _丨十 N 1 fl c2)12i=1式中f jmin从支付表中获得解得x1与fj(x)j=1,n第三步由决策人判断降低某个太好的目标 fl (x1)，下降.'：fl再修改约束条件，使.一 A x w b厂*J x0X2： I fi(x)= fi
10、(x1)fi1fj(x)fj(X) j=1,n j 丰 I* *以X2取代X1，令wl =0重复第二步三、优缺点：直观；修改有针对性；可较难定§ 11.5调和解(Compromise solutio n)和移动理想点法、基本概念(思路)1调和解xpW在求解 MODP：min dp(f(x)-f*)时宁 * *4f * (或f ), W , p要由决策人确定 *4其中由单调性假设，f=maxf,x) j=1,n可以求得x -X W可由决策人设定而P则很难设定因此，给定权向量 W，定义调和解集亠 1= X . X |x 是给定 W 时 min p Wj|fj(x) _ fj|p p 的解
11、x X*p*它是非劣解的子集，即x爲X2各目标偏差的规范化记 fj°= min fj(x)X必用IT 使偏差无量纲、归一化，否则dp量纲、单位的选取有关、求解步骤第一步由决策人估计权W第二步fj0= min fj(x)x X*f = max.x谜第三步构造调和集求解miX> dp(f(x) *-f )p=1,2, g其中ndr () = ' Wj*f j - fj(x)*0j Tjjf j(x)fj - fj(x)2宀j若能从X：中找出BCS，则结束第五步寻找新的理想点nd2()二 ' Wj *jm j fj -fj - fj(x)- m axwj第四步令X2
12、= Xw返回第二步.§ 11.6 SEMOP侈目标问题的序贯解法）、思路与记号-目的为区间偏差测度dj目的类目的表达式型有上界fj(x)/bj有下界fj(x) > aj*给定值f j (x) = cj区间内 aj w f j (x) w bjaj/ fj(x)1 fj(x)Cj2' Cjfj(x)7bjfj(x)ajaj bj bj fj(x)7区间外fj(x) w aj, fj(x) > bj bjaj fj(x) aj d( ) bjbjfj(x)丿n个目标分为两类Iq :加约束的r个目标的下标集合；JqIq J=1,2,nXq : X中的子集，其中的x使lq
13、, fj （x）在标定区间内求解 min Sq - 7 dqj iqs. t. x X将解xq与fj（xq） j=1,n送决策人判断-为了向决策人提供必要信息需解（n-r）个辅问题min Sq =瓦 djj®,j 静s. t. x xq其中，| =1,n-rp是Jq中第I个元素在J中的序号xq是j iq以及j=p的匚（乡均严格处于标定的目的区间内二、解题步骤第一步 由决策人确定r个应严格限定值域的目标，并给出这r个目标的目的区间，这目标的序号构成集合Iq第二步i,解主问题min Sq 八 d：js. t. x 三 X qii,解n-r个辅问题min S：dj®,j护s. t
14、. x XP得出 xq 与 fj(xq) j=l,n «和xq 与 f j (xq)j=1,n l =1,n-r第三步由决策人对第二步结果作判断基对xq满意则停止若 不满意则q=q+1返回第一步三、优缺点1可用于非单调区间2容易反映目标间的矛盾关系3非线性规划问题求解困难，没有规范化的步骤保证收敛§ 11.7Geoffrion 法一、思路用Frank-Wolfe法解线性约束的非线性规划问题max v( f (x)(0)s. t. x X*是在x0处，以一阶Taylor展开V(x)线性逼接v( f (x)记作v( x )： * * *(x) = v( x0) + '
15、xV(X°)T(X-X0)(1) 求(1)的极大值等价于求解线性规划问题max I xV(x0)T x(2)x iX令的最优解为y0，贝Ui, 若l xV(x0)T(yO-X0)是的最优解，迭代停止；* *ii, 若i xV(x°) T ( y0 - x°) 0,则从x°出发沿y°-x°方向作一维搜索* * * *即求 maxv(x0+t0(y0-x0)的最优解 t0只要t0 0足够小，必有v( x1 ) v( x0) *1 0 0 / 0 0、式中 x = x +t (y -x )* * * *对x1三X，重复上述步骤，可得原问题(
16、0)的最优解' xV(X°)虽属未知，但 I xV(X°)=.匕x f j (x0)二 & j除以旦，得£ Wj Jfj(x0)其中，wj =色冋&"%fj j=1,n ； f lj j:V :-f|、求解步骤三、优缺点1只要决策者心目中的效用函数确实存在，并能给出各点的边际置换率，不必给出具体的 效用函数值。2只适用于线性约束的多目标规划3每次迭代都有所增加，收敛性有保证但在实际上所得到的解的优劣取决于决策人提供的局部偏好信息的准确性。§ 11.8 代理值置换法(Surrogate worth Trade-off Me
17、thod)一、思路：置换率：在某个非劣点处若要提高某一目标值一个单位，必须使另一目标降低多少，(设其他目标函数值不变)置换率给出了非常有用的信息 ：如决策人愿意进行这种置换，说明该方向上有决策人更喜爱的非劣解。、求解步骤 第一步：产生非劣解的有代表性的子集 任选一种方法去求得非劣解的有代表性的子集。不失一般性，选fn(x)作为参考目标，构成不等式约束问题min fn(x)(1)*s. t. gi(x)乞0i=1,mfj(X)一 ；jj=1,n-1其中,;j aj ,bjai 二 mirfi(x) b m axf, (x)jx.XjjxWXj为了便于比较，最好选用重要目标或其计量单位是决策人所熟
18、悉的目标作为目标n。第二步：获得置换信息在求解(1)时，可以得到nj(X) = 一 ¥ |f =f(X。)j=1,n-1* * * *其中X0是(1)的解，ni(x°)是的Kuhn-Tucker乘子， 就是在X。处的置换率J »第三步：了解决策人的偏好把第二步计算结果递交给决策人，要决策人回答是否愿意进行这种调整，愿意到何种程度，并据以构造代用值函数wnj(xo) j=1,n-1+ 10非常愿意增加nj (x0)个单位的fn减去一个单位的f j-10非常愿意减少nj(x0)个单位的fn以提高 匚一个单位第四步：寻求最佳调和解当某个X*使Wnj(X )=0j=1,n-1时,x为最佳调和解 若在第一步生成的非劣点中不包含X*，可用多元回归法构造代理值函数wnj()令Wnj ( *) =0即 Wnj(f1, fnJ)=0*T求解联列方程得 ；=(打，,fnj)可用这组；*代入(1)求得X*.