7 目标规划(new)_867103354.ppt

线性规划与目标规划 线性规划通常考虑一个目标函数 问题简单 目标规划考虑多个目标函数 问题复杂 线性规划 目标规划 目标规划 某企业生产甲 乙两种产品 需要用到A B C三种设备 关于产品的盈利与使用设备的工时及限制如下表所示 例1生产安排问题 问该企业应如何安排生产 使得在计划期内总利润最大 1 线性规划建模 设甲 乙产品的产量分别为x1 x2 建立线性规划模型 用单纯形法求解 得到最优解 2 目标规划建模 在上例中 企业的经营目标不仅要考虑利润 还需要考虑多个方面 因此增加下列因素 目标 力求使利润指标不低于1500元 考虑到市场需求 甲 乙两种产品的产量比应尽量保持1 2 设备A为贵重设备 严格禁止超时使用 设备C可以加班 设备B既要求充分利用 又尽可能不加班 在重要性上 设备B是设备C的3倍 从上述问题可以看出 仅用线性规划方法是不够的 需要借助于目标规划的方法进行建模求解 某汽车销售公司委托一个广告公司在电视上为其做广告 汽车销售公司提出三个目标 例2汽车广告费问题 广告公司必须决定购买两种类型的电视广告展播各多少分钟 第一个目标 至少有40万高收入的男性公民 记为HIM 看到这个广告 第二个目标 至少有60万一般收入的公民 记为LIP 看到这个广告 第三个目标 至少有35万高收入的女性公民 记为HIW 看到这个广告 广告公司可以从电视台购买两种类型的广告展播 足球赛中插播广告和电视系列剧插播广告 广告公司最多花费60万元的电视广告费 每一类广告展播每分钟的花费及潜在的观众人数如下表所示 3 尝试线性规划建模 设x1 x2分别是足球赛和电视系列剧中插播的分钟数 按照要求 可以列出相应的线性规划模型 用单纯形法求解 会发现该问题不可行 4 线性规划建模局限性 线性规划要求所求解的问题必须满足全部的约束 而实际问题中并非所有约束都需要严格的满足 线性规划只能处理单目标的优化问题 而对一些次目标只能转化为约束处理 但在实际问题中 目标和约束是可以相互转化的 处理时不一定要严格区分 线性规划在处理问题时 将各个约束 也可看作目标 的地位看成同等重要 而在实际问题中 各个目标的重要性即有层次上的差别 也有在同一层次上不同权重的差别 线性规划寻求最优解 而许多实际问题只需要找到满意解就可以了 目标规划的数学模型 为了克服线性规划的局限性 目标规划采用如下手段 1 设置偏差变量 2 统一处理目标与约束 3 目标的优先级与权系数 目标规划的基本概念 目标值 理想值 决策者事先对每个目标给出的估计值 1 设置偏差变量 用偏差变量 Deviationalvariables 来表示实际值与目标值之间的差异 令 超出目标的差值 称为正偏差变量 未达到目标的差值 称为负偏差变量其中与至少有一个为0 约定如下 当实际值超过目标值时 有当实际值未达到目标值时 有当实际值与目标值一致时 有 2 统一处理目标与约束 在目标规划中 约束可分两类 一类是对资源有严格限制的 称为刚性约束 HardConstraint 绝对约束 例如在用目标规划求解例1中设备A禁止超时使用 则有刚性约束 另一类是可以不严格限制的 连同原线性规划的目标 构成柔性约束 SoftConstraint 目标约束 例如在求解例1中 我们希望利润不低于1500元 则目标可表示为 求解例1中甲 乙两种产品的产量尽量保持1 2的比例 则目标可表示为 设备C可以适当加班 则目标可表示为 设备B既要求充分利用 又尽可能不加班 则目标可表示为 从上面的分析可以看到 如果希望不等式保持大于等于 则极小化负偏差 如果希望不等式保持小于等于 则极小化正偏差 如果希望保持等式 则同时极小化正 负偏差 3 目标的优先级与权系数 在目标规划模型中 目标的优先分为两个层次 第一个层次是目标分成不同的优先级 在计算目标规划时 必须先优化高优先级的目标 然后再优化低优先级的目标 通常以P1 P2 表示不同的因子 并规定Pk Pk 1 第二个层次是目标处于同一优先级 但两个目标的权重不一样 因此两目标同时优化 用权系数的大小来表示目标重要性的差别 4 目标规划的目标函数 由各目标约束的正 负偏差变量及其相应的优先因子 权系数组成 不含决策变量xi 当每一目标值确定后 决策者的要求是尽可能缩小偏差 所以目标规划的目标函数总是极小化 目标线性规划的一般模型 目标线性规划模型的一般数学表达式为 解在例1中设备A是刚性约束 其余是柔性约束 首先 最重要的指标是企业的利润 将它的优先级列为第一级 其次 甲 乙两种产品的产量保持1 2的比例 列为第二级 再次 设备B和C的工作时间要有所控制 列为第三级 设备B的重要性是设备C的三倍 因此它们的权重不一样 由此可以得到相应的目标规划模型 目标规划模型的建立 用目标规划方法求解例1 练习题 某彩电组装厂生产A B C三种规格电视机 装配工作在同一生产线上完成 三种产品装配时的工时消耗分别为6小时 8小时和10小时 生产线每月正常工作时间为200小时 三种产品销售后 每台可获利分别为500元 650元和800元 每月销售量预计为12台 10台 6台 该厂经营目标如下 P1 利润指标为每月16000元 P2 充分利用生产能力 P3 加班时间不超过24小时 P4 产量以预计销量为标准 为确定生产计划 请建立该问题的目标规划模型 第二节目标规划的求解方法 一 图解法 x1 x2 l1 l2 O C B A l3 D l4 1 l1与l2形成的可行域OABC 2 先满足P1 OD线段 E 3 再满足P2 ED线段 满意解 E 500 11 500 11 D 360 7 360 7 150 50 100 50 100 150 x1 x2 l1 l2 O C B A l3 D E F l4 1 绝对约束 可行域OABD 2 满足P1 三角形ABF 3 考虑P2 ABF与OD的最接近点F 满意解 F 40 200 3 50 100 150 50 100 150 A D C B F E 线性目标规划的序贯式算法 基本思想 将目标规划模型按照各目标的优先等级次序 将原目标规划问题依次分解为一系列单目标规划问题分别求其最优解 要求 在求解某一优先级单目标规划问题时 以不破坏所有比它优先的 已满足了的目标为前提 为此 把每一优先级求得的目标值作为新的约束加到优先级在它之后的每一个单目标问题中 步骤 第1步 令i 1 i表示当前正在考虑的优先级别 建立仅含Pi级目标的线性规划单目标模型 i P1是指仅考虑与P1级目标有关的约束条件 第2步 用单纯形法 或其他合适的求解方法 求解第i级单目标规划 得到minzi zi 为原目标规划中Pi级目标所能达到的最优解 第3步 置i i 1 若i k0 k0为优先级别总数 则转第6步 否则转第4步 第4步 建立相应于下一个优先级别Pi的单目标规划模型 第5步 转第2步 第6步 最后一个单目标规划的解是原目标规划模型的解 并且向量反映了各目标实现的程度 称之为达成向量 又称zi 为达成解 用序贯式算法解下列目标规划 解 建立P1级目标构成的单目标线性规划 建立P2级目标构成的单目标线性规划模型 最优表为 P2级目标没有被完全满足 建立P3级目标构成的单目标线性规划模型 消列准则 当得到第k优先级单目标模型的最优单纯形表时 该表检验数行中具有负值检验数的非基变量都可以在以后的问题中消除 其相应的列也从表中消除 即在以后各优先级的求解中不再出现 得到最优表 P3级目标没有被完全满足 建立并求解P4级目标所对应的单目标模型 P1级与P4级目标已完全实现 但P2级与P3级没有完全实现 缺点 计算量大 解目标规划的单纯形法 作以下规定 1 以检验数小于等于0为最优准则 步骤 1 建立初始单纯形表 在表中将检验数行按优先因子个数分别列成K行 置k 1 2 检查该行中是否存在正数 且对应的前k 1行的系数为0 若有取其中最大者对应的变量为进基变量 转 3 否则转 5 3 按最小比值规则确定离基变量 当存在两个或两个以上相同的最小比值时 选取具有较高优先级别的变量为离基变量 4 按单纯形法建立新的计算表 返回 2 5 当k K时 计算结束 表中的解为满意解 否则置k k 1 返回 2 求解下列目标规划问题 1 1 1 1 灵敏度分析 改变目标优先等级的分析 最优表为 新的最优表为 满意解不变 最优表为 在原最优表中将P1行与P3行交换得 1 3 应用举例 某厂计划生产A B C三种产品 有关资源消耗与产品库存费用如下表 根据市场预测 各个阶段每种产品的市场需求量为 现工厂领导确定了以下五个优先等级的目标 P1 及时供货 保证需求 并且C产品及时供货的重要性相当于A B产品的1 2倍 P2 尽量使加工设备的负荷均衡 P3 流动资金占用量不超过限额 P4 稀有材料消耗量不超过限额 P5 产品的库存费用不超过限额 假设计划初期及期末各种产品的库存量均为0 试用目标规划编制各阶段每种产品生产数量的生产计划 设立决策变量 约束条件 1 及时供货 保证需求 第一阶段 第二阶段 第三阶段 2 各阶段设备负荷均衡 3 各阶段流动资金占用不超过限额 4 各阶段稀有材料消耗 5 各阶段库存费用 目标函数 P1 及时供货 保证需求 并且C产品及时供货的重要性相当于A B产品的1 2倍 P2 尽量使加工设备的负荷均衡 P3 流动资金占用量不超过限额 P4 稀有材料消耗量不超过限额 P5 产品的库存费用不超过限额 满意解 某零售店的职工 除了1名经理外 还雇有1名管理员 2名全日售货员和1名半日售货员 根据统计资料 5名职工每人工作1小时的贡献及本月的工作时间如下表 为鼓励销售 对管理员和两位全日售货员 以他们各自完成销售额的5 5 作为工资收入 为保持一定的工作效率 应限制职工的加班时间 各职工每月不许超过的加班时间也列如下表 经理初步确定了如下6个目标 P1 每月销售额14500元 P2 保证全体职工正常工作时间 P3 管理员每月至少收入170元 P4 经理 管理员和全日售货员甲的加班时间不超过规定时间 P5 全日售货员乙和半日售货员的加班时间不超过规定时间 P6 保证两位全日售货员每月收入分别为87元和52元 问题是为了实现商店目标 怎样合理安排工作时间 设立决策变量 约束条件 1 全月销售额达到14500元 2 保证职工正常工作时间 3 保证管理员 全日售货员甲和乙的收入 4 加班时间限制 目标函数 P1 每月销售额14500元 P2 保证全体职工正常工作时间 P3 管理员每月至少收入170元 P4 经理 管理员和全日售货员甲的加班时间不超过规定时间 P5 全日售货员乙和半日售货员的加班时间不超过规定时间 P6 保证两位全日售货员每月收入分别为87元和52元 求解结果与分析 重新规划 通过分析 经理决定降低销售额目标 由于去年的销售额为11000元 又预计今年销售量能增加9 故决定至少应完成12000元 根据过去经验 在报纸或电台上登广告 每增加100元广告费 销售额可增加2 这个广告效应指标在广告费不超过500元时相对不变 超过后将急剧下降 经理提出以下新的目标 P2 至少完成销售额12000元 P1 保证全体职工正常工作时间 P3 管理员每月至少收入170元 P5 全体职工加班不超过规定时间 P6 力争增加销售额11 即1320元 P7 保证两位全日售货员每月收