教学材料《运筹学》-第5章

第5章目标规划学习目标通过本章的学习，认识目标规划的基本特征、基本概念和模型，熟悉目标规划的图解法、几何意义，掌握解目标规划的单纯形法。上一页下一页返回第5章目标规划关键词汇目标规划(GoalProgramming)偏差变量(DeviationalVariables)目标约束(GoalConstraints)绝对约束(AbsoluteConstraints)优先因子(PrioritySymbol)权系数(WeightNumber)上一页下一页返回第5章目标规划关键词汇某公司分厂用一条生产线生产两种产品A和B，每周生产线运行时间为60小时，生产一台A产品需要4小时，生产一台B产品需要6小时。根据市场预测，A,B产品平均销售量分别为每周9台、8台，它们销售利润分别为12万元、18万元。在制仃生产计划时，经理要考虑下述4项目标:首先，产量不能超过市场预测的销售量;其次，工人加班时间最少;最后，希望总利润最大;最后，要尽可能满足市场需求，当不能满足时，市场认为B产品的重要性是A产品的2倍。试建立这个问题的数学模型。上一页返回下一页5.1目标规划模型5.1.1目标规划问题的提出在科学研究、经济建设和生产实践中，人们经常遇到一类含有多个目标的数学规划问题，我们称之为多目标规划。多目标规划的主要特征表现在各目标在优化中常常是相互矛盾的。许多决策人在面临存在资源约束和目标矛盾的复杂决策问题时，往往运用他的判断力分析各目标的重要性，优先考虑某个他认为是最重要的目标，在该目标达到一定数值之前其他目标可以暂缓甚至放弃。本章介绍一种特殊的多目标规划，称为目标规划(GoalProgramming)，这是美国学者Charne*等在1952年提出来的。目标规划法就是用“优先等级”的思想来解决互相矛盾的多目标决策问题的技术。在较高级目标得到满足之后，才考虑较低级目标，这符合人们处理问题要分清轻重缓急保证重点的思考下一页返回上一页5.1目标规划模型

方式，在实践中的应用十分广泛。目标规划能够帮助决策人解决实际的、复杂的多目标决策问题，它可以用来解决带有多重子目标的单目标决策问题，也能处理带多重目标和多重子目标的决策问题。当人们在实践中遇到一些矛盾的目标，由于资源有限和其他各种原因这些目标可能无法达到时，可以把任何起作用的约束都称之为“目标”，不论它们能否达到。总的目的是要给出一个最优的结果，使之尽可能地接近指定的目标。人们把目标按重要性分成不同的优先等级(Priority，并对同一个优先等级中的不同目标加权(Weight，这使目标规划方法在理论上取得了长足的进展，并在许多领域获得了广泛应用。上一页下一页返回5.1目标规划模型为了便于理解目标规划数学模型的特征及建模思路，我们首先用开篇案例来说明，试建立这个问题的数学模型。讨论:

若把总利润最大看做目标，而把产量不能超过市场预测的销售量、工人加班时间最少和要尽可能满足市场需求的目标看做约束，则可建立一个单目标线性规划模型。设决策变量x1，x2分别为产品A,B的产量，上一页下一页返回5.1目标规划模型容易求得上述线性规划的最优解为(9，4)T到(3，8)T所在线段上的点，最优目标值为z*=180，即可选方案有多种。在实际上，这个结果并非完全符合决策者的要求，它只实现了经理的第一、第二、第三条目标，而没有达到最后一个目标。进一步分析可知，要实现全体目标是不可能的。下面结合案例介绍目标规划模型。上一页下一页返回5.1目标规划模型5.1.2目标规划模型的基本概念我们把案例的4个目标表示为不等式。仍设决策变量x1，x2分别为产品A,B的产量。那么，将第一个目标，即产量不能超过市场预测的销售量表示为: 。将第二个目标，即工人加班时间最少表示为: 。第三个目标为希望总利润最大。要将其表示成不等式，需要找到一个目标上界，这里可以估计为力争达到252(12×9+18×8)，于是表示为: 。将第四个目标，即要尽可能满足市场需求表示为: 。另外要考虑，当不能满足时，市场认为B产品的重要性是A产品的2倍。下面引入与建立目标规划数学模型有关的概念。上一页下一页返回5.1目标规划模型1)正、负偏差变量d+,d-设第了个目标函数为fj(x)劝，其右端的目标为 。我们对每个目标j(j=1，2，…，K)引入正偏差变量dj+和负偏差变量dj-，其中显然，当 时， ；当 时， ；两者不可能同时为正，因此有dj+·dj-=0，而且上一页下一页返回5.1目标规划模型2)绝对约束和目标约束我们把所有等式、不等式约束分为两部分:绝对约束和目标约束。绝对约束是指必须严格满足的等式约束和不等式约束，如在线性规划问题中考虑的约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。如果开篇案例中生产A,B产品所需原材料数量有限制，并且无法从其他渠道予以补充，则构成绝对约束。目标约束是目标规划特有的，我们可以把约束右端项看作要努力追求的目标值，但允许发生正、负偏差，在约束中加入正、负偏差变量来表示，于是称它们是目标约束，又称软约束。对于开篇案例，有如下4个目标约束。上一页下一页返回5.1目标规划模型3)优先因子与权系数对于多目标问题，设有K个目标函数f1，f2，…，fk，决策者在要求达到这些目标时，一般有主次之分。为此，我们引入优先因子Pi(i=-1，2，…，L-1)。我们把要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2…并规定 (i=-1，2，…，L-1)。即在计算过程中，首先保证P1级目标的实现，这时可不考虑次级目标;而P2级目标是在实现P1级目标的基础上考虑的，以此类推。当需要区别具有相同优先因子的若干个目标的差别时，可分别赋予它们不同的权系数wj。优先因子及权系数的值，均由决策者按具体情况来确定。上一页下一页返回5.1目标规划模型

