多目标优化方法及实例解析ppt课件

《多目标优化方法及实例解析ppt课件》由会员分享，可在线阅读，更多相关《多目标优化方法及实例解析ppt课件（76页珍藏版）》请在金锄头文库上搜索。

1、第九讲多目标规划方法 多目标规划解的讨论 非劣解多目标规划及其求解技术简介效用最优化模型罚款模型约束模型目标规划模型目标达到法目标规划方法目标规划模型目标规划的图解法求解目标规划的单纯形方法多目标规划应用实例 多目标规划是数学规划的一个分支 研究多于一个的目标函数在给定区域上的最优化 又称多目标最优化 通常记为MOP multi objectiveprogramming 在很多实际问题中 例如经济 管理 军事 科学和工程设计等领域 衡量一个方案的好坏往往难以用一个指标来判断 而需要用多个目标来比较 而这些目标有时不甚协调 甚至是矛盾的 因此有许多学者致力于这方面的研究 1896年法国经济学家V

2、 帕雷托最早研究不可比较目标的优化问题 之后 J 冯 诺伊曼 H W 库恩 A W 塔克 A M 日夫里翁等数学家做了深入的探讨 但是尚未有一个完全令人满意的定义 3 求解多目标规划的方法大体上有以下几种 一种是化多为少的方法 即把多目标化为比较容易求解的单目标或双目标 如主要目标法 线性加权法 理想点法等 另一种叫分层序列法 即把目标按其重要性给出一个序列 每次都在前一目标最优解集内求下一个目标最优解 直到求出共同的最优解 对多目标的线性规划除以上方法外还可以适当修正单纯形法来求解 还有一种称为层次分析法 是由美国运筹学家沙旦于70年代提出的 这是一种定性与定量相结合的多目标决策与分析方法

3、对于目标结构复杂且缺乏必要的数据的情况更为实用 多目标规划模型 一 任何多目标规划问题 都由两个基本部分组成 1 两个以上的目标函数 2 若干个约束条件 二 对于多目标规划问题 可以将其数学模型一般地描写为如下形式 一多目标规划及其非劣解 式中 为决策变量向量 缩写形式 有n个决策变量 k个目标函数 m个约束方程 则 Z F X 是k维函数向量 X 是m维函数向量 G是m维常数向量 1 2 对于线性多目标规划问题 可以进一步用矩阵表示 式中 X为n维决策变量向量 C为k n矩阵 即目标函数系数矩阵 B为m n矩阵 即约束方程系数矩阵 b为m维的向量 即约束向量 多目标规划的非劣解 多目标规划问

4、题的求解不能只追求一个目标的最优化 最大或最小 而不顾其它目标 对于上述多目标规划问题 求解就意味着需要做出如下的复合选择 每一个目标函数取什么值 原问题可以得到最满意的解决 每一个决策变量取什么值 原问题可以得到最满意的解决 在图1中 max f1 f2 就方案 和 来说 的f2目标值比 大 但其目标值f1比 小 因此无法确定这两个方案的优与劣 在各个方案之间 显然 比 好 比 好 比 好 比 好 非劣解可以用图1说明 图1多目标规划的劣解与非劣解 9 而对于方案 之间则无法确定优劣 而且又没有比它们更好的其他方案 所以它们就被称为多目标规划问题的非劣解或有效解 其余方案都称为劣解 所有非劣

5、解构成的集合称为非劣解集 当目标函数处于冲突状态时 就不会存在使所有目标函数同时达到最大或最小值的最优解 于是我们只能寻求非劣解 又称非支配解或帕累托解 效用最优化模型罚款模型约束模型目标达到法目标规划模型 二多目标规划求解技术简介 为了求得多目标规划问题的非劣解 常常需要将多目标规划问题转化为单目标规划问题去处理 实现这种转化 有如下几种建模方法 是与各目标函数相关的效用函数的和函数 方法一效用最优化模型 线性加权法 1 2 思想 规划问题的各个目标函数可以通过一定的方式进行求和运算 这种方法将一系列的目标函数与效用函数建立相关关系 各目标之间通过效用函数协调 使多目标规划问题转化为传统的单

