MBA决策分析教材-多目标决策

1、多目标决策(Multi-objective Decision-making)主要参考文献68, 111§ 11.1序言MA：评估与排序MCDPMO：数学规划一、问题的数学表达N个决策变量x = x1 , x2 , ,xN ?n个目标函数f ( x ) = (f 1 ( x ),?m个约束条件x即 :gk ( x )?f 2 ( x ), ,f n ( x )?0 k=1, ,mx0?(1) 不失一般性， MODP可表示成：P1 Max f 1( x ),f 2( x ), ,f n( x )?s.t.x?这是向量优化问题， 要在可行域X 中找一 x S ，使各目标值达?到极大。通常

2、x S 并不存在，只能找出一集非劣解x*?(2)若能找到价值函数 v( f 1(x),f2(x),fn(x)则可?MODP表示成：P2 Max v (f 1( x ), f2( x ), ,f n( x )?s.t.x?这是纯量优化问题，困难在于v 如何确定。二、最佳调和解 (Best Compromise Solution)P3 DR(f1 ( x ), f2( x ), , f n( x )?s.t.x?即根据适当的 Decision Rule在 X 中寻找 BCS xc?常用的 Decision Rule:max VmaxEU11- 1mind p ( f - f )?求 BCS必须引入

3、决策人的偏好三、决策人偏好信息的获取方式1. 在优化之前，事先一次提供全部偏好信息如：效用函数法，字典式法，满意决策，目的规则2. 在优化过程中：逐步索取偏好信息如： STEM SEMOP Geoffrion, SWT3. 在优化之后：事后索取偏好，由决策人在非劣解集中选择i， 算法复杂，决策人难理解， ii, 计算量大， iii, 决策人不易判断各种方式的利弊比较黄庆来 111 的分类表 :§ 11.2 目的规划法适用场合：决策人愿意并且能用优先级 P (Preemptive priority)权W (Weight)目的 f( Goal )来表示偏好?理想点f * ( Ideal

4、)?11- 2一、距离测度的选择1d p ( f ( x)f ) = w j | f j ( x) f j |p p?范数 p 的意义和作用p=1绝对值范数p=2欧几里德范数p = 契比 E 夫范数在上图中， B、 C点到 A 的距离f1f 2d1d2d3dAB间的距 066666离AC间的距离 5496.45.754p 从 1时最大偏差所起作用越来越大，二、目的规划问题的表述min d p ( f ( x)f ) =f j |p1p w j | f j ( x)?s. t.x即: gk (x )0k=1, ,m?x0?三、分类1. 线性目的规划p = 1f j ,gk 为线性 ;x 连续 ;

5、w,f 事先给定?2. 整数目的规划 除 x 各分量为整数外，均同线性目的规划?(例：人才规划 )3. 非线性目的规划：p=1， w,f 事先给定?11- 3f j ,gk为非线性， X 为凸集， x 连续?4. 调和规划和移动理想点法:1pw 事先给定f =f *是移动的理想点?5.字典序法p = 1f =f *P1P2 PL?6.STEM法 P= f =f * 为理想点，权由计算得出?7.SEMOP目的标定为区间，不是固定点四、例：某车间生产甲、乙两种产品，产量分别为 x1 和 x2 ，产品甲每单位需 2 个单位的劳动力和 3 个单位原料 , 利润为 2；生产产品乙需 3 个单位劳动力和

6、1.5 个单位原料 , 利润为 3。在下一计划期间车间有 12 单劳动力 12 单位原料。假定车间主任有如下目标：(1) 利润至少为6 个单位，(2) 两种产品产量经尽可能保持x1 ： x2 = 3 ：2，(3) 劳动力充分利用解：按传统的线性规划，使利润最大：max 2x1 + 3 x2s. t. 2x1 +3x2 12 ( 劳力约束 )3x1+1.5x212 ( 原料约束 )x1,x20用图解法可得 x1=3,x2=2 时, 利润最大为 12.五、例 ( 续上例 )已知条件中产品甲利润改为4,其余均不变。车间主任希望改为 : 最低利润12 单位(2) 产量比例为 1, 即 x1 = x2

7、;(3)充分利用原料11- 4解 : 新的目标为 4 x1 +3x2 12(最低限度利润 )x1 -x2= 0(产量比例 )3x1 +1.5 x2 =12(材料充分利用 )设定偏差变量d1 : 利润 d2 :产量比例d3 : 原料d 4 : 劳动力利用正、负偏差变量可得：min P1d1+ P2( d 2+d 2)+P3d 3s. t.4x1 +3x2 - d1+d112(利润目标 )x1 -x2 -d2 +d2= 0(产量比例 )3x1 +1.5x2+d3=12(材料充分利用 )2x1 + 3x2+d4=12(劳动力约束 )本题可以用改进的单纯形法求解( 见 pp217-221),也可用图解

8、法求解 :解得 x * = (2.4, 2.4) , d1 = d 2 = d 2 = d 4 =0 , d3 =1.2 , d4 =4.8§ 11.3 字典序法第一步，由决策人给出n，按重要性由高到低排成y1 , y2 , ,yn第二步，用适当方法估计各属性的偏好( 效用或价值 ) 函数w1 ( y1 ), w2 ( y2 ), , wn ( yn )第三步，依次求解下列问题，进行筛选问题 P1max w1 ( y1 (x) 解为 X1x X问题 P2max w2 ( y2 ( x) 解为 X 2x X1 问题 Pj直到 a)max w2 ( y2 ( x)x X j 1问题 Pj

9、 只有唯一解 ,则该解为最优解b) n 个问题全部解过：决策人用其他准则从 X n 中选择一个方案。11- 5§ 11.4 逐步进行法 (STEP Method)特点： P= 只有最大偏差起作用属于 Min max 决策规则算法步骤对多目标决策问题max f ( x) =Cx ?s.t. Ax b?x 0记作 X1?第一步· 求解 n 个单目标优化问题max f j( x)j=1,nx X?解为 x*j得 f j* = f j (x *j )?理想点f * = ( f1* , , f n* )?· 列出支付表使决策人对取不同的x *j时各目标的值有直观?认识 f

10、1f1x1*f 1*?f jf 1 jf nf 1nx *jf j 1f j*f jn?xn*f n1f njf n*?第二步由 d ( f (x)f *)= max w j ( f j*?求解 mind( f ( x)f * )?s. t.xX1等价于解 min入s. t. w j ( f j*xX1 0f j ( x)?f j ( x)j=1,n?11- 6其中 w jnjj=1,nj1j| f j*jf j* (Nf jmin |1c2ji ) 2式中·解 (2) 得x1 与?i 1f jmin 从支付表中获得f j ( x1 )j=1,n?第三步 由决策人判断降低某个太好的目

11、标f l ( x1 ) ，下降 f l 再修改约束条件，使?Ax b?x 0?X 2 :f l ( x) = f l ( x1 ) - f l?f j ( x) f j(x 1 ) j=1, ,n j l?以 X 2 取代 X 1 ，令 w l =0 重复第二步三、优缺点：直观 ;修改有针对性 ;f l 较难定§ 11.5 调和解 (Compromise solution)和移动理想点法一、基本概念 ( 思路 )1. 调和解 x p? W在求解 MODP:min dp ( f ( x)f * ) 时x X?f * ( 或 f), W, p要由决策人确定?其中 ·由单调性假设

12、，f =maxf j ( x)j=1, ,n 可以求得?x X?·W可由决策人设定而 P 则很难设定因此，给定权向量 W，定义调和解集XWC = xX | x 是给定 W时 min 1w j | f j ( x) f j |p p 的解 ?x X?它是非劣解的子集 ,即 XWCX *2. 各目标偏差的规范化11- 7记 f j0 = minf j ( x)xX?f j*f j ( x)使偏差无量纲、归一化，否则d p 量纲、单位的选用f*f0?jj取有关二、求解步骤第一步 由决策人估计权 W第二步f j0 =min f j( x)f * = max f j ( x)xX?x X?第三

13、步构造调和集求解mind p ( f ( x)f * ) p=1,2,x X?nf j*f j ( x)其中d1 ( ?)w j?f*0j1jf jnf j*f j ( x)d2 (?)w j f*0? 2j1jf jf j*f j ( x)d(?)maxw j?f*0jjf j第四步若能从X C 中找出BCS，则结束W令 X2 = XWC 返回第二步 .§ 11.6 SEMOP(多目标问题的序贯解法 )一、思路与记号· 目的为区间目的 目的表达式 偏差测度 d j 类型有上f j(x) bj界?有下f j( x) aj界?f j ( x) / b j?a j / f j

14、( x)?给定f j(x) = c j值?区间a j f j ( x) b j?内1f j(x)?(2 cjb jfj( x)(?a j b jb jcj)f j ( x)?a j)f j ( x)?11- 8区间f j (x) aj, f j( x) bja jf j (x)(?外?bjb jb j· n 个目标分为两类 :I q ：加约束的 r 个目标的下标集合；JqI qJ=1,2,nX q ：X 中的子集，其中的x 使jI q ,?· 求解 min Sqd jq j J qa j1)f j (x)?f j ( x) 在标定区间内?s. t.x X q?将解 x q

15、与 f j ( xq ) j=1,n 送决策人判断?· 为了向决策人提供必要信息需解(n-r)个辅问题· min Slqj Jq , jd jps.t. xX pq?其中 ,l =1, ,n-rp是 J q 中第 l 个元素在 J 中的序号X pq 是 jI q 以及 j=p 的 f j (x) 均严格处于标定的目的区?间内二、解题步骤第一步由决策人确定 r 个应严格限定值域的目标，并给出这r个目标的目的区间，这r 个目标的序号构成集合 I q第二步 i,解主问题minSqd jq j Jqs. t.x X q?ii, 解 n-r 个辅问题minSlqd j j Jq ,

16、j ps.t.xX q?p得出 xq 与?和xq 与? lf j ( x q )?f j ( x q )? lj=1, ,nj=1, ,nl =1, ,n-r第三步由决策人对第二步结果作判断基对 x q 满意则停止?11- 9若 不满意则 q=q+1 返回第一步三、优缺点1. 可用于非单调区间2. 容易反映目标间的矛盾关系3. 非线性规划问题求解困难 , 没有规范化的步骤保证收敛§ 11.7Geoffrion 法一、思路· 用 Frank-Wolfe 法解线性约束的非线性规划问题max v(f ( x) )(0)?s. t.xX?是在 x0处，以一阶Taylor展开 v(

17、x) 线性逼接 v(f (x) ) 记作?v( x ):?0) + 0)T( x -x0)(1)v (x) = v( xxv( x?求 (1)的极大值等价于求解线性规划问题max x v(x 0 ) T · x(2)x X?令 (2)的最优解为 y 0 ，则?i,若 x v( x 0 ) T (y0 -x 0 ) 是(2) 的最优解，迭代停止；?ii,若x v( x 0 ) T (y0 -x 0 ) 0,则从 x 0 出发沿 y0 - x 0 方向作一维搜索?即求 max v(x 0 +t 0 (y0 - x 0 ) 的最优解 t 00 t 01?只要 t 00足够小,必有 v(x

18、1 ) v(x 0 )?式中 x1 =x 0 +t 0 ( y 0 - x 0 )?对 x1X ，重复上述步骤，可得原问题(0)的最优解?xv( x0 ) 虽属未知，但x v( x0 ) = nvx f j (x 0 )j1f j,n0vf j-f l除 以w jx f j ( x )其 中 ， w jf jv得vf lf lj1j=1, ,n二、求解步骤11- 10三、优缺点1. 只要决策者心目中的效用函数确实存在， 并能给出各点的边际置换率，不必给出具体的效用函数值。2. 只适用于线性约束的多目标规划3. 每次迭代 都有所增加，收敛性有保证但在实际上所得到的解的优劣取决于决策人提供的局部偏好信息的准确性。§ 11.8 代理值置换法 (Surrogate worth Trade-off Method)一、思路：·置换率：在某个非劣点处若要提高某一目标值一个单位，必须使另一目标降低多少， ( 设其他目标函数值不变 )置换率给出了非常有用的信息 :如决策人愿意进行这种置换， 说明该方向上有决策人更喜爱的非劣解。二、求解步骤第一步：产生非劣解的有代表性的子集任选一种方法去求得非劣解的有代表性的子集。不失一般性，选f n ( x) 作为参考目标