目标规划——建模与图解法.ppt

第5章 目标规划 本章内容要点 目标规划的基本特征 基本概念和模型目标规划的图解法解目标规划的单纯形法 第5章目标规划 实践中 人们经常遇到一类含有多个目标的数学规划问题 目标规划 goalprogramming 是一种多目标规划方法 目标规划在实践中的应用十分广泛 它的重要特点是对各个目标分级加权与逐级优化 这符合人们处理问题要分别轻重缓急保证重点的思考方式 目标规划问题的提出 例5 1某公司分厂用一条生产线生产两种产品A和B 每周生产线运行时间为60小时 生产一台A产品需要4小时 生产一台B产品需要6小时 根据市场预测 A B产品平均销售量分别为每周9 8台 它们销售利润分别为12 18万元 在制定生产计划时 经理考虑下述4项目标 首先 产量不能超过市场预测的需求 其次 工人加班时间最少 第三 希望总利润最大 最后 要尽可能满足市场需求 当不能满足时 市场认为B产品的重要性是A产品的2倍 试建立这个问题的数学模型 问题分析 如果把总利润最大看作目标 而把产量不能超过市场预测的销售量 工人加班时间最少和要尽可能满足市场需求的目标看作约束 则可建立一个单目标线性规划模型 设决策变量x1 x2分别为产品A B的产量 Maxz 12x1 18x2 s t 4x1 6x2 60 x1 9 x2 8 x1 x2 0 上述线性规划的最优解为 9 4 T到 3 8 T所在线段上的点 最优目标值为z 180 即可选方案有多种 在实际上 这个结果并非完全符合决策者的要求 它只实现了经理的第1 3个目标 而没有达到最后一个目标 进一步分析可知 要实现全体目标是不可能的 目标规划建模 首先 把例5 1的4个目标表示为不等式 设x1 x2分别为产品A B的产量 第1个目标为 x1 9 x2 8 第2个目标为 4x1 6x2 60 第3个目标为 希望总利润最大 要表示成不等式需要找到一个目标上界 这里可以估计为252 12 9 18 8 于是有12x1 18x2 252 第四个目标为 x1 9 x2 8 目标规划模型的基本概念 1 正 负偏差变量d d 我们用正偏差变量d 表示决策值超过目标值的部分 负偏差变量d 表示决策值不足目标值的部分 因决策值不可能既超过目标值同时又末达到目标值 故恒有d d 0 2 绝对约束和目标约束我们把所有等式 不等式约束分为两部分 绝对约束和目标约束 绝对约束 指必须严格满足的等式约束和不等式约束 所以它们是硬约束 如果某种原材料数量有限制 并且无法从其它渠道予以补充 则构成绝对约束 目标约束 是目标规划特有的 我们可以把约束右端项看作要努力追求的目标值 但允许发生正式负偏差 用在约束中加入正 负偏差变量来表示 称它们是软约束 根据分析 我们有如下目标约束x1 d1 d1 9 5 1 x2 d2 d2 8 5 2 4x1 6x2 d3 d3 60 5 3 12x1 18x2 d4 d4 252 5 4 3 优先因子与权系数 设有L个目标函数f1 f2 fL 针对决策者对达到目标的主次要求 引入优先因子Pi i 1 2 L 设目标函数优先序为f1 f2 fL 把要求第1位达到的目标赋于优先因子P1 次位的目标赋于优先因子P2 并规定Pi Pi 1 i 1 2 L 1 Pi的含义 首先保证P1级目标实现 这时可不考虑次级目标 P2级目标在实现P1级目标的基础上考虑 以此类推 当需要区别具有相同优先因子的若干目标的差别时 可分别赋于它们不同的权系数wj 优先因子及权系数的值 均由决策者按具体情况来确定 4 目标规划的目标函效 目标规划的目标函数是通过各目标约束的正 负偏差变量和赋于相应的优先等级来构造的 决策者的要求是尽可能从某个方向缩小偏离目标的数值 于是 目标规划的目标函数应该是求极小 minf f d d 目标函数的基本形式有三种 1 要求恰好达到目标值 即使相应目标约束的正 负偏差变量都要尽可能地小 这时取min d d 2 要求不超过目标值 即使相应目标约束的正偏差变量要尽可能地小 这时取min d 3 要求不低于目标值 即使相应目标约束的负偏差变量要尽可能地小 这时取min d 对于例7 1 根据决策者的考虑知第一优先级要求min d1 d2 第二优先级要求min d3 第三优先级要求min d4 第四优先级要求min d1 2d2 这里 当不能满足市场需求时 市场认为B产品的重要性是A产品的2倍 即减少B产品的影响是A产品的2倍 因此我们引入了2 1的权系数 目标规划模型 Minf P1 d1 d2 P2d3 P3d4 P4 d1 2d2 s t x1 d1 d1 9 x2 d2 d2 8 4x1 6x2 d3 d3 60 5 5 12x1 18x2 d4 d4 252 x1 x2 di di 0 i 1 2 3 4 目标规划模型一般形式 LGP 中的第2行是K个目标约束 第3行是m个绝对约束 ckj和gk是目标参数 5 2目标规划的几何意义及图解法 对只有2个决策变量的目标规划数学模型 可以用图解法来分析求解 通过图解示例 可以看到目标规划中优先因子 正 负偏差变量及权系数等的几何意义 图解法来求解例5 1 首先在平面直角坐标系的第一象限内 x 0 作出与各约束条件对应的直线 然后在这些直线旁分别标上G i i 1 2 3 4 图中x y分别表示问题例5 1的x1和x2 各直线移动使之函数值变大 变小的方向用 表示 其取值即为正负偏差变量di di 如图5 1所示 根据目标函数的优先因子分析求解 首先考虑第1级具有P1优先因子的目标的实现 在目标函数中要求实现min d1 d2 取d1 d2 0 图5 2中阴影部分即表示出该最优解集合的所有点 我们在第1级目标的最优解集合中找满足第2优先级要求min d3 的最优解 取d3 0 可得到图5 3中阴影部分即是满足第1 第2优先级要求的最优解集合 图5 2 图5 3 第3优先级要求min d4 根据图示可知 d4 不可能取0值 我们取使d4 最小的值72得到图5 4中两阴影部分的交线 粗线 其表示满足第1 第2及第3优先级要求的最优解集合 第4优先级要求min d1 2d2 即要在粗线段中找出最优解 由于d1 的权因子小于d2 因此在这里可以考虑取d2 0 于是最优解为A点x1 3 x2 8 解得d1 6 图5 4 5 3目标规划计算机求解 利用软件 按照目标的优先级逐次求解 第1步 取原问题的P1级目标作为目标函数 原约束为问题的约束求解 若以求得第k步的解 第k 1步 取原问题的Pk 1级目标作为目标函数 在上一级约束的基础上添加上一级的最优目标值的等式构成问题的约束再求解 直至得到全问题的最优解 例 目标规划模型 Minf P1 d1 d2 P2d3 P3d4 P4 d1 2d2 s t x1 d1 d1 9 x2 d2 d2 8 4x1 6x2 d3 d3 60 12x1 18x2 d4 d4 252 x1 x2 di di 0 i 1 2 3 4 用计算机求解 第1步求解下列线性规划模型 Minf d1 d2 s t x1 d1 d1 9 x2 d2 d2 8 4x1 6x2 d3 d3 60 12x1 18x2 d4 d4 252 x1 x2 di di 0 i 1 2 3 4 得解 d1 d2 0 第2步求解下列线性规划模型 Minf d3 s t x1 d1 d1 9 x2 d2 d2 8 4x1 6x2 d3 d3 60 12x1 18x2 d4 d4 252 d1 0 d2 0 x1 x2 di di 0 i 1 2 3 4 解得 d3 0 第3步求解下列线性规划模型 Minf d4 s t x1 d1 d1 9 x2 d2 d2 8 4x1 6x2 d3 d3 60 12x1 18x2 d4 d4 252 d1 0 d2 0 d3 0 x1 x2 di di 0 i 1 2 3 4