6、目标规划问题 在用效用函数作为规划目标时 需要确定一组权值 i来反映原问题中各目标函数在总体目标中的权重 即 式中 i应满足 向量形式 方法二罚款模型 理想点法 思想 规划决策者对每一个目标函数都能提出所期望的值 或称满意值 通过比较实际值fi与期望值fi 之间的偏差来选择问题的解 其数学表达式如下 或写成矩阵形式 式中 是与第i个目标函数相关的权重 A是由 i 1 2 k 组成的m m对角矩阵 理论依据 若规划问题的某一目标可以给出一个可供选择的范围 则该目标就可以作为约束条件而被排除出目标组 进入约束条件组中 假如 除第一个目标外 其余目标都可以提出一个可供选择的范围 则该多目标规划问题就

7、可以转化为单目标规划问题 方法三约束模型 极大极小法 方法四目标达到法 首先将多目标规划模型化为如下标准形式 在求解之前 先设计与目标函数相应的一组目标值理想化的期望目标fi i 1 2 k 每一个目标对应的权重系数为 i i 1 2 k 再设 为一松弛因子 那么 多目标规划问题就转化为 17 方法五目标规划模型 目标规划法 需要预先确定各个目标的期望值fi 同时给每一个目标赋予一个优先因子和权系数 假定有K个目标 L个优先级 L K 目标规划模型的数学形式为 18 式中 di 和di 分别表示与fi相应的 与fi 相比的目标超过值和不足值 即正 负偏差变量 pl表示第l个优先级 lk lk

8、表示在同一优先级pl中 不同目标的正 负偏差变量的权系数 三目标规划方法 通过前面的介绍和讨论 我们知道 目标规划方法是解决多目标规划问题的重要技术之一 这一方法是美国学者查恩斯 A Charnes 和库伯 W W Cooper 于1961年在线性规划的基础上提出来的 后来 查斯基莱恩 U Jaashelainen 和李 Sang Lee 等人 进一步给出了求解目标规划问题的一般性方法 单纯形方法 目标规划模型目标规划的图解法求解目标规划的单纯形方法 目标规划模型 给定若干目标以及实现这些目标的优先顺序 在有限的资源条件下 使总的偏离目标值的偏差最小 1 基本思想 2 目标规划的有关概念 例1

9、 某一个企业利用某种原材料和现有设备可生产甲 乙两种产品 其中 甲 乙两种产品的单价分别为8万元和10万元 生产单位甲 乙两种产品需要消耗的原材料分别为2个单位和1个单位 需要占用的设备分别为1单位台时和2单位台时 原材料拥有量为11个单位 可利用的设备总台时为10单位台时 试问 如何确定其生产方案使得企业获利最大 由于决策者所追求的唯一目标是使总产值达到最大 这个企业的生产方案可以由如下线性规划模型给出 求x1 x2 使 将上述问题化为标准后 用单纯形方法求解可得最佳决策方案为 万元 生产甲 乙两种产品 有关数据如表所示 试求获利最大的生产方案 但是 在实际决策时 企业领导者必须考虑市场等一

10、系列其它条件 如 超过计划供应的原材料 需用高价采购 这就会使生产成本增加 应尽可能地充分利用设备的有效台时 但不希望加班 应尽可能达到并超过计划产值指标56万元 这样 该企业生产方案的确定 便成为一个多目标决策问题 这一问题可以运用目标规划方法进行求解 根据市场信息 甲种产品的需求量有下降的趋势 因此甲种产品的产量不应大于乙种产品的产量 23 假定有L个目标 K个优先级 K L n个变量 在同一优先级pk中不同目标的正 负偏差变量的权系数分别为 kl kl 则多目标规划问题可以表示为 目标规划模型的一般形式 目标函数 目标约束 绝对约束 非负约束 24 在以上各式中 kl kl 分别为赋予p

11、l优先因子的第k个目标的正 负偏差变量的权系数 gk为第k个目标的预期值 xj为决策变量 dk dk 分别为第k个目标的正 负偏差变量 目标函数 目标约束 绝对约束 非负约束 目标规划数学模型中的有关概念 1 偏差变量在目标规划模型中 除了决策变量外 还需要引入正 负偏差变量d d 其中 正偏差变量表示决策值超过目标值的部分 负偏差变量表示决策值未达到目标值的部分 因为决策值不可能既超过目标值同时又未达到目标值 故有d d 0成立 2 绝对约束和目标约束绝对约束 必须严格满足的等式约束和不等式约束 譬如 线性规划问题的所有约束条件都是绝对约束 不能满足这些约束条件的解称为非可行解 所以它们是硬

