目标规划及目标规划模型

上传人：6*** IP属地：贵州上传时间：2023-01-03 格式：PPTX 页数：47 大小：241.20KB 积分：20 举报 版权申诉

已阅读5页，还剩42页未读，继续免费阅读

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

目标规划

在科学研究、经济建设和生产实践中，人们经常遇到一类含有多个目标的数学规划问题，我们称之为多目标规划。本章介绍一种特殊的多目标规划叫目标规划(goalprogramming)，这是美国学者Charnes等在1952年提出来的。目标规划在实践中的应用十分广泛，它的重要特点是对各个目标分级加权与逐级优化，这符合人们处理问题要分别轻重缓急保证重点的思考方式。本章分目标规划模型、目标规划的几何意义与图解法和求解目标规划的单纯形方法等三个部分进行介绍。

2.1目标规划模型

2.1.1问题提出

为了便于理解目标规划数学模型的特征及建模思路,我们首先举一个简单的例子来说明.

例2.1.1某公司分厂用一条生产线生产两种产品A和B，每周生产线运行时间为60小时，生产一台A产品需要4小时，生产一台B产品需要6小时．根据市场预测，A、B产品平均销售量分别为每周9、8台，它们销售利润分别为12、18万元。在制定生产计划时，经理考虑下述4项目标：

2.1目标规划模型2.1.1问题提出(续)首先，产量不能超过市场预测的销售量；其次，工人加班时间最少；第三，希望总利润最大；最后，要尽可能满足市场需求,当不能满足时,市场认为B产品的重要性是A产品的2倍．试建立这个问题的数学模型．讨论：

若把总利润最大看作目标，而把产量不能超过市场预测的销售量、工人加班时间最少和要尽可能满2.1目标规划模型

2.1.1问题提出(续)足市场需求的目标看作约束，则可建立一个单目标线性规划模型

设决策变量x1，x2

分别为产品A，B的产量

MaxZ=12x1+18x2

s.t.4x1+6x260

x28

x1,x20

2.1目标规划模型2.1.1问题提出(续)容易求得上述线性规划的最优解为(9,4)T

到(3,8)T

所在线段上的点,最优目标值为Z*=180,即可选方案有多种.在实际上,这个结果并非完全符合决策者的要求,它只实现了经理的第一、二、三条目标，而没有达到最后的一个目标。进一步分析可知，要实现全体目标是不可能的。2.1目标规划模型2.1.2目标规划模型的基本概念把例的4个目标表示为不等式.仍设决策变量x1，x2

分别为产品A，B的产量.那麽,第一个目标为:x19，x28；

第二个目标为:4x1+6x260；

第三个目标为:希望总利润最大，要表示成不等式需要找到一个目标上界，这里可以估计为252（=129+188），于是有12x1+18x2

252；

第四个目标为:x1

9，x2

8；

2.1.2目标规划模型的基本概念（续）下面引入与建立目标规划数学模型有关的概念．

（1）、正、负偏差变量d

+，d-

我们用正偏差变量d

+表示决策值超过目标值的部分；负偏差变量d-表示决策值不足目标值的部分。因决策值不可能既超过目标值同时又未达到目标值，故恒有d

+d-＝0．

（2）、绝对约束和目标约束我们把所有等式、不等式约束分为两部分：绝对约束和目标约束。2.1.2目标规划模型的基本概念（续）绝对约束是指必须严格满足的等式约束和不等式约束；如在线性规划问题中考虑的约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。设例2.1.1中生产A，B产品所需原材料数量有限制，并且无法从其它渠道予以补充，则构成绝对约束。目标约束是目标规划特有的，我们可以把约束右端项看作要努力追求的目标值，但允许发生正式负偏差，用在约束中加入正、负偏差变量来表示，于是称它们是软约束。2.1目标规划模型

2.1.2目标规划模型的基本概念（续）

对于例2.1.1,我们有如下目标约束

+d1--d1+=9(2.1.1)

x2+d2--d2+=8(2.1.2)

4x1+6x2

+d3--d3+=60(2.1.3)

12x1+18x2

