第5章目标规划 Goalprogramming 第1节目标规划的数学模型 第2节目标规划的图解法 第3节目标规划的单纯形法 目标规划是在线性规划的基础上 为适应经济管理中多目标决策的需要而逐步发展起来的一个分支 线性规划只研究在满足一定条件下 单一目标函数取得最优解 在实际问题中 可能会同时考虑几个方面都达到最优 产量最高 成本最低 质量最好 利润最大 环境达标 运输满足等 目标规划能更好地兼顾统筹处理多种目标的关系 求得更切合实际要求的解 第1节目标规划的数学模型 一 目标规划概述 目标规划举例 例1 某工厂生产I II两种产品 已知有关数据如表 试求获利最大的生产方案 实际上 工厂在作决策时 要考虑一系列因素 1 产品I的产量不大于产品II 2 原材料超过时 采购成本增加 3 设备台时尽量用完 4 尽可能达到并超过计划利润指标56元 1 线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题 而目标规划是多个目标决策 可求得更切合实际的解 2 线性规划求最优解 目标规划是找到一个满意解 一 目标规划与线性规划的比较 4 线性规划的最优解是绝对意义下的最优 但需花去大量的人力 物力 财力才能得到 实际过程中 只求得满意解 就能满足需要 或更能满足需要 3 线性规划中的约束条件是同等重要的 是硬约束 而目标规划中有轻重缓急和主次之分 即有优先权 二 目标规划的基本概念 例1 某工厂生产I II两种产品 已知有关数据如表 试求获利最大的生产方案 实际上 工厂在作决策时 要考虑一系列因素 1 产品I的产量不大于产品II 2 原材料超过时 采购成本增加 3 设备台时充分用完 不加班 4 尽可能达到并超过计划利润指标56元 x1 x2 即x1 x2 0 2x1 x2 11 x1 2x2 10 8x1 10 x2 56 目标规划通过引入目标值g和偏差变量d 可以将目标函数转化为目标约束 目标值gk 是指预先给定的某个目标的一个期望值 实现值或决策值fk xj 是指当决策变量xj选定以后 目标函数的对应值 偏差变量 事先无法确定的未知数 是指实现值和目标值之间的差异 记为d 单词deviation的首字母 正偏差变量 记为d 表示实现值超过目标值的部分 负偏差变量 记为d 表示实现值未达到目标值的部分 1 决策变量xj和正 负偏差变量d d 在一次决策中 实现值不可能既超过目标值又未达到目标值 故有d d 0 并规定d 0 d 0 绝对约束 系统约束 是指必须严格满足的等式或不等式约束 如线性规划中的所有约束条件都是绝对约束 否则无可行解 所以 绝对约束是硬约束 引入目标值g 正偏差变量d 负偏差变量d 后 就对某一问题有了新的限制 即目标约束 目标约束既可对原目标函数起作用 也可对原约束起作用 目标约束是目标规划中特有的 是软约束 2 目标约束和绝对约束 一般表示为 f xj g d d 思考 下列三种情形下 如何才算达到目标 若决策目标中规定f xj g 则目标中d 0 若决策目标中规定f xj g 则目标中d 0 若决策目标中规定f xj g 则目标中d d 0 准则函数是一个使总偏差量为最小的目标函数 记为minz f d d 对应一个目标约束 有以下三种情况 但只能出现其中之一 恰好达到规定的目标值 即f xj g 正 负偏差变量d d 都要尽可能小 则minz f d d 不超过目标值 即f xj g 正偏差变量d 尽可能小 则minz f d 超过目标值 即f xj g 负偏差变量d 尽可能小 则minz f d 3 准则函数 即目标规划中的目标函数 为了将不同级别的目标的重要性用数量表示 引进P1 P2 用它表示一级目标 二级目标 的重要程度 规定P1 P2 P3 称P1 P2 为级别系数 优先因子Pk是将决策目标按其重要程度排序并表示出来 P1 P2 Pk Pk 1 k 1 2 K 例如 四个决策目标用四个优先因子排序的准则函数 权系数 k区别具有同一个优先因子的两个目标的差别的情况 例如 目标i和目标j具有相同的优先因子Pk准则函数 4 优先因子 优先等级 Pk与优先权系数 k 对于这种解来说 前面的目标可以保证实现或部分实现 而后面的目标就不一定能保证实现或部分实现 有些可能就不能实现 5 满意解 具有层次意义的解 例1 1 产品I的产量不大于产品II 2 原材料超过时 采购成本增加 3 设备台时充分用完 不加班 4 尽可能达到并超过计划利润指标56元 x1 x2 即x1 x2 0 2x1 x2 11 x1 2x2 10 8x1 10 x2 56 引入优先因子P1 x1 x2 0 P2 2x1 x2 11 P3 x1 2x2 10 P4 8x1 10 x2 56 目标约束 x1 x2 0 d1 d1 2x1 x2 11 d2 d2 x1 2x2 10 d3 d3 8x1 10 x2 56 d4 d4 例1 1 产品I的产量不大于产品II 2 原材料超过时 采购成本增加 3 设备台时尽量用完 4 尽可能达到并超过计划利润指标56元 x1 x2 即x1 x2 0 2x1 x2 11 x1 2x2 10 8x1 10 x2 56 目标函数minP1d1 minP2d2 minP3 d3 d3 minP4d4 minz P1d1 P2d2 P3 d3 d3 P4d4 目标约束 x1 x2 0 d1 d1 2x1 x2 11 d2 d2 x1 2x2 10 d3 d3 8x1 10 x2 56 d4 d4 例a 某厂计划在下一个生产周期内生产甲 乙两种产品 已知资料如表所示 试制定生产计划 使获得的利润最大 同时 根据市场预测 甲的销路不是太好 应尽可能少生产 乙的销路较好 可以扩大生产 试建立此问题的目标规划模型 若在例a中提出下列要求 1 首先完成或超额完成利润指标50000元 2 其次 产品甲不超过200件 产品乙不低于250件 3 再次 现有钢材3600吨必须用完 若在例a中提出下列要求 1 首先 完成或超额完成利润指标50000元 2 其次 产品甲不超过200件 产品乙不低于250件 3 再次 现有钢材3600吨必须用完 试建立目标规划模型 分析 本例引入3个优先因子P1 P2 P3 分析 题目有三个目标层次 包含四个目标值 第一目标 第二目标 有两个要求即甲 乙 但两个具有相同的优先因子P2 因此需要确定权系数 本题可用单件利润比作为权系数即70 120 化简为7 12 第三目标 目标规划模型为 某厂生产 两种产品 有关数据如表所示 试求获利最大的生产方案 在此基础上考虑 1 产品 的产量不低于产品 的产量 2 充分利用设备有效台时 不加班 3 利润不小于56元 解 分析第一目标 minz1 第二目标 minz2 例2 第三目标 minz3 x1 x2 即x1 x2 0 x1 2x2 10 8x1 10 x2 56 规划模型 一 模型的一般形式 二 目标规划的数学模型 其中 gk为目标约束的目标值 bi为绝对约束的资源值 约束 目标函数 目标约束 资源约束 二 建模的步骤 1 根据要研究的问题所提出的各目标与条件 确定目标值 列出目标约束与绝对约束 4 对同一优先等级中的各偏差变量 若需要可按其重要程度的不同 赋予相应的权系数 3 给各目标赋予相应的优先因子Pl l 1 2 L 2 可根据决策者的需要 将某些或全部绝对约束转化为目标约束 这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可 5 根据决策者的要求 按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的 要求实现极小化的目标函数 即准则函数 恰好达到目标值 取 允许超过目标值 取 不允许超过目标值 取 练习1 1 已知条件如表所示 如果工厂经营目标的期望值和优先等级如下 P1 每周总利润不得低于10000元 P2 因合同要求 A型机每周至少生产10台 B型机每周至少生产15台 P3 希望工序 的每周生产时间正好为150小时 工序 的生产时间最好用足 甚至可适当加班 试建立这个问题的目标规划模型 练习2 已知一个生产计划的线性规划模型为 其中目标函数为总利润 x1 x2为产品A B产量 现有下列目标 1 要求总利润必须超过2500元 2 由于甲资源供应比较紧张 不要超过现有量140 3 考虑产品受市场影响 为避免积压 A B的生产量不超过60件和100件 试建立目标规划模型 解 以产品A B的单件利润比2 5 1为权系数 模型如下 三 小结 建立目标规划的数学模型时 需要确定目标值gk 优先因子Pl 权系数 j等 它都具有一定的主观性和模糊性 可以用专家评定法给以量化 图解法同样适用两个变量的目标规划问题 但其操作简单 原理一目了然 同时 也有助于理解一般目标规划的求解原理和过程 图解法解题步骤如下 1 确定各约束条件的可行域 即将所有约束条件 包括目标约束和绝对约束 暂不考虑正负偏差变量 在坐标平面上表示出来 2 在目标约束所代表的边界线上 用箭头标出正 负偏差变量值增大的方向 第2节目标规划的图解法 3 求满足最高优先等级目标的解 4 转到下一个优先等级的目标 在不破坏所有较高优先等级目标的前提下 求出该优先等级目标的解 5 重复4 直到所有优先等级的目标都已审查完毕为止 6 确定最优解和满意解 例2 用图解法求解目标规划问题 G D 结论 有无穷多满意解 G 2 4 D 10 3 10 3 x2 x1 用图解法求解例2的目标规划 0 12345678 123456 A x2 x1 B C B 0 6250 4 6875 C 0 5 2083 B C线段上的所有点均是该问题的解 无穷多满意解 例b 用图解法求解目标规划问题 在例2的图解法求解时 把绝对约束作最高级考虑 在例2中依先后次序都能满足d1 0 d2 d2 0 d3 0 因而z 0 在例b中d1 d1 0 d2 0 因而z 0 但在大多数问题中并非如此 会出现某些约束得不到满足 仅仅得到满意解 例3 该厂目标为 P1 充分利用装配线每周开动超过40小时 P2 加班时间每周尽量不超过10小时 P3 彩色 黑白电视销量尽量超过24 30台 同优先因子下两个目标的权系数可用单件利润比作为权系数即80 40 化简为2 1 设x1 x2分别表示彩色和黑白电视机的产量 以上问题的目标规划模型 10 20 30 40 50 10 20 30 40 50 x2 x1 1 2 3 4 E F B A ABEF区域中无法满足d4 0 只能取一点使d4 尽可能小 即E点 E点为满意解 其坐标 24 26 作业 P127 T5 2 2 练习 P127 T5 2 1 第3节目标规划的单纯形法 一 一般形式 二 单纯形法的计算准则 1 minz 所有cj zj 0为最优准则 2 检验是否为满意解 非基变量的检验数含Pk 即cj zj kjPk k 1 2 k j 1 2 n 首先检查 kj是否全部为零 如果 kj全部为零 则表示目标均已全部达到 获得满意解 停止计算转到第 5 步 否则转入 2 1 建立初始单纯形表 一般假定初始解在原点 即以约束条件中的所有负偏差变量或松弛变量为初始基变量 按目标优先等级从左至右分别计算出各列的检验数 填入表的下半部 三 单纯形法的计算步骤 在Pk行 从负检验数中 选绝对值最大者 对应的变量xs就是进基变量 若Pk行中有几个相同的绝对值最大者 则依次比较它们各列下部的检验数 取其绝对值最大的负检验数的所在列的xs为进基变量 假如仍无法确定 则选最左边的变量 变量下标小者 为进基变量 2 检验是否为满意解 首先检查检验数 kj k 1 2 k 是否全部为零 如果全部为零 则表示目标均已全部达到 获得满意解 停止计算转到第 5 步 某一个 kj 0 并且Pk这一行的检验数 kj 0 j 1 2 n 2m 应继续改进 转到第 3 步 3 确定出基变量其方法同线性规划 即依据最小比值法则故确定xr为出基变量 ers为主元素 若有几个相同的行可供选择时 选最上面