目标规划的数学模型ppt课件

第四章目标规划 第一节目标规划的数学模型 本节内容的安排 目标规划 GoalProgramming 简记为GP 是在线性规划的基础上 为适应经济管理中多目标决策的需要而逐步发展起来的一个运筹学分支 是实行目标管理这种现代化管理技术的一个有效工具 目标规划的有关概念和模型最早在1961年由美国学者查恩斯 A Charnes 和库伯 W W Coopor 在他们合著的 管理模型和性规划的工业应用 一书中提出 以后这种模型又先后经尤吉 艾吉里 Yuji Ijiri 等人的不断完善改进 1976年伊格尼齐奥 J P Ignizio 发表了 目标规划及其扩展 一书 系统归纳总结了目标规划的理论和方法目前研究较多的有线性目标规划 非线性目标规划 线性整数目标规划和0 1目标规划等 本章主要研究线性目标规划 线性规划只研究在满足一定条件下 单一目标函数取得最优解 线性规划致力于某个目标函数的最优解 缺点是 这个最优解若是超过了实际的需要 很可能是以过分地消耗了约束条件中的某些资源作为代价 线性规划把各个约束条件的重要性都不分主次地等同看待 这也不符合实际情况 从线性规划问题可看出 而在企业管理中 经常遇到多目标决策问题 如拟订生产计划时 不仅考虑总产值 同时要考虑利润 产品质量和设备利用率等 这些指标之间的重要程度 即优先顺序 也不相同 有些目标之间往往相互发生矛盾 求解线性规划问题 首先要求约束条件必须相容 如果约束条件中 由于人力 设备等资源条件的限制 使约束条件之间出现了矛盾 就得不到问题的可行解 但实际中出现矛盾时 生产还得继续进行 这将给人们进一步应用线性规划方法带来困难 目标规划正是在线性规划的基础上为适应这种复杂的多目标最优决策的需要 而发展起来的 它对众多的目标分别确定一个希望实现的目标值然后按目标的重要程度 级别 依次进行考虑与计算 以求得最接近各目标预定数值的方案 如果某些目标由于种种约束不能完全实现 它也能指出目标值不能实现的程度以及原因 以供决策者参考 引例1 某生物药厂需在市场上采购某种原料 现市场上有甲 乙两个等级 单价分别为2千元 kg和1千元 kg 要求采购的总费用不得超过20万元 购得原料的总重量不少于100kg 而甲级原料又不得少于50kg 问如何确定最好的采购方案 即用最少的钱 采购最多数量的原料 一 问题的提出 目标函数为 约束条件有 分析 这是一个含有两个目标的数学规划问题 设x1 x2分别为采购甲级 乙级原材料的数量 单位 kg y1为花掉的资金 y2为所购原料总量 则 若只考虑花钱最少 则显然属于线性规划问题 由 1 3 至 6 构成它的数学模型 若只考虑采购数量最多 则也属于线性规划问题 由 2 3 至 6 构成它的数学模型 某厂计划在下一个生产周期内生产甲 乙两种产品 已知资料如表所示 试制定生产计划 使获得的利润最大 同时 根据市场预测 甲的销路不是太好 应尽可能少生产 乙的销路较好 可以扩大生产 在此基础上使产量达到最大 试建立此问题的数学模型 引例2 设 甲 乙产品的产量分别为X1 X2 一般有 maxZ 70 x1 120 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 同时 maxZ1 70 x1 120 x2maxZ2 x1maxZ3 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 显然 这是一个多目标规划问题 用线性规划方法很难找到最优解 对于多目标问题 线性规划很难为其找到最优方案 极有可能出现 第一个方案使第一目标的结果优于第二方案 而对于第二目标 第二方案优于第一方案 就是说很难找到一个方案使所有目标同时达到最优 特别当约束条件中有矛盾方程时 线性规划方法是无法解决的 实践中 人们转而采取 不求最好 但求满意 的策略 在线性规划的基础上建立一种新的数学规划方法 目标规划 目标规划是在线性规划的基础上 为适应经济管理中多目标决策的需要而逐步发展起来的一个分支 2 线性规划求最优解 目标规划是找到一个满意解 1 线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题 而目标规划是多个目标决策 可求得更切合实际的解 二目标规划概述 一 目标规划与线性规划的比较 3 线性规划中的约束条件是同等重要的 是硬约束 而目标规划中有轻重缓急和主次之分 即有优先权是软约束 4 线性规划的最优解是绝对意义下的最优 但需花去大量的人力 物力 财力才能得到 实际过程中 只要求得满意解 就能满足需要 或更能满足需要 因此 目前 目标规划已经在经济计划 生产管理 经营管理 市场分析 财务管理等方面得到了广泛的应用 二 目标规划的基本概念 多目标规划问题的一般形式如下 简记为 GP1 矩阵表示为 其他情况 如目标函数为miny 约束条件为 都可作适当的变换 调整为上面的形式 对于多目标问题中大多的情况是 由于多目标之间存在相互矛盾 最优解往往不可能存在 这就要求我们退而求其次 根据目标之间的相对重要程度 分等级和权重 求出相对最优解 有效解 满意解 为此引入以下概念 对目标函数和约束条件作适当处理 目标值和偏差变量目标约束和绝对约束达成函数 即目标规划中的目标函数 优先因子 优先等级 与优先权系数满意解 具有层次意义的解 目标规划的基本概念 目标规划通过引入目标值和偏差变量 将原目标函数和原约束条件转化为目标约束 目标值 是指预先给定的某个目标的一个期望值 实际值或决策值 是指当决策变量xj选定以后 目标函数的对应值 偏差变量 事先无法确定的未知数 是指实际值和目标值之间的差异 记为d d 0 正偏差变量 表示实际值超过目标值的部分 记为d 负偏差变量 表示实际值未达到目标值的部分 记为d 1 目标值和偏差变量 当完成或超额完成规定的指标则表示 d 0 d 0当未完成规定的指标则表示 d 0 d 0当恰好完成指标时则表示 d 0 d 0 在一次决策中 实际值不可能既超过目标值又未达到目标值 故有d d 0 并规定d 0 d 0 d d 0成立 实际操作中 当目标值确定时 所做的决策只可能出现以下三种情况 即由d 和d 所构成的3种不同组合表示的含义 1 目标约束是目标规划中所特有的 可把约束条件的右端项看作要追求的目标值 也可以对目标函数规定一个目标值 在达到此目标值时允许发生正或负偏差 因此可在这些约束或目标函数中加入正 负偏差变量 引入目标值和正 负偏差变量后 把原目标函数和原约束条件转化成约束方程 都并入到约束条件中 我们称这类具有机动余地的约束为目标约束 也称为软约束 2 目标约束和绝对约束 2 绝对约束 系统约束 是指必须严格满足的等式或不等式约束 如线性规划中的所有约束条件都是绝对约束 否则无可行解 所以 绝对约束是硬约束 例如 在下例中 规定Z1的目标值为50000 正 负偏差为d d 则目标函数可以转换为目标约束 即70 x1 120 x2 50000 同样 若规定产品甲期望值是200件 产品乙期望值是250件 则有 若规定3600的钢材必须用完 原式9x1 4x2 3600则变为 将原目标函数转化为目标约束 需引入目标值和正 负偏差变量 maxZ1 70 x1 120 x2maxZ2 x1maxZ3 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 将原约束条件转化为目标约束 maxZ1 70 x1 120 x2maxZ2 x1maxZ3 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 一个规划问题常常有若干目标 但决策者在要求达到这些目标时 是有主次或轻重缓急的不同 优先因子Pk是将决策目标按其重要程度排序并表示出来 3 优先因子 优先等级 与优先权系数 要求第一位达到的目标赋予优先因子P1 次位的目标赋予优先因子P2 并规定Pk Pk 1 表示Pk比Pk 1有更大的优先权 即首先保证P1级目标的实现 这时可不考虑次级目标 而P2级目标是在实现P1级目标的基础上考虑的 依此类推 即不管Pk 1乘以一个多大的正数M 总成立Pk MPk 1 表示Pk比Pk 1具有绝对的优先权 因此 不同的优先因子代表着不同的优先等级 若要进一步区别具有相同优先级的多个目标 则可分别赋予它们不同的权系数 j j可取一确定的非负实数 根据目标的重要程度而给它们赋值 重要的目标 赋值较大 反之 j值就小 目标规划的目标函数 准则函数 是按各目标约束的正 负偏差变量和赋予相应的优先因子及权系数而构造的 当每一目标值确定后 决策者的要求是尽可能缩小偏离目标值 因此目标规划的目标函数只能是一个使总偏差量为最小的目标函数 记为minZ f d d 4 达成函数 即目标规划中的目标函数 通过引入目标值和偏差变量 使原规划问题中的目标函数变成了目标约束 那么现在问题的目标是什么呢 这样根据各个目标的不同要求 可确定出总的目标函数 一般说来 对于达成函数有以下三种情况 但只能出现其中之一 要求恰好达到规定的目标值 即正 负偏差变量要尽可能小 则minZ f d d 要求不超过目标值 即允许达不到目标值 也就是正偏差变量尽可能小 则minZ f d 要求超过目标值 即超过量不限 但不低于目标值 也就是负偏差变量尽可能小 则minZ f d 对于这种解来说 前面的目标可以保证实现或部分实现 而后面的目标就不一定能保证实现或部分实现 有些可能就不能实现 5 满意解 具有层次意义的解 某厂生产 两种产品 有关数据如表所示 例1 三 目标规划的数学模型 解 这是求获利最大的单目标的规划问题 用x1 x2分别表示 产品的产量 其线性规划模型表述为 用图解法求得最优决策方案为 x1 4 x2 3 z 62 元 4 3 1 产品 的产量不大于 的产量 2 超过计划供应的原材料时 需要高价采购 会使成本大幅度增加 硬约束 3 充分利用设备有效台时 不加班 4 利润不小于56元 解 设x1 x2分别表示产品 和产品 的产量 这样在考虑产品决策时 便为多目标决策问题 目标规划方法是解这类决策问题的方法之一 下面通过前面引入的概念建立目标规划数学模型 现在决策者根据企业的实际情况和市场需求 需要重新制定经营目标 其目标的优先顺序如下 引进正 负偏差变量d d 正偏差变量d 表示决策值超过目标值的部分 负偏差变量d 表示决策值未达到目标值的部分 1 建立目标约束和系统约束 产品 的产量不大于 的产量 充分利用设备有效台时 但不希望加班 利润不小于56元 原材料约束 d1 X1产量不足X2部分d1 X1产量超过X2部分d2 设备使用不足10部分d2 设备使用超过10部分d3 利润不足56部分d3 利润超过56部分 第一目标 即产品 的产量不大于 的产量 第二目标 即充分利用设备有效台时 不加班 第三目标 即利润不小于56元 2 确定优先等级 3 达成函数 目标函数先满足minZ1 d1 再满足minZ2 d2 d2 后满足minZ3 d3 或minZ P1d1 P2 d2 d2 P3 d3 min P1d1 P2 d2 d2 P3 d3 一般记作 目标规划模型 例 常山机器厂生产 两种产品 这两种产品都要分别在A B C三种不同设备上加工 按工艺资料规定 生产每件产品 需占用各设备分别为2h 4h 0h 生产每件产品 需占用各设备分别为2h 0h 5h 已知各设备计划期内用于生产这两种产品的能力分别为12h 16h 15h 又知每生产一件产品 企业能获得2元利润 每生产一件产品 企业能获得3元利润 问该企业应安排生产两种产品各多少件 使总的利润收入为最大 最优解为x1 3 x2 3 z 15元 解 设x1和x2分别为 两种产品在计划期内的产量 1 力求使利润指标不低于15元 2 考虑到市场需求 两种产品的生产量需保持1 2的比例 3 A为贵重设备 严格禁止超时使用 硬约束 4 设备C可以适当加班 但要控制 设备B既要求充分利用 又尽可能不加班 又在重要性上设备B是C的3倍 但企业的经营不仅仅是利润 而是考虑如下多方面 1 设置偏差变量 用来表明实际值同目标值之间的差异 d 超出目标的差值 称正偏差变量d 未达到目标的差值 称负偏差变量d 和d 两者中必有一个为零 2 统一处理目标函数和约束条件 设备A严格禁止超时使用 硬约束 2x1 2x2 12要求 两种产品保持1 2的比例x1 x2 1 2或2x1 x2 0 1 力求使利润指标不低于15元 2 考虑到市场需求 两种产品的生产量需保持1 2的比例 3 A为贵重设备 严格禁止超时使用 硬约束 4 设备C可以适当加班 但要控制 设备B既要求充分利用 又尽可能不加班 又在重要性上设备B是C的3倍 力求使利润指标不低于15元 设备C可以适当加班 但要控制 设备B既要求充分利用 又尽可能不加班 1 力求使利润指标不低于15元 2 考虑到市场需求 两种产品的生产量需保持1 2的比例 3 A为贵重设备 严格禁止超时使用 硬约束 4 设备C可以适当加班 但要控制 设备B既要求充分利用 又尽可能不加班 又在重要性上设备B是C的3倍 3 目标的优先级与权系数 优先因子用P1 P2 表示 并规定Pk Pk 1权系数该厂必须满足设备A的硬性约束 不在目标约束中 第一优先级 利润第二优先级 产品的产量尽可能保持1 2的比例第三优先级 设备C B的工作时间所控制第三优先级 设备B的重要性比设备C大三倍目标函数中在设备B的偏差变量前冠以权系数3 1 力求使利润指标不低于15元 2 考虑到市场需求 两种产品的生产量需保持1 2的比例 3 A为贵重设备 严格禁止超时使用 4 设备C可以适当加班 但要控制 设备B既要求充分利用 又尽可能不加班 又在重要性上设备B是C的3倍 目标规划的一般数学模型 Pk为第k级优先因子 k 1 K kl kl为分别赋予第l个目标约束的正负偏差变量的权系数gl为第l个目标的预期目标值 l 1 L 引例2 某厂计划在下一个生产周期内生产甲 乙两种产品 已知资料如表所示 试制定生产计划 使获得的利润最大 同时 根据市场预测 甲的销路不是太好 应尽可能少生产 乙的销路较好 可以扩大生产 在此基础上使产量达到最大 试建立此问题的数学模型 maxZ1 70 x1 120 x2maxZ2 x1maxZ3 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 若在引例中提出下列要求 1 完成或超额完成利润指标50000元 2 产品甲不超过200件 产品乙不低于250件 3 现有钢材3600吨必须用完 试建立目标规划模型 系统约束与目标约束 maxZ1 70 x1 120 x2maxZ2 x1maxZ3 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 解 设x1 x2分别表示产品甲和产品乙的产量 di di 分别为第i个目标的正 负偏差变量 优先等级 题目有三个目标层次 包含四个目标值 第一目标 第二目标 有两个要求即甲 乙 但两个具有相同的优先因子 因此需要确定权系数 本题可用单件利润比作为权系数即70 120 化简为7 12 第三目标 达成函数 若在引例中提出下列要求 1 完成或超额完成利润指标50000元 2 产品甲不超过200件 产品乙不低于250件 3 现有钢材3600吨必须用完 试建立目标规划模型 目标规划模型为 maxZ1 70 x1 120 x2maxZ2 x1maxZ3 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 一 目标规划模型一般形式 三 目标规划的数学模型 二 建模的步骤 1 根据要研究的问题所提出的各目标与条件 确定目标值 列出目标约束与绝对约束 4 对同一优先等级中的各偏差变量 若需要可按其重要程度的不同 赋予相应的权系数 3 给各目标赋予相应的优先因子Pk k 1 2 K 2 可根据决策者的需要 将某些或全部绝对约束转化为目标约束 这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可 5 根据决策者的要求 按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的 要求实现极小化的目标函数 即达成函数 恰好达到目标值 取 允许超过目标值 取 不允许超过目标值 取 三 小结 测验题 某彩电组装厂 生产A B C三种规格电视机 装配工作在同一生产线上完成 三种产品装配时的工时消耗分别为6小时 8小时和10小时 生产线每月正常工作时间为200小时 三种产品销售后 每台可获利分别为500元 650元和800元 每月销售量预计为12台 10台 6台 该厂经营目标如下 P1 每月利润指标尽可能达到并超过16000元 P2 充分利用生产能力 P3 加班时间不超过24小时 P4 产量以预计销量为标准 为确定生产计划 请建立该问题的GP模型 P1 每月利润指标尽可能达到并超过16000元 P2 充分利用生产能力 P3 加班时间不超过24小时 P4 产量以预计销量为标准 总有效工时 120小时 设x1 x2分别为计划生产产品1和产品2的数量 2 P1 利润不低于400元 例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