多目标规划ppt课件.pptx

《多目标规划ppt课件.pptx》由会员分享，可在线阅读，更多相关《多目标规划ppt课件.pptx（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值第十章第十章 多目标规划的解法多目标规划的解法10.1 分量加权方法分量加权方法 考虑多目标规划考虑多目标规划一、线性加权和法一、线性加权和法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值二、平方加权和法二、平方加权和法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值三、三、NISE法法只适用于双目标凸规划只适用于双目标

2、凸规划,考虑双目标凸规划问题考虑双目标凸规划问题假假定定X是是凸凸集集，f1(x)，f2(x)是是X上上的的凸凸函函数数，X*为为非非劣劣解解集集F是是目目标标集集，F*是是非非劣劣解解集集，则则对对于于双双目目标标规规划划问问题题，有有如下性质：如下性质：性质性质1 因为因为X和和f1(x)，f2(x)的凸性，目标集的凸性，目标集F一定是凸集；一定是凸集；性质性质2 在目标空间中，在目标空间中，F的非劣解集的非劣解集F*一定是一定是F的边界；的边界；性质性质3 非劣解集非劣解集F*一定完全被集合一定完全被集合F0包含，其中包含，其中资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函

3、数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值x1为与目标集中为与目标集中A点相对应的可行解；点相对应的可行解；x2为与目标集中为与目标集中B点相对应的可行解。集合点相对应的可行解。集合F0就是上图中的就是上图中的 ABO，F*曲曲线（线（AB）完全被包含在）完全被包含在F0中。中。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值性性质质4 对对于于非非劣劣曲曲线线 F*上上的的任任意意两两点点P和和Q，总总存存在在一一个个支支撑撑曲曲线线，它它与与直直线线PQ有有相相同同的的斜斜率率，这这个个支支撑

4、撑曲曲线线与与非非劣劣曲曲线线F*相相切切于于点点R，点点R一一定定位位于于P和和Q之之间间，如上图所示。如上图所示。这个切点这个切点R可通过求解如下的参数规划可通过求解如下的参数规划P()得到得到资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值根根据据性性质质4，如如果果沿沿A点点和和B点点之之间间的的非非劣劣曲曲线线F*,通通过过调调整整对对 1和和 2的的选选择择，并并求求解解P()，就就能能生生成成F*的的全全部部非非劣劣解解。特特别别令令 1=1,2=0，就就得得到到端端点点A；令令 2=1,1=0，就就得到

5、端点得到端点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#)，若若是，

6、是，令令i1=i1+1，i2=K，转步骤转步骤2；否则转步骤；否则转步骤6；5、是是否否i2=2且且i1=1?若若是是，则则已已找找到到K个个非非劣劣点点，算算法法终终止止；否则，令否则，令i2=i2-1,i1=i1-1，转步骤，转步骤2；资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值7、令、令K=K+1，对对K+1个非劣点按顺序重新编号，个非劣点按顺序重新编号，并并令令i1=i1+1，i2=K，转步骤转步骤2。其中，其中，K为非劣点的个数，为非劣点的个数，为计算精度。为计算精度。i1和和i2分别为当前分别为当前参与

7、计算的两个非劣点的下标，算法利用这两个非劣点试图参与计算的两个非劣点的下标，算法利用这两个非劣点试图寻找在这两个非劣点之间的另一个非劣点。寻找在这两个非劣点之间的另一个非劣点。例例 考虑问题（考虑问题（n=2，m=6，p=2）如下，已知）如下，已知f1（x）=-5x1+2x2 f2（x）=x1-4x2 X=（x1，x2）-x1+x23，x1+x28，0 xx1 166，0 x0 x2 244试用试用NISE求所有非劣点。求所有非劣点。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值例例 考虑问题（考虑问题（n=2，m=

8、6，p=2）如下，已知）如下，已知f1（x）=-5x1+2x2 f2（x）=x1-4x2 X=（x1，x2）-x1+x23，x1+x28，0 xx1 166，0 x0 x2 244试用试用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）=-15 x2=（1，4）Pi2=f1(x2)，f2(x2)=3，-152）i1=f2(Pi1)-f2(Pi2)=f2(x1)-f2(x2)=6-(-15)=21,i2=f1(Pi2)-f1(Pi1)=f1(x2)

