多目标规划求解方法介绍.ppt

3 3多目标规划求解方法介绍 一 约束法1 基本思想 在多个目标函数中选择一个主要目标作为目标函数 其它目标处理为适当的约束 无妨设为主要目标 对其它各目标可预先给定一个期望值 不妨记为 则有求解下列问题 容易证明 约束法求问题 P 的最优解 其Kuhn Tucker条件与 VP 有效解的K T条件一致 因此 约束法求得的解是有效解 P 问题中各目标函数期望值的取得有多种方法 一种方法是取一点 而取得到下列问题 2 算法一般步骤 考虑上述 VP 问题 为主目标 第一步 1 对 求解单目标问题 得解 2 计算对应的各目标函数值 并对每个函数 求其p个点值中的最大值Mj和最小值mj 得到下表 Mj与mj规定了在有效解集中的取值范围 第二步 选择整数r 1 确定的r个不同阀值 第三步 对 分别求解问题 各目标函数可对应不同的 共有个约束问题 求解后可得到 VP 的一有效解集合 是 VP 有效解集合的一个子集 例6 用约束法求解 设为主目标 第一步 分别求解 得 得 选定r 4 求解于是可得四组解 如图15所示 j 2只有一个 二 分层序列法 基本步骤 把 VP 中的p个目标按其重要程度排一次序 依次求单目标规划的最优解 2 过程 无妨设其次序为先求解得最优值 记再解得最优值 依次进行 直到得最优值则是在分层序列意义下的最优解集合 3 性质 即在分层序列意义下的最优解是有效解 证明 反证 设 但 则必存在使即至少有一个j0 使 由于 即 矛盾 得证 4 进一步讨论 上述方法过程中 当某个问题 Pj 的解唯一时 则问题的求解无意义 因为解都是唯一的 实际求解时 有较宽容意义下的分层序列法 取为预先给定的宽容值 整个解法同原方法类似 只是取各约束集合时 分别取为 三 功效系数法 设目标为 其中 要求min 要求max 由于量纲问题 处理目标之间的关系时往往带来困难 1 功效系数法 针对各目标函数 用功效系数表示 俗称 打分 满足 或使最满意时 最不满意时 即最差时 2 常用的两种产生功效系数的方法 1 线性型 设 由于时求 令故取又时求 令故取 2 指数型 先讨论求最大的函数 考虑 显然 有如下性质 10 当充分大时 20 是的严格递增函数 为了便于确定b0 b1 选取两个估计值 取为合格值 勉强合格 即可接受 为不合格值 不合格 即不可接受 令并取得解得 代入式 得到功效系数 同理可得当时的功效系数 3 利用功效系数求解问题 VP 设 VP 的功效系数为令构造问题 可以证明 上述问题 P 的最优解 即原问题 VP 的有效解 四 评价函数法 1 理想点法 设 即各单目标问题的最优值 令评价函数 做为目标函数 更一般地 取 从不同角度出发 构造评价函数h F 求问题 得到 VP 的有效解 下面介绍一些评价函数的构造 即不同的方法 2 平方和加权法 求出各单目标问题最优值的下界 期望的最好值 令评价函数其中为预先确定的一组权数 且满足的值为各目标函数的权数 较重要的取值较大 3 范数和加权法 同上面类似 先求出各单目标问题的最优值下界 取 构造评价函数 其中为权系数 且 把此方法与分层序列法结合 取 用于线性多目标规划 即得到目标规划方法 运筹学课中所学的 4 虚拟目标法 仍如 2 3 得到 设取评价函数 5 线性加权法 预先给出每一目标函数的权系数 满足 取评价函数 线性加权法是最常用的方法之一 此法可直接解释 VP 有效解的Kuhn Tucker条件 几何意义 设n 2 p 2 线性加权法解问题 在像空间 P 等价为问题 记 则 及分别对应单目标问题 P1 及 P2 当正数确定后 可得问题 PF 的最优值 如图18 可知对应的原像 可以利用线性加权法来逼近有效解的集合 但不是一种准确寻找所有有效解的有效方法 当 从0 时 可得到非劣解的一个子集 如上图19所示 A B为相应集合的端点 当或时 可能是弱有效解 如下图20 只有 由A到B的其余点为弱有效点 它们对应的原像为弱有效解 例7 其中 F映射是由x1ox2到f1of2空间的一个线性变换 可行域是多胞形H A B C D E F 其A 0 0 T B 6 0 T C 6 2 T D 4 4 T E 1 4 T F 0 3 T是每两条直线的交点 F A MA 0 0 T F B MB 30 6 T F C MC 26 2 T F D MD 12 12 T F E ME 3 15 T F F MF 6 12 T F S 是由F A F B F C F D F E F F 构成的多胞形 如图21 图21 当 即时 即 P2 的解 E 1 4 T 对应F E 3 15 T 当 即时 即 P1 的解 B 6 0 T 对应F B 30 6 T 取 1 即时 问题为 最优解为 C 6 2 T 对应F C 26 2 T 取 1 2 即时 问题为 最优解为 D 4 4 T 对应F D 12 12 T 取 1 3 即时 问题为 最优解为 D 4 4 T 对应F D 12 12 T 6 min max 法 极小 极大法 对策论中常遇到 在最不利情况下找出最有利策略 的问题 即 min max 问题 取评价函数然后求解设得解 是x的函数 如右图 实用中 可以使用下列加权形式 取 令 为了求解方便 可把问题 PMm 等价化为下列数学规划问题 定理 设是的最优解 那么为 PMm 的最优解 反之 若是 PMm 的最优解 且那么是的最优解 证 设是问题的最优解 明显地 有由第一组约束知 由目标mint知取得满足上式的最小值 对 PMm 的任意可行解x 令那么 于是即是问题 PMm 的最优解 反之 考虑是的任意可行解 则 第一组约束 是 PMm 的最优解 可得 对 PMm 的任意可行解x 有于是 即为的最优解 7 乘除法 设 VP 中 对 均有再设求min 求max 取评价函数求解 8 评价函数法的收敛性 考虑 VP h F x 为评价函数 定义 设 10 若满足时 均有 则称h F 是F的严格单调增函数 20 若满足 当时 均有 则称h F 是F的单调增函数 定理 若 10 若h F 是严格单调增函数 则数学规划的最优解 20 若h F 是单调增函数 则数学规划的最优解 证明 10 反证 设 由定义 使由h F 的单调增性质 得到与是 P1 的最优解矛盾 20 反证 设 由定义 使由h F 的单调增性质 得到与是 P2 的最优解矛盾 证毕 可以证明 上述各评价函数 1 理想点法 2 平方和加权法 范数和加权法 4 虚拟目标法 5 线性加权法 7 乘除法均为严格单调增函数 而5 线性加权法 6 min max方法为单调增函数 由此 根据定理可得 方法5 线性加权法 方法6 min max法 得到的解 其它各方法得到的解 9 确定权系数的方法 VP 问题的评价函数h F x 中所需预先给出的权系数 1 老手法 基本过程 邀请一批 老手 专家 有经验的人员等 汲取他们对权系数的意见 加以综合得到权系数 设有k位 老手 为了便于其独立发表意见 将事先准备好的调查表送给他们分别填写 设第i位 老手 对第j个目标给出的权系数为 针对每个目标函数 计算平均权系数 得到下表 计算每一位老手i i 1 2 k 关于平均权系数评价的偏差 第二轮讨论 请最大偏差的老手首先发表意见 经充分讨论以达到对目标重要度的正确认识 消除参数估计中的误解 然后重新评价 如此反复进行 最后达到较为一致的认识 2 方法 对p 2的情形叙述 求的最优解 记 像空间的图形如下 图23 在像空间中 点确定一条直线L1 记其方程为 把上面两个点的坐标代入 得到 若问题 VP 不存在绝对最优解 存在绝对最优解时 上述方程组为一个点 即 则有记 解方程组得 取这组时 线性加权法的最优解对应的像点为 如图23 对于一般情况 p 2 记单目标问题的最优解为 记过p个点做超平面 得方程组当 VP 不存在唯一解时 可确定唯一一组解 共p 1个变量 p 1个方程 该解即为一组权系数 10 有限方案多目标决策问题简介前述的一些方法均是针对无限方案多目标决策问题的模型进行讨论的 也是在这一领域中遇到较多的且要求基础知识较深的一部分内容 1 有限方案多目标决策问题的特征及基本思路 特征 仅含有限多个方案 决策情况的范围只涉及分析 评价的内容 基本解题思路 筛选 排序 集结 综合 筛选 对有限个可能方案 按照某种 些 准则 筛去显著不满意的方案 使下一步所考虑的方案尽可能的少 排序 根据各属性特征给各属性赋权 然后 按照不同的方法 给各方案排序 集结 常用三种技术 对上步得到的不同方法下各方案的排序进行集结 按不同技术的综合评价 有下列三种技术 常用的集结方法 平均值法 求各方案在不同方法下名次的平均值 按平均值的大小得到集结名次 若平均值相同时 则取方差较小的排在前 例8 有四个方案 用四种方法进行排序 得到下表 对各方案两两比较 如xi与xj 若认为xi好于xj的方案多 记为胜 M 否则记为败 X 不优于 Borda法 找各方案 胜 的次数之和 进行集结 Copaland法 找各方案 胜 取正 与 败 取负 次数的代数和 进行集结 例9 同上例 结果如下 综合 上步得到三种技术下的排序 一般仍存在不可比的关系 构造一排序集 当xi优于xj时 记为 否则认为不可比 当时 节点xi位于xj上 这样得到一个偏序结构图 2 决策矩阵和规范化决策矩阵 把各方案xi i 1 2 m 及属性集yj j 1 n 列表得到决策矩阵 其中 方案xi的第j个属性值 向量规范化 化为无量纲值 一般达不到0或1 x1 x4 x5 x2 x3 第1等级 第2等级 第3等级 计算 线性变换规范化 使 若求最大时 效益 求最小时 成本 其它规范化变换 统一变换后的属性 求最大时 求最小时 统一最优时 最劣时 3 权系数的确定 一般采用类似层次分析法中的两两比较判断 构造判断矩阵 用特征根法 或和积法 方根法求特征向量的方法确定权系数 理想最优时 最劣时 4 常用的筛选方案的方法 优选法 利用非劣性概念 两方案比较 某一方案A的各属性不劣