运筹学多目标规划.ppt

第二章多目标规划 MultipleObjectiveProgramming 一 多目标决策问题实例 干部评估 德 才兼备教师晋升 教学 科研 论文等购买冰箱 价格 质量 耗电 品牌等球员选择 技术 体能 经验 心理找对象 容貌 学历 气质 家庭状况 1多目标决策简介 二 多目标决策与多目标规划 多目标决策 多目标规划 MultipleObjectiveProgramming 决策变量连续 多准则决策 MultipleCriteriaDecisionMaking 决策变量离散 即有限方案 1多目标决策简介 三 多目标决策与单目标决策区别 点评价与向量评价单目标 方案dj 评价值f dj 多目标 方案dj 评价向量 f1 dj f2 dj fp dj 全序与半序 方案di与dj之间单目标问题 didj多目标问题 除了这三种情况之外 还有一种情况是不可比较大小决策者偏好 多目标决策过程中 反映决策者对目标的偏好 1多目标决策简介 解概念区别 单目标决策的解只有一种 绝对 最优解 多目标决策的解有下面三种情况 绝对最优解 解概念区别 单目标决策的解只有一种 绝对 最优解 多目标决策的解有下面三种情况 数学 外语 专业 解的类型 绝对最优解劣解 如d4劣于d1 有效解 pareto解 非劣解 2多目标规划模型及其解的概念 一 多目标规划举例 例1 喜糖问题 设市场上有甲级糖及乙级糖 单价分别为4元 斤及2元 斤 今要筹办一桩喜事 筹备小组 计划总花费不超过40元 糖的总斤数不少于10斤 甲级糖不少于5斤 问如何确定最佳的采购方案 约束条件 决策变量 甲级糖数量为x1 乙级糖数量为x2 2多目标规划模型及其解的概念 目标函数 何为最佳 1 总花费最小 minf1 x1 x2 4x1 2x2 2 糖的总数量最大 maxf2 x1 x2 x1 x2 3 甲级糖的数量最大 maxf3 x1 x2 x1 2多目标规划模型及其解的概念 例2 投资决策问题 某投资开发公司拥有总资金A万元 今有n 2 个项目可供选择 设投资第i i 1 n 个项目要用资金ai万元 预计可得到收益bi万元 问应如何使用总资金A万元 才能得到最佳的经济效益 约束条件 2多目标规划模型及其解的概念 目标函数 何为最佳的经济效益 1 收益最大 2 投资最少 2多目标规划模型及其解的概念 二 多目标规划的模型 决策变量 目标函数 约束条件 向量数学规划 VectorMathematicalProgramming 2多目标规划模型及其解的概念 多目标规划模型的向量表达形式 记 则模型为 或 2多目标规划模型及其解的概念 一 多目标规划举例二 多目标规划的模型三 多目标规划解的概念 2多目标规划模型及其解的概念 三 多目标规划解的概念 2多目标规划模型及其解的概念 定义1设X R 若对任意X R 均有F X F X 则称X 为问题 VMP 的绝对最优解 其全体记为R ab 0 f1 x f2 x x 绝对最优解示意图 x f 注 绝对最优解往往不存在 2多目标规划模型及其解的概念 定义2设X0 R 若存在另一个可行解X1 R 有F X1 F X0 则称可行解X0相对于X1来说是劣解 注 决策中 劣解不会被考虑 定义3设 R 若不存在X R 使F X F 则称为问题的非劣解 又称有效解 或Pareto解 其全体记为 2多目标规划模型及其解的概念 定义4设 R 若不存在X R 使F X F 则称为问题的弱有效解 其全体记为 注 有效解必是弱有效解 2多目标规划模型及其解的概念 f2 0 f1 D E 劣解与有效解 两个目标的最大化问题 2多目标规划模型及其解的概念 多目标规划 解的关系 定理1 其中为单目标fi X 上最优点集合 2多目标规划模型及其解的概念 多目标规划 解的关系 定理3 定理4 2多目标规划模型及其解的概念 多目标规划 解的关系 例1下图中 R1 x1 R2 x2 2多目标规划模型及其解的概念 多目标规划 解的关系 1多目标决策简介 2多目标规划模型及其解的概念 3多目标规划的解法 多目标规划 3多目标规划的解法 求 有效解或弱有效解 其中 准备工作 目标函数规范化 一 评价函数法 3多目标规划的解法 3多目标规划的解法 3多目标规划的解法 3多目标规划的解法 一 评价函数法1 线性加权和法2 理想点法3 目标规划法二 目标排序法 3多目标规划的解法 三种 3多目标规划的解法 3多目标规划的解法 确定权系数常用方法 特尔菲法 层次分析法 法 法的步骤 以两个目标为例 U F X 1f1 X 2f2 X 3多目标规划的解法 2 方法的出发点 U F X1 U F X2 3多目标规划的解法 方法的几何意义 目标值空间 0 f2 f21 f22 A U minU f11 f12 f1 C B 1 平行直线簇 1f1 2f2 c 2 同一条直线上X1与X2有相同的评价值 即有U F X1 U F X2 3多目标规划的解法 例设有 试用 法求解 解 求解单目标优化问题 得 3多目标规划的解法 一 评价函数法1 线性加权和法 法确定权系数 2 理想点法3 目标规划法二 目标排序法 3多目标规划的解法 2 理想点法 基本思想 X的评价向量F X f1 X f2 X fp X 越接近理想点越好 理想点 一般指由各单目标最优值组成的p维点 0 f1 f2 F X 3多目标规划的解法 理想点法的步骤 1 求理想点 求解p个单目标最优化问题 得理想点 2 检验理想点 绝对最优点 则输出绝对最优解 求解完毕 否则 转 3 3多目标规划的解法 理想点法的步骤 3 作评价函数 4 求解 Note 上述评价函数是严格增函数 故按其求得的解是 VMP 的有效解 3多目标规划的解法 例 设f1 X 3x1 2x2 f2 X 4x1 3x2都要求实现最大 约束集为R X 2x1 3x2 18 2x1 x2 10 x1 x2 0 X R2 试用理想点法求解 解 先分别求解两个单目标问题 3多目标规划的解法 一 评价函数法1 线性加权和法 法确定权系数 2 理想点法3 目标规划法二 目标排序法 3目标规划法 GoalProgramming 是求解多目标规划的一种常用方法 该方法不考虑对各个目标进行极小化或极大化 而是希望在约束条件的限制下 每一目标尽可能地接近于事先给定的目的值 一 目标规划的思想 例 某工厂生产 两种产品 有关数据如下表 决策者在原材料供应受严格限制的基础上 考虑尽量满足如下条件 1 首先 产品 的产量不低于产品 的产量 2 其次 充分利用设备有效台时 不加班 3 再次 利润额不小于56元 二 目标规划的数学模型 1 在每个目标fi X 上预先确定一个希望达到的目标值 得一目标值向量 分析 2 构造评价函数 3 多目标决策问题 单目标问题 其中R为问题的可行域 4 为了求解 3 引入类偏差变量 负偏差 正偏差 可以证明 3 等价于 实际问题中 各目标可赋于不同的优先因子Pj 相同优先因子的两个目标的差别 可分别赋于它们不同的权系数 ij 于是得到目标规划模型 目标规划模型的特点 1 目标函数都是最小化 只有偏差变量和优先因子 不含一般决策变量 2 约束条件中既可包含目标约束 还可包含绝对约束 3 目标约束均为等式 且一般在一个约束中同时含有正 负偏差变量 另外 根据决策者的不同要求 目标函数有三种基本形式 2 要求超过目标值 评价函数为 1 要求恰好达到目标值 评价函数为 3 要求不超过目标值 评价函数为 三 目标规划建模举例 例1 某工厂生产 两种产品 有关数据如下表 决策者在原材料供应受严格限制的基础上 考虑尽量满足如下条件 1 首先 产品 的产量不低于产品 的产量 2 其次 充分利用设备有效台时 不加班 3 再次 利润额不小于56元 例1 某工厂生产 两种产品 有关数据如下表 决策者在原材料供应受严格限制的基础上考虑 1 首先 产品 的产量不低于产品 的产量 2 其次 充分利用设备有效台时 不加班 3 再次 利润额不小于56元 有一纺织厂生产尼龙布和棉布 平均生产能力都是1km h 工厂生产能力为每周80h 根据市场预测 下周最大销售量为 尼龙布为70km 棉布45km 尼龙布利润为2 5元 m 棉布利润为1 5元 m 工厂领导的管理目标如下 P1 保证职工正常上班 避免开工不足 P2 尽量达到最大销售量 P3 尽量减少加班时间 限制加班时间不得超过10h 解 设决策变量x1 x2分别表示尼龙布和棉布的下周计划产量 例2 P100例4 6 四 目标规划的求解 1 图解法 先考虑绝对约束 再考虑目标约束 并令目标约束中的偏差变量为0 作直线 d1 d1 d2 d2 d3 d3 Step1P1 OBC Step2P2 线段ED Step3P3 目标规划的解 线段GD 其中 G 2 4 D 10 3 10 3 注 该例求得最优解 且Z 0 但大多问题可能无法满足所有约束 此时求满意解 例 求解目标规划 分析 1 目标P1 P2 四边形ABCD 2 d3 的权系数大于d4 故优先考虑mind3 四边形ABEF 3 四边形ABEF无法满足d4 0 故选取E为满意解 使d4 尽量小 2 目标规划的单纯形法 与一般单纯形法的区别 1 最优性准则 所有检验数 0 2 检验数的正负 优先取决于P1的系数 其次P2 3 确定进基变量时 其在所有更高级目标函数下的检验数为0 使低级目标上的进基不影响所有高级目标上已获目标值 2 目标规划的单纯形法 步骤 1 建立初始单纯形表 在表中将检验数行按优先因子个数列成K行 置k 1 2 检查该行是否存在负数 且对应的前k 1行的系数是0 若有负数 取最小者对应的变量为进基变量 转3 若无负数 转 5 3 按最小比值规则确定出基变量 当存在两个及以上相同的最小比值时 选取优先级较高的为出基变量 4 按单纯形法进行基变换运算 得新表 转 2 5 当k K时 算法结束 得满意解 否则置k k 1 转 2 3多目标规划的解法 一 评价函数法1 线性加权和法 法确定权系数 2 理想点法3 目标