12、约束 目标约束 目标规划所特有的 可以将约束方程右端项看作是追求的目标值 在达到此目标值时允许发生正的或负的偏差 可加入正负偏差变量 是软约束 线性规划问题的目标函数 在给定目标值和加入正 负偏差变量后可以转化为目标约束 也可以根据问题的需要将绝对约束转化为目标约束 3 优先因子 优先等级 与权系数一个规划问题 常常有若干个目标 决策者对各个目标的考虑 往往是有主次的 凡要求第一位达到的目标赋予优先因子p1 次位的目标赋予优先因子p2 并规定pl pl 1 l 1 2 表示pl比pl 1有更大的优先权 即 首先保证p1级目标的实现 这时可以不考虑次级目标 而p2级目标是在实现p1级目标的基础上

13、考虑的 依此类推 若要区别具有相同优先因子pl的目标的差别 就可以分别赋予它们不同的权系数 i i 1 2 k 这些优先因子和权系数都由决策者按照具体情况而定 3 优先因子 优先等级 与权系数一个规划问题 常常有若干个目标 决策者对各个目标的考虑 往往是有主次的 凡要求第一位达到的目标赋予优先因子p1 次位的目标赋予优先因子p2 并规定pl pl 1 l 1 2 表示pl比pl 1有更大的优先权 即 首先保证p1级目标的实现 这时可以不考虑次级目标 而p2级目标是在实现p1级目标的基础上考虑的 依此类推 4 目标函数目标规划的目标函数 准则函数 是按照各目标约束的正 负偏差变量和赋予相应的优先

14、因子而构造的 当每一目标确定后 尽可能缩小与目标值的偏离 因此 目标规划的目标函数只能是 a 要求恰好达到目标值 就是正 负偏差变量都要尽可能小 即 b 要求不超过目标值 即允许达不到目标值 就是正偏差变量要尽可能小 即 c 要求超过目标值 也就是超过量不限 但负偏差变量要尽可能小 即 基本形式有三种 29 例2 在例1中 如果决策者在原材料供应受严格控制的基础上考虑 首先是甲种产品的产量不超过乙种产品的产量 其次是充分利用设备的有限台时 不加班 再次是产值不小于56万元 并分别赋予这三个目标优先因子p1 p2 p3 试建立该问题的目标规划模型 分析 题目有三个目标层次 包含三个目标值 第一目

15、标 p1d1 即产品甲的产量不大于乙的产量 第二目标 p2 d2 d2 即充分利用设备的有限台时 不加班 第三目标 p3d3 即产值不小于56万元 例2 在例1中 如果决策者在原材料供应受严格控制的基础上考虑 首先是甲种产品的产量不超过乙种产品的产量 其次是充分利用设备的有限台时 不加班 再次是产值不小于56万元 并分别赋予这三个目标优先因子p1 p2 p3 试建立该问题的目标规划模型 解 根据题意 这一决策问题的目标规划模型是 31 例3 某厂计划在下一个生产周期内生产甲 乙两种产品 已知资料如表所示 1 试制定生产计划 使获得的利润最大 解 设生产甲产品 x1 乙产品 x2 1 32 若在

16、例3中提出下列要求 1 完成或超额完成利润指标50000元 2 产品甲不超过200件 产品乙不低于250件 3 现有钢材3600吨必须用完 试建立目标规划模型 分析 题目有三个目标层次 包含四个目标值 第一目标 p1d1 第二目标 有两个要求即甲d2 乙d3 但两个具有相同的优先因子 因此需要确定权系数 本题可用单件利润比作为权系数即70 120 化简为7 12 第三目标 33 所以目标规划模型为 34 图解法同样适用两个变量的目标规划问题 但其操作简单 原理一目了然 同时 也有助于理解一般目标规划的求解原理和过程 图解法解题步骤如下 1 确定各约束条件的可行域 即将所有约束条件 包括目标约束和绝对约束 暂不考虑正负偏差变量 在坐标平面上表示出来 2 在目标约束所代表的边界线上 用箭头标出正 负偏差变量值增大的方向 目标规划的图解法 3 求满足最高优先等级目标的解 4 转到下一个优先等级的目标 再不破坏所有较高优先等级目标的前提下 求出该优先等级目标的解 5 重复4 直到所有优先等级的目标都已审查完毕为止 6 确定最优解和满意解 35 例4 用图解法求解目标规划问题 0 1234567