第六章多目标规划方法

第六章多目标规划方法multipleobjectiveprogramming甘肃农业大学资源与环境学院甘肃农业大学资源与环境学院同时考虑多个决策目标时，称为多目标规划问题。甘肃农业大学资源与环境学院本章主要内容多目标规划及其非劣解多目标规划求解技术简介多目标规划方法多目标规划应用实例甘肃农业大学资源与环境学院在地理学研究中，对于许多规划问题，常常需要考虑多个目标，如经济效益目标、生态效益目标、社会效益目标等等。为了满足这类问题研究之需要，本章拟结合有关实例，对多目标规划方法及其在地理学研究中的应用问题作一些简单地介绍。甘肃农业大学资源与环境学院年经济学中的效用理论。1896年，法国经济学家V·Pareto首先在经济理论的研究中提出了多目标最优化问题。1951年，美国数理经济学家T·C·Koopans从生产和分配的活动分析中考虑了多目标决策问题，并首次提出了多目标最优化问题解的概念，将其命名为“Pareto解”(即有效解)。同年，H·W·Kuhn和A·W·Tucker从数学规划论角度首次提出向量极值问题及有关概念。进入20世纪70年代，随着第一次国际多目标决策研讨会的召开及这方面专著的问世，多目标决策问题的研究工作迅速、蓬勃地开展起来，到目前为止，已取得若干有价值的研究成果。甘肃农业大学资源与环境学院多目标规划及其非劣解多目标规划的非劣解第1节多目标规划及其非劣解甘肃农业大学资源与环境学院：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别为4元/斤及2元/斤。今要筹办一桩喜事。“筹备小组”计划总花费不超过40元，糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定最佳的采购方案。我们先确定此问题应满足的条件（即约束条件）。不难看出，当甲级糖数量为x1，乙级糖数量为x2时，有：121211242401050,0xxxxxxx甘肃农业大学资源与环境学院多目标规划及其非劣解在研究以什么为“最佳”的衡量标准时，“筹备小组”的成员们意见可能会发生分歧，其原因是他们会提出各种各样的目标来。如果要求总花费最小，即要求：f1(x1,x2)=4x1+2x2→min如果要求糖的总数量最大，即要求：如果要求甲级糖的数量最大，即要求：易见，这是具有3个目标的规划问题（由于约束及目标均为线性函数，故它为多目标线性规划问题）。21212(,)maxfxxxx3121(,)maxfxxx甘肃农业大学资源与环境学院：【木梁设计问题】把横截面为圆形的树干加工成矩形横截面的木梁。为使木梁满足一定的规格和应力及强度条件，要求木梁的高度不超过H，横截面的惯性矩不少于给定值W，且横截面的高度要介于其宽度和4倍宽度之间。问应如何确定木梁尺寸，可使木梁的重量最轻，并且成本最低。设所设计的木梁横截面的高为x1，宽为x2。为使具有一定长度的木梁重量最轻，应要求其横截面面积x1x2为最小，即要求x1x2→minx1x2r甘肃农业大学资源与环境学院多目标规划及其非劣解由于矩形横截面的木梁是由横截面为圆形的树干加工而成，故其成本与树干横截面面积的大小成正比。由此，为使木梁的成本最低还应要求尽可能的小，或即：根据问题的要求，应满足下述约束条件：这是具有两个目标的非线性规划问题。22212(/2)(/2)rxx2212()/4xx2212()minxx1121221120400,0xHxxWxxxxxx甘肃农业大学资源与环境学院：【投资决策问题】某投资开发公司拥有总资金A万元，今有n(≥2)个项目可供选择。设投资第i(i=1，2，……，n)个项目要用资金ai万元，预计可得到收益bi万元。问应如何使用总资金A万元，才能得到最佳的经济效益？niii=1ii1ii=12n0iaxAx(x1)0i=12nix决定投资第个项目设，，……，决定不投资第个项目问题的约束条件为，，……，xi=0或1甘肃农业大学资源与环境学院多目标规划及其非劣解所谓“最佳的经济效益”，如果理解为“少花钱多办事”，则变为两个目标的问题，即投资最少，收益最大：这是具有两个目标的0－1规划问题。111211()max()minnniiinniiifxxbxfxxax，……，，……，甘肃农业大学资源与环境学院由以上实例可见，多目标最优化模型与单目标最优化模型的区别主要是目标多于一个。在这些目标中，有的是追求极大化，有的是追求极小化，而极大化与极小化是可以相互转化的。因此，我们不难将多目标最优化模型统一成一般形式：决策变量：x1，……，xn目标函数：minf1(x1，……，xn)………………minfp(x1，……，xn)111()0()0nmngxxgxx，……，约束条件：………………，……，甘肃农业大学资源与环境学院任何多目标规划问题，都由两个基本部分组成：(1)两个以上的目标函数；(2)若干个约束条件。对于多目标规划问题，可以将其数学模型一般地描写为如下形式甘肃农业大学资源与环境学院（6.1.2）)(max(min))(max(min))(max(min))(21XfXfXfXFZkmmgggGXXXX2121)()()()(（6.1.1）式中：，为决策变量向量。TnxxxX],,,[21甘肃农业大学资源与环境学院如果将（6.1.1）和（6.1.2）式进一步缩写，即（6.1.3）（6.1.4）式中：是k维函数向量；k是目标函数的个数；等是m维函数向量；是m维常数向量；m是约束方程的个数。)(max(min)XFZGX)()(XFZ)(XΦG甘肃农业大学资源与环境学院对于线性多目标规划问题，（6.1.3）和（6.1.4）式可以进一步用矩阵表示（6.1.5）（6.1.6）式中：为n维决策变量向量；为k×n矩阵，即目标函数系数矩阵；为m×n矩阵，即约束方程系数矩阵；为m维的向量，约束向量。AXZmax(min)bBXXABb甘肃农业大学资源与环境学院二、多目标规划的非劣解对于上述多目标规划问题，求解就意味着需要做出如下的复合选择：每一个目标函数取什么值，原问题可以得到最满意的解决？每一个决策变量取什么值，原问题可以得到最满意的解决？多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其他目标。甘肃农业大学资源与环境学院中，就方案①和②来说，①的目标值比②大，但其目标值比②小，因此无法确定这两个方案的优与劣。在各个方案之间，显然：③比②好，④比①好，⑦比③好，⑤比④好。而对于方案⑤、⑥、⑦之间则无法确定优劣，而且又没有比它们更好的其他方案，所以它们就被称之为多目标规划问题的非劣解或有效解，其余方案都称为劣解。所有非劣解构成的集合称为非劣解集。2f1f多目标规划的劣解与非劣解甘肃农业大学资源与环境学院当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解）。甘肃农业大学资源与环境学院节多目标规划求解技术效用最优化模型罚款模型约束模型目标达到法目标规划模型甘肃农业大学资源与环境学院)(maxXZGXts)(..是与各目标函数相关的效用函数的和函数。方法一效用最优化模型（线性加权法）（1）（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)组成的m×m对角矩阵。i甘肃农业大学资源与环境学院理论依据：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中。假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：方法三约束模型（极大极小法）),,,(max(min)211nxxxfZ),,2,1(),,,(21migxxxini),,3,2(maxminkjfffjjj甘肃农业大学资源与环境学院方法四目标达到法首先将多目标规划模型化为如下标准形式：)()()(min)(min21XfXfXfxFk000)()()()(21XXXXm甘肃农业大学资源与环境学院在求解之前，先设计与目标函数相应的一组目标值理想化的期望目标fi*(i=1,2,…,k),每一个目标对应的权重系数为i*(i=1,2,…,k)，再设为一松弛因子。那么，多目标规划问题就转化为：,minX),,2,1(,)(*kifXfiii),,2,1(0)(miXi)()()(min)(min21XfXfXfxFk000)()()()(21XXXXm甘肃农业大学资源与环境学院方法五目标规划模型（目标规划法）需要预先确定各个目标的期望值fi*，同时给每一个目标赋予一个优先因子和权系数，假定有K个目标，L个优先级(L≤K)，目标规划模型的数学形式为：LlKkklkklklddpZ11)(min),,,(),,,(migxxxini2121),,,(Kifddfiiii21甘肃农业大学资源与环境学院LlKkklkklklddpZ11)(min),,2,1(),,,(21migxxxini),,2,1(Kifddfiiii式中：di+和di－分别表示与fi相应的、与fi*相比的目标超过值和不足值，即正、负偏差变量；pl表示第l个优先级；lk+、lk-表示在同