第四章目标规划

Chapter4目标规划GoalProgramming 运筹学 第一节目标规划数学模型MathematicalModelofGP第二节目标规划的图解法ThegraphicalmethodofGP第三节单纯形法SimplexMethod第四节目标规划的灵敏度分析第五节目标规划应用举例 目标规划简介 目标规划是由线性规划发展演变而来 线性规划归根结底是研究资源的有效分配和利用 模型特点是在满足一组约束条件的情况下 寻求某个目标的 如产量 利润 成本等 的最大值或最小值 现代企业内分工越来越细 组织机构日趋复杂 为了统一协调企业各部门人员围绕一个整体的目标工作 产生了目标管理这种先进的管理技术 目标规划是实行目标管理的有效工具 它根据企业制定的经营目标以及这些目标的轻重缓急次序 考虑现有资源情况 分析如何达到规定目标或从总体上规定目标的差距最小 目标规划的有关概念和模型最早是在1961年由美国学者A 查恩斯和W 库伯在他们合著的 管理模型和线性规划的工业应用 书中提出 以后这种模型又先后经尤吉 艾吉果 杰斯基莱恩和桑 李不断和完善和改进 1976年伊格尼奇奥发表了 目标规划及其发展 一书 系统的归纳和总结了目标规划的理论与方法 第一节目标规划问题及其数学模型 一 目标规划问题的提出 例1某工厂生产两种产品 已知有关数据见下表 试求获利最大的生产方案 解 这是求获利最大的单目标的规划问题 用x1 x2分别表示 产品的产量 其线性规划模型表述为 最优生产计划为 x1 8 x2 2 z 64 元 例2假设在例1中 计划人员被要求考虑如下的意见 1 由于产品 销售量有下降的趋势 故考虑产品 的产量不超过产品 的一半 2 原材料严重短缺 生产中应避免过量消耗 3 最好能节约4h设备工时 4 计划利润不少于48元 二 目标规划问题的数学模型 这样在考虑产品决策时 便为多目标决策问题 目标规划方法是解这类决策问题的方法之一 下面引入与建立目标规划数学模型有关的概念 1 设x1 x2为决策变量 此外 引进正 负偏差变量d d 正偏差变量d 表示决策值超过目标值的部分 负偏差变量d 表示决策值未达到目标值的部分 因决策值不可能既超过目标值同时又未达到目标值 即恒有d d 0 d 0 d 0 2 绝对约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束 如线性规划问题的所有约束条件 不能满足这些约束条件的解称为非可行解 所以它们是硬约束 目标约束是目标规划特有的 可把约束右端项看作要追求的目标值 在达到此目标值时允许发生正或负偏差 因此在这些约束中加入正 负偏差变量 它们是软约束 线性规划问题的目标函数 在给定目标值和加入正 负偏差变量后可变换为目标约束 也可根据问题的需要将绝对约束变换为目标约束 3 优先因子 优先等级 与权系数 一个规划问题常常有若干目标 但决策者在要求达到这些目标时 是有主次或轻重缓急的不同 要求第一位达到的目标赋予优先因子P1 次位的目标赋予优先因子P2 并规定Pk Pk 1 k 1 2 K 表示Pk比Pk 1有更大的优先权 即首先保证P1级目标的实现 这时可不考虑次级目标 而P2级目标是在实现P1级目标的基础上考虑的 依此类推 若要区别具有相同优先因子的两个目标的差别 这时可分别赋予它们不同的权系数 j 这些都由决策者按具体情况而定 4 目标规划的目标函数 目标规划的目标函数 准则函数或达成函数 是按各目标约束的正 负偏差变量和赋予相应的优先因子及权系数而构造的 当每一目标值确定后 决策者的要求是尽可能缩小偏离目标值 因此目标规划的目标函数只能是极小化 其基本形式有三种 1 要求恰好达到目标值 即正 负偏差变量都要尽可能地小 这时min f d d 2 要求不超过目标值 即允许达不到目标值 就是正偏差变量要尽可能地小 这时min f d 3 要求超过目标值 即超过量不限 但必须是负偏差变量要尽可能地小 这时min f d 对每一个具体目标规划问题 可根据决策者的要求和赋予各目标的优先因子来构造目标函数 以下用例子说明 根据上述概念 例2的目标规划模型如下 目标规划的一般数学模型为 为权系数 三 小结 第二节目标规划的图解法 对只具有两个决策变量的目标规划的数学模型 可以用图解法来分析求解 在用图解法解目标规划时 首先必须满足所有绝对约束 在此基础上 再按照优先级从高到低得顺序 逐个地考虑各个目标约束 例3用图解法解例2的目标规划模型 根据上述概念 例2的目标规划模型如下 例3用图解法解例2的目标规划模型 四边形EDCF区域满足要求 例 用图解法解下面的目标规划 解 图解法求解如下 由图上可以看出 点为满意解 在用图解法解目标规划时 可能会遇到下面两种情况 一种是解能满足所有目标要求 另一种是解不能满足所有目标要求 这时 寻找的是满意解 使他尽可能满足高级别的目标 同时又使他对那些不能满足的较低级别目标的偏离程度尽可能的小 注意 在考虑低级别目标时 不能破坏已经满足的高级别目标 这是目标规划的基本原则 第三节目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别 所以可用单纯形法求解 但要考虑目标规划的数学模型一些特点 作以下规定 1 因目标规划问题的目标函数都是求最小化 所以以cj zj 0 j 1 2 n 为最优准则 2 因非基变量的检验数中含有不同等级的优先因子 即 因P1 P2 PK 从每个检验数的整体来看 检验数的正 负首先决定于P1的系数 1j的正 负 若 1j 0 这时此检验数的正 负就决定于P2的系数 2j的正 负 下面可依此类推 解目标规划问题的单纯形法的计算步骤 1 建立初始单纯形表 在表中将检验数行按优先因子个数分别列成K行 置k 1 2 检查该行中是否存在负数 且对应的前k 1行的系数是零 若有负数取其中最小者对应的变量为换入变量 转 3 若无负数 则转 5 3 按最小比值规则确定换出变量 当存在两个和两个以上相同的最小比值时 选取具有较高优先级别的变量为换出变量 4 按单纯形法进行基变换运算 建立新的计算表 返回 2 5 当k K时 计算结束 表中的解即为满意解 否则置k k 1 返回到 2 例5用单纯形法求解例2 解 引入松弛变量x3 将例2的目标规划模型化为线性规划标准形式 表1 表3 从单纯形表3得例2的一个满意解x1 24 5 4 8 x2 2 4 对应图解法中的F点 第四节目标规划的灵敏度分析 在目标规划建模时 目标优先级和权系数的确定往往带有一定的主观性 灵敏度分析是目标是目标规划灵敏度分析的主要内容 目标规划灵敏度分析的方法 原理同线性规划的灵敏度分析本质上相同 例7对例4的目标规划问题 已求得满意解为x1 13 2 x2 5 4 现决策者想知道 目标函数中各目标的优先因子和权系数对最终解的影响 为此 提出了两个灵敏度分析问题 即目标函数分别为 解 目标函数的变化仅影响原解的最优性 即各变量的检验数 因此 应当先考虑检验数的变化 然后再做适当处理 1 当目标函数变为 1 则需了解交换第三和第四优先级目标对原解的影响 此时有单纯形表4 8 表4 8 从表4 8可见 原最优解已被破坏故应用单纯形法继续求解 见表4 9 表4 9 由表4 9可知 第三和第四优先级目标交换后 原满意解已失去了最优性 新的满意解为x1 5 x2 1 2 即图4 2中F点 2 当目标函数变为 2 就是要了解第三优先级中两目标权系数取值对原解的影响 有单纯形表4 10 表4 10 从表4 10可知 原解是否改变取决于的检验数 因此有 当 即时 原解不变 仍为x1 13 2 x2 5 4 即图4 2中E点 当时 原解改变 用单纯形法继续求解 可得新的满意解x1 5 x2 2 即图4 2中G点 当时 E点和G点皆为满意解 从上面的分析知道 第三优先级两目标权系数的改变可能会影响所得的满意解 第五节目标规划应用举例 表4 11 解 用表上作业法可以求得不考虑P1至P6各目标时的最小调运方案 相应的最小运费为2950元 现建立问题的目标规划模型 设Ai运往Bj的物资为xijt i 1 2 3 j 1 2 3 4 问题的目标规划模型为 约束条件的含义为 4 3a 4 3b 4 3c 是供应量约束 考虑到各销地的需要量可以有20 的向下浮动 故作为绝对约束条件 且皆取 号 4 3d 至 4 3g 是需求量目标约束 4 3h 是A3向B1的供应量目标约束 4 3i 至 4 3l 是向各销地的最低供应量目标约束 4 3m 是实际运费的上限目标约束 4 3n 是A2尽量不向B4调运物资的目标约束 4 3o 是给B1和B3的供应率尽量相同的目标约束 4 3p 是总运费尽量小的目标约束