7.运筹学之目标规划(胡运权版)

1 第七章第七章 目标规划目标规划 1 目标规划的提出目标规划的提出 线性规划问题是讨论一个给定的线性目标函数在一组线性约束 条件下的最大值或最小值问题 对于一个实际问题 管理科学者根 据管理层决策目标的要求 首先确定一个目标函数以衡量不同决策 的优劣 且根据实际问题中的资源 资金和环境等因素对决策的限 制提出相应的约束条件以建立线性规划模型 然后用计算机软件求 出最优方案并作灵敏度分析以供管理层决策之用 而在一些问题中 决策目标往往不只一个 且模型中有可能存在一些互相矛盾的约束 条件的情况 用已有的线性规划的理论和方法无法解决这些问题 因此 1961 年美国学者查恩斯 A Charnes 和库柏 W W Coopor 提出了目标规划的概念与数学模型 以解决经济管 理中的多目标决策问题 我们将通过几个例子来说明在实际应用中线性规划存在一系列 的局限性 例例 1 某厂生产 A B 两种产品每件所需的劳动力分别为 4 个人工和 6 个人工 所需设备的单位台时均为 1 已知该厂有 10 个单位机器 台时提供制造这两种产品 并且至少能提供 70 个人工 又 A B 产品的利润 每件分别为 300 元和 500 元 试问 该厂各应生产多 少件 A B 产品 才能使其利润值最大 解解 设该厂能生产 A B 产品的数量分别为件 则有 12 x x 2 12 12 12 max300500 10 4670 0 1 2 j zxx xx stxx xj 图解法求解如下 由上图可得 满足约束条件的可行解集为 即机时约束和人工 约束之间产生矛盾 因而该问题无解 但在实际中 该厂要增加利 润 不可能不生产 A B 两种产品 而由线性规划模型无法为其找 到一个合适的方案 例例 2 某厂为进行生产需采购 A B 两种原材料 单价分别为 70 元 公斤和 50 元 公斤 现要求购买资金不超过 5000 元 总购买量不少 于 80 公斤 而 A 原材料不少于 20 公斤 问如何确定最好的采购方 案 即花掉的资金最少 购买的总量最大 解解 这是一个含有两个目标的数学规划问题 设分别为购买两 12 x x 种原材料的公斤数 为花掉的资金 为购买的总量 112 fx x 212 fx x 建立该问题的数学模型形式如下 3 11212 21212 12 12 1 12 min 7050 max 70505000 80 20 0 fx xxx fx xxx xx xx st x x x 对于这样的多目标问题 线性规划很难为其找到最优方案 极 可能的结果是 第一个方案使第一目标的结果值优于第二方案 同 时第二方案使第二目标的结果值优于第一方案 也就是说很难找到 一个最优方案 使两个目标的函数值同时达到最优 另外 对于多 目标问题 还存在有多个目标存在有不同重要程度的因素 而这也 是线性规划所无法解决的 在线性规划的基础上 建立了一种新的数学规划方法 目标规 划法 用于弥补线性规划的上述局限性 总的来说 目标规划和线 性规划的不同之处可以从以下几点反映出来 1 线性规划只能处理一个目标 而现实问题往往存在多个目标 目标规划能统筹兼顾地处理多个目标的关系 求得切合实际需求的 解 2 线性规划是求满足所有约束条件的最优解 而在实际问题中 可能存在相互矛盾的约束条件而导致无可行解 但此时生产还得继 续进行 即使存在可行解 实际问题中也未必一定需要求出最优解 目标规划是要找一个满意解 即使在相互矛盾的约束条件下也找到 尽量满足约束的满意解 即满意方案 4 3 线性规划的约束条件是不分主次地等同对待 这也并不都符 合实际情况 而目标规划可根据实际需要给予轻重缓急的考虑 2 目标规划的基本概念与数学模型目标规划的基本概念与数学模型 2 1 2 1 基本概念基本概念 在这一小节里介绍与目标规划有关的基本概念 1 偏差变量 偏差变量 对于例 1 造成无解的关键在于约束条件太死板 设想把约束条 件 放松 比如占用的人力可以少于 70 人的话 机时约束和人工 约束就可以不再发生矛盾 在此基础上 引入了正负偏差的概念 来表示决策值与目标值之间的差异 正偏差变量 表示决策值超出目标值的部分 目标规划 i d 里规定 0 i d 负偏差变量 表示决策值未达到目标值的部分 目标规划 i d 里规定 0 i d 实际操作中 当目标值 也就是计划的利润值 确定时 所作的 决策可能出现以下三种情况之一 1 决策值超过了目标值 即完成或超额完成计划利润值 表 示为 0 i d 0 i d 5 2 决策值未达到目标值 即未完成计划利润值 表示为 0 i d 0 i d 3 决策值恰好等于目标值 即恰好完成计划利润指标 表示 为 0 i d 0 i d 以上三种情况 无论哪种情况发生 均有 0 i d i d 2 绝对约束与目标约束 绝对约束与目标约束 绝对约束也称系统约束 是指必须严格满足的等式约束和不等式 约束 它对应于线性规划模型中的约束条件 目标约束是目标规划所特有的 当确定了目标值 进行决策时 允许与目标值存在正或负的偏差 因而目标约束中加入了正 负偏 差变量 如 例 1 中假定该企业计划利润值为 5000 元 那么对于目标函 数 可变换为 12 max300500zxx 12 3005005000 ii xxdd 该式表示决策值与目标值 5000 之间可能存在正或负的偏差 请 读者分别按照上面所讲的三种情况来理解 绝对约束也可根据问题的需要变换为目标约束 此时将约束右端 项看作所追求的目标值 如 例 1 中绝对约束 可变换为 12 10 xx 目标约束 12 10 ii xxdd 6 3 目标规划的目标函数 目标规划的目标函数 对于满足绝对约束与目标约束的所有解 从决策者的角度来看 判断其优劣的依据是决策值与目标值的偏差越小越好 因此目标规 划的目标函数是与正 负偏差变量密切相关的函数 我们表示为 它有如下三种基本形式 min ii zf dd 1 要求恰好达到目标值 即正 负偏差变量都尽可能地小 此时 构造目标函数为 min ii zdd 2 要求不超过目标值 即允许达不到目标值 正偏差变量尽 可能地小 此时构造目标函数为 min i zd 3 求超过目标值 即超过量不限 负偏差变量尽可能地小 此时构造目标函数为 min i zd 4 优先次序系数与权系数 优先次序系数与权系数 一个规划问题往往有多个目标 决策者在实现这些目标时 存在 有主次与轻重缓急的不同 对于有级目标的问题 按照优先次序K 分别赋予不同大小的大系数 M 为无穷大的正数 并且 1 M 2 M K M 1 M 2 M K M 1 M 符号表示 远大于 这样 只有当某一 2 M K M 级目标实现以后 即目标值为 0 才能忽略大的影响 否则目M 标偏离量会因为大的原因而无穷放大 并且由于 所以M 1kk MM 只有先考虑忽略影响 实现第 级目标 后 才能考虑第级 k Mk1k 目标 实际上这里的大是对偏离目标值的惩罚系数 优先级别越M 7 高 惩罚系数越大 权系数用来区别具有相同优先级别的若干目标 在同一优先级 i 别中 可能包含有两个或多个目标 它们的正负偏差变量的重要程 度有差别 此时可以给正负偏差变量赋予不同的权系数和 i i 各级目标的优先次序及权系数的确定由决策者按具体情况给出 2 2 目标规划的数学模型目标规划的数学模型 综上所述 目标规划模型由目标函数 目标约束 绝对约束以及 变量非负约束等几部分构成 目标规划的一般数学模型为 目标函数 11 min KL kkllkll kl ZMdd 目标约束 1 1 2 n ijjlll j c xddglL 绝对约束 1 1 2 n ijji j a xbim 非负约束 0 1 2 j xjn 0 1 2 kk ddkK 例例 3 在例例 1 中 假定目标利润不少于 15000 元 为第一目标 占 用的人力可以少于 70 人 为第二目标 求决策方案 解解 按决策者的要求分别赋予两个目标大系数 列出模型M 12 M M 如下 8 1122 1211 1222 12 12 min 30050015000 4670 10 0 1 2 3 ii zM dM d xxdd xxdd st xx x x ddi 例例 4 某纺织厂生产 A B 两种布料 平均生产能力均为 1 千米 小 时 工厂正常生产能力是 80 小时 周 又 A 布料每千米获利 2500 元 B 布料每千米获利 1500 元 已知 A B 两种布料每周的市场需求量 分别是 70 千米和 45 千米 现该厂确定一周内的目标为 第一优先级 避免生产开工不足 第二优先级 加班时间不超过 10 小时 第三优先级 根据市场需求达到最大销售量 第四优先级 尽可能减少加班时间 试求该问题的最优方案 解 设分别为生产甲 乙布料的小时数 对于第三优先级目标 12 x x 根据 A B 布料利润的比值 取二者达到最大销量的2500 15005 3 权系数分别为 5 和 3 该问题的目标规划模型为 112233441 1211 1222 133 244 12 min53 80 90 70 45 0 1 4 ii zM dM dMddM d xxdd xxdd stxdd xdd x x ddi 9 综上所述 目标规划建立模型的步骤为 1 根据问题所提出的各目标与条件 确定目标值 列出目 标约束与绝对约束 2 根据决策者的需要将某些或全部绝对约束转换为目标约束 方法是绝对约束的左式加上负偏差变量和减去正偏差变量 3 给各级目标赋予相应的惩罚系数 为无 k M1 2 kK k M 穷大的正数 且 1 M 2 M K M 4 对同一优先级的各目标 再按其重要程度不同 赋予相应的 权系数 kl 5 根据决策者的要求 各目标按三种情况取值 恰好达到目 标值 取 允许超过目标值 取 不允许超过目标值 取 ii dd i d 然后构造一个由惩罚系数 权系数和偏差变量组成的 要求实 i d 现极小化的目标函数 3 目标规划的求解目标规划的求解 3 1 图解法图解法 只有两个决策变量的目标规划数学模型 可以使用简单直观的图 解法求解 其方法与线性规划图解法类似 先在平面直角坐标系第 一象限内作出各约束等式或不等式的图象 然后由绝对约束确定了 可行域 由目标约束和目标函数确定最优解或满意解 10 对于绝对约束 与线性规划中的约束条件画法完全相同 对于目 标约束方程 除作出直线外 还要在直线上要标出正负偏差变量的 方向 其可行域方向取决于目标函数中对应目标 另外 目标规划 是在前一级目标满足的情况下再来考虑下一级目标 很有可能尽可 能满足目标的解不是可行解 即非可行解 而是权衡以后得出的最 优解 满意解 因而在目标规划里称求得的解为满意解满意解 注意在求解的时候 把绝对约束作最高级别考虑 例例 5 用图解法求解目标规划问题 1112233 1211 1222 1233 12 12 min 0 3515 4324 7 0 1 2 3 ii zMddM dM d xxdd xxdd stxxdd xx x x ddi 解解 在平面直角坐标系第一象限内作出各约束条件的图像 目标约 束要在直线旁标上和 di i d 11 首先 绝对约束确定了可行解范围在三角形 OEF 内 12 7xx 根据第一级目标 要求实现 恰好 因而可行解范 11 min dd 围缩小到线段 OC 上 根据第二级目标 要求实现 不少于 在线段 OC 上 取 2 mind 的点 A 此时可行解范围缩小到线段 AC 上 2 0d 根据第三级目标 要求实现 在线段 AC 上 取的点 3 mind 3 0d B 此时解的范围缩小到线段 AB 上 所以 线段 AB 上的所有点为满意解 可求得 A 15 8 15 8 B 24 7 24 7 例例 6 用图解法求解例例 4 的目标规划模型 解解 在平面直角坐标系第一象限内作出各约束条件对应的图象 并 在目标约束直线旁标上和 i d i d 根据第一级目标 目标函数要求实现 解的范围是线段 1 mind AC 的右上方区域 12 根据第二级目标 目标函数要求实现 解的范围缩小到四 2 mind 边形 ABDC 内的区域 根据第三级目标 目标函数要求实现 先考虑 34 min 53dd 解的范围缩小为四边形 ABFE 内的区域 再考虑 3 min5d 4 min3d 四边形 ABFE 内的所有点 均无法满足 此时在可行域 ABFE 4 0d 内考虑使达到最小的满意点 F F 点不满足 但它是使第三 4 d 4 0d 级目标最满意的满意解 根据第四级目标 目标函数要求实现 由于解的范围已经 1 mind 缩小到点 F 所以唯一的点 F 也是使第四级目标最满意的满意解 综上所述 该问题的满意解为点 F 可求得 F 70 20 给出图解法求解步骤如下 1 在直角坐标系的第一象限作出绝对约束和目标约束的图象 绝对约束确定出可行解的区域 在目标约束直线上用箭头标出正负 偏差变量值增大的方向 正 负偏差变量增大的方向相反 2 在可行解的区域内 求满足最高优先等级目标的解 3 转到下一个优先等级的目标 在满足上一优先等级目标的前 提下 求出满足该等级目标的解 4 重复 3 直到所有优先等级目标都审查完毕 5 确定最优解或满意解 3 2 单纯形法单纯形法 13 目标规划是线性规划的推广与发展 其数学模型结构与线性规划 的数学模型结构没有本质的区别 求解线性规划的单纯形法 同样 也是目标规划的求解方法 在目标规划里加入了大 M 惩罚系数 可 用大 M 法来进行求解 这里不再举例 用单纯形法求解目标规划 迭代结束有两种情况 一种所有检 验数均已非负时 所获得的解使所有目标偏离量为 0 此解为最优 解 另一种情况是所有检验数均已非负时 并没有使所有目标达到 最优值 但达到最优的目标值一定是优先等级排在前面的 此时获 得的解为满意解 如例例 4 4 用单纯形法求的满意解为 目标值 70 20 T 为 可以看到求得的解并没有使第三级和第四级目标 34 7510zMM 达到最优 但已使第一 二级目标达到最优 这和前面用图解法求 得的结果一致 3 3 EXCEL 电子表格法电子表格法 目标规划同样能由 EXCEL 求得其满意解 关键在于如何建立 电子表格模型 例例 7 用 EXCEL 求解例例 4 的目标规划模型 解解 我们来看一下如何为例 4 中的目标规划问题建立电子表格模型 见图 7 4 14 图图 7 4 单元格 B5 C8 实际上是决策变量在目标规划数学模型中的 系数 又可理解为对各对应因素的单位贡献 如单元格 B5 是产品 1 对开工时间这一因素的单位贡献 即生产 1 千米的 A 布料使开工 时间增加 1 D 列计算了决策变量对每一因素的总贡献值 如单元格 D5 为总 的开工时间 由公式 SUMPRODUCT B5 C5 B9 C9 计算而得 B9 C9 为可变单元格可变单元格 G5 H8 为附加的可变单元格 G H I K 列是该模型微妙所在 G 列和 H 列分别表示了实 际的正负偏差的值 I 列按照数学模型中目标约束方程计算出的左端 值 如单元格 I5 为第一个目标约束方程的左端值 由 D5 G5 H5 计 算而得 单元格 G10 为目标单元格目标单元格 它是各因素未达目标的总偏差 总 15 罚数 但是要注意的是 比如第一级目标 只有负偏差大于 0 时 才会产生罚数 同样的第二级目标只有正偏差大于 0 时才会产生罚 数 依此类推 在这里 决策者还要根据实际情况给出各级目标的 罚系数 本题给出的假定罚系数见单元格 G10 的计算公式 注意 目标等级越高 罚系数越大 目标是使总罚数最小 在规划求解参数规划求解参数对话框里 给出目标单元格 可变单元格和约 束 约束是使目标约束等式两端相等 由于依然属于线性规划问题 仍需在选项对话框里选择 采用 线性模型 和 假定非负 复选框 可以看到图图 7 4 的计算结果与前面两种方法相同 对于包含有绝对约束的目标规划模型 绝对约束的优先等级高 于任何目标约束 因而要把它放入规划求解的约束条件里 例例 8 将例例 3 中的目标利润改为 4000 试用 EXCEL 求解最优方案 解 该问题包含有一个绝对约束 机时约束 把它定义到 12 10 xx 规划求解对话框的约束里 模型与求解结果见图图 7 5 16 图图 7 5 模型中对两目标的罚系数分别设为 10 和 1 求解结果 利润目 标实现了 人工也少于 70 目标偏离量为 0 习题习题 7 1 判断以下目标规划的目标函数是否正确 1 2 max zdd min zdd 3 4 max zdd min zdd 17 7 2 用图解法求解下列目标规划问题 1 2 112332 1211 1222 1233 12 min 24 24 28 0 1 2 3 ii zM dM dM d xxdd xxdd st xxdd x x ddi 1322311 1211 1222 233 12 min 6224 5 515 0 1 2 3 ii zM dM dMdd xxdd xxdd st xdd x x ddi 3 4 111222 12 12 1211 1222 12 min 4 26 2318 3218 0 1 2 ii zM ddMdd xx xx stxxdd xxdd x x ddi 112233 1211 122 233 2 12 min 3 2210 2 60 45 80 0 ii zM dM dM d xxdd xdd stxdd x x x dd 7 3 某厂组装两种产品 有关数据如表 7 1 要求确定两种产品 的日生产计划 并满足 1 不得使装配线超负荷生产 2 不得有剩余产品 3 日产值尽可能达到 5000 元 试找出满意解 并用图示说明之 表表 7 1 产 品 单件组装工 时 日销量 件 产值 元 件 日装配 能力 18 A1 17040 B1 36060 150 7 4 上题中 若将目标要求改为 1 尽可能发挥工厂的装配能力 2 尽可能满足市场的需求 并使产量与销量保持一致 3 装配生产线可加班 但时数不得超过 30 小时 4 尽可能使日产值最大 试定出两种产品满意的日产计划 7 5 已知目标规划问题的约束条件如下 1211 1222 1 12 22 236 6 0 1 2 ii xxdd xxdd st x x x ddi 求在下述各目标函数下的满意解 1 11122 min zM dddd 2 111222 min2 zM ddMdd 3 111222 min 2 zM ddMdd 4 111222 min zM ddMdd 7 6 某公司要将一批货从三个产地运到四个销地 有关数据如 表 7 2 现要求订出调运计划 且依次满足 1 B4要保证供应 19 2 其余销地的供应量不低于 80 3 A2给 B2的供应量不低于 150 4 A2尽可能少给 B1 5 销地 B1 B2 的供应量尽可能保持平衡 要求 1 建立使总运费最小的目标规划模型 2 建立该问题的电子表格模型 并用 EXCEL 规划求解进行 求解 表 7 2 产地 销地 B1B2B3B4供应量 A17379560 A226511400 A36425750 需求量320240480380 7 7 某公司的管理层已经为其公司的两种新产品制定了各自的 市场目标 具体地说 产品 1 必须占据 15 的市场份额 而产品 2 必须有 10 的市场份额 为了获得市场 准备开展