虽然优先级和权都是用来衡量目标之间的相对重要性的，但是在概念上和算法上有着明显的区别。权是用区间标度来衡量目标之间的相对重要性的，在一定条件下，利用权可以把多目标问题转换成“单目标”问题求解，但是这种单目标问题实际上同时综合考虑了多个目标。而优先级把目标粼fj(j=1，2，…，k)，分成若干个等级，比如说L个 ，若某个目标处于第i个等级，记作Pi，则它的优先级低于P1，P2，…，Pi-1，但高于Pi+1，…，PL。对优先级Pi不设固定数值，若是硬要把优先级看做一种权重，则有Pi远远大于Pi+1，即Pi>>Pi+1。在用优先级概念求解问题时需依次考虑不同优先级的目标，在优先级高的目的值达到之前不考虑优先级较低的目标。上一页下一页返回5.1目标规划模型4)目标规划的目标函效目标规划的目标函数是通过各目标约束的正、负偏差变量和赋予相应的优先等级来构造的。决策者的要求是尽可能从某个方向缩小偏离目标的数值，于是，目标规划的目标函数应该是求极小:minf=f(d+,d-)。其基本形式有三种。①要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可能地小。这时取min(d+,d-)。②要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。这时取min(d+)。③要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取min(d-)。上一页下一页返回5.1目标规划模型

对于开篇案例，根据决策者的考虑知第一优先级要求:min(d1++d2+);

第二优先级要求:min(d3+);

第三优先级要求:min(d4-);

第四优先级要求:min(d1--2d2-);，这里，当不能满足市场需求时，市场认为B产品的重要性是A产品的2倍，即减少B产品的影响是A产品的2倍，因此我们引入了1:2的权系数。上一页下一页返回5.1目标规划模型综合上述分析，我们可得到下列目标规划模型。上一页下一页返回5.1目标规划模型5.1.3目标规划模型的一般形式目标规划问题要求决策人对每个目标fj设定一个目标值，给定各目标的优先级及权重，在备选方案集中选择方案x，使其目标函数f(x)与目标值 的组合偏差最小，即对于线性目标规划，一般取p=1。根据上面讨论，我们可以得到目标规划的一般形式。上一页下一页返回5.1目标规划模型(LGP)中的第二部分是K个目标约束，第三部分是m,个绝对约束，ckj和gk是目标约束的参数。思考题(1)如何理解绝对约束和目标约束?(2)如何正确理解目标规划的目标函数?上一页返回下一页5.2目标规划的几何意义及图解法5.2.1目标规划图解法过程对于只有两个变量的线性目标规划问题(LGP)，可以在二维直角坐标平面上作图表示线性目标规划问题的有关概念，并求解。图解法求解线性目标规划问题的步骤如下。(1)分别取决策变量x1，x2为坐标向量建立直角坐标系。(2)对每个绝对约束(包括非负约束)条件，做法同线性规划的约束处理:先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面，得到各绝对约束半平面交出来的区域。对每个目标约束条件，先取其不考虑正负偏差变量的等式在坐标系中作出直线，判断其变大、变小的方向，标出正负偏差变量的变化方向。综合绝对约束得到的区域，产生所有约束(绝对约束和目标约束)交出来的区域，进行(3)。(3)依据优先的顺序及权重的比例关系，对目标函数中各偏差变量取值进行优化。最终得到最优解(或最优解集合)。下一页返回上一页5.2目标规划的几何意义及图解法5.2.2算例及几何意义考虑开篇案例的目标规划模型:我们通过算例来说明计算过程。对只具有两个决策变量的目标规划的数学模型，可以用图解法来分析求解。通过图解示例，可以看到目标规划中优先因子，正、负偏差变量及权系数等的几何意义。上一页下一页返回5.2目标规划的几何意义及图解法下面用图解法来求解开篇案例。

