最优化方法第五章(1)

1、 第第2第第4章讨论的都是具有单一目标函数的最优化问章讨论的都是具有单一目标函数的最优化问题。实际中，还会遇到同时追求多个目标的最优化问题。题。实际中，还会遇到同时追求多个目标的最优化问题。例如，对于一个生产过程，总是期望高产出，同时还要求例如，对于一个生产过程，总是期望高产出，同时还要求少用料、省工时等等。像这样有多个目标的最优化问题称少用料、省工时等等。像这样有多个目标的最优化问题称为为多目标规划多目标规划。自二十世纪。自二十世纪70年代以来，对多目标规划的年代以来，对多目标规划的研究开始广泛起来，所获成果已对现代经济、政治、科技研究开始广泛起来，所获成果已对现代经济、政治、科技和军事等方

2、面产生重要影响。这里将介绍多目标规划的数和军事等方面产生重要影响。这里将介绍多目标规划的数学模型、有关概念，以及基本的求解方法。学模型、有关概念，以及基本的求解方法。第五章第五章 多目标规划多目标规划5.1 数学模型数学模型例例5.1 P298例例5.2 P298多目标最优化问题的数学模型多目标最优化问题的数学模型的一般形式为的一般形式为11212112121212min( ,) min( ,)max( ,) max( ,). . ( ,)0, 1,2, ( ,)0, 1,2,()npnnqninjnf x xxfx xxg x xxgx xxsts x xximh x xxjl ln （5.

3、1） 如设如设1212 , ,( )( ),1,2, ( )( ),( ),( ) , ( )0,1,2,( )0,1,2, (),Tnp kkTrijxx xxfxgxkqf xf xfxfxrpqDx s xim h xjl ln 则（则（5.1）将可简单地表示成）将可简单地表示成vmin( )x Df x（5.3） D( )f x12( ),( ),( )rf xfxfx（5.3）是多目标问题的）是多目标问题的向量极小化模型向量极小化模型，其中，其中v是是vector为容许集。为容许集。称为称为向量目标函数向量目标函数；称为称为分量目标函数分量目标函数。（向量）的字头，（向量）的字头，

4、如果（如果（5.1）中的所有函数都是线性的，那么通过变换，）中的所有函数都是线性的，那么通过变换，（5.1）可写成如下形式）可写成如下形式vmin . . 0.x DCxstAxbx（5.4） Crn这是多目标线性规划的标准形式，其中这是多目标线性规划的标准形式，其中是矩阵。矩阵。5.2 解的概念与性质解的概念与性质 与单目标最优化问题相比，由于目标函数不再是单一与单目标最优化问题相比，由于目标函数不再是单一的，因此多目标最优化问题的最优解概念变得复杂起来，的，因此多目标最优化问题的最优解概念变得复杂起来，并产生了各种意义下的并产生了各种意义下的“最优最优”概念。概念。*xDxD 定义定义5.

5、1 考虑问题（考虑问题（5.3）。若存在）。若存在，使得对于，使得对于，都有，都有*()( )f xf x（5.5） *x*( ,)Xf D*X则称为（称为（5.3）的）的绝对最优解绝对最优解。所有绝对最优解的集合。所有绝对最优解的集合或。称为称为绝对最优解集绝对最优解集，记作，记作注意，（注意，（5.5）等价于）等价于*()( ),1,2, .iif xf xir例例5.3 P300 在实际中，多目标最优化问题存在绝对最优解的情况在实际中，多目标最优化问题存在绝对最优解的情况不多见。因此，必需扩充最优解的概念。为此需要建立向不多见。因此，必需扩充最优解的概念。为此需要建立向量间的自然序关系。

6、除在定义量间的自然序关系。除在定义1.1中定义的序关系外，还中定义的序关系外，还要用到下面的序关系。要用到下面的序关系。12,Tmaa aa12 ,Tmbb bbm(1,2,)iiab im定义定义5.2 设设和和都是都是维向量。若维向量。若 ababbaba,并且至少有一个等号并且至少有一个等号小于向量小于向量，记作，记作或称或称向量向量大于向量大于向量，记作，记作。是严格小于号，则称是严格小于号，则称向量向量，1,1 ,3,1TTab2,2Tc abacbc例如，向量例如，向量和和之间有之间有，（参看定义（参看定义1.1），而），而和和之间不存在自然序关系。之间不存在自然序关系。如下的序关