+d4--d4+=252(2.1.4)2.1目标标规规划划模模型型目标标规规划划模模型型的的基基本本概概念念（（续续））(3)、、优先先因因子子与与权权系系数数．．对于于多多目目标标问问题题，，设设有有L个目目标标函函数数f1,f2,,fL,决策策者者在在要要求求达达到到这这些些目目标标时时，，一一般般有有主主次次之之分分。。为为此此，，我我们们引引入入优优先先因因子子Pi，i=1,2,,L.无妨妨设设预预期期的的目目标标函函数数优优先先顺顺序序为为f1,f2,,fL,我们们把把要要求求第第一一位位达达到到的的目目标标赋赋于于优优先先因因子子P1，次位位的的目目标标赋赋于于优优先先因因子子P2、……，，并规规定定Pi>>Pi+1，i=1,2,,L-1.目标标规规划划模模型型的的基基本本概概念念（（续续））即在在计计算算过过程程中中,首首先先保保证证P1级目目标标的的实实现现，，这这时时可可不不考考虑虑次次级级目目标标；；而而P2级目目标标是是在在实实现现P1级目目标标的的基基础础上上考考虑虑的的，，以以此此类类推推。。当当需需要要区区别别具具有有相相同同优优先先因因子子的的若若干干个个目目标标的的差差别别时时，，可可分分别别赋赋于于它它们们不不同同的的权权系系数数wj。优先先因因子子及及权权系系数数的的值值，，均均由由决决策策者者按按具具体体情情况况来来确确定定．（4））、、目目标标规规划划的的目目标标函函效效．．目标标规规划划的的目目标标函函数数是是通通过过各各目目标标约约束束的的正正、、负负偏偏差差变变量量和和赋赋于于相相应应的的优优先先等等级级来来构构造造的的．．§2.1目标标规规划划模模型型目标标规规划划模模型型的的基基本本概概念念（（续续））决策策者者的的要要求求是是尽尽可可能能从从某某个个方方向向缩缩小小偏偏离离目目标标的的数数值值。。于于是是，，目目标标规规划划的的目目标标函函数数应应该该是是求求极极小小：：minf＝f（d+，d-)．．其基基本本形形式式有有三三种种：①要要求求恰恰好好达达到到目目标标值值，，即即使使相相应应目目标标约约束束的的正正、、负负偏偏差差变变量量都都要要尽尽可可能能地地小小。。这这时时取取min（（d++d-)；；②要要求求不不超超过过目目标标值值，，即即使使相相应应目目标标约约束束的的正正偏偏差差变变量量要要尽尽可可能能地地小小。。这这时时取取min（（d+)；；目标标规规划划模模型型的的基基本本概概念念（（续续））③要要求求不不低低于于目目标标值值，，即即使使相相应应目目标标约约束束的的负负偏偏差差变变量量要要尽尽可可能能地地小小。。这这时时取取min（（d-)；；对于于例例2.1.1,我们们根根据据决决策策者者的的考考虑虑知知第一一优优先先级级要要求求min（（d1++d2+)；；第二二优优先先级级要要求求min（（d3+)；；第三三优优先先级级要要求求min（（d4-)；；第四四优优先先级级要要求求min（（d1-+2d2-)，，这里里,当当不不能能满满足足市市场场需需求求时时,市市场场认认为为B产品品的的重重要要性性是是A产品品的的2倍倍．．即即减减少少B产品品的的影影响响是是A产品品的的2倍倍，，因因此此我我们们引引入入了了2:1的的权权系系数数。。§2.1目标标规规划划模模型型目标标规规划划模模型型的的基基本本概概念念（（续续））综合合上上述述分分析析，，我我们们可可得得到到下下列列目目标标规规划划模模型型Minf=P1（d1++d2+)+P2d3++P3d4-+P4（d1-+2d2-)s.t.x1+d1--d1+=9x2+d2--d2+=84x1+6x2+d3--d3+=60(2.1.5)12x1+18x2+d4--d4+=252x1,x2,di-,di+0,i=1,2,3,4.§2.1目标标规规划划模模型型目标标规规划划模模型型的的一一般般形形式式根据据上上面面讨讨论论,我我们们可可以以得得到到目目标标规规划划的的一一般般形形式式如如下下§2.1目标标规规划划模模型型目标标规规划划模模型型的的一一般般形形式式(续续)（LGP））中的的第第二二行行是是K个目目标标约约束束，，第第三三行行是是m个绝绝对对约约束束，，ckj和gk是目目标标参参数数。。§2.2目标标规规划划的的几几何何意意义义及及图图解解法法对只只具具有有两两个个决决策策变变量量的的目目标标规规划划的的数数学学模模型型，，我我们们可可以以用用图图解解法法来来分分析析求求解解．．通通过过图图解解示示例例，，可可以以看看到到目目标标规规划划中中优优先先因因子子，，正正、、负负偏偏差差变变量量及及权权系系数数等等的的几几何何意意义义。。§2.2目标规划的几几何意义及图图解法§2.2目标规划的几几何意义及图图解法（续续）下面用图解法法来求解例我们先在平面面直角坐标系系的第一象限限内，作出与与各约束条件件对应的直线线，然后在这这些直线旁分分别标上G-i，i=1，2，，3，4。图中x，y分别表示问题题（）的x1和x2；各直线移动使使之函数值变变大、变小的的方向用+、-表示示di+,di-（如图所示）．§2.2目标规划的几几何意义及图图解法05101520y

