多目标规划方法培训课程

《多目标规划方法培训课程》由会员分享，可在线阅读，更多相关《多目标规划方法培训课程（93页珍藏版）》请在金锄头文库上搜索。

1、第六章 多目标规划方法 multiple objective programming,甘肃农业大学 资源与环境学院,甘肃农业大学资源与环境学院,,同时考虑多个决策目标时，称为多目标规划问题。,甘肃农业大学资源与环境学院,,本章主要内容,多目标规划及其非劣解 多目标规划求解技术简介 多目标规划方法 多目标规划应用实例,甘肃农业大学资源与环境学院,,在地理学研究中，对于许多规划问题，常常需要考虑多个目标，如经济效益目标、生态效益目标、社会效益目标等等。为了满足这类问题研究之需要，本章拟结合有关实例，对多目标规划方法及其在地理学研究中的应用问题作一些简单地介绍。,甘肃农业大学资源与环境学院,,多目标

2、最优化的思想萌芽于1776年经济学中的效用理论。1896年，法国经济学家VPareto首先在经济理论的研究中提出了多目标最优化问题。1951年，美国数理经济学家TCKoopans从生产和分配的活动分析中考虑了多目标决策问题，并首次提出了多目标最优化问题解的概念，将其命名为“Pareto解”(即有效解)。同年，HWKuhn和AWTucker从数学规划论角度首次提出向量极值问题及有关概念。进入20世纪70年代，随着第一次国际多目标决策研讨会的召开及这方面专著的问世，多目标决策问题的研究工作迅速、蓬勃地开展起来，到目前为止，已取得若干有价值的研究成果。,甘肃农业大学资源与环境学院,,多目标规划及其非

3、劣解 多目标规划的非劣解,第1节 多目标规划及其非劣解,甘肃农业大学资源与环境学院,,多目标规划及其非劣解,例1：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别 为4元/斤及2元/斤。今要筹办一桩喜事。“筹备小组”计划总花费不超过40元，糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定最佳的采购方案。 我们先确定此问题应满足的条件（即约束条件）。不难看出，当甲级糖数量为x1，乙级糖数量为x2时，有：,甘肃农业大学资源与环境学院,,多目标规划及其非劣解,在研究以什么为“最佳”的衡量标准时，“筹备小组”的成员们意见可能会发生分歧，其原因是他们会提出各种各样的目标来。 如果要求总花费最小，即要求

4、： f1(x1,x2)=4x1+2x2 min 如果要求糖的总数量最大，即要求： 如果要求甲级糖的数量最大，即要求： 易见，这是具有3个目标的规划问题（由于约束及目标均为线性函数，故它为多目标线性规划问题）。,甘肃农业大学资源与环境学院,,多目标规划及其非劣解,例2：【木梁设计问题】把横截面为圆形的树干加工成矩形横截面的木梁。为使木梁满足一定的规格和应力及强度条件，要求木梁的高度不超过H，横截面的惯性矩不少于给定值W，且横截面的高度要介于其宽度和4倍宽度之间。 问应如何确定木梁尺寸，可使木 梁的重量最轻，并且成本最低。 设所设计的木梁横截面的 高为x1 ，宽为x2。 为使具有一定长度的木梁重量

5、最轻，应要求其横截面面积x1x2为最小，即要求x1x2min,甘肃农业大学资源与环境学院,,多目标规划及其非劣解,由于矩形横截面的木梁是由横截面为圆形的树干加工而成，故其成本与树干横截面面积的大小 成正比。由此，为使木梁的成本最低还应要求 尽可能的小，或即： 根据问题的要求，应满足下述约束条件： 这是具有两个目标的非线性规划问题。,甘肃农业大学资源与环境学院,,多目标规划及其非劣解,例3：【投资决策问题】某投资开发公司拥有总资金A万元，今有n(2)个项目可供选择。设投资第i(i=1，2，n)个项目要用资金ai万元，预计可得到收益bi万元。问应如何使用总资金A万元，才能得到最佳的经济效益？,xi

6、=0或1,甘肃农业大学资源与环境学院,,多目标规划及其非劣解,所谓“最佳的经济效益”，如果理解为“少花钱多办事”，则变为两个目标的问题，即投资最少，收益最大： 这是具有两个目标的01规划问题。,甘肃农业大学资源与环境学院,,由以上实例可见，多目标最优化模型与单目标最优化模型的区别主要是目标多于一个。在这些目标中，有的是追求极大化，有的是追求极小化，而极大化与极小化是可以相互转化的。因此，我们不难将多目标最优化模型统一成一般形式： 决策变量：x1，xn 目标函数：minf1(x1，xn) minfp(x1，xn),甘肃农业大学资源与环境学院,,任何多目标规划问题，都由两个基本部分组成： (1)两

7、个以上的目标函数； (2)若干个约束条件。,对于多目标规划问题，可以将其数学模型一般地描写为如下形式,甘肃农业大学资源与环境学院,,（6.1.2）,（6.1.1）,式中： ，为决策变量向量。,甘肃农业大学资源与环境学院,,如果将（6.1.1）和（6.1.2）式进一步缩写， 即 （6.1.3） （6.1.4） 式中： 是k维函数向量； k是目标函数的个数； 等是m维函数向量； 是m维常数向量； m是约束方程的个数。,甘肃农业大学资源与环境学院,,对于线性多目标规划问题，（6.1.3）和（6.1.4）式可以进一步用矩阵表示 （6.1.5） （6.1.6） 式中： 为n维决策变量向量； 为kn矩阵，