7、系：如下的序关系：ababaaaaaa需要注意的是，由关系式需要注意的是，由关系式可以导出可以导出但反过来不成立。例如但反过来不成立。例如和的序关系可以写成的序关系可以写成但不能写成但不能写成。*xDxD*( )()f xf x*x定义定义5.3 考虑问题（考虑问题（5.3），设），设。若不存在。若不存在，使得，使得，则称，则称 是（是（5.3）的）的有效解有效解， 又称又称Pareto解解（这个概念是经济学家（这个概念是经济学家V.Pareto于于1896年引年引入的）。所有有效解的集合称为入的）。所有有效解的集合称为有效解集有效解集，记作，记作 ( ,)P f DP或或。 ， 绝对最优解是

8、从正面定义的，而有效解是从反面定绝对最优解是从正面定义的，而有效解是从反面定义的。义的。 为有效解的含义是，在容许集内找不到比为有效解的含义是，在容许集内找不到比 在在“ ”意义下更好的解。意义下更好的解。 *x*x一般说来，有效解不是一般说来，有效解不是“最优的最优的”，但可以说它是，但可以说它是“不坏不坏的的”，因此有效解又称为，因此有效解又称为非劣解非劣解。在多目标最优化理论中，。在多目标最优化理论中，这是一个最基本的概念。比有效解还差的这是一个最基本的概念。比有效解还差的“非劣非劣”解是弱解是弱有效解。有效解。*xDxD*( )()f xf x*x( ,)wPf DwP定义定义5.4

9、考虑问题（考虑问题（5.3），设），设。若不存在。若不存在，使得，使得，则称，则称是（是（5.3）的）的弱有弱有或或。效解效解。所有弱有效解的集合称为。所有弱有效解的集合称为弱有效解集弱有效解集，记作，记作 弱有效解也是从反面定义的。弱有效解也是从反面定义的。 为弱有效解的含义是，为弱有效解的含义是，在容许集内找不到比在容许集内找不到比 在在“ ”意义下更好的解，也就意义下更好的解，也就是在是在 中找不到中找不到 ，使得，使得 *x*xDx*( )(),1,2,iif xf xir。下面的几个定理描述了各种解之间的关系。下面的几个定理描述了各种解之间的关系。定理定理5.1 设设 *(1,2,

10、)iXir表示（表示（5.3）中第）中第 i分量目标分量目标函数函数( )if x在在 D上的最优解集，则（上的最优解集，则（5.3）的绝对最优解集）的绝对最优解集*1.riiXX定理定理5.2 绝对最优解必是有效解。绝对最优解必是有效解。*xXxD *( )()f xf xxD *( )()f xf xxD*( )()f xf x*xP证证 设设，则对，则对，都有，都有这表明对于这表明对于，即不存在，即不存在使得使得，故，故。，定理定理5.2表明表明。*XP定理定理5.3 有效解必是弱有效解。有效解必是弱有效解。*xPxD*( )()f xf xxD *( )()f xf x证证 设设，则不

11、存在，则不存在，使得，使得换句话说，对于换句话说，对于，都有，都有 xD *( )()f xf xxD*( )()f xf x。这。这，更有，更有，即不存在，即不存在使得使得，故，故。表明对表明对，*wxP定理定理5.3表明表明。wPP。 定理定理5.4 各分量目标函数在各分量目标函数在D上的最优解必是弱有效解。上的最优解必是弱有效解。1,2,ir*iixXxD *( )()iiif xf xxD*( )()f xf x*iwxP证证 对于对于，设，设，则对，则对，都，都。从而不存在。从而不存在，使得，使得故故。有有，定理定理5.4表明表明*(1,2, )iwXP ir。推论推论5.5 *1(

12、).riwiPXP综上所述，各种解集之间有如下关系：综上所述，各种解集之间有如下关系：*1.riwiXXPPD*X *PX定理定理5.6 若（若（5.3）的绝对最优解集）的绝对最优解集，则它的，则它的。有效解集有效解集D( )if xD定理定理5.7 若（若（5.3）的容许集）的容许集是凸集，且每个分量是凸集，且每个分量在在上均是严格凸函数，则它的有效解集上均是严格凸函数，则它的有效解集目标函数目标函数与弱有效解集相等。与弱有效解集相等。例例5.3 考虑多目标最优化问题考虑多目标最优化问题1222min( )21(3) , 31min( )1, 31. . 1.f xxxxxfxxstx当当试

