目标规划建模与图解法.pptx

本章内容要点本章内容要点 目标规划的基本特征、基本概目标规划的基本特征、基本概念和模型念和模型 目标规划的图解法目标规划的图解法 解目标规划的单纯形法解目标规划的单纯形法第第5 5章章 目标规划目标规划 实践中，人们经常遇到一类含有实践中，人们经常遇到一类含有多个目标的数学规划问题，多个目标的数学规划问题，目标规划目标规划(goal programming)，是一种多目标是一种多目标规划方法。规划方法。目标规划在实践中的应用十分广泛，目标规划在实践中的应用十分广泛，它的重要特点是对各个目标分级加权它的重要特点是对各个目标分级加权与逐级优化，这符合人们处理问题要与逐级优化，这符合人们处理问题要分别轻重缓急保证重点的思考方式。分别轻重缓急保证重点的思考方式。目标规划问题的提出目标规划问题的提出例例5.1 某公司分厂用一条生产线生产两某公司分厂用一条生产线生产两种产品种产品A和和B，每周生产线运行时间为每周生产线运行时间为60小时，生产一台小时，生产一台A产品需要产品需要4小时，生小时，生产一台产一台B产品需要产品需要6小时根据市场预测，小时根据市场预测，A、B产品平均销售量分别为每周产品平均销售量分别为每周9、8台，它们销售利润分别为台，它们销售利润分别为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上述线性规划的最优解为上述线性规划的最优解为(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（=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）目标规划的目标函效）目标规划的目标函效 目标规划的目标函数是通过各目目标规划的目标函数是通过各目标约束的正、负偏差变量和赋于相应标约束的正、负偏差变量和赋于相应的优先等级来构造的的优先等级来构造的 决决策策者者的的要要求求是是尽尽可可能能从从某某个个方方向向缩缩小小偏偏离离目目标标的的数数值值。于于是是，目目标标规划的目标函数应该是求极小：规划的目标函数应该是求极小：min f 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的权系数。的权系数。目标规划模型目标规划模型 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 (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 5.2 目标规划的几何意义及图解法目标规划的几何意义及图解法 对只有对只有2 2个决策变量的目标规个决策变量的目标规划数学模型，可以用图解法来分划数学模型，可以用图解法来分析求解。析求解。通过图解示例，可以看到目标通过图解示例，可以看到目标规划中优先因子，正、负偏差变规划中优先因子，正、负偏差变量及权系数等的几何意义。量及权系数等的几何意义。图解法来求解例图解法来求解例5-1 首先在平面直角坐标系的第一象首先在平面直角坐标系的第一象限内限内(x0)，作出与各约束条件对应的，作出与各约束条件对应的直线直线;然后在这些直线旁分别标上然后在这些直线旁分别标上 G-i，i=1，2，3，4。图中图中 x,y 分别表示问题例分别表示问题例 5.1 的的x1和和x2；各直线移动使之函数值变大、各直线移动使之函数值变大、变小的方向用变小的方向用+、-表示表示,其取值即为其取值即为正负偏差变量正负偏差变量di+,di-(如图如图5-1所示所示)。0 5 10 15 20 x1x22015105+-G-1+-G-2+-G-4+-G-3图5-1 根据目标函数的优先因子分析求解：根据目标函数的优先因子分析求解：首先考虑第首先考虑第1级具有级具有P1优先因子的目标的实优先因子的目标的实现，在目标函数中要求实现现，在目标函数中要求实现 min(d1+d2+)，取，取d1+=d2+=0.图图 52 中阴影部分即表示出该最中阴影部分即表示出该最优解集合的所有点。优解集合的所有点。我们在第我们在第1级目标的最优解集合中找满足第级目标的最优解集合中找满足第2 优先级要求优先级要求min(d3+)的最优解，取的最优解，取 d3+=0，可得到图可得到图53中阴影部分即是满足第中阴影部分即是满足第1、第、第2优优先级要求的最优解集合。先级要求的最优解集合。图5-20 5 10 15 20 x1x22015105+-G-1+-G-2-+G-4+-G-3A(3,8)图5 3 0 5 10 15 20 x1x22015105+-G-1+-G-2-+G-4+-G-3A(3,8)第第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 0 5 10 15 20 x1x22015105+-G-1+-G-2-+G-4+-G-3A(3,8)5.3 目标规划计算机求解目标规划计算机求解利用软件按照目标的优先级逐次求解：利用软件，按照目标的优先级逐次求解：第第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,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-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