5线性目标规划.ppt

一 目标规划概述二 目标规划的数学模型三 目标规划的图解法四 目标规划的单纯形法 第5章线性目标规划 GoalProgramming 一 目标规划概述 线性规划在实践中得到广泛应用 但有两个方面不足 一是不能处理多目标的优化问题 二是其约束条件过于刚性化 不允许约束资源有丝毫超差 目标规划是为了解决这一不足而创建的一类数学模型 线性规划是在一组线性约束条件下 寻求某一项目标的最优值 而实际问题往往要考虑多个目标的决策问题 如核电站的设计问题 传统的单目标规划只允许设定一个目标 那么单一目标选择什么 电站建设费用最低 安全运行的可靠性最高 电能输出最大 对周围环境的影响最小 显然 上述目标都很重要 且又互相矛盾 这是一个多目标决策问题 普通的线性规划是无能为力的 1 问题的提出 例1 工厂生产两种产品 受到原材料供应和设备工时的限制 在单件利润等有关数据已知的条件下 要求制订一个获利最大的生产计划 具体数据见下表 目标规划问题实例 设产品 的产量分别为 建立线性规划模型 解得最优生产计划为件 件 利润为元 如果工厂作决策时可能还需根据市场和工厂实际情况 考虑其它问题 如 1 由于产品 销售疲软 故希望产品 的产量不超过产品 的一半 2 原材料严重短缺 原料数量只有60 3 最好能节约4小时设备工时 4 计划利润不少于48元 2 目标规划的基本概念 1 目标值和正 负偏差变量 目标规划通过引入目标值和正 负偏差变量 所谓目标值是预先给定的某个目标的一个期望值 实际值 或决策值 是当决策变量x1 x2 xn选定以后目标函数的对应值 显然 实际值和目标值之间会有一定的差异 这种差异称为偏差变量 事先无法确定的未知量 用d 和d 表示 d 超出目标值的差值 称正偏差变量 d 未达到目标值的差值 称负偏差变量 当实际值超出目标值时 有d 0 d 0 当实际值未达到目标值时 有d 0 d 0 当实际值同目标值恰好一致时 d d 0 2 绝对约束与目标约束 绝对约束又称系统约束 是指必须严格满足的等式和不等式约束 如线性规划问题的所有约束都是绝对约束 不满足这些约束条件的解称为非可行解 所以它们是硬约束 目标约束是目标规划特有的 可把约束右端看做要追求的目标 在达到此目标值时允许发生正偏差或负偏差 因此在这些约束中加入正 负偏差变量 是软约束 原材料严重短缺 原料数量只有60 目标函数变为目标约束 线性规划问题的目标函数 在给定目标值和偏差变量后可变换为目标约束 这样就将目标函数则转化为目标约束 比如 计划利润不少于48元 绝对约束变为目标约束 该约束的右端项看作目标值 再引入正 负偏差变量即可 或 此为系统约束 在达到此目标值时允许发生正或负偏差 因此在这些约束中加入正 负偏差变量 它们是软约束 在给定目标值和加入正 负偏差变量之后 可以将绝对约束转化为目标约束 3 优先因子 优先等级 与权系数 在一个规划问题中 决策者在要求达到这些目标时 是有轻重缓急的 称这些目标是属于不同层次的优先等级 优先等级层次的高低可分别通过优先因子P1 P2 表示 并规定Pk Pk 1 符号 表示 远大于 表示Pk与Pk 1 不是同一各级别的量 即Pk与Pk 1有更大的优先权 对属于同一层次优先等级的不同目标 按其重要程度可分别乘上不同的权系数 权系数是一个个具体数字 乘上的权系数越大 表明该目标越重要 4 目标规划的目标函数 准则函数 从决策者的要求分析 总希望得到的结果与规定的目标值间的偏差愈小愈好 由此决策者可根据自己的要求构造一个使总偏差量为最小的目标函数 这就是目标规划的目标函数称为准则函数 记为 即目标函数是正 负偏变量的函数 一般来说 可能提出的要求只能是以下三种情况之一 对应每种要求 可分别构造目标函数 构造目标函数的方法 如希望产品 产量恰好等于产品 的产量 即正 负偏变量都要尽可能地小 这时目标函数是 如希望产品 产量低于产品 的产量 即允许达不到目标值 正偏差变量要尽可能地小 这时目标函数是 如希望产品 产量不低于产品 的产量 即要求超过目标值 不得低于目标值 负偏差变量尽可能地小 这时目标函数是 例1中目标函数的构成 希望产品 产量不超过产品 产量的一半 即正偏差变量要尽可能地小 不希望上式中的d 0 这时目标函数是 希望能节约4小时设备工时 即正偏差变量要尽可能小 不希望上式中的d 0 这时目标函数是 希望计划利润不少于48元 即负偏差变量尽可能小 不希望上式中的d 0 这时目标函数是 5 满意解 目标规划问题的求解是分级进行的 首先要求满足P1级目标的解 然后再保证P1级目标不被破坏的前提下 再要求满足P2级目标的解 依次类推 总之 是在不破坏上一级目标的前提下 实现下一级目标的最优 因此 这样最后求出的解就不是通常意义下的最优解 我们称它为满意解 之所以叫满意解 是因为前面的目标是可以保证实现或部分实现的 后面的目标就不一定能保证实现 满意解这一概念的提出是对最优化概念的一种突破 显然它更切合实际 更便于运用 因而受到广大实际工作者的欢迎而被广泛采用 3 目标规划的数学模型 在例1中若工厂提出的管理目标按优先级排列如下 级目标 希望产品 的产量不超过产品 的一半 级目标 最好能节约4小时设备工时 级目标 希望计划利润不小于48元 由于原材料严重短缺 故原材料约束作为绝对约束 试建立目标规划模型 解 引入偏差变量 目标约束 按优先级确定目标函数 级目标要求 级目标要求 级目标要求该问题的目标规划模型为 其中 为绝对约束 为目标约束 而把级目标要求设为 其余依次后退优先级 得 该问题也可以这样处理 把绝对约束 化为目标约束 1 模型的一般形式 二 目标规划的数学模型 4 对同一优先等级中的各偏差变量 若需要可按其重要程度的不同 赋予相应的权系数 2 目标规划问题的建模步骤 1 根据要研究的问题所提出的各目标与条件 确定目标值 列出目标约束与绝对约束 3 给各目标赋予相应的优先因子Pk k 1 2 K 2 可根据决策者的需要 将某些或全部绝对约束转化为目标约束 这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可 5 根据决策者的要求 按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的 要求实现极小化的目标函数 恰好达到目标值 取 允许超过目标值 取 不允许超过目标值 取 例3 某厂计划在下一个生产周期内生产甲 乙两种产品 已知资料如表所示 试制定生产计划 使获得的利润最大 同时 根据市场预测 甲的销路不是太好 应尽可能少生产 乙的销路较好 可以扩大生产 试建立此问题的数学模型 若提出下列要求 1 完成或超额完成利润指标50000元 2 产品甲不超过200件 产品乙不低于250件 3 现有钢材3600吨正好用完 试建立目标规划模型 分析 题目有三个目标层次 包含四个目标值 第三目标 第二目标 有两个要求即甲 乙 但两个具有相同的优先因子 因此需要确定权系数 本题可用单件利润比作为权系数即70 120 化简为7 12 第一目标 规定利润的目标值为50000 正 负偏差为d d 则目标函数可以转换为目标约束 既70 x1 120 x2 50000 同样 规定x2 200 x3 250则有 规定3600的钢材正好用完 原式9x1 4x2 3600则变为 目标规划模型为 例4 某工艺品厂手工生产两种工艺品A B 已知生产一件产品A需要耗费人力2工时 生产一件产品B需要耗费人力3工时 A B产品单位利润分别为250元和125元 为了最大效率利用人力资源 确定生产首要任务是保证人员高负荷生产 要求每周总耗费人力资源不能低于600工时 但也不能超过680工时的极限 次要任务是要求每周的利润超过70000元 在前两个任务的前提下 为了保证库存需要 要求每周产品A和B的产量分别不低于200和120件 因为B产品比A产品更重要 不妨假设B完成最低产量120件的重要性是A完成200件的重要性的1倍 试求如何安排生产 解 本问题中有3个不同优先权的目标 不妨用P1 P2 P3表示从高至低的优先权 P1有两个目标 每周总耗费人力资源不能低于600工时 也不能超过680工时 P2有一个目标 每周利润超过70000元 P3有两个目标 每周产品A和B的产量分别不低于200和120件 采用简化模式 最终得到目标线性规划如下 某厂生产 两种产品 有关数据如表所示 试求获利最大的生产方案 在此基础上考虑 1 产品 的产量不低于产品 的产量 2 充分利用设备有效台时 不加班 3 利润不小于56元 解 第一目标 即产品 的产量不大于 的产量 第二目标 练习 第三目标 规划模型 小结 目标规划模型与线性规划模型的异同 三 目标规划的图解法 和线性规划问题一样 图解法虽然只适用于两个决策变量的目标规划问题 但其操作简便 原理一目了然 并且有助于理解一般目标规划问题的求解原理和过程 例 用图解法求解目标规划问题 解 确定各个约束条件的可行域 在x1Ox2坐标平面上 暂不考虑每个约束方程中的正 负偏差变量 将上述每一个约束方程用一条直线表示出来 再用两个箭头分别表示上述目标约束方程中的正 负偏差变量 E D F 3x1 4x2 0 x1 2x2 8得x1 3 2 x2 2 4 例 用图解法求解 x2 x1 0 L1 L2 L3 L4 B C D E F 结论 CDEF内均为满意解 最优解 无穷多最优解 A 例 用图解法求解目标规划问题 0 12345678 123456 A x2 x1 B C B 0 6250 4 6875 C 0 5 2083 B C线段上的所有点均是该问题的解 无穷多最优解 例 已知一个生产计划的线性规划模型为 其中目标函数为总利润 x1 x2为产品A B产量 现有下列目标 1 要求总利润必须超过2500元 2 考虑产品受市场影响 为避免积压 A B的生产量不超过60件和100件 3 由于甲资源供应比较紧张 不要超过现有量140 试建立目标规划模型 并用图解法求解 解 以产品A B的单件利润比2 5 1为权系数 模型如下 0 x2 0 x1 14012010080604020 20406080100 A B C D 结论 C 60 58 3 为所求的满意解 检验 将上述结果带入模型 因 0 0 0 存在 0 存在 所以 有下式 minZ P3 将x1 60 x2 58 3带入约束条件 得 30 60 12 58 3 2499 6 2500 2 60 58 3 178 3 140 1 60 601 58 3 58 3 100 由上可知 若A B的计划产量为60件和58 3件时 所需甲资源数量将超过现有库存 在现有条件下 此解为非可行解 为此 企业必须采取措施降低A B产品对甲资源的消耗量 由原来的100 降至78 5 140 178 3 0 785 才能使生产方案 60 58 3 成为可行方案 练习 用图解法求解下列目标规划问题 C D 结论 有无穷多最优解 C 2 4 D 10 3 10 3 1 建立初始单纯形表 由于目标规划中的目标函数一定是求最小 检验准则发生改变 以约束条件中的所有负偏差变量或松弛变量为初始基变量 即构成一个基 检验数按优先因子分成K行 分别计算出各列的检验数 2 检验是否为满意解 判别准则如下 1 对目标函数的优化是按优先级顺序逐级进行的 当P1行的所有检验数均为非负 说明第一级已得到优化 可转入下一级 再考查P2行的检验数是否存在负值 单纯形法的计算步骤 四 目标规划的单纯形法 3 确定进基换入变量 在Pk行 从那些上面没有正检验数的负检验数中 选绝对值最大者 对应的变量xs就是换入变量 若Pk行中有几个相同的绝对值最大者 则依次比较它们各列下部的检验数 取其绝对值最大的负检验数的所在列的xs为换入变量 假如仍无法确定 则选最左边的变量 变量下标小者 为换入变量 2 计算停止的准则 检验数P1 P2 PK行的所有值均为非负 如P1 P2 Pi行的所有检验数为非负 第Pi 1行存在负检验数 但在负检验数所在列的上面行中有正检验数 4 确定出基换出变量 其方法同线性规划 即依据最小比值法则故确定xr为出基变量 ers为主元素 若有几个相同的行可供选择时 选最上面那一行所对应得变量为xr 5 变量迭代 以为主元素进行变换 得到新的单纯形表 获得一组新解 返回到第2步 6 对求得的解进行分析 若计算结果满意 停止运算 若不满意 需修改模型 即调整目标优先等级和权系数 或者改变目标值 重新进行第1步 例 用单纯形法求解下列目标规划问题 min 2500 30 140 2 60 1 60 故为换出变量 min 700 30 20 2 10 故为换出变量 min 400 15 10 故为换出变量 min 350 6 1250 6 100 1 75 故为换出变量 P3行的检验数中有负数 但上面行有正检验数 说明P3优先等级目标没有实现 但已无法改进 得到满意解x1 60 x2 175 3 115 3 125 3 结果分析 计算结果表明 应生产A产品60件 B产品175 3件 2500元的利润目标刚好达到 125 3 表明产品比最高限额少125 3件 满足要求 115 3表明甲资源超过库存115 3公斤 该目标没有达到 从表中还可以看到 P3的检验数还有负数 但其高等级的检验数却是正数 要保证P1目标实现 P3等级目标则无法实现 所以 按现有消耗水平和资源库存量 无法实现2500元的利润目标 可考虑如下措施 降低A B产品对甲资源的消耗量 以满足现有甲资源库存量的目标 或改变P3等级目标的指标值 增加甲资源115 3公斤 若很难实现上述措施 则需改变现有目标的优先等级 以取得可行的满意解果 练习 用单纯形法求解下列目标规划问题 min 10 2 56 10 11 1 5 故为换出变量 min 10 3 10 6 3 12 3 2 故为换出变量 最优解为x1 2 x2 4 但非基变量的检验数为零 故此题有无穷多最优解 min 4 24 6 4 故为换出变量 最优解为x1 10 3 x2 10 3 作业 1 某厂生产A B C三种产品 装配工作在同一生产线上完成 三种产品时的工时消耗分别为6 8 10小时 生产线每月正常工作时间为200小时 三种产品销售后 每台可获利分别为500 650和800元 每月销售量预计为12 10和6台 该厂经营目标如下 1 利润指标为每月16000元 争取超额完成 2 充分利用现有生产能力 3 可以适当加班 但加班时间不得超过24小时 4 产量以预计销售量为准 试建立目标规划模型 答案 1 设x1 x2 x3分别表示三种产品的产量 则该问题的目标规划模型为 2 用图解法求解下列目标规划问题 满意解为由x1 3 3 x2 3 5 1 5 所连线段 3 用图解法解下列目标规划模型 x1 400 x2 0 Z 8