笔记--多目标规划.docx

处理多目标规划的方法1.约束法1.1原理约束法乂裕主襄目标法.它根据问题的实际怡况.确定个目标为主要目标，而把其余目标作为次要目标.并根据决策者的经喻次聂的目标选取一定的界限值,这样就可以把次聂目标作为的束来处理从而就将反彳f多目标规划向的转化为一个在新的约束下，求主要I1.标的单目标最优化问逊.假设在P个I1.标中，/()为主要目标，而对应于其余IpD个目标函数£(x)均可以确定其允许的边界伯：a1.fi(×)h,i=2,3,p-这样我们就可以招这(P-I)个目标函数当做最优化问跑的约束来处理，于是多目标规划何咫转化称为单目标规划问题SP向题：minf.(×)公式1.1.nr、s.t.gi(×)0(=1.,2,.,wz)aifj(×)b.(j=2,3P)上述问题的可行域为2.评价函数法其根本思就是将多目标规划向区转化为个垠目标规划问区来求解，而旦该单目标规划向区的目标的数是用多目标问题的各个目标的数构造出来的，称为评价函数，例如假设原务目标规划问题的目标函数为F(X),那么我们可以通过各种不同的方式构造评价函数h(F(x),然后求解加下问遨：求解上述问即之后，可以用上述问遨的最优解/作为多目标规划向阳的最优解，正是由于可以用不同的方法来构造评价用数，因此有各种不同的评价函数方法，下面介绍几种肺用的方法。评价函数法中主要有：理想点法、平方和加权法、线性加权和法、票除法、大小法2.1理想点法考虑多目标规划问卷：IV-minF(x),首先分别求解P个第目标规划问题:s.t.gj(x)O(/=1.2.m)令各个问题的最优斛为X；(=1.,2,.,p)而其目标函数值可以表示为：其中：R=xgx)O(y=1.,2一般来说，不可能所有的X；(i=1,2,.,P)均相同，故其最优值f(i=1,2,p)组成的向懵F1,=*f；.£并不WF多目标规划的象娱，所以F°是一个几乎不可能到达理想点那么，理想点法就是在多目标规划的可行域R中找到一点,使其对应的F(x')与理想点F”最为接近，即当理想点FO时,在目标空间拉”中适当引进某种度以标掂来确定F(X)和F"之间的距离，并在这个度信标准的意义下使得多目标规划何麴集合R上某点X的目标函数F(X)与理想点F1.J之间的“即离”尽可能小而距离的度量可以利用向盘的某种模M,当我们给模M<予不同的意义是，使可以解到不同的埋想点法。下面我们给HI最坦距离理想点法，这种方法是将M取为RP中的卜卜的形式，即构造如下的单Ii标规划问SS：公式I则(F(X)=I1.F(X)-Fn=Mx)-G',f1.xrv-'"1.&")金："1.这里的评价函数MF(X)是F(X)到FO的距离,当然我们也可以采用其他评价函数的方式,例如更殷的物(8-7)进行推广，得到评价函数为：JB八式J(F(X)=馋1(X)-为，2且取整数值或音於如下形式：公式(F(X)=督H(X)Ti2.2基于加权的方法如果P个非负实数4'4''4满足其和为1.那么称=44ZiJ为一组权向“或者将44”4称为纨权不数,线设所有权系数4>°J=1.2那么称这组权系数为正权,正权的全体可以记2-kz,>J-.2.3.n.0为：J：假设所有权系数4NU./=1".,P.那么称这组权系数为非A，=,.4O,Z=1.2.p:£4=H负权，非负权的全体可以记为：IIJ上述对权向豉和权系数的定义适用于下面所介绍的各种加权和的方法.(minZ(x)(f=1.p)先求出各个单目标规划问题回g(x)2°"=1.,2的一个尽可能好的卜界工,S1，即满mZ(x)Z0,Z=1.,2,.,pA1.：xci(x)=(F(x)=(Z(x)-Z0)2然后构造评价函数：一»情况下，权系数4的值由各目标的数f(x)的鬟程度给出.平方和加权法平方和加权法是求解如下单目标规划问跑：八"1MF(x)=*1.,(X)T。丫公式1将其最优解作为多目标规划的解，线性加权和法线性加权和法是一种最常用的方法而且在理论上有理要意义,该方法是按照P个目标'(x)''=S',”的揖要程度,分别乘以组权系数4"=1.2,./»然后相加作为目标函数,再对此目标函数在多目标规划问题的约束集合R上求最优解,即构造如下单目标规划何题；八斗«1.MF(X)=E4/(X)=IF(X)公式1'求此单目标规划问题的必优解，并把它叫做多目标规划问题在践性加权意义下的以优解，且该问题中的=IA，4厂wA'或者A?,设p=2,那么多目标规划问鹿具有两个目标函数、人，取=不为6如下图,目标函数的等(S线儿/=C是一条直线.求mini=:右+NAJXF(R)的过程就是在F中找一点，使得'F=C取以小伯C=工年.从图上可以百出.H是目标函数片F的等值线与IF在左下角的切点,即F的有效点.对应于#,存在e夫使得F=F，那么又为多H标规划向曲的有效解,wA'时，G可能是弱有效解。加权因子M确定的方法：.将各分目标转化后加权为消除各分目标在量级上的差异，光将分目标函数九X)转化为无量纲等玳级目标函数/(*)N=1,2/)(Z(x)卜I)再组成统一目标函数：w,一一按各分目标的重要程度来决定如各分目标有相I可的正要性，蜃么取w1=1.0=1,2,I)一称为均匀计权，否那么取各分目标不同的加权因子，取£叱=1I-I将以M特换为无量纲的等量级目标的数Z(X)的方法：设各分FI标函数值的变动范用为：a,f,(x).即将各单目标函数的G优值的例数作为权系数，它反映了各单目标函数离开各自生优值的程度，另外相当于各分目标函数进行了无量纲的处理，而消除了各分目标在数量双上的龙异。(2)宣按加权法利加权因子分成两局部：W1=W11Wi1.(i=1.,2,.,0其中，IV11一一本征权因子，反映各分目标的重要程度S1.一校正权因子,调整各分目标间Ift级差异的影响Tmf”就FX2一个分目标函敷启X)变化越快，|以5)的值越大，加权因子W2,念小，反之，亦然.这样可辑蔓不同的目标函数值同步下降.2.4 乘除法(存疑：乘除法原理即乘塞指数有变化，1或-1,为何不是2或-2?按照重要性嘉指数应变大！)假设我们的目标可以分为两组：一组要求/人3的值越小越好：另一组要求工“/一”/小)越大越好.而且对于任意的XeR,均满足函数值非负的条件E(x)>(U=1.,2,”,此时可以令:Z(X)=Z(x)f=1.2k(8-12)/.；义)f=A+1.A+2,p这样就可以把多目标规划砸统-为：F(x)=("x闭X)以X)'乘除法的原理就是构造如下目标的数：min(F(x)=11(x)=x*JCi1.口“)/;(XM(X).(x)公式111/().1().j()-4(×)Z7那么多目标规划何起已经转化为刑目标规划问遨.在乘除法中我们是把求最大的目标作为分母,把求最小的目标作为分子，如此化为单目标问题后再求最小。2.5 最大最小法X=FMINIMAX(FUN,XOABrAeq1Beq,1.B,UB.NON1.CON,OPTIONS)在对策论中，人们经常遇到这样的问题：在最不利的条件下如何寻求最有利的策略。因此，求解极小化的多目标规划，也就是要在R中求出各个目标函数的最大值中的G小值.这就是极大极小法的根本思想，基于上述根本思想.极大极小法是构造评价函数：*F(X)=瞎V(X)1.从而求解下述尊目标规划问题P的最优解：喧M",)=既"Oo1.有时也给每个配上权系数4,即考虑如下问叫嘲MF(X)明"(*)其中=(A,4JWA或者A”.当"=1.”=2时极大极小法的几何意义如下图.x是MF(X)在R中的极小点.2.6 结论(看不懂。，。)以上我们借助于不同形式的评价函数MF(X)符多目标规划问遨转化为单目标规划何跑.现在我们将要讨论：上述何即的股优解在什么条件之下才是多目标燃划问起的的有效例或弱有效解.为此,给出两个定义：如果对于UFFR当满足FF'时均满足MF)<Mr).那么MF)称为F的严格瓶调增函数.如果对于VFFe肥，当湎足F<F时均满足力(F)S(F)那么力(F)称为F的单调堵南数。在上述定义下，转化后的单目标规划问璃是多目标规划何题的有效解或者弱有效解的条件由下面两个定理描述：假设MF(X)是F(X)的严格单调增函数,那么转化后的单目标规划问题的以优解是多目标规划问即的有效解，线设MF(X)是F(X)的单调增函数那么转化后的刑目标规划问曲的最优解是多目标规划何题的就有效解.可以证明，评价函数法中所给的评价函数都是严格单调增函数或单调增函数，因而其最优解是多目标规划问造的有效解或弱有效解，3.成效系数法我们知遒，多目标规划的仔意一个可行解XGR.时每个目标/(X)的相应值是有好有坏的。一个XeR对某个X)的相应(的好坏程度，称为X对£(、)的成效.为了便于对每个XGR比拟它对某个/(X)的成效大小，可将以"X)作一个函数变换4(x),即令：4=4(E(X),''/U=2.P并规定：对x)产生成奴最好的X,评分为4=1；成效破坏的X,评分为4=°：对不是最好也不是最坏的中间状态，评分为°<4<1.换句话说.我们用一个值在。与1之间的成效函数4("M)''cA来反映"x)的好坏。下面介绍以常用的两种评分方法：战性型和指数型，3.1 线性成效系数法这种方法是用成效最好与最坏的两点之间的底线来反映成效程度的，考虑如下的多目标规划问超：求出X)的最大值和破小曲>")="="p;嘿X)=加=2由于当i=12./时，£(x)要求越小越好，故可取:4=4()=公式1Z-Z=B/其中式选取1a作为函数值，主要是因为过两点（!,）和（/°）可作一条口鼓，其方程为:Z(X)-Z4"(X)WkX-Z0-1,4（£（x）的图形见图所示.<U()=,-if'=,2由上式得：X显然，越澈近（狗的成效越好.越靠近伉°）的成效越坏.所以4（工（、）便可以反映诸要求I（X）越大越好，故可取:Z(x)'-1.2”A越小越好（2）对于当i=+1，攵+2,.p时,4=4(f()=公式2E(X)-ZITrr/=Z/=Zf1<f<fi其中式选取I-£作为函数假，主要是因为过两点（£°）和"）可作一条宜饯，其方程为:z-zI-。4(X)=)J,i=k+1.k+2,Pd()于是可得：f1.i,“八川X的图形见图所示.由（2）可知，对所有的AR"”2，均给出了相应的成效系数4（/（、），用所推导出的4（E（x）的公式中,节诸4（X）=I时便可以同时保证前k个目标越小越好.而后一“个Ii标越大越好.为了求解一个实际问时，我们不会寻求目标函数成效G坏的解X，即我们不殳求使得4=0,i=1.,2,的解，因此我们不妨假设4时于WXeR，'=i，2,，我们作其几何平均数:公式3£MF(X)=1.(/(x)J