x2015105+-G-1+-G-2+-G-4+-G-3图2-1§2.2目标规划的几几何意义及图图解法下面我们根据据目标函数的的优先因子来来分析求解．．首先考虑第第一级具有P1优先因子的目目标的实现，，在目标函数数中要求实现现min（d1++d2+),取d1+=d2+=0.图2–2中阴影部分即即表示出该最最优解集合的的所有点。我们在第一级级目标的最优优解集合中找找满足第二优优先级要求min（d3+)的最优解.取取d3+=0,可得到图2–3中阴影部分即即是满足第一一、第二优先先级要求的最最优解集合。。§2.2目标规划的几几何意义及图图解法图2-205101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目标规划的几几何意义及图图解法图2–305101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目标规划的几几何意义及图图解法第三优先级要要求min（d4-)，根据图示可知知，d4-不可能取0值值，我们取使使d4-最小的值72得到图2–4中两阴影部分分的交线(红红色粗线)，，其表示满足足第一、第二二及第三优先先级要求的最最优解集合。。最后，考虑第第四优先级要要求min（d1-+2d2-)，即要在黑色粗粗线段中找出出最优解。由由于d1-的权因子小于于d2-，因此在这里可可以考虑取d2-=0。于是解得d1-=5，最优解为A点x=3，y=8。§2.2目标规划的几几何意义及图图解法图2–405101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.3求解目标规划划的单纯形方方法目标规划的数数学模型,特特别是约束的的结构与线性性规划模型没没有本质的区区别，只是它它的目标不止止是一个,虽虽然其利用优优先因子和权权系数把目标标写成一个函函数的形式,但在计算算中无法按单单目标处理,所以可用用单纯形法进进行适当改进进后求解。在在组织、构造造算法时，我我们要考虑目目标规划的数数学模型一些些特点，作以以下规定：(1)因为为目标规划问问题的目标函函数都是求最最小化，所以以检验数的最最优准则与线线性规划是相相同的；§2.3求解目标规划划的单纯形方方法(续)(2)因为为非基变量的的检验数中含含有不同等级级的优先因子子，Pi>>Pi+1，i=1,2,,L-1.于是从每个检检验数的整体体来看：Pi+1（i=1,2,,L-1）优先级第k个检验数的正正、负首先决决定于P1，P2，…，Pi优先级第k个检验数的正正、负。若P1级第k个检验数为0，则此检验验数的正、负负取决于P2级第k个检验数；若若P2级第k个检验数仍为为0，则此检检验数的正、、负取决于P3级第k个检验数，依依次类推。换换一句话说，，当某Pi级第k个检验数为负负数时，计算算中不必再考考察Pj（j>I）级第k个检验数的正正、负情况；；§2.3求解目标规划划的单纯形方方法(续)（3）根据（（LGP）模型特征，当当不含绝对约约束时，di-（i=1,2,…,K）构成了一组基基本可行解。。在寻找单纯纯形法初始可可行点时，这这个特点是很很有用的。解目标规划问问题的单纯形形法的计算步步骤(1)建立初初始单纯形表表．在表中将将检验数行按按优先因子个个数分别列成成K行。初始的检检验数需根据据初始可行解解计算出来，，方法同基本本单纯形法。。当不含绝对对约束时，di-（i=1,2,…,K）构成了一组基基本可行解，，这时只需利利用相应单位位向量把各级级目标行中对对应di-（i=1,2,…,K）的量消成0即即可得到初始始单纯形表。。置k＝1；§2.3求解目标规划划的单纯形方方法(续)(2)检查当当前第k行中是否存在在大于0，且且对应的前k-1行的同列检验验数为零的检检验数。若有有取其中最大大者对应的变变量为换入变变量，转(3)。若无这这样的检验数数，则转(5)；(3)按单纯纯形法中的最最小比值规则则确定换出变变量，当存在在两个和两个个以上相同的的最小比值时时，选取具有有较高优先级级别的变量为为换出变量，，转（4）；；§2.3求解目标规划划的单纯形方方法(续)(4)按单纯纯形法进行基基变换运算，，建立新的单单纯形表，（（注意：要对对所有的行进进行转轴运算算）返回(2)；(5)当k＝K时，计算结束束。表中的解解即为满意解解。否则置k=k+1，返回（2）。。§2.3求解目标规划划的单纯形方方法(续)例试用单纯形法法来求解例的目标规划模模型(2.1.5)Minf=P1（d1++d2+)+P2d3++P3d4-+P4（d1-+2d2-)s.t.x1+d1--d1+=9x2+d2--d2+=84x1+6x2+d3--d3+=6012x1+18x2+d4--d4+=252x1,x2,di-,di+0,i=1,2,3,4.§2.3求解目标规划划的单纯形方方法(续)解:首先处理初始始基本可行解解对应的各级级检验数。由于P1,P2优先级对应的的目标函数中中不含di-,所以其检验数数只需取系数数负值。分别别为(0，0，，0，-1，，0，-1，，0，0，0，0；0)和(0，0，，0，0，，0，0，0，-1，0，0；0)