管理运筹学义目标规划PPT课件

1 管理运筹学 管理科学方法 中山大学南方学院工商管理系 演讲 王甜源 2 第5章目标规划 Subtitle 学习要点 了解目标规划与线性规划的异同理解目标约束中的正负偏差变量思考目标约束与系统约束的差异理解目标的优先级和目标权系数了解目标规划图解法和单纯形法 3 第一节多目标规划问题 一 线性规划的局限性 线性规划的局限性只能解决一组线性约束条件下 某一目标而且只能是一个目标的最大或最小值的问题实际决策中 衡量方案优劣考虑多个目标生产计划决策 通常考虑产值 利润 满足市场需求等生产布局决策 考虑运费 投资 供应 市场 污染等这些目标中 有主要的 也有次要的 有最大的 有最小的 有定量的 有定性的 有互相补充的 有互相对立的 LP则无能为力目标规划 GoalProgramming 多目标线性规划含有多个优化目标的线性规划 4 问题的提出 目标规划是在线性规划的基础上 为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支 由于现代化企业内专业分工越来越细 组织机构日益复杂 为了统一协调企业各部门围绕一个整体的目标工作 产生了目标管理这种先进的管理技术 目标规划是实行目标管理的有效工具 它根据企业制定的经营目标以及这些目标的轻重缓急次序 考虑现有资源情况 分析如何达到规定目标或从总体上离规定目标的差距为最小 第5章目标规划 5 第一节多目标规划问题 二 多目标规划的提出 例 甲乙产品的最优生产计划 解 线规划模型 maxZ 3x1 5x22x1 162x2 103x1 4x2 32x1 x2 0 根据市场需求 合同规定 希望尽量扩大甲产品减少乙产品产量 又增加二个目标 maxZ1 3x1 5x2maxZ2 x1minZ3 x22x1 162x2 103x1 4x2 32x1 x2 0 这些目标之间相互矛盾 一般的线性规划方法不能求解 6 第一节多目标规划问题 二 多目标规划的提出 多目标线性规划模型的原始一般形式如下 n个决策变量 m个约束条件 L个目标函数 当L 1时 即为我们熟悉的单目标线性规划模型 7 例 某企业计划生产甲 乙两种产品 这些产品分别要在A B C D四种不同设备上加工 按工艺文件规定 如表所示 问该企业应如何安排计划 使得计划期内的总利润收入为最大 第一节多目标规划问题 8 解 设甲 乙产品的产量分别为x1 x2 建立线性规划模型 其最优解为x1 4 x2 2 z 14元 第一节多目标规划问题 9 但企业的经营目标不仅仅是利润 而且要考虑多个方面 如 力求使利润指标不低于12元 考虑到市场需求 甲 乙两种产品的生产量需保持1 1的比例 C和D为贵重设备 严格禁止超时使用 设备B必要时可以加班 但加班时间要控制 设备A即要求充分利用 又尽可能不加班 要考虑上述多方面的目标 需要借助目标规划的方法 第一节多目标规划问题 10 线性规划模型存在的局限性 1 要求问题的解必须满足全部约束条件 实际问题中并非所有约束都需要严格满足 2 只能处理单目标的优化问题 实际问题中 目标和约束可以相互转化 3 线性规划中各个约束条件都处于同等重要地位 但现实问题中 各目标的重要性即有层次上的差别 同一层次中又可以有权重上的区分 4 线性规划寻求最优解 但很多实际问题中只需找出满意解就可以 第一节多目标规划问题 11 第一节多目标规划问题 三 多目标规划的解法 加权系数法 为每一目标赋一权数 把多目标转化成单目标 但权系数难以科学确定 优先等级法 各目标按重要性归不同优先级而化为单目标 有效解法 寻求能照顾到各目标而使决策者感到满意的解 但可行域大时难以列出所有有效解的组合 目标规划法 对每一个目标函数引入正的或负的偏差变量 引入目标的优先等级和加权系数 12 目标规划怎样解决前例线性规划模型建模中的局限性 1 设置偏差变量 用来表明实际值同目标值之间的差异 偏差变量用下列符号表示 d 超出目标的偏差 称正偏差变量d 未达到目标的偏差 称负偏差变量 正负偏差变量两者必有一个为0 当实际值超出目标值时 d 0 d 0 当实际值未达到目标值时 d 0 d 0 当实际值同目标值恰好一致时 d 0 d 0 故恒有d d 0 第一节多目标规划问题 13 2 统一处理目标和约束 对有严格限制的资源使用建立系统约束 数学形式同线性规划中的约束条件 如C和D设备的使用限制 对不严格限制的约束 连同原线性规划建模时的目标 均通过目标约束来表达 1 例如要求甲 乙两种产品保持1 1的比例 系统约束表达为 x1 x2 由于这个比例允许有偏差 当x1x2时 出现正偏差d 即 x1 d x2或x1 x2 d 0 第一节多目标规划问题 14 正负偏差不可能同时出现 故总有 x1 x2 d d 0 若希望甲的产量不低于乙的产量 即不希望d 0 用目标约束可表为 若希望甲的产量低于乙的产量 即不希望d 0 用目标约束可表为 若希望甲的产量恰好等于乙的产量 即不希望d 0 也不希望d 0用目标约束可表为 第一节多目标规划问题 15 3 设备B必要时可加班及加班时间要控制 目标约束表示为 2 力求使利润指标不低于12元 目标约束表示为 4 设备A既要求充分利用 又尽可能不加班 目标约束表示为 第一节多目标规划问题 16 3 目标的优先级与权系数 在一个目标规划的模型中 为达到某一目标可牺牲其他一些目标 称这些目标是属于不同层次的优先级 优先级层次的高低可分别通过优先因子P1 P2 表示 对于同一层次优先级的不同目标 按其重要程度可分别乘上不同的权系数 权系数是一个个具体数字 乘上的权系数越大 表明该目标越重要 现假定 第1优先级P1 企业利润 第2优先级P2 甲乙产品的产量保持1 1的比例第3优先级P3 设备A充分利用但尽量不超负荷工作 设备B尽量不超负荷工作 其中设备A的重要性比设备B大三倍 第一节多目标规划问题 17 上述目标规划模型可以表示为 第一节多目标规划问题 18 目标规划数学模型的一般形式 达成函数 目标约束 其中 gk为第k个目标约束的预期目标值 和为pl优先因子对应各目标的权系数 第一节多目标规划问题 19 目标规划问题及其数学模型 总结 用目标规划求解问题的过程 明确问题 列出目标的优先级和权系数 构造目标规划模型 求出满意解 满意否 分析各项目标完成情况 据此制定出决策方案 N Y 20 第二节目标规划的数学模型 一 目标期望值 每一个目标希望达到的期望值 或目标值 理想值 根据历史资料 市场需求或上级部门的布置等来确定 二 偏差变量 目标约束 目标的实际值和期望值之间可能存在正的或负的偏差 正偏差变量dk 表示第k个目标超过期望值的数值 负偏差变量dk 表示第k个目标未达到期望值的数值 同一目标的dk 和dk 中至少有一个必须为零 引入正负偏差变量 对各个目标建立目标约束 软约束 总结 用目标规划求解问题的过程 21 第二节目标规划的数学模型 三 目标达成函数 目标达成函数 偏差变量之和为最小值 若要求尽可能达到规定的目标值正负偏差变量dk dk 都尽可能小 即minSk dk dk 若希望尽可能不低于期望值 允许超过 负偏差变量dk 尽可能小 不关心超出量dk minSk dk 若允许某个目标低于期望值 但希望不超过正偏差变量dk 尽可能小 不关心低于量dk minSk dk 四 优先等级权数 目标重要度不同 用优先等级因子Pk表示第k等级目标 优先等级因子Pk是正的常数 Pk Pk 1 同一优先等级下目标的相对重要性赋以不同权数w 总结 用目标规划求解问题的过程 22 第二节目标规划的数学模型 Z为利润 两个决策变量是甲乙产品的产量 若做出如下要求 目标一是利润最大 拟定利润目标是30 目标二是减少乙产品产量但希望不低于4件 目标三是甲产品产量希望不少于6件 对各目标引入正 负偏差变量 3x1 5x2 d1 d1 30 x2 d2 d2 4x1 d3 d3 6 maxZ 3x1 5x2 0 x3 0 x4 0 x5 02x1 x3 162x2 x4 103x1 4x2 x5 32 23 第二节目标规划的数学模型 对上例而言 若 P1级目标实现利润至少30元 P2级目标是甲乙产品的产量假设 乙产品产量不少于4件比甲产品产量不少于6件更重要 取其权重为2目标规划为 minG P1d1 P2 2d2 d3 3x1 5x2 d1 d1 30 x2 d2 d2 4x1 d3 d3 6x1 x2 dk dk 0 k 1 2 3 24 目标规划的图解法 适用两个变量的目标规划问题 但其操作简单 原理一目了然 同时 也有助于理解一般目标规划的求解原理和过程 图解法解题步骤 1 将所有约束条件 包括目标约束和绝对约束 暂不考虑正负偏差变量 的直线方程分别标示于坐标平面上 2 确定系统约束的可行域 3 在目标约束所代表的边界线上 用箭头标出正 负偏差变量值增大的方向 第三节目标规划的图解法 25 3 求满足最高优先等级目标的解4 转到下一个优先等级的目标 在不破坏所有较高优先等级目标的前提下 求出该优先等级目标的解5 重复4 直到所有优先等级的目标都已审查完毕为止6 确定最优解和满意解 第三节目标规划的图解法 26 例 装配两种型号的笔记本 每台需装备时间1小时 每周工作5天 计划开动8小时 天 预计型号I每周销售型号I24台 利润80元 台 型号II30台 利润40元 台 该厂目标如下 充分利用装配线 避免开工不足允许装配线加班 但加班时间尽可能短 但不超过10小时尽量满足市场需求 重要性和利润成正比每周的利润5000以上请合理安排工作任务 甲乙产量 建立目标规划的模型 第三节目标规划的图解法 27 第三节目标规划的图解法 目标规划的图解法首先 按照绝对约束画出可行域 其次 不考虑正负偏差变量 画出目标约束的边界线 最后 按优先级别和权重依次分析各级目标 F G H 满意解 x1 5 x2 4 28 补充例1 用图解法求解下列目标规划问题 第三节目标规划的图解法 29 a b c d x2 x1 e f d1 d1 d2 d2 d3 d3 d4 d4 满意解 3 3 0 4 6 8 3 4 6 2 2 第三节目标规划的图解法 30 x1 x2 a b d1 d1 c d2 d2 d d3 d3 G D 满意解是线段GD上任意点 其中G点X 2 4 D点X 10 3 10 3 0 5 5 10 5 5 6 11 2 4 10 3 10 3 5 10 7 课堂练习 第三节目标规划的图解法 31 第三节目标规划的图解法 32 目标规划应用举例 补充例2 已知一个生产计划的线性规划模型如下 其中目标函数为总利润 x1 x2为产品A B产量 其中乙资源和丙资源为稀缺资源现有下列目标 1 要求总利润必须超过2500元 2 考虑产品受市场影响 为避免积压 A B的生产量不超过60件和100件 产品A B的单件利润比2 5 1为权系数3 由于甲资源供应比较紧张 尽量不要超过现有量140 试建立目标规划模型 并用图解法求解 33 目标规划应用举例 解 以产品A B的单件利润比2 5 1为权系数 模型如下 34 目标规划应用举例 0 x2 0 x1 14012010080604020 20406080100 A B C D C 60 58 3 为所求的满意解 24 26 35 第四节目标规划的单纯形法 了解 目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型 将优先等级Pk视为正常数 大 法 正负偏差变量dk dk 视为松弛变量以负偏差变量dk 为初始基变量 建立初始单纯形表检验数的计算与LP单纯形法相同 即 j cj CBiPj最优性判别准则类似于LP的单纯形算法 检验数一般是各优先等级因子的代数和判断检验数的正负和大小 36 第五节目标规划的应用案例 一 无穷多满意解 解 设x1 x2表示A B产品的产量 两个等级的目标 P1 充分利用电量限额 正负偏差之和为最小目标达成函数目标约束条件P2 利润额希望不能低于100元 负偏差最小目标达成函数目标约束条件 计划生产两种产品 首先要充分利用设备工时而不加班 然后考虑利润不低于100元 问应如何制定产品A B的产量 37 第五节目标规划的应用案例 一 无穷多满意解 由于材料供应限量为8单位 所以有系统约束条件 如下 该问题的目标规划模型如下 图解法求解如图 C G 38 第五节目标规划的应用案例 二 加班时间问题 例 某音像店有5名全职售货员和4名兼职售货员 全职售货员每月工作160小时 兼职售货员每月工作80小时 根据记录 全职每小时销售CD25张 平均每小时工资15元 加班工资每小时22 5元 兼职售货员每小时销售CD10张 平均工资每小时10元 加班工资每小时10元 现在预测下月CD销售量为27500张 商店每周开门营业6天 所以可能要加班 每出售一张CD盈利1 5元 商店经理认为 保持稳定的就业水平加上必要的加班 比不加班就业水平要好 但全职销售员如果加班过多 就会因为疲劳过度而造成效率下降 因此不允许每月加班超过100小时 建立相应的目标规划模型 39 第五节目标规划的应用案例 二 加班时间问题 首先 确定目标约束的优先级 如下 P1 下月的CD销售量达到27500张 P2 全职售货员加班时间不超过100小时 P3 保持全体售货员充分就业 对全职的要比兼职的加倍优先考虑 P4 尽量减少加班时间 对两种售货员区别对待 权重由他们对利润的贡献而定 其次 建立目标约束函数 1 销售目标约束 设全体全职售货员下月的工作时间x1 全体兼职售货员下月的工作时间x2 达不到销售目标的偏差d1 超过销售目标的偏差d1 40 第五节目标规划的应用案例 二 加班时间问题 2 加班时间的限制 设全体全职售货员下月的加班不足100小时的偏差d4 加班超过100小时的偏差d4 3 正常工作时间约束 设全体全职售货员下月的停工时间d2 加班时间d2 全体兼职售货员下月的停工时间d3 加班时间d3 两类售货员区别对待 权重比d2 d3 1 3 另一加班目标约束为 41 第五节目标规划的应用案例 二 加班时间问题 第三 按目标的优先级 写出相应的目标规划模型 运用LINGO软件求解得x1 900 x2 500 下月共销售CD盘27500张 获利27500 1 5 800 1