《目标规划——建模与图解法》由会员分享，可在线阅读，更多相关《目标规划——建模与图解法（33页珍藏版）》请在金锄头文库上搜索。
1、第5章,目 标 规 划,本章内容要点,目标规划的基本特征、基本概念和模型 目标规划的图解法 解目标规划的单纯形法,第5章 目标规划,实践中，人们经常遇到一类含有多个目标的数学规划问题，目标规划(goal programming)，是一种多目标规划方法。 目标规划在实践中的应用十分广泛，它的重要特点是对各个目标分级加权与逐级优化，这符合人们处理问题要分别轻重缓急保证重点的思考方式。,目标规划问题的提出,例5.1 某公司分厂用一条生产线生产两种产品A和B ，每周生产线运行时间为60小时，生产一台A产品需要4小时，生产一台B产品需要6小时根据市场预测，A、B产品平均销售量分别为每周9、8台，它们销售
2、利润分别为12、18万元。在制定生产计划时，经理考虑下述4项目标：,首先，产量不能超过市场预测的需求； 其次，工人加班时间最少； 第三，希望总利润最大； 最后，要尽可能满足市场需求, 当不能满足时, 市场认为B产品的重要性是A产品的2倍 试建立这个问题的数学模型,问题分析,如果把总利润最大看作目标，而把产量不能超过市场预测的销售量、工人加班时间最少和要尽可能满足市场需求的目标看作约束，则可建立一个单目标线性规划模型：,设决策变量 x1，x2 分别为产品A，B的产量 Max z = 12x1 + 18x2 s.t. 4x1 + 6x2 60 x1 9 x2 8 x1 , x2 0,上述线性规划的
3、最优解为(9,4)T 到 (3,8)T 所在线段上的点, 最优目标值为z* = 180, 即可选方案有多种。 在实际上, 这个结果并非完全符合决策者的要求, 它只实现了经理的第13个目标，而没有达到最后一个目标。进一步分析可知，要实现全体目标是不可能的。,目标规划建模,首先，把例5.1的4个目标表示为不等式。 设x1, x2 分别为产品A, B的产量. 第1个目标为: x1 9 ，x2 8 ； 第2个目标为: 4x1 + 6x2 60 ； 第3个目标为: 希望总利润最大，要表示成不等式需要找到一个目标上界，这里可以估计为252（=129 + 188），于是有 12x1 + 18x2 252；
4、第四个目标为: x1 9，x2 8；,目标规划模型的基本概念,（1）正、负偏差变量d+，d- 我们用正偏差变量d+ 表示决策值超过目标值的部分；负偏差变量d- 表示决策值不足目标值的部分。因决策值不可能既超过目标值同时又末达到目标值，故恒有 d+ d- 0 （2）绝对约束和目标约束 我们把所有等式、不等式约束分为两部分：绝对约束和目标约束。,绝对约束:指必须严格满足的等式约束和不等式约束；所以它们是硬约束。如果某种原材料数量有限制，并且无法从其它渠道予以补充，则构成绝对约束。 目标约束：是目标规划特有的，我们可以把约束右端项看作要努力追求的目标值，但允许发生正式负偏差，用在约束中加入正、负偏差
5、变量来表示，称它们是软约束。,根据分析, 我们有如下目标约束 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.,P
6、i的含义： 首先保证P1级目标实现，这时可不考虑次级目标；P2级目标在实现P1级目标的基础上考虑，以此类推。 当需要区别具有相同优先因子的若干目标的差别时，可分别赋于它们不同的权系数wj 。 优先因子及权系数的值，均由决策者按具体情况来确定,（4）目标规划的目标函效 目标规划的目标函数是通过各目标约束的正、负偏差变量和赋于相应的优先等级来构造的 决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数应该是求极小： min f f (d+，d-),目标函数的基本形式有三种： （1） 要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可能地小。这时取 min（d+ +
7、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的权系数。,目标规划模型 Min f =P1(d1+d2+
8、)+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个决策变量的目标规划数学模型，可以用图解法来分析求解。 通过图解示例，可以看到目标规划中优先因子，正、负偏差变量及权系数等
9、的几何意义。,图解法来求解例5-1,首先在平面直角坐标系的第一象限内(x0)，作出与各约束条件对应的直线; 然后在这些直线旁分别标上 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. 图 52 中阴影部分即表示出该最优解集合的所有点。 我们在第1级目标的最优解集合中找满足第2 优先级要
10、求min(d3+ ) 的最优解，取 d3+ = 0 ，可得到图53中阴影部分即是满足第1、第2优先级要求的最优解集合。,图5 - 2,图5 3,第3优先级要求 min(d4-)，根据图示可知，d4- 不可能取0值，我们取使d4- 最小的值72得到图54中两阴影部分的交线(粗线)，其表示满足第1、第2及第3优先级要求的最优解集合。 第4优先级要求 min(d1- + 2d2-) ，即要在粗线段中找出最优解。由于d1- 的权因子小于d2- ，因此在这里可以考虑取d2- =0。于是最优解为A点x1 = 3，x2 = 8，解得d1-=6。,图5 4,5.3 目标规划计算机求解,利用软件，按照目标的优先
11、级逐次求解： 第1步：取原问题的P1级目标作为目标函数，原约束为问题的约束求解； 若以求得第k步的解； 第k+1步：取原问题的Pk+1级目标作为目标函数，在上一级约束的基础上添加上一级的最优目标值的等式构成问题的约束再求解； 直至得到全问题的最优解。,例：目标规划模型 Min f =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,
12、2,3,4. 用计算机求解,第1步 求解下列线性规划模型 Min f = 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步 求解下列线性规划模型 Min f = d3+ s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 12x1 + 18x2 +d4
13、- -d4+ =252 d1+ = 0， d2+ = 0 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4. 解得： d3+ = 0,第3步 求解下列线性规划模型 Min f = 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. 解得： d4- = 72,第4步 求解下列线性规划模型 Min f = d1- +2d2- 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， d4- =72 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4. 解得： x1 =3, x2 = 8, d1- =5, d2- = 0, f =180,
