第十一章 多目标决策_
第十一章 多目标决策 (Multi-objective Decision-making) 主要参考文献 68, 111 §11.1 序言 MA： 评估与排序 MCDP MO： 数学规划 一、问题的数学表达 N个决策变量 [pic]= {[pic],[pic],…, [pic]} n个目标函数 [pic]([pic]) = ([pic]([pic]),[pic]([pic]),…, [pic]([pic])) m个约束条件 [pic](( 即: [pic]([pic])( 0 k=1,…,m [pic]( 0 (1) 不失一般性，MODP可表示成： P1 Max {[pic]([pic]),[pic]([pic]),…, [pic]([pic])} s.t. [pic](( 这是向量优化问题，要在可行域X中找一[pic]，使各目标值达到极大。 通常[pic]并不存在，只能找出一集非劣解[pic] 2) 若能找到价值函数v([pic]([pic]),[pic]([pic]),…, [pic]([pic])) 则MODP可表示成： P2 Max v ([pic]([pic]),[pic]([pic]),…, [pic]([pic])) s.t. [pic](( 这是纯量优化问题，困难在于v如何确定。 二、最佳调和解(Best Compromise Solution) P3 DR ([pic]([pic]),[pic]([pic]),…, [pic]([pic])) s.t. [pic](( 即根据适当的Decision Rule在X中寻找BCS [pic] 常用的Decision Rule: max V maxEU min [pic]([pic]-[pic]) 求BCS必须引入决策人的偏好 三、决策人偏好信息的获取方式 1.在优化之前，事先一次提供全部偏好信息 如：效用函数法，字典式法，满意决策，目的规则 2.在优化过程中：逐步索取偏好信息 如：STEM SEMOP Geoffrion, SWT 3.在优化之后：事后索取偏好，由决策人在非劣解集中选择 i. 算法复杂，决策人难理解， ii,计算量大， iii,决策人不易判断各种方式的利弊比较 黄庆来[111]的分类表: [pic] §11.2 目的规划法 适用场合： 决策人愿意并且能用 优先级P (Preemptive priority) 权 W (Weight) 目的[pic] ( Goal ) 来表示偏好 理想点 [pic]( Ideal ) 一、距离测度的选择 [pic] = [pic] 范数p的意义和作用 p=1 绝对值范数 p=2 欧几里德范数 p =∞契比E夫范数 [pic] 在上图中，B、C点到A的距离 | |[pic]|[pic]|[pic]|[pic]|[pic]|[pic]| | | | |[pic]| | | | |AB间的距 |0 |6 |6 |6 |6 |6 | |离 | | | | | | | |AC间的距 |5 |4 |9 |6.4 |5.74 |5 | |离 | | | | | | | p从1→∞时最大偏差所起作用越来越大， 二、目的规划问题的表述 min{[pic] = [pic]} s. t. [pic](( 即: [pic]([pic])( 0 k=1,…,m [pic]( 0 三、分类 1.线性目的规划 p = 1 [pic], [pic]为线性; [pic]连续; w, [pic]事先给定 2.整数目的规划 除[pic]各分量为整数外，均同线性目的规划 (例：人才规划) 3.非线性目的规划： p=1， w, [pic]事先给定 [pic], [pic] 为非线性，X为凸集，[pic]连续 4.调和规划和移动理想点法: 1( p(( w事先给定 [pic]= [pic] 是移动的理想点 5. 字典序法 p = 1 [pic]= [pic] P1》P2》…》PL 6.STEM法 P=∞ [pic]= [pic]为理想点，权由计算得出 7.SEMOP 目的标定为区间，不是固定点 四、例： 某车间生产甲、乙两种产品，产量分别为[pic]和[pic]，产品甲每单位需2个单位的劳动 力和3个单位 原料,利润为2；生产产品乙需3个单位劳动力和1.5个单位原料,利润为3。在下一计划期 间车间有12单劳动力12单位原料。 假定车间主任有如下目标： 1) 利润至少为6个单位， (2)两种产品产量经尽可能保持[pic]：[pic]= 3：2， 3) 劳动力充分利用 解：按传统的线性规划，使利润最大： max 2[pic]+ 3[pic] s. t. 2[pic]+ 3[pic]≤12 (劳力约束) 3[pic]+1.5[pic]≤12 (原料约束) [pic], [pic]≥0 用图解法可得[pic]=3, [pic]=2时,利润最大为12. [pic] 五、例(续上例) 已知条件中产品甲利润改为4, 其余均不变。 车间主任希望改为: 最低利润12单位 2) 产量比例为1, 即[pic]=[pic]; (3)充分利用原料 解: 新的目标为 4[pic]+3[pic]≥12 (最低限度利润) [pic]- [pic] = 0 (产量比例) 3[pic]+1.5[pic]=12 (材料充分利用) 设定偏差变量 [pic]: 利润 [pic]: 产量比例 [pic]: 原料 [pic]:劳动力 利用正、负偏差变量可得： min P1[pic][pic]+ P2([pic][pic]+[pic][pic]) + P3[pic][pic] s. t. 4[pic]+3[pic]-[pic][pic]+[pic][pic]≥12 (利润目标) [pic]- [pic] -[pic] + [pic][pic]= 0 (产量比例) 3[pic]+1.5[pic] + [pic][pic] =12 (材料充分利用) 2[pic]+ 3[pic] + [pic][pic] =12 (劳动力约束) 本题可以用改进的单纯形法求解(见pp217-221), 也可用图解法求解: [pic] 解得[pic]= (2.4, 2.4) , [pic][pic]=[pic][pic]=[pic][pic]=[pic][pic]=0 , [pic][pic]=1.2 , [pic][pic]=4.8 §11.3字典序法 第一步，由决策人给出n，按重要性由高到低排成 [pic],[pic],…, [pic] 第二步，用适当方法估计各属性的偏好(效用或价值)函数 [pic]([pic]), [pic]([pic]), …, [pic]([pic]) 第三步，依次求解下列问题，进行筛选 问题P1 [pic] 解为[pic] 问题P2 [pic] 解为[pic] … … 问题Pj [pic] 直到 a) 问题Pj 只有唯一解, 则该解为最优解 b) n个问题全部解过：决策人用其他准则从[pic]中选择一个方案。 §11.4 逐步进行法(STEP Method) 特点：P=∞ 只有最大偏差起作用 属于Min max 决策规则 算法步骤 对多目标决策问题 max{[pic]=C[pic]} s. t. A[pic]≤b [pic] ≥0 记作[pic] 第一步 求解n个单目标优化问题 [pic] j=1,…,n 解为 [pic]得[pic]= [pic] 理想点 [pic]= ([pic],…,[pic]) 列出支付表——使决策人对取不同的[pic]时各目标的值有直观认识[pic] | |[pic]|… |[pic]|… |[pic]| |[pic|[pic]|… |[pic]|… |[pic]| |] | | | | | | |… |… |… |… |… |… | |[pic|[pic]|… |[pic]|… |[pic]| |] | | | | | | |… |… |… |… |… |… | |[pic|[pic]|… |[pic]|… |[pic]| |] | | | | | | 第二步 由 [pic] = max[pic] 求解 min [pic] s. t. [pic] 等价于解 min入 s. t. λ≥[pic] j=1,…,n [pic] λ≥0 其中 [pic] j=1,…,n [pic][pic] 式中 [pic]从支付表中获得 ·解(2)得 [pic]与 [pic] j=1,…,n 第三步 由决策人判断 降低某个太好的目标 [pic]，下降[pic]再修改约束条件，使 A[pic]≤b [pic]≥0 [pic]: [pic]=[pic]-[pic] [pic]≥[pic] j=1,…,n j≠[pic] 以[pic]取代[pic]，令[pic]=0重复第二步 三、优缺点： 直观; 修改有针对性; [pic]较难定 §11.5 调和解(Compromise solution)和移动理想点法 一、基本概念(思路) 1.调和解 [pic] 在求解MODP: [pic][pic] 时 [pic](或[pic]), W , p要由决策人确定 其中 ·由单调性假设，[pic]=[pic][pic] j=1,…,n可以求得 ·W可由决策人设定 而P则很难设定 因此，给定权向量W，定义调和解集 [pic] = {[pic]|[pic]是给定W时[pic][pic]的解} 它是非劣解的子集, 即 [pic]([pic] 2.各目标偏差的规范化 记[pic]= [pic][pic] 用[pic]使偏差无量纲、归一化，否则[pic]量纲、单位的选取有关 二、求解步骤 第一步 由决策人估计权W 第二步 [pic]= [pic][pic] [pic]=[pic][pic] 第三步 构造调和集 求解 [pic][pic] p=1,2,∞ 其中 [pic][pic] [pic][[pic]][pic] [pic][pic] 第四步 若能从[pic]中找出BCS，则结束 第五步 寻找新的理想点 令 [pic]=[pic] 返回第二步. §11.6 SEMOP(多目标问题的序贯解法) 一、思路与记号 目的为区间 |目的类|目的表达式 |偏差测度 [pic] | |型 | | | |有上界|[pic]≤[pic] |[pic]/[pic] | |有下界|[pic]≥[pic] |[pic]/[pic] | |给定值|[pic]= [pic] |[pic] | |区间内|[pic]≤[pic]≤[pic]|[pic] | |区间外|[pic]≤[pic],[pic]|[pic] | | |≥[pic] | | ·n个目标分为两类: [pic]：加约束的r个目标的下标集合； [pic]=J[pic] J={1,2,…,n} [pic]：X中的子集，其中的[pic]使 (j([pic], [pic]在标定区间内 求解min{[pic]} s. t. [pic] 将解[pic]与 [pic] j=1,…,n送决策人判断 为了向决策人提供必要信息需解(n-r)个辅问题 min{[pic]} s. t. [pic] 其中, [pic]=1,…,n-r p是[pic]中第[pic]个元素在J中的序号 [pic]是j([pic]以及j=p的[pic]均严格处于标定的目的区间内 二、解题步骤 第一步 由决策人确定r个应严格限定值域的目标，并给出这r个目标的目的区间，这r个目标的序 号构成集合[pic] 第二步 i, 解主问题 min{[pic]} s. t. [pic] ii, 解n-r个辅问题 min{[pic]} s. t. [pic] 得出[pic]与 [pic] j=1,…,n 和 [pic]与 [pic] j=1,…,n [pic]=1,…,n-r 第三步 由决策人对第二步结果作判断 基对[pic]满意则停止 若 不满意则q=q+1返回第一步 三、优缺点 1.可用于非单调区间 2.容易反映目标间的矛盾关系 3.非线性规划问题求解困难,没有规范化的步骤保证收敛 §11.7Geoffrion法 一、思路 用Frank-Wolfe法解线性约束的非线性规划问题 max v([pic]) (0) s. t. [pic] 是在[pic] 处，以一阶Taylor展开[pic]线性逼接v([pic])[记作v([pic])]: [pic]= v([pic]) + [[pic]][pic]([pic]-[pic]) (1) 求(1)的极大值等价于求解线性规划问题 [pic][[pic]][pic]·[pic] (2) 令(2)的最优解为[pic]，则 i,若 [[pic]][pic]([pic]-[pic]) 是(2)的最优解，迭代停止； ii,若[[pic]][pic]([pic]-[pic])(0, 则从[pic]出发沿[pic]-[pic]方向作一维搜索 即求 [pic]v([pic]+[pic]([pic]-[pic]))的最优解[pic] 只要 [pic](0足够小, 必有 v([pic])(v([pic]) 式中 [pic]= [pic]+[pic]([pic]-[pic]) 对[pic]，重复上述步骤，可得原问题(0)的最优解 [pic]虽属未知，但[pic]=[pic] [pic] 除以[pic], 得[pic][pic] 其中，[pic](-[pic] j=1,…,n 二、求解步骤 2. 三、优缺点 1.只要决策者心目中的效用函数确实存在，并能给出各点的边际置换率，不必给出具体 的 效用函数值。 2.只适用于线性约束的多目标规划 3.每次迭代 都有所增加，收敛性有保证 但在实际上所得到的解的优劣取决于决策人提供的局部偏好信息的准确性。 §11.8 代理值置换法(Surrogate worth Trade-off Method) 一、思路： ·置换率：在某个非劣点处若要提高某一目标值一个单位，必须使另一目标降低多少，( 设 其他目标函数值不变) 置换率给出了非常有用的信息: 如决策人愿意进行这种置换，说明该方向上有决策人更喜爱的非劣解。 二、求解步骤 第一步：产生非劣解的有代表性的子集 任选一种方法去求得非劣解的有代表性的子集。 不失一般性，选[pic]作为参考目标，构成不等式约束问题: min [pic] (1) s. t. [pic] i=1,…,m [pic] j=1,…,n-1 其中, [pic] [pic] [pic] 为了便于比较，最好选用重要目标或其计量单位是决策人所熟悉的目标作为目标n。 第二步：获得置换信息 在求解(1)时，可以得到 [pic] j=1,…,n-1 其中[pic]是(1)的解，[pic] 是(1)的Kuhn-Tucker乘子， 就是在[pic]处的置换率 第三步：了解决策人的偏好 把第二步计算结果递交给决策人，要决策人回答是否愿意进行这种调整，愿意到何种 程度，并据以构造代用值函数[pic] j=1,…,n-1 +10 非常愿意增加[pic]个单位的[pic]减去一个单位的[pic] -10 非常愿意减少 [pic]个单位的[pic]以提高 [pic]一个单位 第四步：寻求最佳调和解 当某个[pic]使 [pic]=0 j=1,…,n-1时, [pic]为最佳调和解. 若在第一步生成的非劣点中不包含[pic]，可用多元回归法构造代理值函数[pic] 令[pic]=0 即 [pic]=0 求解联列方程 得 [pic] 可用这组 [pic]代入(1)求得[pic] .
第十一章 多目标决策_