9、-f1(x1)=3-(-30)=33求解线性规划求解线性规划 Min Z=21f1(x)+33f2(x),x X,得得x#=(4,4),f 1#=-12,f2#=-123)x#为唯一解；为唯一解；资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值四四、确定加权系数的方法确定加权系数的方法 法法1、基本思路：以理想点基本思路：以理想点F*为标准来确定各个目标的权系数为标准来确定各个目标的权系数2、双目

10、标规划问题双目标规划问题的情形的情形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）求解单目标最优化问题求解单目标最优化问题设其最优解为设其最优解为x0，记，记F0=f1(x0)，f2(x0)3）求）求F0点的加权系数点的加权系数F0点的几何意义如下图点的几何意义如下图从图中可见，从图中可

11、见，F0恰是以恰是以理想点理想点z*为圆点所作圆为圆点所作圆与目标集与目标集F相切的切点。相切的切点。连接连接z*和和F0两点，直线两点，直线F0 z*的斜率为的斜率为资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值设与直线设与直线F0 z*垂直的直线方程为垂直的直线方程为 1f1+2f2=(1)其中，其中，0 1,20称为宽容度称为宽容度这种方法所得到满意解与所取的宽容度这种方法所得到满意解与所取的宽容度 k大小有关。大小有关。10.4 理想点法理想点法一一、基基本本思思路路：先先求求理理想想点点Z*，然然后后在在可

12、可行行目目标标集集中中找找与与Z*距离最近的可行点（称为最好妥协解）。距离最近的可行点（称为最好妥协解）。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值二、理想点法的步骤二、理想点法的步骤1、求理想点、求理想点 Z*=（f1*，f2*，fP*）2、求最好妥协解，即求如下单目标最优化问题、求最好妥协解，即求如下单目标最优化问题特别地，（特别地，（1）当）当=1时，时，P(d)问题为问题为（2）当）当=时，时，P(d)问题为问题为资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的

13、这部分资金就是原有资金的时间价值例、考虑双目标规划问题例、考虑双目标规划问题解解 1）Z*=（-30，-15）2）当）当=1 时，时，P(d)问题为问题为最最 优优 解解 为为 x1*=6，x2*=2，f1*=-26，f2*=-2 3)当当=2 时，时，P(d)问题为问题为最优解为最优解为x1*=5.5，x2*=2.5，f1*=-22.5，f2*=-4.54)当当=时，时，P(d)问题为问题为资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值最优解为最优解为x1*=5.25，x2*=2.75，f1*=-20.75，f2*

14、=-5.75一一般般地地，最最好好妥妥协协解解定定义义了了一一个个界界于于d1意意义义下下的的最最好好妥妥协协解解和和d 意意义义下下最最好好妥妥协协解解范范围围之之间间的的非非劣劣解子集合，如下图所示。解子集合，如下图所示。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值三、加权距离理想点法三、加权距离理想点法1、当、当 取不同值时，满意解取不同值时，满意解xW 是不同的；是不同的；2、对于、对

15、于1 ，只要，只要w0，满意解，满意解xW 一定是非劣解，且一定是非劣解，且妥协解集妥协解集XWC一定包含于非劣解集一定包含于非劣解集X*中，即中，即XWC X*3、在线性多目标规划问题中，妥协解集、在线性多目标规划问题中，妥协解集XWC可完全被点可完全被点xW1 和点和点xW 所决定所决定4、对于线性双目标规划问题、对于线性双目标规划问题XWC=x|x=xW1+(1-)xW，015、对于、对于3个以上目标的线性多目标规划问题，个以上目标的线性多目标规划问题，XWC可近似地可近似地表示成如下双目标规划问题的非劣解集合表示成如下双目标规划问题的非劣解集合资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值四、反理想点法四、反理想点法1、求反理想点、求反理想点 Z=（f1，f2，fP）2、求最好妥协解，即求如下单目标最优化问题、求最好妥协解，即求如下单目标最优化问题五、综合理想点法五、综合理想点法当当决决策策者者已已知知Z*和和Z 时时，此此时时可可把把多多目目标标规规划划问问题题转转化化为为双双目目标标规规划划问问题题。而而求求解解双双目目标标规规划划问问题题有有很很多多有有效效的算法，便于迅速求解。的算法，便于迅速求解。