多目标优化方法及实例解析.ppt
《多目标优化方法及实例解析.ppt》由会员分享,可在线阅读,更多相关《多目标优化方法及实例解析.ppt(76页珍藏版)》请在咨信网上搜索。
1、第九讲第九讲 多目标规划方法多目标规划方法l多目标规划解的讨论多目标规划解的讨论非劣解非劣解 l多目标规划及其求解技术简介多目标规划及其求解技术简介效用最效用最优化模型化模型罚款模型款模型约束模型束模型目目标规划模型划模型目目标达到法达到法l目标规划方法目标规划方法l目目标规划模型划模型l目目标规划的划的图解法解法 l求解目求解目标规划的划的单纯形方法形方法l多目标规划应用实例多目标规划应用实例 多目标规划是数学规划的一个分支。多目标规划是数学规划的一个分支。研研究究多多于于一一个个的的目目标标函函数数在在给给定定区区域域上上的的最最优优化化。又又称称多多目目标标最最优优化化。通通常常记记为为
2、MOP(multi-objectiveprogramming)。在在很很多多实实际际问问题题中中,例例如如经经济济、管管理理、军军事事、科科学学和和工工程程设设计计等等领领域域,衡衡量量一一个个方方案案的的好好坏坏往往往往难难以以用用一一个个指指标标来来判判断断,而而需需要要用用多多个个目目标标来来比比较较,而而这这些些目标有时不甚协调,甚至是矛盾的。因此有许多学者致力于这方面的研究。目标有时不甚协调,甚至是矛盾的。因此有许多学者致力于这方面的研究。1896年年法法国国经经济济学学家家V.帕帕雷雷托托最最早早研研究究不不可可比比较较目目标标的的优优化化问问题题,之之后后,J.冯冯诺诺伊伊曼曼、
3、H.W.库库恩恩、A.W.塔塔克克、A.M.日日夫夫里里翁翁等等数数学学家家做做了了深深入入的的探探讨讨,但但是是尚未有一个完全令人满意的定义尚未有一个完全令人满意的定义。3求解多目标规划的方法大体上有以下几种:求解多目标规划的方法大体上有以下几种:一一种种是是化化多多为为少少的的方方法法,即即把把多多目目标标化化为为比比较较容容易易求求解解的的单单目目标标或或双双目目标标,如主要目标法、线性加权法、理想点法等;如主要目标法、线性加权法、理想点法等;另另一一种种叫叫分分层层序序列列法法,即即把把目目标标按按其其重重要要性性给给出出一一个个序序列列,每每次次都都在在前前一一目目标标最优解集内求下
4、一个目标最优解,直到求出共同的最优解。最优解集内求下一个目标最优解,直到求出共同的最优解。对对多多目目标标的的线线性性规规划划除除以以上上方方法法外外还还可可以以适适当当修修正正单单纯纯形形法法来来求求解解;还还有有一一种种称称为为层层次次分分析析法法,是是由由美美国国运运筹筹学学家家沙沙旦旦于于70年年代代提提出出的的,这这是是一一种种定定性性与与定定量量相相结结合合的的多多目目标标决决策策与与分分析析方方法法,对对于于目目标标结结构构复复杂杂且且缺缺乏乏必必要要的的数数据据的的情情况更为实用。况更为实用。多目标规划模型多目标规划模型(一)任何多目标规划问题,都由两个基本部分组成:(一)任何
5、多目标规划问题,都由两个基本部分组成:(1 1)两个以上的目标函数;)两个以上的目标函数;(2 2)若干个约束条件。)若干个约束条件。(二)对于多目标规划问题,可以将其数学模型一般地描写为如下形式:(二)对于多目标规划问题,可以将其数学模型一般地描写为如下形式:一一 多目标规划及其非劣解多目标规划及其非劣解式中:为决策变量向量。缩写形式:缩写形式:有有n个决策变量,个决策变量,k个目标函数,个目标函数,m个约束方程,个约束方程,则:则:Z=F(X)是是k维函数向量,维函数向量,(X)是是m维函数向量;维函数向量;G是是m维常数向量;维常数向量;(1)(2)对于线性多目标规划线性多目标规划问题,
6、可以进一步用矩阵表示:式中:式中:X X 为为n n 维决策变量向量;维决策变量向量;C C 为为k kn n 矩阵,即目标函数系数矩阵;矩阵,即目标函数系数矩阵;B B 为为m mn n 矩阵,即约束方程系数矩阵;矩阵,即约束方程系数矩阵;b b 为为m m 维的向量,即约束向量。维的向量,即约束向量。多目标规划的非劣解多目标规划的非劣解多目标规划问题的求解不能只追求一个目标的最优化(最大或最小),而不顾其它目标。对于上述多目标规划问题,求解就意味着需要做出如下的复合选择:每一个目标函数取什么值,原问题可以得到最满意的解决?每一个决策变量取什么值,原问题可以得到最满意的解决?在在图图1中中,
7、max(f1,f2).就就方方案案和和来来说说,的的f2目目标标值值比比大大,但但其其目目标标值值f1比比小小,因因此此无无法法确确定定这这两两个个方方案案的的优优与与劣。劣。在在各各个个方方案案之之间间,显显然然:比比好好,比比好好,比比好好,比比好好。非劣解非劣解可以用图1说明。图图1 多目标规划的劣解与非劣解多目标规划的劣解与非劣解9而而对对于于方方案案、之之间间则则无无法法确确定定优优劣劣,而而且且又又没没有有比比它它们们更更好好的的其其他他方方案案,所所以以它它们们就就被被称称为为多多目目标标规规划划问题的问题的非劣解非劣解或或有效解有效解,其余方案都称为其余方案都称为劣解劣解。所所
8、有有非非劣劣解解构构成成的的集集合合称称为为非非劣解集劣解集。当目标函数处于冲突状态时,就不会存在使所有目标函数同时达到最当目标函数处于冲突状态时,就不会存在使所有目标函数同时达到最大或最小值的最优解,于是我们只能寻求非劣解(又称大或最小值的最优解,于是我们只能寻求非劣解(又称非支配解或帕累托非支配解或帕累托解解)。)。效用最优化模型效用最优化模型 罚款模型罚款模型 约束模型约束模型 目标达到法目标达到法 目标规划模型目标规划模型二二 多目标规划求解技术简介多目标规划求解技术简介 为为了了求求得得多多目目标标规规划划问问题题的的非非劣劣解解,常常常常需需要要将将多多目目标标规规划划问问题题转转
9、化为单目标规划问题化为单目标规划问题去处理。实现这种转化,有如下几种建模方法。去处理。实现这种转化,有如下几种建模方法。是与各目标函数相关的是与各目标函数相关的效用函数的效用函数的和函数和函数。方法一方法一效用最优化模型效用最优化模型(线性加权法线性加权法)(1 1)(2 2)思想思想:规划问题的各个目标函数可以通过:规划问题的各个目标函数可以通过一定一定的的方式方式进行进行求和求和运算。这运算。这种方法将一系列的种方法将一系列的目标函数目标函数与与效用函数效用函数建立相关关系,各目标之间通过建立相关关系,各目标之间通过效用函数协调,使多目标规划问题转化为传统的单目标规划问题:效用函数协调,使
10、多目标规划问题转化为传统的单目标规划问题:在在用用效效用用函函数数作作为为规规划划目目标标时时,需需要要确确定定一一组组权权值值 i 来来反反映映原原问问题题中中各各目标函数在总体目标中的权重,即目标函数在总体目标中的权重,即:式中,i 应满足:向量形式:方法二方法二罚款模型罚款模型(理想点法)(理想点法)思想思想:规划决策者对每一个目标函数都能提出所规划决策者对每一个目标函数都能提出所期望的值期望的值(或称(或称满意值满意值););通过比较实际值通过比较实际值fi与期望值与期望值fi*之间的偏差来选择问题的之间的偏差来选择问题的解,其数学表达式如下:解,其数学表达式如下:或写成矩阵形式:式中
11、,式中,是与第是与第i个目标函数相关的个目标函数相关的权重权重;A是由是由(i=1,2,k)组成的组成的mm对角矩阵。对角矩阵。理论依据理论依据 :若规划问题的:若规划问题的某一目标某一目标可以给出一个可供选择的范围,则该目标可以给出一个可供选择的范围,则该目标就可以就可以作为约束条件作为约束条件而被排除出目标组,进入约束条件组中。而被排除出目标组,进入约束条件组中。假如,除第一个目标外,其余目标都可以提出一个可供选择的范围,则该多假如,除第一个目标外,其余目标都可以提出一个可供选择的范围,则该多目标规划问题就可以转化为单目标规划问题:目标规划问题就可以转化为单目标规划问题:方法三方法三 约束
12、模型约束模型(极大极小法极大极小法)方法四方法四 目标达到法目标达到法 首先将多目标规划模型化为如下标准形式:首先将多目标规划模型化为如下标准形式:在求解之前,先设计与目标函数相应的一组目标值理想化的期望目标在求解之前,先设计与目标函数相应的一组目标值理想化的期望目标fi*(i=1,2,k),每一个目标对应的权重系数为每一个目标对应的权重系数为 i*(i=1,2,k),再设再设 为一松弛因子。为一松弛因子。那么,多目标规划问题就转化为:那么,多目标规划问题就转化为:17方法五方法五 目标规划模型(目标规划法)目标规划模型(目标规划法)需要预先确定各个目标的期望值需要预先确定各个目标的期望值fi
13、*,同时给每一个目标赋予一个,同时给每一个目标赋予一个优先优先因子因子和和权系数权系数,假定有,假定有K个目标,个目标,L个优先级个优先级(LK),目标规划模型的数学形,目标规划模型的数学形式为:式为:18式中:式中:di+和和di分别表示与分别表示与fi相应的、与相应的、与fi*相比的目标超过值和不足值,相比的目标超过值和不足值,即正、负偏差变量;即正、负偏差变量;pl表示第表示第l个优先级;个优先级;lk+、lk-表示在同一优先级表示在同一优先级pl 中,不同目标的正、负偏差变量的权中,不同目标的正、负偏差变量的权系数。系数。三三 目标规划方法目标规划方法通过前面的介绍和讨论,我们知道,目
14、标规划方法通过前面的介绍和讨论,我们知道,目标规划方法是解决多目标规划问题的重要技术之一。是解决多目标规划问题的重要技术之一。这一方法是美国学者查恩斯(这一方法是美国学者查恩斯(A.Charnes)和库伯(和库伯(W.W.Cooper)于)于1961年在线性规划的基础上年在线性规划的基础上提出来的。后来,查斯基莱恩(提出来的。后来,查斯基莱恩(U.Jaashelainen)和李)和李(Sang.Lee)等人,进一步给出了求解目标规划问题的)等人,进一步给出了求解目标规划问题的一般性方法一般性方法单纯形方法。单纯形方法。目标规划模型目标规划模型目标规划的图解法目标规划的图解法求解目标规划的单纯形
15、方法求解目标规划的单纯形方法 目标规划模型目标规划模型给定若干目标以及实现这些目标的优先顺给定若干目标以及实现这些目标的优先顺序,在有限的资源条件下,使总的偏离目序,在有限的资源条件下,使总的偏离目标值的偏差最小。标值的偏差最小。1.1.基本思想基本思想:2.2.目标规划的有关概念目标规划的有关概念例例1 1:某某一一个个企企业业利利用用某某种种原原材材料料和和现现有有设设备备可可生生产产甲甲、乙乙两两种种产产品品,其其中中,甲甲、乙乙两两种种产产品品的的单单价价分分别别为为8 8万万元元和和1010万万元元;生生产产单单位位甲甲、乙乙两两种种产产品品需需要要消消耗耗的的原原材材料料分分别别为
16、为2 2个个单单位位和和1 1个个单单位位,需需要要占占用用的的设设备备分分别别为为1 1单单位位台台时时和和2 2单单位位台台时时;原原材材料料拥拥有有量量为为1111个个单单位位;可可利利用用的的设设备备总总台台时时为为1010单单位位台时。试问:如何确定其生产方案使得企业获利最大?台时。试问:如何确定其生产方案使得企业获利最大?由于决策者所追求的唯一目标是使总产值达到最大,这个企业的生产由于决策者所追求的唯一目标是使总产值达到最大,这个企业的生产方案可以由如下线性规划模型给出:求方案可以由如下线性规划模型给出:求x1,x2,使,使将上述问题化为标准后,用单纯形方法求解可得最佳决策方案为将
17、上述问题化为标准后,用单纯形方法求解可得最佳决策方案为:(万元)。(万元)。甲甲乙乙拥有量有量原材料原材料2111设备(台台时)1210单件利件利润810生产甲、乙两种产品,有关数据如表所示。试求获利最大的生产方案?但是,在实际决策时,企业领导者必须考虑市场等一系列其它条件,如:但是,在实际决策时,企业领导者必须考虑市场等一系列其它条件,如:超过计划供应的超过计划供应的原材料原材料,需用高价采购,这就会使生产,需用高价采购,这就会使生产 成本增加。成本增加。应尽可能地应尽可能地充分利用设备的有效台时充分利用设备的有效台时,但,但不希望加班不希望加班。应尽可能应尽可能达到并超过计划产值指标达到并
18、超过计划产值指标5656万元万元。这样,该企业生产方案的确定,便成为一个多目标决策问题,这一问题可这样,该企业生产方案的确定,便成为一个多目标决策问题,这一问题可以运用目标规划方法进行求解。以运用目标规划方法进行求解。根据市场信息,甲种产品的需求量有下降的趋势,因根据市场信息,甲种产品的需求量有下降的趋势,因 此此甲种产品的产量不应大于乙种产品的产量甲种产品的产量不应大于乙种产品的产量。23假假定定有有L个个目目标标,K个个优优先先级级(KL),n个个变变量量。在在同同一一优优先先级级pk中中不不同同目目标标的的正正、负负偏偏差差变变量量的的权权系系数数分分别别为为 kl+、kl-,则多目标规
19、划问题可以表示为:,则多目标规划问题可以表示为:n目标规划模型的一般形式目标规划模型的一般形式目标函数目标约束绝对约束非负约束24在以上各式中,在以上各式中,kl+、kl-、分别为赋予、分别为赋予pl优先因子的第优先因子的第k个目标的正、负偏差变量的权系数,个目标的正、负偏差变量的权系数,gk为第为第k个目标的预期值,个目标的预期值,xj为决策变量,为决策变量,dk+、dk-、分别为第、分别为第k 个目标的正、负偏差变量,个目标的正、负偏差变量,目标函数目标函数目标约束目标约束绝对约束绝对约束非负约束非负约束目标规划数学模型中的有关概念。目标规划数学模型中的有关概念。(1)偏差变量偏差变量在在
20、目目标标规规划划模模型型中中,除除了了决决策策变变量量外外,还还需需要要引引入入正正、负负偏偏差差变变量量d+、d-。其其中中,正正偏偏差差变变量量表表示示决决策策值值超超过过目目标标值值的的部部分分,负负偏偏差差变变量量表表示示决决策策值值未未达达到到目标值的部分。目标值的部分。因为决策值不可能既超过目标值同时又未达到目标值,故有因为决策值不可能既超过目标值同时又未达到目标值,故有d+d-=0成立。成立。(2)绝对约束和目标约束绝对约束和目标约束 绝对约束绝对约束,必须严格满足的等式约束和不等式约束,譬如,线性规划问必须严格满足的等式约束和不等式约束,譬如,线性规划问题的所有约束条件都是绝对
21、约束,不能满足这些约束条件的解称为非可行解,题的所有约束条件都是绝对约束,不能满足这些约束条件的解称为非可行解,所以它们是所以它们是硬约束硬约束。目标约束目标约束,目标规划所特有的,可以将约束方程右端项看目标规划所特有的,可以将约束方程右端项看作是追求的目标值,在达到此目标值时允许发生正的或负作是追求的目标值,在达到此目标值时允许发生正的或负的偏差的偏差 ,可加入正负偏差变量,是,可加入正负偏差变量,是软约束软约束。线性规划问题的目标函数,在给定目标值和加入正、线性规划问题的目标函数,在给定目标值和加入正、负偏差变量后可以转化为目标约束,也可以根据问题的需负偏差变量后可以转化为目标约束,也可以
22、根据问题的需要将绝对约束转化为目标约束。要将绝对约束转化为目标约束。(3)优先因子(优先等级)与权系数优先因子(优先等级)与权系数一个规划问题一个规划问题,常常有若干个目标,决策者对各个目标的考虑常常有若干个目标,决策者对各个目标的考虑,往往是有主次往往是有主次的。凡要求第一位达到的目标赋予优先因子的。凡要求第一位达到的目标赋予优先因子p1,次位的目标赋予优先因子,次位的目标赋予优先因子p2,并规定,并规定plpl+1(l=1,2,.)表示表示pl比比pl+1有更大的优先权。有更大的优先权。即即:首先保证首先保证p1级目标的实现,这时可以不考虑次级目标;而级目标的实现,这时可以不考虑次级目标;
23、而p2级目标是在实现级目标是在实现p1级目标的基础上考虑的;依此类推。级目标的基础上考虑的;依此类推。若要区别具有相同优先因子若要区别具有相同优先因子 pl的目标的差别,就可以分的目标的差别,就可以分别赋予它们不同的权系数别赋予它们不同的权系数 i*(i=1,2,k)。这些优先因子和权。这些优先因子和权系数都由决策者按照具体情况而定。系数都由决策者按照具体情况而定。(3)优先因子(优先等级)与权系数优先因子(优先等级)与权系数一个规划问题一个规划问题,常常有若干个目标,决策者对各个目标的考虑常常有若干个目标,决策者对各个目标的考虑,往往是有主次往往是有主次的。凡要求第一位达到的目标赋予优先因子
24、的。凡要求第一位达到的目标赋予优先因子p1,次位的目标赋予优先因子,次位的目标赋予优先因子p2,并规定,并规定plpl+1(l=1,2,.)表示表示pl比比pl+1有更大的优先权。有更大的优先权。即即:首先保证首先保证p1级目标的实现,这时可以不考虑次级目标;而级目标的实现,这时可以不考虑次级目标;而p2级目标是在实现级目标是在实现p1级目标的基础上考虑的;依此类推。级目标的基础上考虑的;依此类推。(4)(4)目标函数目标函数 目标规划的目标函数(准则函数)是目标规划的目标函数(准则函数)是按照各目标约束的正、负偏差变量和按照各目标约束的正、负偏差变量和赋予相应的优先因子而构造赋予相应的优先因
25、子而构造的。当每一目标确定后,尽可能缩小与目标值的偏的。当每一目标确定后,尽可能缩小与目标值的偏离。因此,目标规划的目标函数只能是:离。因此,目标规划的目标函数只能是:a)a)要求要求恰好达到目标值恰好达到目标值,就是正、负偏差变量都要尽可能小,就是正、负偏差变量都要尽可能小,即即 b)b)要要求求不不超超过过目目标标值值,即即允允许许达达不不到到目目标标值值,就就是是正正偏偏差差变变量量要要尽尽可可能能小,即小,即 c)c)要求要求超过目标值超过目标值,也就是超过量不限,但负偏差变量要尽可能小,即,也就是超过量不限,但负偏差变量要尽可能小,即 基本形式有三种:基本形式有三种:29例例2:在在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多目标 优化 方法 实例 解析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。