多目标规划课件

主讲人主讲人:穆学文穆学文西安电子科技大学数学系西安电子科技大学数学系数学建模讲义数学建模讲义多目标规划最优化模型最优化模型 -多目标规划多目标规划多目标规划第七讲第七讲 多目标规划多目标规划方法方法 l多目标规划解的讨论多目标规划解的讨论非劣解非劣解l多目标规划及其求解技术简介多目标规划及其求解技术简介效用最优化模型效用最优化模型 罚款模型罚款模型约束模型约束模型 目标规划模型目标规划模型目标达到法目标达到法l多目标规划应用实例多目标规划应用实例多目标规划多目标规划是数学规划的一个分支。多目标规划是数学规划的一个分支。研究研究多于一个的目标函数多于一个的目标函数在在给定区域给定区域上的最优化。又称多上的最优化。又称多目标最优化。通常记为目标最优化。通常记为MOP(multi-objectiveprogramming)。在很多实际问题中，例如经济、管理、军事、科学和工程在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方面的研究。调，甚至是矛盾的。因此有许多学者致力于这方面的研究。1896年法国年法国经济学家经济学家V.帕雷托最早研究帕雷托最早研究不可比较目标的优不可比较目标的优化问题，之后，化问题，之后，J.冯冯诺伊曼、诺伊曼、H.W.库恩、库恩、A.W.塔克、塔克、A.M.日夫里翁等日夫里翁等数学家做了深入的探讨数学家做了深入的探讨，但是，但是尚未有一个完全尚未有一个完全令人满意的定义令人满意的定义。多目标规划求解多目标规划的方法大体上有以下几种：求解多目标规划的方法大体上有以下几种：一种是一种是化多为少的方法化多为少的方法，即把多目标化为比较容易求解的即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法单目标或双目标，如主要目标法、线性加权法、理想点法等；等；另一种叫另一种叫分层序列法分层序列法，即把目标按其重要性给出一个序列，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。求出共同的最优解。对多目标的线性规划除以上方法外还可以适当对多目标的线性规划除以上方法外还可以适当修正单纯形修正单纯形法法来求解；还有一种称为来求解；还有一种称为层次分析法层次分析法，是由美国运筹学家，是由美国运筹学家沙旦于沙旦于70年代提出的，这是一种定性与定量相结合的多目年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。的情况更为实用。多目标规划 多目标规划模型多目标规划模型（一）任何多目标规划问题，都由两个基本部分组成：（一）任何多目标规划问题，都由两个基本部分组成：（1 1）两个以上的目标函数；）两个以上的目标函数；（2 2）若干个约束条件。）若干个约束条件。（二）对于多目标规划问题，可以将其数学模型一般地描（二）对于多目标规划问题，可以将其数学模型一般地描写为如下形式：写为如下形式：)(max(min)(max(min)(max(min)(XfXfXfXFZk21 mmgggGXXXX2121)()()()(s.t.式中：为决策变量向量。TnxxxX,21 多目标规划)(max(min)XFZ GXts )(.缩写形式：缩写形式：有有n个决策变量，个决策变量，k个目标函数，个目标函数，m个约束方程，个约束方程，则：则：Z=F(X)是是k维函数向量，维函数向量，(X)是是m维函数向量；维函数向量；G是是m维常数向量；维常数向量；（1）（2）多目标规划 对于线性多目标规划线性多目标规划问题，可以进一步用矩阵表示：CXZ max(min)bAX s.t.式中：式中：X X 为为n n 维决策变量向量；维决策变量向量；C C 为为k kn n 矩阵，即目标函数系数矩阵；矩阵，即目标函数系数矩阵；B B 为为m mn n 矩阵，即约束方程系数矩阵；矩阵，即约束方程系数矩阵；b b 为为m m 维的向量，即约束向量。维的向量，即约束向量。多目标规划多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其它目标。对于上述多目标规划问题，求解就意味着需要做出如下的复合选择：每一个目标函数取什么值，原问题可以得到最满意的解决？每一个决策变量取什么值，原问题可以得到最满意的解决？)(max(min)XFZ GX )(s.t.多目标规划 在图在图1中，中，max(f1,f2).就就方案方案和和来说，来说，的的f2目标值比目标值比大，但其目大，但其目标值标值f1比比小，因此无小，因此无法确定这两个方案的优法确定这两个方案的优与劣。与劣。在各个方案之间，在各个方案之间，显然：显然：比比好，好，比比好好,比比好好,比比好好。非劣解非劣解可以用图1说明。图图1 多目标规划的劣解与非劣解多目标规划的劣解与非劣解多目标规划 而对于方案而对于方案、之间则无法确之间则无法确定优劣，而且又没有定优劣，而且又没有比它们更好的其他方比它们更好的其他方案，所以它们就被称案，所以它们就被称为多目标规划问题的为多目标规划问题的非劣解非劣解或或有效解有效解，其余方案都称为其余方案都称为劣解劣解。所有非劣解构成的集所有非劣解构成的集合称为合称为非劣解集非劣解集。当目标函数处于冲突状态时，就不会存在使所有目当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解（又称寻求非劣解（又称非支配解或帕累托解非支配解或帕累托解）。）。多目标规划 效用最优化模型效用最优化模型 罚款模型罚款模型 约束模型约束模型 目标达到法目标达到法 目标规划模型目标规划模型 为了求得多目标规划问题的非劣解，常常需要将为了求得多目标规划问题的非劣解，常常需要将多目标规划问题转化为单目标规划问题多目标规划问题转化为单目标规划问题去处理。实现去处理。实现这种转化，有如下几种建模方法。这种转化，有如下几种建模方法。多目标规划)(maxXZ GXts )(.是与各目标函数相关的是与各目标函数相关的效用函数的效用函数的和函数和函数。方法一方法一效用最优化模型效用最优化模型（线性加权法线性加权法）（1 1）（2 2）思想思想：规划问题的各个目标函数可以通过：规划问题的各个目标函数可以通过一定一定的的方式方式进行进行求和求和运算。这种方法将一系列的运算。这种方法将一系列的目标函数目标函数与与效用效用函数函数建立相关关系，各目标之间通过效用函数协调，建立相关关系，各目标之间通过效用函数协调，使多目标规划问题转化为传统的单目标规划问题：使多目标规划问题转化为传统的单目标规划问题：多目标规划在在用效用函数作为规划目标用效用函数作为规划目标时，需要确定一组时，需要确定一组权值权值 i 来反映原问题中各目标函数在总体目标中的权重，即来反映原问题中各目标函数在总体目标中的权重，即：kiii1max ),2,1(),(21migxxxini kii11 T maxGXts )(.式中，i 应满足：向量形式：多目标规划思想思想:规划决策者对每一个目标函数都能提出所规划决策者对每一个目标函数都能提出所期望的值期望的值（或称（或称满意值满意值）；）；通过比较实际值通过比较实际值fi与期望值与期望值fi*之间的偏差来选择问题的之间的偏差来选择问题的解，其数学表达式如下：解，其数学表达式如下：i 21)(min kiiiiffZ),2,1(),(21migxxxini 或写成矩阵形式：)()(min FFAFFZTGX )(式中，式中，是与第是与第i个目标函数相关的个目标函数相关的权重权重；A是由是由(i=1,2,k)组成的组成的mm对角矩阵。对角矩阵。i 多目标规划理论依据理论依据 ：若规划问题的：若规划问题的某一目标某一目标可以给出一个可供选可以给出一个可供选择的范围，则该目标就可以择的范围，则该目标就可以作为约束条件作为约束条件而被排除出目标而被排除出目标组，进入约束条件组中。组，进入约束条件组中。假如，除第一个目标外，其余目标都可以提出一个可供选假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划择的范围，则该多目标规划问题就可以转化为单目标规划问题：问题：方法三方法三 约束模型约束模型（极大极小法极大极小法）),(max(min)211nxxxfZ),2,1(),(21migxxxini ),3,2(maxminkjfffjjj 多目标规划方法四方法四 目标达到法目标达到法 首先将多目标规划模型化为如下标准形式：首先将多目标规划模型化为如下标准形式：)()()(min)(min21XfXfXfxFk 000)()()()(21XXXXm 多目标规划在求解之前，先设计与目标函数相应的一组目标值理想在求解之前，先设计与目标函数相应的一组目标值理想化的期望目标化的期望目标fi*(i=1,2,k),每一个目标对应的权重系数为每一个目标对应的权重系数为 i*(i=1,2,k)，再设再设 为一松弛因子。为一松弛因子。那么，多目标规划问题就转化为：那么，多目标规划问题就转化为：,minX),2,1(,)(*kifXfiii ),2,1(0)(miXi )()()(min)(min21XfXfXfxFk 000)()()()(21XXXXm 多目标规划方法五方法五 目标规划模型（目标规划法）目标规划模型（目标规划法）需要预先确定各个目标的期望值需要预先确定各个目标的期望值fi*，同时给每一个，同时给每一个目标赋予一个目标赋予一个优先因子优先因子和和权系数权系数，假定有，假定有K个目标，个目标，L个个优先级优先级(LK)，目标规划模型的数学形式为：，目标规划模型的数学形式为：LlKkklkklklddpZ11)(min ),(),(migxxxini2121 ),(Kifddfiiii21 多目标规划 LlKkklkklklddpZ11)(min ),2,1(),(21migxxxini ),2,1(Kifddfiiii 式中：式中：di+和和di分别表示与分别表示与fi相应的、与相应的、与fi*相比的目标相比的目标超过值和不足值，即正、负偏差变量；超过值和不足值，即正、负偏差变量；pl表示第表示第l个优先级；个优先级；lk+、lk-表示在同一优先级表示在同一优先级pl 中，不同目标的正、中，不同目标的正、负偏差变量的权系数。负偏差变量的权系数。多目标规划投资的收益和风险投资的收益和风险多目标规划二、基本假设和符号规定二、基本假设和符号规定多目标规划二、基本假设和符号规定二、基本假设和符号规定多目标规划三、模型的建立与分析三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即 max qixi|i=1，2,n多目标规划三、模型的建立与分析三、模型的建立与分析多目标规划4.模型简化模型简化：多目标规划四、模型四、模型1 1的求解的求解 由于由于a是任意给定的风险度，到底怎样给定没有一个准是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从则，不同的投资者有不同的风险度。我们从a=0开始，以开始，以步长步长a=0.001进行循环搜索，编制程序如下进行循环搜索，编制程序如下：多目标规划a=0;while(1.1-a)1 c=-0.05-0.27-0.19-0.185-0.185;Aeq=1 1.01 1.02 1.045 1.065;beq=1;A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To Matlab（xxgh5）多目标规划a=0.0030 x=0.4949 0.1200 0.2000 0.0545 0.1154 Q=0.1266a=0.0060 x=0 0.2400 0.4000 0.1091 0.2212 Q=0.2019a=0.0080 x=0.0000 0.3200 0.5333 0.1271 0.0000 Q=0.2112a=0.0100 x=0 0.4000 0.5843 0 0 Q=0.2190a=0.0200 x=0 0.8000 0.1882 0 0 Q=0.2518 a=0.0400 x=0.0000 0.9901 0.0000 0 0 Q=0.2673计算结果：计算结果：多目标规划五、五、结果分析结果分析3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2 2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。多目标规划返 回4 4.在a=0.006=0.006 附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度 收益 x0 x1 x2 x3 x40.00600.201900.24000.40000.10910.2212多目标规划