第十一章多目标决策 ( Multi-objective Decision-making) 主要参考文献68,111 §11序言 MA:评估与排序 MCDP MO:数学规划 问题的数学表达 N个决策变量x={x1,x2…,x} n个目标函数f(x)=(f(x),f2(x),…,fn(x) 个约束条件了∈X即8(x)<0k=1…m (1)不失一般性,MODP可表示成 ∫1(x),f2(x)…,fn(x)} t. 这是向量优化问题,要在可行域X中找一x°,使各目标值达到极大 通常x3并不存在,只能找出一集非劣解 (2)若能找到价值函数vf1(x),f2(x)2…,fn(x)则MODP可表示成 P2 Max V((x),f2(x),,f,(x)) 这是纯量优化问题,困难在于ⅴ如何确定。 最佳调和解( Best Compromise Solution) P3 DR(A(X),2(X),f,(x) st 即根据适当的 Decision rule在X中寻找BCS 常用的 Decision rule:maxV maxed min d,(.f) 求BCS必须引入决策人的偏好
11- 1 第十一章 多目标决策 (Multi-objective Decision-making) 主要参考文献 68, 111 §11.1 序言 MA： 评估与排序 MCDP MO： 数学规划 一、问题的数学表达 N 个决策变量 x • = { x1 , x 2 ,… , xN } n 个目标函数 f • ( x • ) = ( f 1 ( x • ), f 2 ( x • ),… , f n ( x • )) m 个约束条件 x • 即: gk ( x • ) 0 k=1,… ,m x • 0 (1) 不失一般性，MODP 可表示成： P1 Max { f 1 ( x • ), f 2 ( x • ),… , f n ( x • )} s.t. x • 这是向量优化问题，要在可行域 X 中找一 x S • ，使各目标值达到极大。 通常 x S • 并不存在，只能找出一集非劣解 x • * (2) 若能找到价值函数 v( f 1 ( x • ), f 2 ( x • ),… , f n ( x • )) 则 MODP 可表示成： P2 Max v ( f 1 ( x • ), f 2 ( x • ),… , f n ( x • )) s.t. x • 这是纯量优化问题，困难在于 v 如何确定。 二、最佳调和解(Best Compromise Solution) P3 DR ( f 1 ( x • ), f 2 ( x • ),… , f n ( x • )) s.t. x • 即根据适当的 Decision Rule 在 X 中寻找 BCS x c • 常用的 Decision Rule: max V maxEU min d p ( f • - f • ) 求 BCS 必须引入决策人的偏好
决策人偏好信息的获取方式 1在优化之前,事先一次提供全部偏好信息 如:效用函数法,字典式法,满意决策,目的规则 2在优化过程中:逐步索取偏好信息 n: STEM SEMOP Geoffrion, SWT 3在优化之后:事后索取偏好,由决策人在非劣解集中选择 i,算法复杂,决策人难理解,ⅱ计算量大, ⅲ决策人不易判断各种方式的利弊比较 黄庆来[1类表 §112目的规划法 适用场合 决策人愿意并且能用 优先级P( Preemptive priority) 权 目的∫(Goal 来表示偏好 理想点f∫"( Ideal) 距离测度的选择 d,((x)-f)=wI,(x)-fIP) 范数p的意义和作用 绝对值范数 p=2欧几里德范数 11-2
11- 2 三、决策人偏好信息的获取方式 1.在优化之前，事先一次提供全部偏好信息 如：效用函数法，字典式法，满意决策，目的规则 2.在优化过程中：逐步索取偏好信息 如：STEM SEMOP Geoffrion, SWT 3.在优化之后：事后索取偏好，由决策人在非劣解集中选择 i， 算法复杂，决策人难理解， ii,计算量大， iii,决策人不易判断各种方式的利弊比较 黄庆来[111]的分类表: §11.2 目的规划法 适用场合： 决策人愿意并且能用 优先级 P (Preemptive priority) 权 W (Weight) 目的 f • ( Goal ) 来表示偏好 理想点 f * • ( Ideal ) 一、距离测度的选择 d f x f p ( ( ) ) • • • − = { | ( ) w f x f | } j j j p p • − 1 范数 p 的意义和作用 p=1 绝对值范数 p=2 欧几里德范数
p=∞契比E夫范数 ↑A(6,6) C(1,0) B(6,0) 123456 在上图中,B、C点到A的距离 fr f2 d d2 d AB间的距离066666 AC间的距离5 64|574 p从1→∞时最大偏差所起作用越来越大, 目的规划问题的表述 in(d(()-1)=w()-P 三、分类 1线性目的规划p=1 J,g为线性x连续。w,∫事先给定 2整数目的规划除x各分量为整数外,均同线性目的规划 (例:人才规划 3非线性目的规划:p=1,w,f事先给定 J,gk为非线性,X为凸集,x连续 4调和规划和移动理想点法:1≤p≤∞w事先给定 ∫=∫是移动的理想点 5字典序法p=1 P》P2》.》PL 6STEM法P=∞ ∫为理想点,权由计算得出 7 SEMOP目的标定为区间,不是固定点 11-3
11- 3 p =∞契比 E 夫范数 在上图中，B、C 点到 A 的距离 f 1 f 2 d1 d2 d3 d AB 间的距离 0 6 6 6 6 6 AC 间的距离 5 4 9 6.4 5.74 5 p 从 1→∞时最大偏差所起作用越来越大， 二、目的规划问题的表述 min{ d f x f p ( ( ) ) • • • − = { | ( ) w f x f | } j j j p p • − 1 } s. t. x • 即: gk ( x • ) 0 k=1,… ,m x • 0 三、分类 1.线性目的规划 p = 1 f j , gk 为线性; x • 连续; w, f • 事先给定 2.整数目的规划 除 x • 各分量为整数外，均同线性目的规划 (例：人才规划) 3.非线性目的规划： p=1， w, f • 事先给定 f j , gk 为非线性，X 为凸集， x • 连续 4.调和规划和移动理想点法: 1 p w 事先给定 f • = f * • 是移动的理想点 5.字典序法 p = 1 f • = f * • P1》P2》… 》PL 6.STEM 法 P=∞ f • = f * • 为理想点，权由计算得出 7.SEMOP 目的标定为区间，不是固定点
四、例 某车间生产甲、乙两种产品,产量分别为x1和x2,产品甲每单位需2个单位的劳动力和3 个单位 原料利润为2;生产产品乙需3个单位劳动力和15个单位原料利润为3。在下一计划期间 车间有12单劳动力12单位原料。 假定车间主任有如下目标 (1)利润至少为6个单位, (2两种产品产量经尽可能保持x1:x2=3:2, (3)劳动力充分利用 解:按传统的线性规划,使利润最大 max 2 st.2x1+3x2≤12(劳力约束) 3x1+1.5x2≤12(原料约束) ≥0 用图解法可得x1=3,x,=2时利润最大为12 X2 原料约束 产量成比例 利 劳动力约束 五、例续上例 已知条件中产品甲利润改为4,其余均不变。 车间主任希望改为:最低利润12单位 (2)产量比例为1,即x=x2;(3)充分利用原料 解:新的目标为4x1+3x2≥12(最低限度利润 (产量比例) 3x1+1.5x2=12(材料充分利用) 设定偏差变量d1:利润d2产量比例d3:原料d4劳动力 利用正、负偏差变量可得 min Pid, + Pi(d2 +d2)+P3d, st4x1+3x2-d1-+d1+212(利润目标) x1x2-d2+d2+=0(产量比例) 3x1+1.5x2+d3=12(材料充分利用) 劳动力约束) 本题可以用改进的单纯形法求解(见pp217-221),也可用图解法求解
11- 4 四、例： 某车间生产甲、乙两种产品，产量分别为 x1 和 x 2 ，产品甲每单位需 2 个单位的劳动力和 3 个单位 原料,利润为 2；生产产品乙需 3 个单位劳动力和 1.5 个单位原料,利润为 3。在下一计划期间 车间有 12 单劳动力 12 单位原料。 假定车间主任有如下目标： (1)利润至少为 6 个单位， (2)两种产品产量经尽可能保持 x1 ： x 2 = 3：2， (3)劳动力充分利用 解：按传统的线性规划，使利润最大： max 2 x1 + 3 x 2 s. t. 2 x1 + 3 x 2 ≤ 12 (劳力约束) 3 x1 +1.5 x 2 ≤ 12 (原料约束) x1 , x 2 ≥ 0 用图解法可得 x1 =3, x 2 =2 时,利润最大为 12. 五、例(续上例) 已知条件中产品甲利润改为 4, 其余均不变。 车间主任希望改为: 最低利润 12 单位 (2)产量比例为 1, 即 x1 = x 2 ; (3)充分利用原料 解: 新的目标为 4 x1 +3 x 2 ≥ 12 (最低限度利润) x1 - x 2 = 0 (产量比例) 3 x1 +1.5 x 2 =12 (材料充分利用) 设定偏差变量 d1 : 利润 d2 : 产量比例 d3 : 原料 d4 :劳动力 利用正、负偏差变量可得： min P1 d1 − + P2( d2 − + d2 + ) + P3 d3 − s. t. 4 x1 +3 x 2 - d1 − + d1 + ≥ 12 (利润目标) x1 - x 2 - d2 + d2 + = 0 (产量比例) 3 x1 +1.5 x 2 + d3 − =12 (材料充分利用) 2 x1 + 3 x 2 + d4 − =12 (劳动力约束) 本题可以用改进的单纯形法求解(见 pp217-221), 也可用图解法求解:
x2原料约束 产量成比例 劳动力约束 解得x=(24,2.4),d1=d2=d2=d4-=0,d3-=1.2,d4+=48 5113字典序法 第一步,由决策人给出n,按重要性由高到低排成 y1,y2…,yn 第二步,用适当方法估计各属性的偏好(效用或价值函数 v1(y1),W2(y2),…,wn(yn) 第三步,依次求解下列问题,进行筛选 问题 PI max m(y1(x)解为X1 问题 P2 maxw2(y2(x)解为X2 问题 Pi max M2(y2(x) 直到a)问题P只有唯一解,则该解为最优解 b)n个问题全部解过:决策人用其他准则从X,中选择一个方案。 5114逐步进行法 STEP Method) 特点:P=∞只有最大偏差起作用 属于 Min max决策规则 算法步骤 对多目标决策问题max{f(x)=Cx} t.Ax≤b 记作X1 求解n个单目标优化问题maxf(x) 解为x得∫=∫(x) 理想点f∫=(f1…f) 列出支付表使决策人对取不同的x时各目标的值有直观认识f 11-5
11- 5 解得 x * = (2.4, 2.4) , d1 − = d2 + = d2 − = d4 − =0 , d3 − =1.2 , d4 + =4.8 §11.3 字典序法 第一步，由决策人给出 n，按重要性由高到低排成 y1 , y 2 ,… , y n 第二步，用适当方法估计各属性的偏好(效用或价值)函数 w1 ( y1 ), w2 ( y 2 ), … , wn ( y n ) 第三步，依次求解下列问题，进行筛选 问题 P1 max ( ( )) x X w y x 1 1 解为 X1 问题 P2 max ( ( )) x X w y x 1 2 2 解为 X2 … … 问题 Pj max ( ( )) x X j w y x −1 2 2 直到 a) 问题 Pj 只有唯一解, 则该解为最优解 b) n 个问题全部解过：决策人用其他准则从 Xn 中选择一个方案。 §11.4 逐步进行法(STEP Method) 特点：P=∞ 只有最大偏差起作用 属于 Min max 决策规则 算法步骤 对多目标决策问题 max{ f x • • ( ) =C x • } s. t. A x • ≤ b x • ≥ 0 记作 X 1 第一步 ·求解 n 个单目标优化问题 max ( ) x X j f x • j=1,… ,n 解为 x j * • 得 f j * = f x j j ( ) * • 理想点 f * • = ( f 1 * ,… , f n * ) ·列出支付表——使决策人对取不同的 x j * • 时各目标的值有直观认识 f 1