(1)先在平面直角坐标系的第一象限内作出与各约束条件对应的直线，然后在这些直线旁分别标上其所代表的约束G-i(i=1,2,3,4)。图中x，y分别表示开篇案例中的x1，和x2;各直线移动使函数值变大、变小的方向用+、-表示，记为di+,di-，如图5-1所示。

(2)根据目标函数的优先因子来分析求解。首先考虑第一级具有P1优先因子的目标的实现，在目标函数中要求实现min(d1++d2+)，取d1+=d2+=0。图5-2中阴影部分即表示出该最优解集合的所有点。上一页下一页返回5.2目标规划的几何意义及图解法(3)进一步在第一级目标的最优解集合中找满足第二优先级要求min(d3+)的最优解。取d3+=0，可得到图5-3中阴影部分即是满足第一、第二优先级要求的最优解集合。(4)第三优先级要求min(d4-)，根据图示可知，d4-不可能取0值，我们取使心最小的值72得到图5-4所示的黑色粗线段，其表示满足第一、第二及第三优先级要求的最优解集合。(5)考虑第四优先级要求min(d1-+d2-)，即要在黑色粗线段中找出最优解。由于d1-的权因子小于d2-

，因此在这里可以考虑取d2-=0。于是解得d1-=s，最优解为点x=3，y=8。虽然这组解没有满足决策者的所有目标，但是已经是符合决策者各优先级思路的最好结果了。思考题(1)总结目标规划图解法与一般线性规划图解法的区别。(2)在第④步中，使心最小的值72是如何求出的?上一页返回下一页5.3求解目标规划的单纯形方法5.3.1线性目标规划的单纯形法过程目标规划的数学模型，特别是约束的结构与线性规划模型没有本质的区别，只是它的目标不止一个，虽然其利用优先因子和权系数把目标写成一个函数的形式，但在计算中无法按单目标处理，所以可用单纯形法进行适当改进后求解。根据线性目标规划与线性规划的不同点，在组织、构造算法时，我们要考虑线性目标规划数学模型的一些特点，作以下规定。

(1)因为目标规划问题的目标函数都是求最小化，这里检验数与线性规划检验数相差一个符号，所以检验数的最优准则与线性规划是相同的。下一页返回上一页5.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个检验数的正、负情况。

(3)根据(LGP)模型特征，当不含绝对约束时，di-(i=1，2，…，K)构成了一组基本可行解。在寻找单纯形法初始可行点时，这个特点是很有用的。下面给出求解目标规划问题的单纯形法的计算步骤。

(1)建立初始单纯形表。上一页下一页返回5.3求解目标规划的单纯形方法

在表中将检验数行按优先因子个数分别列成K行。初始的检验数需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约束时，di-(i=1，2，…，K)构成了一组基本可行解，这时只需利用相应单位向量把各级目标行中对应di-(i=1，2，…，K)的量消成0即可得到初始单纯形表。置k=0。

(2)检查确定进基变量。看当前第k行中是否存在大于0，且对应的前k一1行的同列检验数为零的检验数，若有，则取其中最大者对应的变量为换入变量，转(3)。否则，若无这样的检验数，则转(5)。

(3)确定出基变量。按单纯形法中的最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，转(4)。上一页下一页返回5.3求解目标规划的单纯形方法(4)换基运算。按单纯形法的相关步骤进行基变换运算，建立新的单纯形表(注意:要对所有的目标行进行转轴运算)，返回(2)。

(5)终止或迭代。当k=K时，计算结束，表中的解即为满意解。否则置k=k+1，返回(2)。上一页下一页返回5.3求解目标规划的单纯形方法5.3.2线性目标规划的单纯形法算例例5.1试用单纯形法来求解开篇案例的目标规划模型(5-5)解①对目标规划问题建立如下的目标规划初始表格，见表5-1。上一页下一页返回5.3求解目标规划的单纯形方法②首先处理初始基本可行解对应的各级检验数，均需处理成典式表示的形式。由于P1，P2优先级对应的目标函数中不含di-，所以其检验数只需取系数负值。分别为 和

P3优先级对应的目标函数中含d4-

，所以该行不是典式表示。我们将第4个约束行加到这一行上，使得基变量对应的检验数为0。得到 如表5-2所示。上一页下一页返回5.3求解目标规划的单纯形方法P4优先级对应的目标函数中含(d4-+2d2-)，所以该行也不是典式表示，应将第1个约束行与第2个约束行的2倍加到这一行上，使得基变量对应的检验数为0，得到 。至此，已经把所有目标行处理成为典式表示，于是得到此目标规划的初始单纯形表，如表5-3所示。下面进行计算。(1)k=1，在初始单纯形表中基变量为

(2)因为P1与，P2优先级的检验数均已经为非正，所以这个单纯形表对P1与，P2优先级已经是最优单纯形表。上一页下一页返回5.3求解目标规划的单纯形方法(3)下面考虑P3优先级。第二列的检验数为18，此为进基变量，计算相应的比值bi/aij写在