8、即目标函数系数矩阵； 为mn矩阵，即约束方程系数矩阵； 为m维的向量，约束向量。,甘肃农业大学资源与环境学院,,二、多目标规划的非劣解,对于上述多目标规划问题，求解就意味着需要做出如下的复合选择： 每一个目标函数取什么值，原问题可以得到最满意的解决？ 每一个决策变量取什么值，原问题可以得到最满意的解决 ？ 多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其他目标。,甘肃农业大学资源与环境学院,,在图6.1.1中，就方案和来说，的 目标值比大，但其目标值 比小，因此无法确定这两个方案的优与劣。在各个方案之间，显然：比好，比好，比好，比好。而对于方案、之间则无法确定优劣，而且又

9、没有比它们更好的其他方案，所以它们就被称之为多目标规划问题的非劣解或有效解，其余方案都称为劣解。所有非劣解构成的集合称为非劣解集。,多目标规划的劣解与 非劣解,甘肃农业大学资源与环境学院,,当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解）。,甘肃农业大学资源与环境学院,,第2节 多目标规划求解技术,效用最优化模型 罚款模型 约束模型 目标达到法 目标规划模型,甘肃农业大学资源与环境学院,,是与各目标函数相关的效用函数的和函数。,方法一 效用最优化模型（线性加权法）,（1）,（2）,思想：规划问题的各个目标函数可以通

10、过一定的方式进行求和运算。这种方法将一系列的目标函数与效用函数建立相关关系，各目标之间通过效用函数协调，使多目标规划问题转化为传统的单目标规划问题：,甘肃农业大学资源与环境学院,,在用效用函数作为规划目标时，需要确定一组权值 i 来反映原问题中各目标函数在总体目标中的权重，即：,式中， i 应满足：,向量形式：,甘肃农业大学资源与环境学院,,方法二 罚款模型（理想点法）,思想: 规划决策者对每一个目标函数都能提出所期望的值（或称满意值）； 通过比较实际值 fi 与期望值 fi* 之间的偏差来选择问题的解，其数学表达式如下：,或写成矩阵形式：,式中， 是与第i个目标函数相关的权重； A是由 (i

11、=1,2,k )组成的mm对角矩阵。,甘肃农业大学资源与环境学院,,理论依据 ：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中。 假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：,方法三 约束模型（极大极小法）,甘肃农业大学资源与环境学院,,方法四 目标达到法,首先将多目标规划模型化为如下标准形式：,甘肃农业大学资源与环境学院,,在求解之前，先设计与目标函数相应的一组目标值理想化的期望目标 fi* ( i=1,2,k ) , 每一个目标对应的权重系数为 i* ( i=1,2,

12、k ) ， 再设 为一松弛因子。 那么，多目标规划问题就转化为：,甘肃农业大学资源与环境学院,,方法五 目标规划模型（目标规划法）,需要预先确定各个目标的期望值 fi* ，同时给每一个目标赋予一个优先因子和权系数，假定有K个目标，L个优先级( LK)，目标规划模型的数学形式为：,甘肃农业大学资源与环境学院,,式中： di+ 和 di分别表示与 fi 相应的、与fi* 相比的目标超过值和不足值，即正、负偏差变量； pl表示第l个优先级； lk+、lk-表示在同一优先级 pl 中，不同目标的正、负偏差变量的权系数。,甘肃农业大学资源与环境学院,,用目标达到法求解多目标规划的计算过程，可以通过调用M

13、atlab软件系统优化工具箱中的fgoalattain函数实现。,甘肃农业大学资源与环境学院,,第3节 目标规划方法,目标规划模型 求解目标规划的单纯形方法,甘肃农业大学资源与环境学院,,通过上节的介绍和讨论，我们知道，目标规划方法是解决多目标规划问题的重要技术之一。 这一方法是美国学者查恩斯（A.Charnes）和库伯（W.W.Cooper）于1961年在线性规划的基础上提出来的。后来，查斯基莱恩（U.Jaashelainen）和李（S.Lee）等人，进一步给出了求解目标规划问题的一般性方法单纯形方法。,甘肃农业大学资源与环境学院,,一、目标规划模型,给定若干目标以及实现这些目标的优先顺序，

14、在有限的资源条件下，使总的偏离目标值的偏差最小。,（一）基本思想,甘肃农业大学资源与环境学院,,例1：某一个企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价分别为8元和10元；生产单位甲、乙两种产品需要消耗的原材料分别为2个单位和1个单位，需要占用的设备分别为1台时和2台时；原材料拥有量为11个单位；可利用的设备总台时为10台时。试问：如何确定其生产方案？,（二）目标规划的有关概念,甘肃农业大学资源与环境学院,,如果决策者所追求的唯一目标是使总产值达到最大，则这个企业的生产方案可以由如下线性规划模型给出：求 ， ，使,（6.3.1）,而且满足,式中： 和 为决策变量，z为目标函数值。将上述问题化为标准后，用单纯形方法求解可得最佳决策方案为 （万元）。,甘肃农业大学资源与环境学院,,但是，在实际决策时，企业领导者必须考虑市场等一系列其他条件，如：,根据市场信息，甲种产品的需求量有下降的趋势，因此甲种产品的产量不应大于乙种产品的产量。 超过计划供应的原材料，需用高价