多目标决策管理概述

1、第十一章多目标决策(Multi-objective Decision-making)主要参考文献68, 11111.1序言MA :评估与排序MCDPMO :数学规划一、问题的数学表达N个决策变量=Xi,X2,Xn n 个目标函数 f ( X ) = ( f1( X 工 f2( X ),fn( X )m个约束条件x 即：gk ( X ) 0 k=1,mx 0(1)不失一般性,MODP可表示成：P1Max X), f2(X),fn(X)s.t. xS 这是向量优化问题,要在可行域x中找一 x,使各目标值到达极大.通常Xs并不存在,只能找出一集非劣解X*?(2)假设能找到价值函数 V( f1(X),

2、 f2(X),fn( X)那么MODP可表示成:P2 Max V ( 3(X), f2(X),fn(X)s.t. x这是纯量优化问题,困难在于V如何确定.二、最正确调和解(Best Compromise Solution)P3 DR ( fi), f2(X),fn)s.t. Xc即根据适当的 Decision Rule在X中寻找BCS X ?常用的 Decision Rule:max VmaxEUmin dp( f- f) ?求BCS必须引入决策人的偏好三、决策人偏好信息的获取方式1 .在优化之前,事先一次提供全部偏好信息如：效用函数法,字典式法,满意决策,目的规那么2 .在优化过程中：逐步索

3、取偏好信息如：STEM SEMOP Geoffrion, SWT3 .在优化之后：事后索取偏好,由决策人在非劣解集中选择i,算法复杂,决策人难理解,ii,计算量大,iii,决策人不易判断各种方式的利弊比拟黄庆来111的分类表：11.2目的规划法适用场合：决策人愿意并且能用优先级 P (Preemptive priority)权 W (Weight)目的f ( Goal )来表示偏好?理想点 f ( Ideal ) ?一、距离测度的选择1dp(f(x) f) = Wj|fj(X) fj|P p ?范数p的意义和作用p=1绝对值范数p=2 欧几里德范数p =0契比E夫范数6 tfC Cl,I Ir

4、 i123456在上图中,B、C点到A的距离f1f2d1d2d3dAB间的距离066666AC间的距离5496.45.745P从1 00时最大偏差所起作用越来越大,二、目的规划问题的表述1min dpfx f = wj|fjx fj|p p ?s. t. X 即：gkX 0k=1,mX 0三、分类1 .线性目的规划p = 1fj, gk为线性；X连续；w, f事先给定2 .整数目的规划 除X各分量为整数外,均同线性目的规划例：人才规划3.非线性目的规戈IJ:p=1 , w, f事先给定fj, gk为非线性,X为凸集,X连续4 .调和规划和移动理想点法：1 p w事先给定 _ _ * f = f

5、 是移动的理想点5 .字典序法p = 1一 一 *f = f P1 P2? PL* 一 一一. , , 一 一 ,6.5 TEM法 P=8 f = f为理想点,权由计算得出6.6 EMOP目的标定为区间,不是固定点四、例：某车间生产甲、乙两种产品,产量分别为X1和X2 ,产品甲每单位需 2个单位的劳动力和个单位原料,利润为2;生产产品乙需3个单位劳动力和1.5个单位原料,利润为3.在下一方案期间车间有12单劳动力12单位原料.假定车间主任有如下目标：(1)利润至少为6个单位,(2)两种产品产量经尽可能保持 Xi： X2 = 3:2,劳动力充分利用解：按传统的线性规划,使利润最大：max 2x1

6、+ 3x2s. t. 2Xi+ 3X212(劳力约束)3X1+1.5X212(原料约束)x1,x2 A 0用图解法可得Xi=3, X2 =2时,利润最大为12.利润 下限原料约束产量或比例劳翰力匏耒1 -五、例续上例条件中产品甲利润改为4,其余均不变.车间主任希望改为:最低利润12单位2产量比例为1,即x1 = x2；3充分利用原料解：新的目标为4x1+3 x2 12最低限度利润x- x2 = 0产量比例3x1 +1.5 x2=12材料充分利用设定偏差变量 d1：利润d2：产量比例d3：原料 d4：劳动力利用正、负偏差变量可得:min P1d1 + P2(d2+ d2)+ P3d3s. t.

7、4x+3x2-d1+ d112利润目标x - x2 - d2+ d2产量比例3x1 +1.5 x2 + d3=12材料充分利用2x1+ 3x2 + d4=12劳动力约束此题可以用改良的单纯形法求解见pp217-221,也可用图解法求解：原料约束产量成比例劳动力约束5利润 下限解得 x = (2.4, 2.4) , d1 = d2 =d2 =d4 =0 , d3 =1.2 , d4 =4.811.3字典序法第一步,由决策人给出 n,按重要性由高到低排成yi,y2,yn第二步,用适当方法估计各属性的偏好(效用或价值)函数Wi( yi), W2(y2),Wn(yn)第三步,依次求解以下问题,进行筛选

8、问题 P1 max w1(y1(x)解为 X1x X问题 P2 max W2( y2 (x)解为 Xx X1-、 一、,_问题 Pj max w2(y2 (x)x Xj 1直到a)问题Pj只有唯一解,那么该解为最优解b) n个问题全部解过：决策人用其他准那么从Xn中选择一个方案.11.4 逐步进行法(STEP Method)特点：P=8只有最大偏差起作用属于Min max决策规那么算法步骤对多目标决策问题max f(x)=Cxs. t. A x w b1x 0 记作X ?第一步求解n个单目标优化问题max fj (x)j=1,nxX ?解为 xj 得 f j = f j (xj)理想点 f *

9、 = (fi*,fn*)fi列出支付表一一使决策人对取不同的xj时各目标的值有直观熟悉fifjfn*Xi*Xj*xn*fifijfinfjifni*fjfnjf jn*fn第二步?xf )= maxwj_ * _(fj fj(x)求解 _ _ *min d (f(x) f )?s. t. x Xi等价于解 min入S. t.入Wj (f jfjXj=1,.nj=1,nminT j IxXi入0其中 Wjj i j*|fjN2fj (c2)i i式中fjmin从支付表中获得 11、解得 x 与 f jX j=1,n第三步由决策人判断降低某个太好的目标父,下降 再修改约束条件,使, AXWb 广?

10、x2：1 fix= fix1- flf jx fjX、尸1,n jw 1以x2取代X1 ,令叫=0重复第二步三、优缺点：直观；修改有针对性；fl较难定11.5调和解Compromise solution刖移动理想点法一、根本概念思路1 .调和解xp? W, ,、八一_ ,-, 、-* 、 一 I在求解 MODP:min dpfx f 时x X? ?f * 或f , W , p要由决策人确定 ?其中由单调性假设,f = max f j x j=1,n可以求得 ? xX,W可由决策人设定而P那么很难设定因此,给定权向量 W,定义调和解集Cp 1xw = x X|x是给定 w 时mi? Wj|fjx

11、 fj|p的解 ?它是非劣解的子集,即XWC X*2 .各目标偏差的标准化记 f：= min fj(X)_ * _dp量纲、单位的选取有关 pfj fj(x)用 一*0一使偏差无量纲、归一化,否那么f f0j j、求解步骤 第一步由决策人估计权W. 一 0第二步 fj = rrnin fj(x) f =% fj(x)第三步构造调和集求解其中min dx Xp(f(x)f?)p=1,2,8nfj fj(x)di(?) Wj 0j i f j f jd2(?)d (?)n fjfj(x) 2Wj *0j 1fjf jfjfj(x)maxWj *0j j fjfj0第四步 假设能从X：中找出BOS,

12、那么结束 第五步寻找新的理想点C令X2=XW返回第二步11.6 SEMOP(多目标问题白序贯解法)一、思路与记号目的为区间目的类目的表达式偏差测度dj有上界fj(x)ajaj/fj(X)给定值fj(X)= Cj1 fj(X)Cj()2Cjfj(X)区间内 aj f j (x) a bj a j f j (x)a j 1?()bjbjfj(x)n个目标分为两类：Iq :加约束的r个目标的下标集合；JqIq J=1,2,nXq：X中的子集,其中的x使j Iq , fj (x)在标定区间内求解 min Sq d： j Jqs. t. x X q将解xq与fj(xq) j=1,n送决策人判断 ?为了向

13、决策人提供必要信息需解(n-r)个辅问题min q dj j Jq,j ps. t. X xp其中,l =1,n-rp是Jq中第l个元素在J中的序号Xq是j Iq以及j=p的fj(x)均严格处于标定的目的区间内、解题步骤第一步 由决策人确定r个应严格限定值域的目标,并给出这r个目标的目的区间,这目标的序号构成集合Iq第二步i,解主问题min Sqdqj Jqs. t. xii,解n-r个辅问题min Sqdjj Jq,j ps. t. x X q? p得出 x fj(xq)j=1,n和 xq 与 fj(xq)j=1,nl=1,n-r?iJ ?i第三步由决策人对第二步结果作判断基对xq满意那么停

14、止 ?假设 不满意那么q=q+1返回第一步三、优缺点1 .可用于非单调区间2 .容易反映目标间的矛盾关系3 .非线性规划问题求解困难,没有标准化的步骤保证收敛11.7Geoffrion 法一、思路用Frank-Wolfe法解线性约束的非线性规划问题(0)max v( f(X)s. t. X X ?是在x处,以一阶Taylor展开母线性逼接v( f (x)记彳v( X )：00T ,0、v(X)= v( X ) + xV(X ) (x-x )求(1)的极大值等价于求解线性规划问题max xv(x0)T x(2)x X?令(2)的最优解为y,那么 ?i,假设xv(x0)T(y-xO)是(2)的最优

15、解,迭代停止；加假设xv(xO)T( y-xO) 0,那么从x0出发沿y-xO方向作一维搜索 ?即求 maxv( x0+1( y0-x0)的最优解 t00 t0 1?只要t0 0足够小,必有v(X1) v(X)式中 x1 = x0 + t0(y0 -x0)?对X1X ,重复上述步骤,可得原问题(0)的最优解?0. .0 n0、xV(X )虽属未知,但xv(x )=xfj(x )j 1 f jj=1,n除以,得 w jX f j (x) 其中,wj - j- - /f jflj 1v fl、求解步骤三、优缺点1 .只要决策者心目中的效用函数确实存在,并能给出各点的边际置换率,不必给出具体的效用函

16、数值.2 .只适用于线性约束的多目标规划3 .每次迭代都有所增加,收敛性有保证但在实际上所得到的解的优劣取决于决策人提供的局部偏好信息的准确性.11.8 代理值置换法(Surrogate worth Trade-off Method)一、思路：置换率：在某个非劣点处假设要提升某一目标值一个单位,必须使另一目标降低多少,(设其他目标函数值不变)置换率给出了非常有用的信息：如决策人愿意进行这种置换,说明该方向上有决策人更喜爱的非劣解.二、求解步骤第一步：产生非劣解的有代表性的子集任选一种方法去求得非劣解的有代表性的子集.不失一般性,选fn(X)作为参考目标,构成不等式约束问题：?min fn(x)

17、(1)s. t. gi (x)0 i=1,mfj (x) j j=1,n-1其中,j aj,bj aj mipfj(x) bj max f j (x) x X ?x X ?为了便于比拟,最好选用重要目标或其计量单位是决策人所熟悉的目标作为目标no第二步：获得置换信息在求解(1)时,可以得到 nj(x) x|f f(x0)j=1, -,n-1? ?其中x0是(1)的解,nj(x)是(1)的Kuhn-Tucker乘子, 就是在x处的置换率第三步：了解决策人的偏好把第二步计算结果递交给决策人,要决策人答复是否愿意进行这种调整,愿意到何种程度,并据以构造代用值函数Wnj(x) j=1,n-1+ 10非

18、常愿意增加nj(X)个单位的fn减去一个单位的fj-10非常愿意减少nj(X)个单位的fn以提升fj 一个单位 第四步：寻求最正确调和解 、 一* 一一.、一 一,.当某个X使 wnj(X ) =0 j=1,n-1时,x为取佳倜和解. * . . . . 假设在第一步生成的非劣点中不包含X,可用多兀回归法构造代理值函数Wnj(?)令Wnj (?) =0即 Wnj(f1,fn 1)=020.5.55.5.202121:5808:58:20May-2021:58求解联u域很法变动人得但翻门能够变.生观;然而我们能够转变心绪.二0二0年五月五日2021年5月5日星期二 *将良品率预定为 85%,那么彳熟悉了生活的全部意义的人,不公洲更死女