《目标规划xfj》PPT课件.ppt

第四章目标规划 目标规划的数学模型解目标规划的图解法解目标规划的单纯形法灵敏度分析 例1 某工厂生产 两种产品 已知有关数据见下表 试求获利最大生产方案 目标规划的数学模型 问题是 在实际生产时的考虑如下 1 根据市场信息 产品 的销量有下降的趋势 故产品 的产量不大于产品 的产量 2 超过计划供应的原材料时 需用高价采购 这就使得成本增加 3 应尽可能充分利用设备 但不希望加班 4 应尽可能达到并超过计划利润指标56元 显然 这个决策问题有多个目标需要满足 应该怎样建立目标规划的数学模型 它和前面所讲的线性规划的数学模型有何异同 线性规划的数学模型 用一组未知变量表示要求的方案 这组未知变量称为决策变量 存在一定的约束条件 且为线性表达式 有一个目标要求 最大化 当然也可以是最小化 目标表示为未知变量的线性表达式 称之为目标函数 对决策变量有非负要求 目标规划数学模型的相关概念 用一组未知变量xi表示决策变量 此外 引进正 负偏差变量d d 存在一定的约束条件 包含绝对约束和目标约束 各目标具有不同的优先因子Pk或权系数wj 目标函数由各目标约束的正 负偏差变量d d 和赋予其的优先因子及权系数构造 对决策变量和正 负偏差变量有非负要求 用一组未知变量xi表示决策变量 此外 引进正 负偏差变量d d 正偏差量d 表示决策值超过目标值的部分 负偏差量d 表示决策值未达到目标值的部分 因为决策值不可能既超过目标值同时又未达到目标值 则恒有d d 0 存在一定的约束条件 包含绝对约束和目标约束 绝对约束是指必须严格满足的约束条件 如线性规划中的约束条件都是绝对约束 目标约束是目标规划特有的 目标约束的右端是所要追求的目标值 允许该值发生正负偏差 因此在此约束的左端加入正 负偏差量d d 各目标具有不同的优先因子或权系数 决策者对于不同的目标要求 有主次轻重之分 要求第一位达到的目标赋予优先因子P1 次位的目标赋予优先因子P2 依次类推 并规定Pk Pk 1 若要区别具有相同优先因子的两个目标的差别 可分别赋予它们不同的权系数wj 注 目标的主次轻重之分由决策者确定 目标函数由各目标约束的正负偏差量和各目标相应的优先因子及权系数构造 当某一目标值确定后 决策者的要求是尽可能地缩小与目标值的偏离 因此目标规划的目标函数形式为minz f d d 其基本形式有三种 1 要求恰好达到目标值 即正负偏差都要尽可能的小 这时要求minz f d d 2 要求不超过目标值 也就是允许达不到目标值 而正偏差量要尽可能的小 即minz f d 3 要求不低于目标值 也就是允许超过目标值 而负偏差量要尽可能的小 即minz f d 例2对于例1中需要考虑的多个目标 试给出合适的目标规划数学模型 解 1 设定决策变量xi 2 确定所需考虑的各个目标的优先级及权系数 假定决策者在原材料供应受严格限制的基础上考虑 首先是产品 的产量不低于产品 的产量 P1级 其次是充分利用设备有效台时 不加班 P2级 再次是利润不小于56元 P3级 原材料供应受严格限制 绝对约束 首先是产品 的产量不低于产品 的产量 优先级为P1的目标约束 其次是充分利用设备有效台时 不加班 优先级为P2的目标约束 再次是利润不小于56元 优先级为P3的目标约束 3 将各个目标写入目标规划的约束条件 包括绝对约束和目标约束 4 确定各个目标约束对于各自正负偏差量的的要求 首先是产品 的产量不低于产品 的产量 也就是要求x1 x2不超过目标值0 即尽量小 其次是充分利用设备有效台时 不加班 也就是要求x1 2x2最好恰好为10 即尽量小 再次是利润不小于56元 也就是要求8x1 10 x2不小于目标值56 即尽量小 5 用各目标约束的优先因子及权系数与其自身偏差量要求的乘积的加和构造目标函数 6 给出各决策变量和偏差变量的非负要求 将上述步骤加以整理 得例2的数学模型为 目标规划的一般数学模型 目标规划vs线性规划 1 线性规划只有一个目标 而目标规划具有多个目标 并有不同的优先级 低优先级目标必须服从高优先级目标的实现 2 线性规划寻求单一目标的最优值 而目标规划寻求所有目标与预计成果的最小差距 差距越小 目标实现的可能性越大 3 线性规划只接受最优解 而目标规划接受满意解 即如果某些低优先级的约束得不到满足 将目标规划问题的解称为满意解 2 解目标规划的图解法 求解思路 1 在平面直角系的第一象限 做出满足绝对约束条件的可行域 2 令 做出相应的目标约束线 并确定正负偏差量的方向 3 根据目标函数中各目标偏差量的优先等级依次分析求解 例 用图解法求解例2 O x1 x2 d1 d1 d2 d2 d3 d3 例3解 假设x1 x2分别表示彩色和黑白电视机的产量 F E G J D C O B A x1 x2 d1 d1 d2 d2 d3 d3 d4 d4 H 3解目标规划的单纯形法 例 用单纯形法求解书上例2的目标规划数学模型 1 将该目标规划中的第四个约束 绝对约束 修正为标准化形式 2 按标准化模型列出单纯形表 将检验数行按优先因子的个数排成K行 见下表 确定初始解 cB d1 x1 b xB x2 xs d2 d1 d3 d2 d3 cj P3 P2 P1 P2 11211 01 11 1 10121 1 568101 1 xsd1 d2 d3 00P2P3 cj zj P1P2P3 1 8 2 10 1 2 1 3 由高优先级开始检查每行检验数是否存在负数 且对应前几行的系数为0 若存在 取最小者对应的变量为换入变量进基 然后用最小比原则确定出基变量 得到主元素 若不存在 计算结束 判断是否满意 cB d1 x1 b xB x2 xs d2 d1 d3 d2 d3 cj P3 P2 P1 P2 11211 01 11 1 10121 1 568101 1 xsd1 d2 d3 00P2P3 cj zj P1P2P3 1 8 2 10 1 2 1 4 确定主元素后 按照单纯形法进行基变换运算 得到关于新基的计算表 换基迭代 然后重新计算检验数 第2步 并判断是否最优 第三步 cB d1 x1 b xB x2 xs d2 d1 d3 d2 d3 cj P3 P2 P1 P2 63 21 1 21 2 53 21 1 1 21 2 51 211 2 1 2 63 551 1 xsd1 x2d3 000P3 cj zj P1P2P3 3 1 15 1 3 1 5 5 继续进行基变换运算 得到关于新基的计算表 然后计算检验数 判断是否满意 cB d1 x1 b xB x2 xs d2 d1 d3 d2 d3 cj P3 P2 P1 P2 312 2 1 21 2 21 13 3 1 21 2 414 3 4 3 1 61 6 21 5 35 31 3 1 3 xsd1 x2x1 0000 cj zj P1P2P3 1 1 1 1 所有非基变量的检验数均 0 已达到满意 6 由于非基变量d3 的检验数为0 表明存在多重解 在上表的基础上以d3 作为换入变量 继续迭代 cB d1 x1 b xB x2 xs d2 d1 d3 d2 d3 cj P3 P2 P1 P2 312 2 1 21 2 21 13 3 1 21 2 414 3 4 3 1 61 6 21 5 35 31 3 1 3 xsd1 x2x1 0000 cj zj P1P2P3 1 1 1 1 第一个满意解为 x1 2 x2 4 对应于图解法中的G点第二个满意解为 x1 10 3 x2 10 3 对应于图解法中的D点 G D两点的凸线性组合都是此问题的满意解 4目标规划的灵敏度分析 目标规划的灵敏度分析方法与线性规划相似 但其除了分析各项系数 b cj aij 的变化外 还有优先因子的变化问题 例 已知目标规划问题 其最终满意表如下所示 如果目标函数的优先等级发生变化 试分析原解有什么变化 1 2 解 分析式 1 可见 式 1 实际是将原目标函数中的优先因子对换了 这时需将原满意表的检验数的P2 P3行和cj行的P2 P3对换即可 前两行检验数都为正 最后一行检验数有负 但对应前两行有系数为正 说明仍达到满意 解 分析式 2 可见 式 2 实际是将原目标函数中的优先因子对换了 这时需将原满意表的检验数行和cj行的相应位置对换 第一行检验数有负数 选择最小者对应的变量进基 然后用最小比原则确定出基变量 得到主元素 通过换基迭代 然后计算检验数 并判断是否达到满意 如果不满意 继续换基进行运算 前两行检验数都为正 最后一行检验数有负 但对应前两行有系数为正 说明已达到满意 x1 4 x2 12 5应用举例 例6某单位领导在考虑本单位职工的升级调资方案时 依次遵守以下规定 1 不超过年工资总额60000 2 每级的人数不超过定编规定的人数 3 级的升级面尽可能达到现有人数的20 且无越级提升 4 级不足编制的人数可录用新职工 又 级的职工有10 要退休 有关资料汇总下表 问如何拟定满意的方案 解 1 设定决策变量 假设x1 x2 x3分别表示提升到 级和录用到 级的新职工人数 2 确定所需考虑的各个目标的优先级及权系数 对各目标的优先因子确定为 P1 不超过年工资总额60000元 P2 每级的人数不超过定编规定的人数 P3 级升级面尽可能达到现有人数的20 3 将各