多目标规划2

第十章多目标规划的解法10.1分量加权方法考虑多目标规划mixhRxxXtsxfxfxfPinp,)(,Xx..)](,...),(),([F(x)MinZ)(其中，一、线性加权和法Xx..)(w(x)Min)(jtsxfUPpjj二、平方加权和法XxS.t.))((w(x))(*jpjjfxfUP三、NISE法只适用于双目标凸规划,考虑双目标凸规划问题Xx..)](),([)(tSxfxfxFMin假定X是凸集，f1(x)，f2(x)是X上的凸函数，X*为非劣解集F是目标集，F*是非劣解集，则对于双目标规划问题，有如下性质：性质1因为X和f1(x)，f2(x)的凸性，目标集F一定是凸集；性质2在目标空间中，F的非劣解集F*一定是F的边界；性质3非劣解集F*一定完全被集合F0包含，其中),()](),([B),,()](),([A,),()(,),()(},)(),(,,|),{(******ffxfxfffxfxfXxxfMinxffXxxfMinxffBAfffffffffFff*ff*ffoAB*FFx1为与目标集中A点相对应的可行解；x2为与目标集中B点相对应的可行解。集合F0就是上图中的ABO，F*曲线（AB）完全被包含在F0中。ffffAB*FRPQTH性质4对于非劣曲线F*上的任意两点P和Q，总存在一个支撑曲线，它与直线PQ有相同的斜率，这个支撑曲线与非劣曲线F*相切于点R，点R一定位于P和Q之间，如上图所示。这个切点R可通过求解如下的参数规划P()得到)()()()(S.t.)]()(Min[:)(1QfPfQfPfPQPQXxxfxfP的非劣性，所以的斜率，由于曲线是直线，这里，根据性质4，如果沿A点和B点之间的非劣曲线F*,通过调整对1和2的选择，并求解P()，就能生成F*的全部非劣解。特别令1=1,2=0，就得到端点A；令2=1,1=0，就得到端点B。性质4是NISE算法的基础。NISE算法的步骤1、求f1*和f2*，最优解分别为x1,x2，i1=1,i2=2,K=2；记Pi1=[f1(x1)，f2(x1)]，Pi2=[f1(x2)，f2(x2)]；2、求解P():3、P()的最优解x#是否唯一？若是，转步骤4；否则转5；4、是否存在一个Pj(j=1,2,…,K)，使得Pj=[f1(x#),f2(x#)]，若是，令i1=i1+1，i2=K，转步骤2；否则转步骤6；5、是否i2=2且i1=1?若是，则已找到K个非劣点，算法终止；否则，令i2=i2-1,i1=i1-1，转步骤2；)()(),()(,S.t.)]()(Min[:)(#iiiiiiiipfpfpfpfxXxxfxfP其中，设最优解为；否则转步骤；是否成立？若是转步骤判断、)()()()()()()()(##iiiiiipfpfpfpfpfxfxfpf7、令K=K+1，对K+1个非劣点按顺序重新编号，并令i1=i1+1，i2=K，转步骤2。其中，K为非劣点的个数，为计算精度。i1和i2分别为当前参与计算的两个非劣点的下标，算法利用这两个非劣点试图寻找在这两个非劣点之间的另一个非劣点。例考虑问题（n=2，m=6，p=2）如下，已知f1（x）=-5x1+2x2f2（x）=x1-4x2X={（x1，x2）∣-x1+x2≤3，x1+x2≤8，0≤x1≤6，0≤x2≤4}试用NISE求所有非劣点。例考虑问题（n=2，m=6，p=2）如下，已知f1（x）=-5x1+2x2f2（x）=x1-4x2X={（x1，x2）∣-x1+x2≤3，x1+x2≤8，0≤x1≤6，0≤x2≤4}试用NISE求所有非劣点。解：1）f1*=Minf1（x）=-30，x1=（6，0），i1=1,i2=2,K=2,Pi1=[f1(x1)，f2(x1)]=[-30,6],f2*=Minf2（x）=-15x2=（1，4）Pi2=[f1(x2)，f2(x2)]=[3，-15]2）i1=f2(Pi1)-f2(Pi2)=f2(x1)-f2(x2)=6-(-15)=21,i2=f1(Pi2)-f1(Pi1)=f1(x2)-f1(x1)=3-(-30)=33求解线性规划MinZ=21f1(x)+33f2(x),xX,得x#=(4,4),f1#=-12,f2#=-123)x#为唯一解；四、确定加权系数的方法法1、基本思路：以理想点F*为标准来确定各个目标的权系数2、双目标规划问题的情形1）求f1*，得最优解为x1，求f2*，得最优解为x2，F(x1)=[f1*，f21]=[f1(x1)，f2(x1)],F(x2)=[f12，f2*]=[f1(x2)，f2(x2)]记理想点F*=（f1*，f2*）2）求解单目标最优化问题])([])([**XxfxffxfdMin设其最优解为x0，记F0=[f1(x0)，f2(x0)]3）求F0点的加权系数F0点的几何意义如下图ff*ff*ffAB*FF*z从图中可见，F0恰是以理想点z*为圆点所作圆与目标集F相切的切点。连接z*和F0两点，直线F0z*的斜率为**ffffk设与直线F0z*垂直的直线方程为1f1+2f2=(1)其中，01,21，1+2=1(2)由（1）式得21212ff由两垂线的斜率关系有（负倒数关系）(3)**ffffK联立求解（2）、（3）即可得0)()(0)()(******ffffffffffff1，2就是所求的双目标f1,f2的权系数3、多目标规划问题情形1）分别对P个目标求最优解，即求fj*，(j-1,2,…,P)记理想点Z*=（f1*，f2*,…,fP*）2）求解单目标最优化问题])([*XxfxfdMinPjjj设其最优解为x0，记F0=[f10，f20，…，fP0]则类似于双目标规划问题，可求得其加权系数为1P,1,2,...,k0,,...,,0)(1kk**PkPiiikkkPkffff且满足10.2分量最优化方法这一方法是把多目标问题转化成求其分量的单目标最优化问题，对于各个分量处理方法不同，就形成了不同方法。一、主要目标法从多目标函数F(x)的p个分量中选出一个最重要的目标作为主要目标，设fs(x)为主要目标，同时对于其余p-1个分量fj(x)，(1jP，js)，估计出其上、下限并将其作为约束条件，这样就把MOP转化为单目标优化问题sjPjfxffjjj,)(sjPjfxffXxtSxfzMinjjjs,)(..)(二、恰当等式约束法只有当cj(js)取得“恰当”时，所求的单目标最优化解才是原MOP的非劣解。三、恰当不等式约束法sjPjxfXxtSxfzMinjjs,c)(..)(sjPjxfXxtSxfzMinjjs,c)(..)(只有常数cj(js)取得恰当时，求得的最优解才是原MOP的非劣解。l1,2,...,j)(,...,,)()(xgmixhxfMinji附：非线性规划的K-T条件为设x*为极小点，且ljgljxgxgxhxfljxgmixhjjjjljjimiilmji,...,,,...,,)()()()(......),...,,)((),...,,)((******************）使下式成立，，，（）和，，，（线性无关，则存在向量和例：用恰当不等式法求解MOP},|{X)()()()()(..)](),(),([)(xxRxxxxfxxxfxxxfXxtSxfxfxfxMinF其中，解：构造单目标最优化问题4321gggg)()(1,0--..)()()(,)()(..)()()(xxfxxxxcxxctSxxxfMinxxcxxxfcxxxftSxxxfMin）（即设x*为单目标优化问题（1）的最优解，则有cccccccccccxccxccxxxxxcxxcxx,),()(,,,,)()()()(***************************，必须满足其中所以时，可求得，当如果c2，c3选取恰当，则x*(c)就是原MOP的非劣解。如（1）c2=1，c3=1，x*=(1,0)，F*=(8,1,1)（2）c2=2，c3=3，x*=(1,1)，F*=(5,2,3)是否是非劣解？10.3分量排序方法一、字典序法设原MOP为)(...)()(Xx..)](,...),(),([F(x)MinZ)(xfxfxftsxfxfxfPpp另设则字典序法的步骤如下：1）求单目标优化问题设最优目标函数值为f1*，令l=22）建立并求解第l层次的单目标规划问题)(XxxfMin）；），否则转步骤（，转步骤（，若令，最优目标函数值为设最优解为241)31,...,2,1)(..)(***PlllfxlkfxfXxtSxfMinplllkkl4)终止，输出结果。满意解x*=xP*.例用字典序法求解如下多目标规划},,|{X)()()(..)](),(),([)(xxxxRxxxxxxfxxxxxfxxxxxxxfXxtSxfxfxfxMinF其中，解设目标的重要性排序为f1f2f31)构造并求解单目标规划))(()(xxxxxxxxfMinP得最优解x(1)*=(x1,x2,2),f1*=1,这时有x12+2x2=1,x3=22）建立并求解第2层次单目标规划)()(xxxxxxxxxxxxfMinP得最优解x(2)*=(-1，0，2)或x(2)*=(1，0，2)，f2*=2。3）建立并求解第3层次单目标规划1)(xxxxxxxxxxfMinP得最优解x(3)*=(1，0，2)，f3*=-2。因此，x*=(1，0，2)，F*=（1，2，-2）二、宽容排序法运用“字典序”法，常常在较高层次就会发现问题（pl）只有唯一解，因此再往下求解就没有意义，上例中若原多目标规划问题的约束方程增