13、验证：试验证：*,1.5,2,1.5,4wXPP 。1f2f*11.5X *22,4X *12XX *X 解解 容易验证，容易验证， 和和都是容许集上的凸函数，它们的都是容许集上的凸函数，它们的和和。因为。因为根据定理根据定理5.1，绝对最优解集，绝对最优解集。最优解集分别为最优解集分别为， 由于由于 和和 在各自最优解集的左侧和右侧分别都是在各自最优解集的左侧和右侧分别都是严格递减函数和严格递增函数（见图），严格递减函数和严格递增函数（见图），1f2f5.4，不存在弱有效解。，不存在弱有效解。所以在所以在 和和 中，根据定义中，根据定义1,1.5)(4,) 在在 中，中， 是严格是严格递增的

14、，而递增的，而 是严格递减是严格递减的，因此，根据定义的，因此，根据定义5.3 可可以判断以判断 中的点都是有效中的点都是有效解。又在解。又在 中，中， 是严格是严格递增的，而递增的，而 是常数，根据是常数，根据定义定义5.3可以判断可以判断 中不中不存在有效解。因此，有效解存在有效解。因此，有效解集集 。1f1.5,22f1.5,22f(2,41f(2,41.5,2P 综上所述，并依据推论综上所述，并依据推论5.5可知，弱有效解集可知，弱有效解集*121.5,4wPXXP。5.3 5.3 评价函数法评价函数法 求解多目标最优化问题，最好求出绝对最优解。如果求解多目标最优化问题，最好求出绝对最

15、优解。如果绝对最优解不存在，则应该求出有效解，最差也要求出弱绝对最优解不存在，则应该求出有效解，最差也要求出弱有效解（如果存在的话）。有效解（如果存在的话）。 有效解和弱有效解通常可以构成解集，但要想求出这有效解和弱有效解通常可以构成解集，但要想求出这个解集是比较困难的。对于实际问题，能求出满足要求的个解集是比较困难的。对于实际问题，能求出满足要求的有效解或弱有效解就可以了。求解多目标最优化问题有多有效解或弱有效解就可以了。求解多目标最优化问题有多种方法，包括主要目标法、分层排序法、重点目标法、评种方法，包括主要目标法、分层排序法、重点目标法、评价函数法以及分组排序法等。最基本有效的方法是下面

16、要价函数法以及分组排序法等。最基本有效的方法是下面要介绍的评价函数法。介绍的评价函数法。1. 1. 基本定理基本定理1:rRR,rz zR 定义定义5.55.5 设，。zz( )()zz( )zz）若当）若当时，总有时，总有，则称，则称是是的的严格单调增函数严格单调增函数。zz( )()zz( )zz）若当）若当时，总有时，总有，则称，则称是的的单调增函数单调增函数。1:rRR:nrfDRR*x定理定理5.8 设设，又设，又设是如下问题是如下问题min ( ( )x Df x（5.7） 的极小点，那么的极小点，那么( )zz*( ,)xP f D）若）若是的严格单调增函数，则的严格单调增函数，

17、则；( )zz*( ,)wxPf D）若）若是是的单调增函数，则的单调增函数，则。*( ,)xP f DxD证证 ）使用反证法。假设）使用反证法。假设。根据。根据 定义定义5.3，则必存在，则必存在*( )()f xf x *( ( )( ()f xf x*x，使得，使得。由。由的严格单调性，则必有的严格单调性，则必有。这与。这与是（是（5.7）的极小点相矛盾。）的极小点相矛盾。）证明与证明与）类似（习题类似（习题5.11）。）。2. 2. 几个常用的评价函数几个常用的评价函数（1）线性加权函数）线性加权函数12,Truu uu0(1,2, )iuir11riiu( )Tzu z设设满足满足和

18、和如取如取，称为，称为线性加权和函数线性加权和函数，则有如下结论：，则有如下结论：。0u ( )zz）当）当时，时，是是的严格单调增函数；的严格单调增函数；0u( )zz）当）当时，时，是是的单调增函数。的单调增函数。0u 0u根据定理根据定理5.8，只要取，只要取（或或），那么求解），那么求解多目标最优化问题（多目标最优化问题（5.3）就可以转化为求解单目标最优化）就可以转化为求解单目标最优化问题问题min( )Tx Du f x即即1min( ).riix Diu f x这个单目标最优化问题的极小点就是（这个单目标最优化问题的极小点就是（5.3）的有效解）的有效解（或弱有效解）。（或弱有效

19、解）。 ( )z12,ru uu12( ),( ),( )rf xfxfx12,Truu uu该方法因该方法因称为称为线性加权和法线性加权和法。这里的。这里的分别称为分量目标函数分别称为分量目标函数的的权系数权系数， 称为权系数向量。权系数的称为权系数向量。权系数的相对大小表征各分量目标的相对重要程度。重要的目标应相对大小表征各分量目标的相对重要程度。重要的目标应赋予较大的权系数，不重要的目标应赋予较小的权系数。赋予较大的权系数，不重要的目标应赋予较小的权系数。因此，特别是在对实际问题的求解中，权系数的选取就成因此，特别是在对实际问题的求解中，权系数的选取就成为求到合理的有效解的关键。的具体选

20、取方法将在为求到合理的有效解的关键。的具体选取方法将在3.3.中讨中讨论。论。例例5.5 用线性加权和法求解例用线性加权和法求解例5.1。解解 把例把例5.1中第二分量目标函数的求极大转化为求极中第二分量目标函数的求极大转化为求极小，问题变成小，问题变成12212221212min min. .1 , 0.x xx xstxxxx如果第一和第二分量目标函数的权系数分别取为如果第一和第二分量目标函数的权系数分别取为0.3和和0.7，那么上述问题就转化为如下单目标最优化问题那么上述问题就转化为如下单目标最优化问题21212221212min0.30.7. . 1 , 0.x xx xstxxxx用

21、第用第4章中的方法可以解出这个问题的极小点章中的方法可以解出这个问题的极小点 *0.5013,0.8653Tx 它是原问题（例它是原问题（例5.1）的有效解。其实际含义是，当宽为）的有效解。其实际含义是，当宽为0.5013而高为而高为0.8653时，可使木梁的重量最轻且强度最时，可使木梁的重量最轻且强度最大。需要指出的是，这是在重量和强度的权系数分别取大。需要指出的是，这是在重量和强度的权系数分别取0.3和和0.7时得出的有效解。时得出的有效解。，（2）理想点函数）理想点函数 假设（假设（5.3）的各分量目标函数在）的各分量目标函数在D上都存在极小点。上都存在极小点。因此可设因此可设*()mi

22、n( ),1,2, .iiiix Dzf xf xir*izi*12,Trzzzz极小值极小值称为第称为第分量目标函数的分量目标函数的理想值理想值，点，点 称为向量目标函数称为向量目标函数( )f x在其值域在其值域空间中的的空间中的的理想点理想点。 ( )f x( ),Zz zf xxD ZrrR的的值域值域是是而而值域空间值域空间是指是指所在的所在的维空间维空间。 ，*12rxxxxD *1()( )iif xf x(1,2, )ir当当时，因为对于时，因为对于，均有，均有 *1x*1xD，因此，因此是是(5.3)的绝对的绝对 最优解最优解。又因为。又因为*1122(),(),()Trrz

23、f xfxfxZ*12,rxxx( )f x，此时，此时因此，当因此，当彼此相等时，彼此相等时， 的理想点在其的理想点在其*12,rxxx不完全相等时，不完全相等时， 值域中。但是，当值域中。但是，当( )f x*1122(),(),()Trrzf xfxfxZ xD的理想点的理想点就很可能就很可能 不在其值域中了。对此，有一个很自然的想法：找一点不在其值域中了。对此，有一个很自然的想法：找一点( )()f xZ*z x，使得，使得与理想点与理想点的的“距离距离”在某种在某种应该是（应该是（5.3）的一个最优解。这个）的一个最优解。这个意义下最小，那么意义下最小，那么想法导致产生如下的评价函数

24、想法导致产生如下的评价函数*( ),zzzzZrR称为称为理想点函数理想点函数，其中，其中是是中的某种模。中的某种模。例如，采用例如，采用p 模的评价函数为模的评价函数为1*1( )() ,rppiipizzzzz1p 。而其中最常用的是。而其中最常用的是2模评价函数模评价函数1* 2221( )() riiizzzzz（5.9） （5.8） ,z zZ zz *zzzz容易验证，（容易验证，（5.8）是严格单调增函数。事实上，设）是严格单调增函数。事实上，设，则，则。于是，。于是，11*11( ) ) ().rrppppiiiiiizzzzzz这样，求解（这样，求解（5.3）就转化为求解）就

25、转化为求解*min( )px Df xz即即1*1min( ).rppiix Dif xz这个问题的极小点就是（这个问题的极小点就是（5.3）的有效解（定理）的有效解（定理5.8）。该）。该方法称为方法称为理想点法理想点法。（3）平方加权函数）平方加权函数 对形如（对形如（5.9）的评价函数从两个方面加以改造：第）的评价函数从两个方面加以改造：第一，把一，把 换换 为为在在 上极小值的一个尽可能好的估上极小值的一个尽可能好的估计计 。这样可以避免对每个分量目标函数求极小值。这样可以避免对每个分量目标函数求极小值的计算；第二，对平方和的各项赋予权系数。此外，去除的计算；第二，对平方和的各项赋予权

26、系数。此外，去除（5.9）中的开平方运算。这样既考虑了各分量目标函数）中的开平方运算。这样既考虑了各分量目标函数的不同重要程度，又避免了不利于数值计算的开平方计算。的不同重要程度，又避免了不利于数值计算的开平方计算。因此，获得评价函数因此，获得评价函数*iz( )if xD0*()iizz021( )() .riiiizu zz（5.10） 12,0Truu uu( )zz容易验证，当容易验证，当时，时，是是的严格单的严格单调增函数（习题调增函数（习题5.13）。于是，求解（）。于是，求解（5.3）就转化为求解）就转化为求解021min( )riiix Diuf xz这个单目标最优化问题的极小

27、点即是（这个单目标最优化问题的极小点即是（5.3）的有效解。）的有效解。该方法称为该方法称为平方和加权法平方和加权法。（4 4）极大函数）极大函数取极大函数取极大函数1( )max ii rzz （5.11） 作为评价函数。作为评价函数。12,rzzz12,ru uu更一般地，也可以对更一般地，也可以对依次赋予权系数依次赋予权系数，取，取1( )maxiii rzu z （5.12） 12,0ru uu ( )zzzz(1,2, )iiiiu zu zir作为评价函数。容易验证，当作为评价函数。容易验证，当时，时，是是的单调增函数。这是因为：若的单调增函数。这是因为：若，则有，则有 。因此，。

28、因此，11( )maxmax().iiiii ri rzu zu zz 在选取（在选取（5.12）作为评价函数时，求解（）作为评价函数时，求解（5.3）就转化）就转化为求解单目标最优化问题为求解单目标最优化问题1minmax( ).iix Di ru f x （5.13） 根据定理根据定理5.85.8，这个问题的最优解是（，这个问题的最优解是（5.3）的弱有效解。）的弱有效解。该方法称为该方法称为极大极小法极大极小法。（5.13）可以解释为在最不利的情况下求最好的结果。）可以解释为在最不利的情况下求最好的结果。1 122( ),( ),( )rru f x u fxu fxDv在实际计算中，直

29、接求解在实际计算中，直接求解( (5.13) )是不简便的。考虑对是不简便的。考虑对在在上的共同上界上的共同上界求极小，即求极小，即min. . ( ),1,2, .iivst u f xv irxD（5.14） 定理定理5.9将说明（将说明（5.14）和（）和（5.13）是等价问题。）是等价问题。12,0ru uu *x*v*,TTxv定理定理5.9 设设，则，则为（为（5.13）最优）最优使得使得是（是（5.14）的）的解的充要条件是，存在数解的充要条件是，存在数最优解。最优解。证证 必要性必要性 设设*x是（是（5.13）的最优解，并取）的最优解，并取*1max().iii rvu f

30、x *,TTxv, TTxv显然显然是（是（5.14）的容许解。又设）的容许解。又设是（是（5.14）的任意一个容许解，则的任意一个容许解，则*11max()max( )iiiii ri rvu f xu f xv 这表明这表明*,TTxv是（是（5.14）的最优解。）的最优解。充分性充分性 设设*,TTxv是（是（5.14）的最优解。显然）的最优解。显然*1max().iii rvu f x xD 1max( )iii rvu f x , TTxv对于对于，取，取，易见，易见是（是（5.14）的容许解。的容许解。 于是于是*11max()max( ).iiiii ri ru f xvvu f

31、 x 上式表明，上式表明，*x是（是（5.13）的最优解。）的最优解。 如果选取（如果选取（5.11）作为评价函数，那么求解（）作为评价函数，那么求解（5.3）就）就转化为求解单目标最优化问题转化为求解单目标最优化问题 1minmaxix Di rfx 即即min. . ( ),1,2, .ivst f xv irxD其最优解即是（其最优解即是（5.3）的弱有效解。）的弱有效解。3. 权系数的确定方法权系数的确定方法 在上述几个评价函数中，一般都可以赋予权函数。不在上述几个评价函数中，一般都可以赋予权函数。不同的权系数通常对应不同的有效解或弱有效解。对于实际同的权系数通常对应不同的有效解或弱有

32、效解。对于实际中的多目标最优化问题，并不是所有的有效解或弱有效解中的多目标最优化问题，并不是所有的有效解或弱有效解都有实用意义。例如，例都有实用意义。例如，例5.1中有效解中有效解 和和 无实际意无实际意义。因此，选取合适的权系数有时就显得至关重要。义。因此，选取合适的权系数有时就显得至关重要。 0,1T1,0T 在确定权系数之前，一般要对各分量目标函数值做统在确定权系数之前，一般要对各分量目标函数值做统一量纲的处理。不然的话，可能会由于各分量目标函数值一量纲的处理。不然的话，可能会由于各分量目标函数值存在数量级上的较大差别，而导致权系数作用的失效。例存在数量级上的较大差别，而导致权系数作用的

33、失效。例如，数量级较小的目标函数即使赋予较大的权系数。在变如，数量级较小的目标函数即使赋予较大的权系数。在变换后的单目标最优化问题中它也不起太大的作用。换后的单目标最优化问题中它也不起太大的作用。 统一量纲的处理一般分为两步：第一，各分量目标函统一量纲的处理一般分为两步：第一，各分量目标函数都加上同一个正数，使得新的各分量目标函数数都加上同一个正数，使得新的各分量目标函数 12( ),( ),( )rf xfxfx在在D上的取值都大于零；上的取值都大于零； 第二，求12( ),( ),( )rf xfxfx 在在D上的极小值，依次设为上的极小值，依次设为 *12,rzzz，然后把，然后把 *(

34、 )1,2,iif xzir作为最终的作为最终的分量目标函数。分量目标函数。下面介绍两种常用的确定权系数的方法。下面介绍两种常用的确定权系数的方法。（1）老手法）老手法 如果问题的目标仅有少数几个，而且计算者对问题有如果问题的目标仅有少数几个，而且计算者对问题有深入的了解，能够从专业理论和实践经验中找到根据，那深入的了解，能够从专业理论和实践经验中找到根据，那么计算者可以直接确定各目标的权系数。但是，当目标较么计算者可以直接确定各目标的权系数。但是，当目标较多时，单凭一个人的经验估计就那么不科学了。这时，可多时，单凭一个人的经验估计就那么不科学了。这时，可使用使用老手法老手法：通过汇集多位老手

35、的经验估计来确定权系数：通过汇集多位老手的经验估计来确定权系数的一种方法。而的一种方法。而老手老手是指有关专家和有实践经验的工作者。是指有关专家和有实践经验的工作者。下面介绍老手法。下面介绍老手法。rq设有设有个目标，请了个目标，请了位老手。在老手们对问题位老手。在老手们对问题了解之后，他们独自地对各目标的重要程度进行评估。了解之后，他们独自地对各目标的重要程度进行评估。充分充分ijiju01,2,ijujr111,2,rijjuiq设第设第位老手对第位老手对第个目标赋予的权系数是个目标赋予的权系数是，要求，要求，。计算各目标。计算各目标权系数的算术平均值权系数的算术平均值11,1,2, ,qjijiuujrq显然显然11, 0rjjjuu。再计算各位