多目标规划求解方法介绍.ppt

多目标规划求解方法介绍.ppt

ID:59825643

大小:624.50 KB

页数:37页

时间:2020-11-24

多目标规划求解方法介绍.ppt_第1页
多目标规划求解方法介绍.ppt_第2页
多目标规划求解方法介绍.ppt_第3页
多目标规划求解方法介绍.ppt_第4页
多目标规划求解方法介绍.ppt_第5页
资源描述:

《多目标规划求解方法介绍.ppt》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、§3.3多目标规划求解方法介绍一、约束法1.基本思想:在多个目标函数中选择一个主要目标作为目标函数,其它目标处理为适当的约束。无妨设为主要目标,对其它各目标可预先给定一个期望值,不妨记为,则有求解下列问题:容易证明,约束法求问题(P)的最优解,其Kuhn-Tucker条件与(VP)有效解的K-T条件一致。因此,约束法求得的解是有效解。(P)问题中各目标函数期望值的取得有多种方法,一种方法是取一点,而取得到下列问题:2.算法一般步骤:考虑上述(VP)问题,为主目标。第一步:(1)对,求解单目标问题:得解;(2)计算对应的各目标函数值,并对每个函数,求其p个点值中的最大值Mj和最小值

2、mj。得到下表:Mj与mj规定了在有效解集中的取值范围。x(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………第二步:选择整数r>1,确定的r个不同阀值:第三步:对,分别求解问题:各目标函数可对应不同的(共有个约束问题)。求解后可得到(VP)的一有效解集合,是(VP)有效解集合的一个子集。例6:用约束法求解。设为主目标。第一步:分别求解得得f1f2x(1)x(2)Mjmj-3063-1536-30-15选定r=4:求解于是可得四组解,如图15所示

3、。j=2只有一个tf02t0123-15-8-16二、分层序列法:基本步骤:把(VP)中的p个目标按其重要程度排一次序。依次求单目标规划的最优解。2.过程:无妨设其次序为先求解得最优值,记再解得最优值,依次进行,直到得最优值则是在分层序列意义下的最优解集合。3.性质:,即在分层序列意义下的最优解是有效解。证明:反证。设,但,则必存在使即至少有一个j0,使,由于,即,矛盾。得证。4.进一步讨论:上述方法过程中,当某个问题(Pj)的解唯一时,则问题的求解无意义,因为解都是唯一的。实际求解时,有较宽容意义下的分层序列法:取为预先给定的宽容值,整个解法同原方法类似,只是取各约束集合时,分

4、别取为:三、功效系数法:设目标为:其中:要求min;要求max。由于量纲问题,处理目标之间的关系时往往带来困难。1.功效系数法:针对各目标函数,用功效系数表示(俗称“打分”):满足:或使最满意时,最不满意时(即最差时)。2.常用的两种产生功效系数的方法:(1)线性型:设由于时求,令故取又时求,令故取(2)指数型:先讨论求最大的函数,。考虑:显然,有如下性质:10.当充分大时,;20.是的严格递增函数。(△)为了便于确定b0、b1,选取两个估计值:取为合格值(勉强合格,即可接受);为不合格值(不合格,即不可接受)。令并取得解得:代入式(△),得到功效系数:同理可得当时的功效系数:3

5、.利用功效系数求解问题(VP):设(VP)的功效系数为令构造问题:可以证明:上述问题(P)的最优解,即原问题(VP)的有效解。四、评价函数法:1.理想点法:设,即各单目标问题的最优值。令评价函数,做为目标函数。更一般地,取从不同角度出发,构造评价函数h(F),求问题,得到(VP)的有效解。下面介绍一些评价函数的构造(即不同的方法)。2.平方和加权法:求出各单目标问题最优值的下界(期望的最好值)。令评价函数其中为预先确定的一组权数,且满足的值为各目标函数的权数,较重要的取值较大。3.范数和加权法:同上面类似,先求出各单目标问题的最优值下界,取,构造评价函数:其中为权系数,且。把此方

6、法与分层序列法结合,取,用于线性多目标规划,即得到目标规划方法(运筹学课中所学的)。4.虚拟目标法:仍如“2、3”得到,设取评价函数:5.线性加权法:预先给出每一目标函数的权系数,满足。取评价函数:线性加权法是最常用的方法之一。此法可直接解释(VP)有效解的Kuhn-Tucker条件。△几何意义:设n=2,p=2。线性加权法解问题:在像空间,(P)等价为问题:记,则。及分别对应单目标问题(P1)及(P2)。当正数确定后,可得问题(PF)的最优值,如图18,可知对应的原像。、。可以利用线性加权法来逼近有效解的集合,但不是一种准确寻找所有有效解的有效方法。当μ从0→-∞时,可得到非劣

7、解的一个子集。如上图19所示。A、B为相应集合的端点。当或时,可能是弱有效解,如下图20。只有,由A到B的其余点为弱有效点。它们对应的原像为弱有效解。例7:其中:,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)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。