多目标决策简介

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

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

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

4、 s. t. ÎC 即: ()< 0 k=1,m > 0三、分类1.线性目的规划 p = 1 , 为线性; 连续; w, 事先给定2.整数目的规划 除各分量为整数外，均同线性目的规划 (例：人才规划)3.非线性目的规划： p=1， w, 事先给定 , 为非线性，X为凸集，连续4.调和规划和移动理想点法: 1£ p£¥ w事先给定 = 是移动的理想点5. 字典序法 p = 1 = P1P2PL法 P= = 为理想点，权由计算得出7.SEMOP 目的标定为区间，不是固定点四、例：某车间生产甲、乙两种产品，产量分别为和，产品甲每单位需2个单位的劳动

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

6、- = 0 (产量比例) 3=12 (材料充分利用)设定偏差变量 : 利润 : 产量比例 : 原料 :劳动力利用正、负偏差变量可得： min P1+ P2(+) + P3s. t. 4+3-+12 (利润目标) - - + = 0 (产量比例) 3 + =12 (材料充分利用) 2+ 3 + =12 (劳动力约束)本题可以用改进的单纯形法求解(见pp217-221), 也可用图解法求解:解得= (2.4, 2.4) , =0 , =1.2 , §字典序法第一步，由决策人给出n，按重要性由高到低排成 , 第二步，用适当方法估计各属性的偏好(效用或价值)函数 (), (), , ()第三

7、步，依次求解下列问题，进行筛选问题P1 解为问题P2 解为 问题Pj 直到 a) 问题Pj 只有唯一解, 则该解为最优解 b) n个问题全部解过：决策人用其他准则从中选择一个方案。§11.4 逐步进行法(STEP Method)特点：P= 只有最大偏差起作用 属于Min max 决策规则算法步骤对多目标决策问题 max=Cs. t. Ab 0 记作 第一步· 求解n个单目标优化问题 j=1,n 解为 得= 理想点 = (,) · 列出支付表使决策人对取不同的时各目标的值有直观认识第二步由 = max求解 min s. t. 等价于解 min入s. t. j=1,n

8、 0 其中 j=1,n 式中 从支付表中获得·解(2)得 与 j=1,n第三步 由决策人判断降低某个太好的目标 ，下降再修改约束条件，使 Ab 0 : =- j=1,n j 以取代，令=0重复第二步三、优缺点：直观; 修改有针对性; 较难定§11.5 调和解(Compromise solution)和移动理想点法一、基本概念(思路)1.调和解 在求解MODP: 时 (或), W , p要由决策人确定其中 ·由单调性假设，= j=1,n可以求得 ·W可由决策人设定 而P则很难设定因此，给定权向量W，定义调和解集 = |是给定W时的解它是非劣解的子集, 即

9、Ì2.各目标偏差的规范化 记= 用使偏差无量纲、归一化，否则量纲、单位的选取有关二、求解步骤第一步 由决策人估计权W第二步 = =第三步 构造调和集求解 p=1,2,其中 第四步若能从中找出BCS，则结束第五步 寻找新的理想点令 = 返回第二步.§11.6 SEMOP(多目标问题的序贯解法)一、思路与记号· 目的为区间目的类型目的表达式偏差测度 有上界/有下界/给定值= 区间内区间外,·n个目标分为两类:：加约束的r个目标的下标集合；=J J=1,2,n ：X中的子集，其中的使 "jÎ, 在标定区间内· 求解min s. t

10、. 将解与 j=1,n送决策人判断· 为了向决策人提供必要信息需解(n-r)个辅问题· mins. t. 其中, =1,n-r p是中第个元素在J中的序号 是jÎ以及j=p的均严格处于标定的目的区间内二、解题步骤第一步 由决策人确定r个应严格限定值域的目标，并给出这r个目标的目的区间，这r个目标的序号构成集合第二步 i, 解主问题 min s. t. ii, 解n-r个辅问题 mins. t. 得出与 j=1,n和 与 j=1,n =1,n-r第三步 由决策人对第二步结果作判断基对满意则停止若 不满意则q=q+1返回第一步三、优缺点1.可用于非单调区间2.容易反映

11、目标间的矛盾关系3.非线性规划问题求解困难,没有规范化的步骤保证收敛§法一、思路· 用Frank-Wolfe法解线性约束的非线性规划问题max v() (0) s. t. 是在 处，以一阶Taylor展开线性逼接v()记作v(): = v() + (-) (1)求(1)的极大值等价于求解线性规划问题 · (2)令(2)的最优解为，则i,若 (-) 是(2)的最优解，迭代停止；ii,若(-)>0, 则从出发沿-方向作一维搜索即求 v(+(-)的最优解只要 >0足够小, 必有 v()>v() 式中 = +(-)对，重复上述步骤，可得原问题(0)的最优

12、解虽属未知，但= 除以, 得 其中，»- j=1,n二、求解步骤三、优缺点1.只要决策者心目中的效用函数确实存在，并能给出各点的边际置换率，不必给出具体的效用函数值。2.只适用于线性约束的多目标规划3.每次迭代 都有所增加，收敛性有保证但在实际上所得到的解的优劣取决于决策人提供的局部偏好信息的准确性。§11.8 代理值置换法(Surrogate worth Trade-off Method)一、思路：·置换率：在某个非劣点处若要提高某一目标值一个单位，必须使另一目标降低多少，(设其他目标函数值不变)置换率给出了非常有用的信息:如决策人愿意进行这种置换，说明该方向上有决策人更喜爱的非劣解。二、求解步骤第一步：产生非劣解的有代表性的子集任选一种方法去求得非劣解的有代表性的子集。不失一般性，选作为参考目标，构成不等式约束问题:min (1)s. t. i=1,m j=1,n-1 其中, 为了便于比较，最好选用重要目标或其计量单位是决策人所熟悉的目标作为目标n。第二步：获得置换信息在求解(1)时，可以得到 j=1,n-1其中是(1)的解， 是(1)的Kuhn-Tucker乘子， 就是在处的置换率第三步：了解决策人的偏