多目标规划求解方法介绍

§3.3多目标规划求解方法介绍一、约束法1.基本思想：在多个目标函数中选择一个主要目标作为目标函数，其它目标处理为适当的约束。无妨设为主要目标，对其它各目标可预先给定一个期望值，不妨记为，则有求解下列问题：mixgtsxfxfxFVVPiTp,,1,0)(..)(,),()(min)(1mixgxSi,,1,0)()(1xf)(,),(2xfxfp00302,,,pfffpjxffjSxj,,3,2),(min0pjfxfmixgtsxfPjji,,3,2,0)(,,2,1,0)(..)(min)(01容易证明，约束法求问题(P)的最优解，其Kuhn-Tucker条件与(VP)有效解的K-T条件一致。因此，约束法求得的解是有效解。(P)问题中各目标函数期望值的取得有多种方法，一种方法是取一点，而取得到下列问题：2.算法一般步骤：考虑上述(VP)问题，为主目标。Sx)0(pjxffjj,,3,2),()0(0pjxfxfmixgtsxfPjji,,3,2),()(,,2,1,0)(..)(min)()0(1~)(xfk第一步：（1）对，求解单目标问题：得解；（2）计算对应的各目标函数值，并对每个函数，求其p个点值中的最大值Mj和最小值mj。得到下表：Mj与mj规定了在有效解集中的取值范围。pj,,2,1SxtsxfVPjj..)(min)(Tjnjjjxxxx),,,()()(2)(1)()()2()1(,,,pxxx)(xfj)(xfjx(1)x(p)f1(x)f2(x)…fp(x)m1m2…mpf1(x(1))f2(x(1))…fp(x(1))f1(x(p))f2(x(p))…fp(x(p))M1M2…MpMjmj………第二步：选择整数r1，确定的r个不同阀值：第三步：对，分别求解问题：各目标函数可对应不同的（共有个约束问题）。求解后可得到(VP)的一有效解集合，是(VP)有效解集合的一个子集。)1,,1,0(rttjj)(kjfj0jf1,,1,0;,,1,1,,1),(10rtpkkjmMrtmfjjjjt1,,1,0rtpkkjfxfmixgtsxfPjjjtjikt,,1,1,,1,0)(,,2,1,0)(..)(min)(1pr例6：用约束法求解。设为主目标。第一步：分别求解0)(0)(04)(06)(08)(03)(..)(),()(min)(2615241321221121xxgxxgxxgxxgxxxgxxxgtsxfxfxFVLVPT21125)(xxxf2124)(xxxf)(1xfSxtsxf..)(min1Tx)0,6()1(得Sxtsxf..)(min2Tx)4,1()2(得f1f2x(1)x(2)Mjmj-3063-1536-30-15选定r=4:求解于是可得四组解，如图15所示。0)(..)(min)(221jjttfxfSxtsxfPj=2只有一个6,30,3,)0,6(;1,5.26,2,)75.1,6(;8,6.17,1,)2.3,8.4(;15,3,0,)4,1(32313~22212~12111~02010~fftxfftxfftxfftxTTTTtf02t0123-15-8-16二、分层序列法：1.基本步骤：把(VP)中的p个目标按其重要程度排一次序。依次求单目标规划的最优解。2.过程：无妨设其次序为先求解得最优值，记再解得最优值，依次进行，直到得最优值则是在分层序列意义下的最优解集合。)(,),(1xfxfppfff,,,21SxtsxfP..)(min)(11*1fSfxfxS*111)(122..)(min)(SxtsxfP*2f1*222)(SfxfxS1..)(min)(pppSxtsxfP*pf1*)(ppppSfxfxS3.性质：，即在分层序列意义下的最优解是有效解。证明：反证。设，但，则必存在使即至少有一个j0，使,由于，即，矛盾。得证。4.进一步讨论：上述方法过程中，当某个问题(Pj)的解唯一时，则问题的求解无意义，因为解都是唯一的。实际求解时，有较宽容意义下的分层序列法：取为预先给定的宽容值，整个解法同原方法类似，只是取各约束集合时，分别取为：pjPP,,10,,011ppjSfxfxSjjjj,,3,2,)(1^*^)(min)(0000*~xffxfjSxjjj0~jSx)()(~~00xfyfjj1,,1),()(0~~jjxfyfjj)()(~~xFyFSy~*~paSxpSx~*papSS三、功效系数法：设目标为：其中：要求min；要求max。由于量纲问题，处理目标之间的关系时往往带来困难。1.功效系数法：针对各目标函数，用功效系数表示（俗称“打分”）：满足：或使最满意时，最不满意时（即最差时）。2.常用的两种产生功效系数的方法：（1）线性型：设0jd1jd10jd10jdpjxfddjjj,,1,))((),,1)((pjxfj)(,),(1xfxfpk)(,),(1xfxfk)(,),(),(21xfxfxfppjfxffxfjjSxjjSx,,2,1,)(max,)(minmaxminjd由于时求，令故取又时求，令故取（2）指数型：先讨论求最大的函数，。考虑：显然，有如下性质：10.当充分大时，；20.是的严格递增函数。)())((1minmaxminjjjjjfffxfdmaxmin,0,1jjjjjffffdkj,,1)())((minmaxminjjjjjfffxfdminmax,0,1jjjjjffffdpkj,,1)(maxxfj)(minxfjpkj,,1jdjdjf1jdjf0,1)10(bedjfbbej（△）为了便于确定b0、b1，选取两个估计值：取为合格值（勉强合格，即可接受）；为不合格值（不合格，即不可接受）。令并取得解得：代入式(△)，得到功效系数：同理可得当时的功效系数：011)(,0660.0)(,3679.0jjejjjfxfefxfed0jf1jf10,jjff)010()110(1jfbbjfbbeeeeeee10010110jjfbbfbb)0()(1,)(11011010bffbfffbjjjjjkj,,1)10()1)((jfjfjfxjfejed)10())(1(jfjfxjfjfejed3.利用功效系数求解问题(VP)：设(VP)的功效系数为令构造问题：可以证明：上述问题(P)的最优解，即原问题(VP)的有效解。四、评价函数法：1.理想点法：设，即各单目标问题的最优值。令评价函数，做为目标函数。更一般地，取*xmixgtsxfdxFhPippjjj,,1,0)(..)))((())((max)(11ppjjdFh11)()(pjxfddjjj,,2,1)),((pjxffjSxj,,2,1),(min*pjjjfxfFh12*))(()(qpjqjjfxfFh11*)))((()(从不同角度出发，构造评价函数h(F)，求问题,得到(VP)的有效解。下面介绍一些评价函数的构造(即不同的方法)。2.平方和加权法：求出各单目标问题最优值的下界(期望的最好值)。令评价函数其中为预先确定的一组权数，且满足的值为各目标函数的权数，较重要的取值较大。SxtsxFh..))((minj1;,,2,1,01pjjjpjp,,,21pjjjjfxfFh10))(()(mixgtsxfPijj,,2,1,0)(..)(min)(0jfj3.范数和加权法：同上面类似，先求出各单目标问题的最优值下界，取，构造评价函数：其中为权系数，且。把此方法与分层序列法结合，取，用于线性多目标规划，即得到目标规划方法（运筹学课中所学的）。4.虚拟目标法：仍如“2、3”得到，设取评价函数：gl0jfj1;,,2,1,01pjjjpj1q1qqpjqjjjfxfxFh110)))((())((),,2,1(0pjfjpjjjjffxfFh1200)))((()(),,2,1(00pjfj5.线性加权法：预先给出每一目标函数的权系数，满足。取评价函数：线性加权法是最常用的方法之一。此法可直接解释(VP)有效解的Kuhn-Tucker条件。△几何意义：设n=2,p=2。线性加权法解问题：j1,01pjjjpjjjxfxFh1)())(()(xfj1,0,21210)(0)(..)()(min)(212211xgxgtsxfxfP在像空间，(P)等价为问题：记，则。及分别对应单目标问题(P1)及(P2)。当正数确定后，可得问题(PF)的最优值，如图18，可知对应的原像。、。)(),(~2~2~1~1xffxff~22~11~fff~f*~paSx0021)(),(..min)(212211SFfftsfffPTF21,~f可以利用线性加权法来逼近有效解的集合，但不是一种准确寻找所有有效解的有效方法。当μ从0→-∞时，可得到非劣解的一个子集。如上图19所示。A、B为相应集合的端点。当或时，可能是弱有效解，如下图20。只有，由A到B的其余点为弱有效点。它们对应的原像为弱有效解。例7：)0(2)0(01*paEA0)(0)(04)(06)(08)(03)(..)(),()(min)(2615241321221121xxgxxgxxgxxgxxxgxxxgtsxfxfxFVLVPT~x其中：，F映射是由x1ox2到f1of2空间的一个线性变换。可行域是多胞形H(A,B,C,D,E,F)。其A(0,0)T、B(6,0)T、C(6,2)T、D(4,4)T、E(1,4)T、F(0,3)T是每两条直线的交点。F(A)=MA=(0,0)T，F(B)=MB=(-30,6)T，F(C)=MC=(-26,-2)T，F(D)=MD=(-12,-12)T，F(E)=ME=(3,-15)T，F(F)=MF=(6,-12)T。F(S)是由F(A)、F(B)、F(C)、F(D)、F(E)、F(F)构成的多胞形。如图21。21125)(xxxf2124)(xxxf214125)(xxMxxFTc)4,1(2Tc)2,5(1•图21：当,即时,即(P2)的解:E(1,4)T,对应F(E)=(3,-15)T；当,即时,即(P1)的解:B(6,0)T,对应F(B)=(-30,6)T；取μ=-1,即时,问题为：最优解为:C(6,2)T,对应F(C)=(-26,-2)T；取μ=-1/2,即时,问题为：最优解为:D(4,4)T,对应F(D)=(-12,-12)T；取μ=-1/3,即时,问题为:最优解为:D(4,4)T,对应F(D)=(-12,-12)T。01,02121,21210,121