多目标规划求解方法介绍(课堂PPT).ppt
《多目标规划求解方法介绍(课堂PPT).ppt》由会员分享,可在线阅读,更多相关《多目标规划求解方法介绍(课堂PPT).ppt(37页珍藏版)》请在咨信网上搜索。
1、3.3 多目标规划求解方法介绍一、约束法一、约束法1.基本思想:基本思想:在多个目标函数中选择一个主要目标作为在多个目标函数中选择一个主要目标作为目标函数,其它目标处理为适当的约束。目标函数,其它目标处理为适当的约束。无妨设无妨设 为主要目标,对其它各目标为主要目标,对其它各目标 可预先可预先给定一个期望值,不妨记为给定一个期望值,不妨记为 ,则有则有求解下列问题:求解下列问题:1 容易证明,约束法求问题容易证明,约束法求问题(P)的最优解,其的最优解,其Kuhn-Tucker条件与条件与(VP)有效解的有效解的K-T条件一致。条件一致。因此,约束法求得的解是有效解。因此,约束法求得的解是有效
2、解。(P)问题中各目标函数期望值的取得有多种方法,问题中各目标函数期望值的取得有多种方法,一种方法是取一点一种方法是取一点 ,而取,而取 得到下列问题:得到下列问题:2.算法一般步骤:算法一般步骤:考虑上述考虑上述(VP)问题,问题,为主目标。为主目标。2第一步:(1)对 ,求解单目标问题:得解 ;(2)计算 对应的各目标函数值,并对每个函数 ,求其p个点值中的最大值Mj和最小值mj。得到下表:Mj与mj规定了 在有效解集中的取值范围。x(1)x(p)f 1(x)f 2(x)f p(x)m 1 m 2 m pf 1(x(1)f 2(x(1)f p(x(1)f 1(x(p)f 2(x(p)f p
3、(x(p)M 1 M 2 M pMjmj3第二步:选择整数r1,确定 的r个不同阀值:第三步:对 ,分别求解问题:各目标函数 可对应不同的 (共有 个约束问题)。求解后可得到(VP)的一有效解集合,是(VP)有效解集合的一个子集。4例6:用约束法求解。设 为主目标。第一步:分别求解 得得f1f2x(1)x(2)Mjmj-3063-1536-30-155选定r=4:求解于是可得四组解,如图15所示。j=2只有一个 tf 02t 0 1 2 3 -15 -8 -1 667二、分层序列法:1.基本步骤:把(VP)中的p个目标 按其重要程度排一次序。依次求单目标规划的最优解。2.过程:无妨设其次序为
4、先求解 得最优值 ,记再解 得最优值 ,依次进行,直到 得最优值则 是在分层序列意义下的最优解集合。83.性质:,即在分层序列意义下的最优解是有效解。证明:反证。设 ,但 ,则必存在 使 即至少有一个j0,使 ,由于 ,即 ,矛盾。得证。4.进一步讨论:上述方法过程中,当某个问题(Pj)的解唯一时,则问题 的求解无意义,因为解都是唯一的。实际求解时,有较宽容意义下的分层序列法:取 为预先给定的宽容值,整个解法同原方法类似,只是取各约束集合时,分别取为:9三、功效系数法:设目标为:其中:要求min;要求max。由于量纲问题,处理目标之间的关系时往往带来困难。1.功效系数法:针对各目标函数 ,用功
5、效系数 表示(俗称“打分”):满足:或使最满意时 ,最不满意时(即最差时)。2.常用的两种产生功效系数的方法:(1)线性型:设 10由于 时求 ,令故取又 时求 ,令故取(2)指数型:先讨论求最大的函数,。考虑:显然,有如下性质:10.当 充分大时,;20.是 的严格递增函数。()11 为了便于确定b0、b1,选取两个估计值 :取 为合格值(勉强合格,即可接受);为不合格值(不合格,即不可接受)。令并取 得解得:代入式(),得到功效系数:同理可得当 时的功效系数:12133.利用功效系数求解问题(VP):设(VP)的功效系数为令构造问题:可以证明:上述问题(P)的最优解 ,即原问题(VP)的有
6、效解。四、评价函数法:1.理想点法:设 ,即各单目标问题的最优值。令评价函数 ,做为目标函数。更一般地,取14 从不同角度出发,构造评价函数h(F),求问题 ,得到(VP)的有效解。下面介绍一些评价函数的构造(即不同的方法)。2.平方和加权法:求出各单目标问题最优值的下界 (期望的最好值)。令评价函数其中 为预先确定的一组权数,且满足 的值为各目标函数的权数,较重要的取值较大。153.范数和加权法:同上面类似,先求出各单目标问题的最优值下界 ,取 ,构造评价函数:其中 为权系数,且 。把此方法与分层序列法结合,取 ,用于线性多目标规划,即得到目标规划方法(运筹学课中所学的)。4.虚拟目标法:仍
7、如“2、3”得到 ,设 取评价函数:165.线性加权法:预先给出每一目标函数 的权系数 ,满足 。取评价函数:线性加权法是最常用的方法之一。此法可直接解释(VP)有效解的Kuhn-Tucker条件。几何意义:设n=2,p=2。线性加权法解问题:17 在像空间,(P)等价为问题:记 ,则 。及 分别对应单目标问题(P1)及(P2)。当正数 确定后,可得问题(PF)的最优值 ,如图18,可知 对应的原像 。、。18 可以利用线性加权法来逼近有效解的集合,但不是一种准确寻找所有有效解的有效方法。当从0-时,可得到非劣解的一个子集。如上图19所示。A、B为相应集合的端点。当 或 时,可能是弱有效解,如
8、下图20。只有 ,由A到B的其余点为弱有效点。它们对应的原像为弱有效解。例7:19其中:,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)构成的多
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多目标 规划 求解 方法 介绍 课堂 PPT
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。