多目标规划课件.ppt

第四章多目标规划 同时考虑多个决策目标时 称为多目标规划问题 4 0引言从线性规划问题可看出 线性规划只研究在满足一定条件下 单一目标函数取得最优解 而在企业管理中 经常遇到多目标决策问题 如拟订生产计划时 不仅考虑总产值 同时要考虑利润 产品质量和设备利用率等 这些指标之间的重要程度 即优先顺序 也不相同 有些目标之间往往相互发生矛盾 线性规划致力于某个目标函数的最优解 这个最优解若是超过了实际的需要 很可能是以过分地消耗了约束条件中的某些资源作为代价 线性规划把各个约束条件的重要性都不分主次地等同看待 这也不符合实际情况 求解线性规划问题 首先要求约束条件必须相容 如果约束条件中 由于人力 设备等资源条件的限制 使约束条件之间出现了矛盾 就得不到问题的可行解 但生产还得继续进行 这将给人们进一步应用线性规划方法带来困难 为了弥补线性规划问题的局限性 解决有限资源和计划指标之间的矛盾 在线性规划基础上 建立目标规划方法 从而使一些线性规划无法解决的问题得到满意的解答 4 1多目标规划问题多目标规划问题的提出在实际问题中 可能会同时考虑几个方面都达到最优 产量最高 成本最低 质量最好 利润最大 环境达标 运输满足等 多目标规划能更好地兼顾统筹处理多种目标的关系 求得更切合实际要求的解 目标规划可根据实际情况 分主次地 轻重缓急地考虑问题 例4 1 一个企业需要同一种原材料生产甲乙两种产品 它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同 从而获得的利润也不相同 如下表 那么 该企业应如何安排生产计划 才能使获得的利润达到最大 如何安排生产 使利润达到最大 用单纯形法求得最优解 20 20 最优值 200 百元 问题 该厂提出如下目标 1 利润达到280百元 2 钢材不超过100吨 工时不超过120小时 如何安排生产 例4 2 某车间有A B两条设备相同的生产线 它们生产同一种产品 A生产线每小时可制造2件产品 B生产线每小时可制造1 5件产品 如果每周正常工作时数为45小时 要求制定完成下列目标的生产计划 1 生产量达到210件 周 2 A生产线加班时间限制在15小时内 3 充分利用工时指标 并依A B产量的比例确定重要性 例4 3 某电器公司经营的唱机和录音机均有车间A B流水作业组装 数据见下表 要求按以下目标制订月生产计划 1 库存费用不超过4600元 2 每月销售唱机不少于80台 3 不使A B车间停工 权数由生产费用确定 4 A车间加班时间限制在20小时内 5 每月销售录音机为100台 6 两车间加班时数总和要尽可能小 权数由生产费用确定 多目标优先级先将目标等级化 将目标按重要性的程度不同依次分成一级目标 二级目标 最次要的目标放在次要的等级中 目标优先级作如下约定 对同一个目标而言 若有几个决策方案都能使其达到 可认为这些方案就这个目标而言都是最优方案 若达不到 则与目标差距越小的越好 目标优先级作如下约定 不同级别的目标的重要性是不可比的 即较高级别的目标没有达到的损失 任何较低级别的目标上的收获都不可弥补 所以在判断最优方案时 首先从较高级别的目标达到的程度来决策 然后再其次级目标的判断 目标优先级作如下约定 同一级别的目标可以是多个 各自之间的重要程度可用数量 权数 来描述 因此 同一级别的目标的其中一个的损失 可有其余目标的适当收获来弥补 多目标规划解的概念 若多目标规划问题的解能使所有的目标都达到 就称该解为多目标规划的最优解 若解只能满足部分目标 就称该解为多目标规划的次优解 若找不到满足任何一个目标的解 就称该问题为无解 例4 4 例4 1 一个企业需要同一种原材料生产甲乙两种产品 它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同 从而获得的利润也不相同 如下表 那么 该企业应如何安排生产计划 才能使获得的利润达到最大 如何安排生产 使利润达到最大 前面已经求得最优解 20 20 最优值 200 百元 问题 该厂提出如下目标 1 利润达到280百元 2 钢材不超过100吨 工时不超过120小时 如何安排生产 对例4 1的问题 设超过一吨钢材与超过5个工时的损失相同 现有四个方案进行比较优劣 目标 1 利润达到280百元 2 钢材不超过100吨 工时不超过120小时 对于 1 只有方案4没有完成 排除方案4 对于 2 只有方案2达到了 因此方案2是最优 目标 1 利润达到280百元 2 钢材不超过100吨 工时不超过120小时 方案1与方案3都达到了 1 又没达到 2 方案1与 2 的差距 工时损失 110 100 5 130 120 1 60 方案3与 2 的差距 工时损失 0 5 190 120 1 70方案1优于方案3 方案2优于方案1优于方案3优于方案4 例4 4 继续上例 目标 1 利润达到280百元 2 钢材不超过100吨 工时不超过120小时 对于 1 三个方案都没有完成 但方案3离目标最远 方案3最差 方案1与 2 的差距 工时损失 108 100 5 130 120 1 50 方案2与 2 的差距 工时损失 0 5 160 120 1 40方案2优于方案1方案2优于方案1优于方案3 4 2多目标规划问题的数学模型多目标的处理为了将不同级别的目标的重要性用数量表示 引进P1 P2 用它表示一级目标 二级目标 的重要程度 规定P1 P2 P3 称P1 P2 为级别系数 约束方程的处理差异变量 决策变量x超过目标值b的部分记d 决策变量x不足目标值b的部分记d d 0 d 0且x d d b 多目标的综合若决策目标中规定x b 当d 0时目标才算达到 多目标的综合若决策目标中规定x b 当y 0时目标才算达到 若决策目标中规定x b 当d 0时目标才算达到 多目标的综合若决策目标中规定x b 当y 0时目标才算达到 若决策目标中规定x b 当y 0时目标才算达到 若决策目标中规定x b 当d d 0时目标才算达到 例4 5 例4 4 解 引进级别系数P1 1 利润达到280百元 P2 2 钢材不超过100吨 工时不超过120小时 权数之比5 1 数学模型 目标函数 MinS P1d1 P2 5d2 d3 约束方程 6X1 4X2 d1 d1 2802X1 3X2 d2 d2 1004X1 2X2 d3 d3 120X1 X2 di di 0 i 1 2 3 例4 6 例4 2 某车间有A B两条设备相同的生产线 它们生产同一种产品 A生产线每小时可制造2件产品 B生产线每小时可制造1 5件产品 如果每周正常工作时数为45小时 要求制定完成下列目标的生产计划 1 生产量达到210件 周 2 A生产线加班时间限制在15小时内 3 充分利用工时指标 并依A B产量的比例确定重要性 解 设A B生产线每周工作时间为X1 X2 A B的产量比例2 1 5 4 3目标函数 MinS P1d1 P2d2 4P3d3 3P3d4 约束方程 2X1 1 5X2 d1 d1 210 生产量达到210件 周 X1 d2 d2 60 A生产线加班时间限制在15小时内 X1 d3 d3 45 充分利用A的工时指标 X2 d4 d4 45 充分利用B的工时指标 X1 X2 di di 0 i 1 2 3 4 A B的产量比例2 1 5 4 3目标函数 MinS P1d1 P2d2 4P3d3 3P3d4 约束方程 2X1 1 5X2 d1 d1 210X1 d2 d2 60X1 d3 d3 45X2 d4 d4 45X1 X2 di di 0 i 1 2 3 4 例4 7 例4 3 1 库存费用不超过4600元 2 每月销售唱机不少于80台 3 不使A B车间停工 权数由生产费用确定 4 A车间加班时间限制在20小时内 5 每月销售录音机为100台 6 两车间加班时数总和要尽可能小 权数由生产费用确定 解 设每月生产唱机 录音机X1 X2台 且A B的生产费用之比为100 50 2 1 目标函数 MinS P1d1 P2d2 2P3d4 P3d5 P4d41 P5d3 P5d3 2P6d4 P6d5 约束方程 50X1 30X2 d1 d1 4600 库存费用不超过4600元 X1 d2 d2 80 每月销售唱机不少于80台 X2 d3 d3 100 每月销售录音机为100台 2X1 X2 d4 d4 180 不使A车间停工 X1 3X2 d5 d5 200 不使B车间停工 d4 d41 d41 20 A车间加班时间限制在20小时内 X1 X2 di di d41 d41 0 i 1 2 3 4 5 目标函数 MinS P1d1 P2d2 2P3d4 P3d5 P4d41 P5d3 P5d3 2P6d4 P6d5 约束方程 50X1 30X2 d1 d1 4600X1 d2 d2 80X2 d3 d3 1002X1 X2 d4 d4 180X1 3X2 d5 d5 200d4 d41 d41 20X1 X2 di di d41 d41 0 i 1 2 3 4 5 4 3多目标规划问题的求解多目标规划问题的图解法例4 8MinS d1 X1 2X2 d1 d1 10X1 2X2 6X1 X2 4X1 X2 d1 d1 0 x1 x2 0 4 6 8 10 2 1 3 4 2 X1 2X2 6 x1 x2 0 4 6 8 10 2 1 3 4 2 X1 X2 4 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 2x2 10 5 d1 d1 A B 2 2 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 2x2 10 5 d1 d1 A B 2 2 当MinS d1 达到时d1 0 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 2x2 10 5 d1 A B 2 2 当MinS d1 达到时d1 0 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 2x2 d1 10d1 2 5 d1 A B 2 2 当MinS d1 达到时d1 0 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 2x2 d1 10d1 4 5 d1 A B 2 2 有无穷多解 点 0 3 和点 2 2 连线上的点都是最优解 0 3 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 2x2 d1 10d1 6 5 d1 A B 2 2 有无穷多解 点 4 0 和点 0 2 连线上的点都是最优解 0 3 4 0 0 2 x1 x2 0 4 6 8 10 2 1 3 4 2 x1 2x2 d1 10d1 7 5 d1 A B 2 2 有无穷多解 点 1 1 和点 0 3 2 3 0 连线上的点都是最优解 0 3 4 0 1 1 例4 9MinS P1d1 P2d2 5P3d3 P3d1 X1 X2 d1 d1 40X1 X2 d2 d2 50X1 d3 30X2 d4 30X1 X2 dI dI 0 I 1 2 3 4 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1 d1 X1 X2 40 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1 d1 d2 d2 X1 X2 50 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1 d1 d2 d2 d3 X1 30 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1 d1 d2 d2 d3 d4 X2 30 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1 d2 d2 d3 d4 Mind1 0可行域如图 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1 d2 d3 d4 Mind2 0可行域如图 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1 d2 d4 Mind3 0线段AB是可行域 A B x1 x2 0 20 30 40 50 10 10 30 40 20 50 d2 d4 Mind1 0P 30 10 唯一最优解 d2 10d4 20 P 例4 10MinS P1d1 P2d2 P3d3 P3d4 5X1 10X2 d1 d1 1002X1 X2 d2 d2 14X1 d3 d3 6X2 d4 d4 10X1 X2 di di 0 i 1 2 3 4 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1 d1 5X1 10X2 100 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1 d1 d2 d2 2X1 X2 14 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1 d1 d2 d2 d3 d3 X1 6 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1 d1 d2 d2 d3 d3 d4 d4 X2 10 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1 d2 d2 d3 d3 d4 d4 Mind1 0 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1 d2 d3 d3 d4 d4 Mind2 0可行域如图 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1 d2 d3 d4 d4 Mind3 0可行域为空如图 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1 d2 d3 d4 Mind3 0M