第六章多目标规划方法ppt课件

1、第六章 多目的规划方法 multiple objective programming甘肃农业大学 资源与环境学院 同时思索多个决策目的时，称为多目的规划问题。本章主要内容多目的规划及其非劣解多目的规划求解技术简介 多目的规划方法多目的规划运用实例 在地理学研讨中，对于许多规划问题，经常需求思索多个目的，如经济效益目的、生态效益目的、社会效益目的等等。为了满足这类问题研讨之需求，本章拟结合有关实例，对多目的规划方法及其在地理学研讨中的运用问题作一些简单地引见。 多目的最优化的思想萌芽于1776年经济学中的成效实际。1896年，法国经济学家VPareto首先在经济实际的研讨中提出了多目的最优化问题

2、。1951年，美国数理经济学家TCKoopans从消费和分配的活动分析中思索了多目的决策问题，并初次提出了多目的最优化问题解的概念，将其命名为“Pareto解(即有效解)。同年，HWKuhn和AWTucker从数学规划论角度初次提出向量极值问题及有关概念。进入20世纪70年代，随着第一次国际多目的决策研讨会的召开及这方面专著的问世，多目的决策问题的研讨任务迅速、蓬勃地开展起来，到目前为止，已获得假设干有价值的研讨成果。多目的规划及其非劣解多目的规划的非劣解第1节 多目的规划及其非劣解 多目的规划及其非劣解例1：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别 为4元/斤及2元/斤。今要筹办一桩喜

3、事。“筹备小组方案总破费不超越40元，糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定最正确的采购方案。 我们先确定此问题应满足的条件即约束条件。不难看出，当甲级糖数量为x1，乙级糖数量为x2时，有：多目的规划及其非劣解 在研讨以什么为“最正确的衡量规范时，“筹备小组的成员们意见能够会发生分歧，其缘由是他们会提出各种各样的目的来。 假设要求总破费最小，即要求： f1(x1,x2)=4x1+2x2 min 假设要求糖的总数量最大，即要求： 假设要求甲级糖的数量最大，即要求： 易见，这是具有3个目的的规划问题由于约束及目的均为线性函数，故它为多目的线性规划问题。多目的规划及其非劣解例2：【木梁

4、设计问题】把横截面为圆形的树干加工成矩形横截面的木梁。为使木梁满足一定的规格和应力及强度条件，要求木梁的高度不超越H，横截面的惯性矩不少于给定值W，且横截面的高度要介于其宽度和4倍宽度之间。 问应如何确定木梁尺寸，可使木 梁的分量最轻，并且本钱最低。 设所设计的木梁横截面的 高为x1 ，宽为x2。 为使具有一定长度的木梁分量最轻，应要求其横截面面积x1x2为最小，即要求x1x2min x1 x2r多目的规划及其非劣解 由于矩形横截面的木梁是由横截面为圆形的树干加工而成，故其本钱与树干横截面面积的大小 成正比。由此，为使木梁的本钱最低还应要求 尽能够的小，或即： 根据问题的要求，应满足下述约束条

5、件： 这是具有两个目的的非线性规划问题。多目的规划及其非劣解例3：【投资决策问题】某投资开发公司拥有总资金A万元，今有n(2)个工程可供选择。设投资第i(i=1，2，n)个工程要用资金ai万元，估计可得到收益bi万元。问应如何运用总资金A万元，才干得到最正确的经济效益？xi=0或1多目的规划及其非劣解 所谓“最正确的经济效益，假设了解为“少花钱多办事，那么变为两个目的的问题，即投资最少，收益最大： 这是具有两个目的的01规划问题。 由以上实例可见，多目的最优化模型与单目的最优化模型的区别主要是目的多于一个。在这些目的中，有的是追求极大化，有的是追求极小化，而极大化与极小化是可以相互转化的。因此

6、，我们不难将多目的最优化模型一致成普通方式： 决策变量：x1，xn 目的函数：minf1(x1，xn) minfp(x1，xn) 任何多目的规划问题，都由两个根本部分组成： (1)两个以上的目的函数； (2)假设干个约束条件。 对于多目的规划问题，可以将其数学模型普通地描写为如下方式 .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.

7、1.6式中： 为n维决策变量向量； 为kn矩阵，即目的函数系数矩阵； 为mn矩阵，即约束方程系数矩阵； 为m维的向量，约束向量。 二、多目的规划的非劣解 对于上述多目的规划问题，求解就意味着需求做出如下的复合选择： 每一个目的函数取什么值，原问题可以得到最称心的处理？ 每一个决策变量取什么值，原问题可以得到最称心的处理 ？ 多目的规划问题的求解不能只追求一个目的的最优化最大或最小，而不顾其他目的。 在图6.1.1中，就方案和来说，的 目的值比大，但其目的值 比小，因此无法确定这两个方案的优与劣。在各个方案之间，显然：比好，比好，比好，比好。而对于方案、之间那么无法确定优劣，而且又没有比它们更好

8、的其他方案，所以它们就被称之为多目的规划问题的非劣解或有效解，其他方案都称为劣解。一切非劣解构成的集合称为非劣解集。多目的规划的劣解与 非劣解 当目的函数处于冲突形状时，就不会存在使一切目的函数同时到达最大或最小值的最优解，于是我们只能寻求非劣解又称非支配解或帕累托解。 第2节 多目的规划求解技术 成效最优化模型罚款模型约束模型目的到达法目的规划模型是与各目的函数相关的成效函数的和函数。 方法一 成效最优化模型线性加权法 1 2 思想：规划问题的各个目的函数可以经过一定的方式进展求和运算。这种方法将一系列的目的函数与成效函数建立相关关系，各目的之间经过成效函数协调，使多目的规划问题转化为传统的

9、单目的规划问题： 在用成效函数作为规划目的时，需求确定一组权值 i 来反映原问题中各目的函数在总体目的中的权重，即：式中， i 应满足：向量方式：方法二 罚款模型理想点法 思想: 规划决策者对每一个目的函数都能提出所期望的值或称称心值；经过比较实践值 fi 与期望值 fi* 之间的偏向来选择问题的解，其数学表达式如下：或写成矩阵方式： 式中， 是与第i个目的函数相关的权重； A是由 (i=1,2,k )组成的mm对角矩阵。实际根据 ：假设规划问题的某一目的可以给出一个可供选择的范围，那么该目的就可以作为约束条件而被排除出目的组，进入约束条件组中。假设，除第一个目的外，其他目的都可以提出一个可供

10、选择的范围，那么该多目的规划问题就可以转化为单目的规划问题： 方法三 约束模型极大极小法 方法四 目的到达法 首先将多目的规划模型化为如下规范方式： 在求解之前，先设计与目的函数相应的一组目的值理想化的期望目的 fi* ( i=1,2,k ) ,每一个目的对应的权重系数为 i* ( i=1,2,k ) ，再设 为一松弛因子。那么，多目的规划问题就转化为： 方法五 目的规划模型目的规划法 需求预先确定各个目的的期望值 fi* ，同时给每一个目的赋予一个优先因子和权系数，假定有K个目的，L个优先级( LK)，目的规划模型的数学方式为： 式中： di+ 和 di分别表示与 fi 相应的、与fi* 相

11、比的目的超越值和缺乏值，即正、负偏向变量； pl表示第l个优先级； lk+、lk-表示在同一优先级 pl 中，不同目的的正、负偏向变量的权系数。 用目的到达法求解多目的规划的计算过程，可以经过调用Matlab软件系统优化工具箱中的fgoalattain函数实现。第3节 目的规划方法 目的规划模型 求解目的规划的单纯形方法 经过上节的引见和讨论，我们知道，目的规划方法是处理多目的规划问题的重要技术之一。 这一方法是美国学者查恩斯A.Charnes和库伯W.W.Cooper于1961年在线性规划的根底上提出来的。后来，查斯基莱恩U.Jaashelainen和李S.Lee等人，进一步给出了求解目的规

12、划问题的普通性方法单纯形方法。一、目的规划模型 给定假设干目的以及实现这些目的的优先顺序，在有限的资源条件下，使总的偏离目的值的偏向最小。一根本思想例1：某一个企业利用某种原资料和现有设备可消费甲、乙两种产品，其中，甲、乙两种产品的单价分别为8元和10元；消费单位甲、乙两种产品需求耗费的原资料分别为2个单位和1个单位，需求占用的设备分别为1台时和2台时；原资料拥有量为11个单位；可利用的设备总台时为10台时。试问：如何确定其消费方案？二目的规划的有关概念 假设断策者所追求的独一目的是使总产值到达最大，那么这个企业的消费方案可以由如下线性规划模型给出：求 ， ，使 6.3.1 而且满足 式中：

13、和 为决策变量，z为目的函数值。将上述问题化为规范后，用单纯形方法求解可得最正确决策方案为 万元。 但是，在实践决策时，企业指点者必需思索市场等一系列其他条件，如：根据市场信息，甲种产品的需求量有下降的趋势，因此甲种产品的产量不应大于乙种产品的产量。超越方案供应的原资料，需用高价采购，这就会使消费本钱添加。应尽能够地充分利用设备的有效台时，但不希望加班。应尽能够到达并超越方案产值目的56万元。 这样，该企业消费方案确实定，便成为一个多目的决策问题，这一问题可以运用目的规划方法进展求解。 为了建立目的规划数学模型，下面引入有关概念。 偏向变量 在目的规划模型中，除了决策变量外，还 需求引入正、负

14、偏向变量 、 。其中，正偏向变量表示决策值超越目的值的部分，负偏向变量表示决策值未到达目的值的部分。 由于决策值不能够既超越目的值同时又未到达目的值，故有 成立。绝对约束和目的约束 绝对约束，必需严厉满足的等式约束和不等式约束，譬如，线性规划问题的一切约束条件都是绝对约束，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目的约束，目的规划所特有的，可以将约束方程右端项看做是追求的目的值，在到达此目的值时允许发生正的或负的偏向 ，可参与正负偏向变量，是软约束。 线性规划问题的目的函数，在给定目的值和参与正、负偏向变量后可以转化为目的约束，也可以根据问题的需求将绝对约束转化为目的约束。优先

15、因子优先等级与权系数 一个规划问题,经常有假设干个目的，决策者对各个目的的思索,往往是有主次或轻重缓急的。凡要求第一位到达的目的赋予优先因子 ，次位的目的赋予优先因子 ，并规定 表示 比 有更大的优先权。这就是说，首先保证 级目的的实现，这时可以不思索次级目的；而 级目的是在实现 级目的的根底上思索的；依此类推。， 假设要区别具有一样优先因子 的目的的差别，就可以分别赋予它们不同的权系数 。这些优先因子和权系数都由决策者按照详细情况而定。 目的函数 目的规划的目的函数准那么函数是按照各目的约束的正、负偏向变量和赋予相应的优先因子而构造的。当每一目确实定后，尽能够减少与目的值的偏离。因此，目的规

16、划的目的函数只能是根本方式有3种： (6.3.5 要求恰好到达目的值，就是正、负偏向变量都要尽能够小,即 6.3.6 要求不超越目的值，即允许达不到目的值，就是正偏向变量要尽能够小，即6.3.7 要求超越目的值，也就是超越量不限，但负偏向变量要尽能够小，即 6.3.8 在实践问题中，可以根据决策者的要求，引入正、负偏向变量和目的约束，并给不同目的赋予相应的优先因子和权系数，构造目的函数，建立模型。 例2：在例1中，假设断策者在原资料供应受严厉控制的根底上思索：首先是甲种产品的产量不超越乙种产品的产量；其次是充分利用设备的有限台时，不加班；再次是产值不小于56万元。并分别赋予这3个目的优先因子

17、。试建立该问题的目的规划模型。解：根据题意，这一决策问题的目的规划模型是...14 假定有L个目的，K个优先级(KL)，n个变量。在同一优先级 中不同目的的正、负偏向变量的权系数分别为 、 ，那么多目的规划问题可以表示为三目的规划模型的普通方式 ..186.3.19目的函数目的约束绝对约束非负约束在以上各式中： 、 分别为赋予 优先因子的第 个目的的正、负偏向变量的权系数； 为第 个目的的预期值； 为决策变量； 、 分别为第 个目的的正、负偏向变量。6.3.15式为目的函数;6.3.16式为目的

18、约束;6.3.17式为绝对约束;6.3.18式和6.3.19式为非负约束; 、 、 分别为目的约束和绝对约束中决策变量的系数及约束值。其中： ； ； ； 。 二、求解目的规那么的单纯形方法 目的规划模型仍可以用单纯形方法求解 ，在求解时作以下规定： 由于目的函数都是求最小值，所以，最优判别检验数为 由于非基变量的检验数中含有不同等级的优先因子 所以检验数的正、负首先决议于 的系数 的正、负，假设 ，那么检验数的正、负就决议于 的系数 的正、负，下面可依此类推。 据此，我们可以总结出求解目的规划问题的单纯形方法的计算步骤如下： 建立初始单纯形表，在表中将检验数行按优先因子个数分别排成L行，置 。

19、 检查该行中能否存在负数，且对应的前L-1行的系数是零。假设有，取其中最小者对应的变量为换入变量，转。假设无负数，那么转。 按最小比值规那么 规那么确定换出变量，当存在两个和两个以上一样的最小比值时，选取具有较高优先级别的变量为换出变量。 按单纯形法进展基变换运算，建立新的计算表，前往。 当l=L时，计算终了，表中的解即为称心解。否那么置l=l+1，前往 。例3：试用单纯形法求解例2所描画的目的规划问题解：首先将这一问题化为如下规范方式 (1)取 , , , ,为初始基变量，列出初始单纯形表。表6.3.1 (2)取 ，检查检验数的 行，因该行无负检验数，故转(5) 。 (5) 由于 ，置 ，前

20、往(2)。 (2) 检查发现检验数 行中有 ， ，由于有 ，所以 为换入变量，转入(3)。 (3按 规那么计算： ，所以 为换出变量，转入(4)。 (4)进展换基运算，得到表6.3.2。以此类推，直至得到最终单纯形表为止，如表6.3.3所示。 取 为初始基变量，列出初始单纯形表。 取 l =1 ，检查检验数的 p1 行，因该行无负检验数，故转。 由于 l =1L=3 ，置 l = l+1=2 ，前往。 检查发现检验数 p2行中有-1，-2，由于有min-1,-2=-2 ，所以x2为换入变量，转入。 按 规那么计算： ，所以 d2- 为换出变量，转入。 进展换基运算，得表3。以此类推，直至得到最

21、终单纯形表4为止。 由表3可知，x1* =2，x2* =4，为称心解。检查检验数行，发现非基变量d3+的检验数为0，这阐明该问题存在多重解。 在表3中，以非基变量d3+为换入变量，d1-为换出变量，经迭代得到表4。 从表4可以看出，x1*=10/3，x2*=10/3也是该问题的称心解。 多目的规划的Matlab求解 用目的到达法求解多目的规划的计算过程，可以经过调用Matlab软件系统优化工具箱中的fgoalattain函数实现。该函数的运用方法，如下: X = FGOALATTAIN(FUN,X0,GOAL,WEIGHT)X=FGOALATTAIN(FUN,X0,GOAL,WEIGHT,A,

22、B,Aeq,Beq,LB,UB) X,FVAL,ATTAINFACTOR,EXITFLAG,OUTPUT=FGOALATTAIN(FUN,X0,.)在MATLAB中，多目的问题的规范方式为:其中：x、b、beq、lb、ub是向量；A、Aeq为矩阵；C(x)、Ceq(x)和F(x)是前往向量的函数；F(x)、C(x)、Ceq(x)可以是非线性函数；weight为权值系数向量，用于控制对应的目的函数与用户定义的目的函数值的接近程度；goal为用户设计的与目的函数相应的目的函数值向量； 为一个松弛因子标量；F(x)为多目的规划中的目的函数向量。多目的规划的Matlab求解例：某工厂因消费需求，欲采购

23、一种原料，市场上这种原资料有两个等级，甲级单价2元/kg,乙级单价1元/kg，现要求总费用不超越200元，购得原料总量不少于100kg,其中甲级原料不少于50kg，问如何确定最好的采购方案。分析:列出方程x150; 2x1+x2200; x1+x2100; x1,x20化为规范形min f1=2x1+x2min f2= x1 x2min f3= x1s.t :2x1+x2200 x1 x2 100 x1 50 x1, x20多目的规划的Matlab求解matlab程序fun=2*x(1)+x(2),-x(1)-x(2),-x(1);a=2 1;-1 -1;-1 0;b=200 -100 -20

24、;goal=200,-100,-50;weight=goal;x0=55, 55;lb=0,0;X,FVAL,ATTAINFACTOR,EXITFLAG,OUTPUT,LAMBDA=fgoalattain(fun,x0,goal,weight,a,b,lb,) 化为规范形min f1=2x1+x2min f2= x1 x2min f3= x1s.t :2x1+x2200 x1 x2 100 x1 50 x1,x20多目的规划的Matlab求解Optimization terminated: Search direction less than 2*options.TolXand maximum

25、 constraint violation is less than options.TolCon.Active inequalities (to within options.TolCon = 1e-006): lower upper ineqlin ineqnonlin 2 2 3x = 50.0000 50.0000fval = 150.0000 -100.0000 -50.0000attainfactor =-1.4476e-024exitflag = 4多目的规划的Matlab求解土地利用问题 消费方案问题 投资问题 第4节 多目的规划运用实例 第5章第1节中，我们运用线性规划方法讨

26、论了表5.1.4所描画的农场作物种植方案的问题。但是，由于线性规划只需单一的目的函数，所以当时我们建立的作物种植方案模型属于单目的规划模型，给出的种植方案方案，要么使总产量最大，要么使总产值最大；两个目的无法兼得。那么，终究怎样制定作物种植方案，才干兼顾总产量和总产值双重目的呢？下面我们用多目的规划的思想方法处理这个问题。 一、土地利用问题 取 为决策变量，它表示在第 j 等级的耕地上种植第i种作物的面积。假设追求总产量最大和总产值最大双重目的，那么，目的函数包括： 追求总产量最大 6.4.1 追求总产值最大6.4.2 根据题意，约束方程包括： 耕地面积约束 最低收获量约束6.4.3 6.4.

27、4 6.4.5 非负约束 对上述多目的规划问题，我们可以采用如下方法，求其非劣解。用线性加权方法 取 ，重新构造目的函数 这样，就将多目的规划转化为单目的线性规划。 用单纯形方法对该问题求解，可以得到一个称心解非劣解方案，结果见表6.4.1。 此方案是：III等耕地全部种植水稻，I等耕地全部种植玉米，II等耕地种植大豆19.117 6 hm2、种植玉米280.882 4 hm2。在此方案下，线性加权目的函数的最大取值为6 445 600。 表6.4.1 线性加权目的下的非劣解方案单位：hm2 目的规划方法 实践上，除了线性加权求和法以外，我们还可以用目的规划方法求解上述多目的规划问题。 假设我

28、们对总产量 和总产值 ，分别提出一个期望目的值kg元 并将两个目的视为一样的优先级。 假设 、 分别表示对应第1个目的期望值的正、负偏向变量， 、 分别表示对应于第2个目的期望值的正、负偏向变量，而且将每一个目的的正、负偏向变量同等对待即可将它们的权系数都赋为1，那么，该目的规划问题的目的函数为 对应的两个目的约束为 6.4.8 6.4.9即 除了目的约束以外，该模型的约束条件，还包括硬约束和非负约束的限制。其中，硬约束包括耕地面积约束6.4.3式和最低收获量约束6.4.4式；非负约束，不但包括决策变量的非负约束6.4.5式，还包括正、负偏向变量的非负约束 解上述目的规划问题，可以得到一个非劣

29、解方案，详见表6.4.2。 表6.4.2 目的规划的非劣解方案单位:hm2 在此非劣解方案下，两个目的的正、负差变量分为 ， ， ， 。 二、消费方案问题 某企业拟消费A和B两种产品，其消费投资费用分别为2 100元/t和4 800元/t。A、B两种产品的利润分别为3 600元/t和6 500元/t。A、B产品每月的最大消费才干分别为5 t和8 t；市场对这两种产品总量的需求每月不少于9 t。试问该企业应该如何安排消费方案，才干既能满足市场需求，又节约投资，而且使消费利润到达最大? 该问题是一个线性多目的规划问题。假设方案决策变量用 和 表示，它们分别代表A、B产品每月的消费量单位：t； 表示

30、消费A、B两种产品的总投资费用单位：元； 表示消费A、B两种产品获得的总利润单位：元。那么，该多目的规划问题就是：求 和 ，使 而且满足 对于上述多目的规划问题，假设断策者提出的期望目的是：1每个月的总投资不超30 000元；2每个月的总利润到达或超越45 000元；3两个目的同等重要。那么，借助Matlab软件系统中的优化计算工具进展求解，可以得到一个非劣解方案为 按照此方案进展消费，该企业每个月可以获得利润44 000元，同时需求投资29 700元。 某企业拟用1 000万元投资于A、B两个工程的技术改造。设 、 分别表示分配给A、B工程的投资万元。据估计，投资工程A、B的年收益分别为投资

31、的60%和70%；但投资风险损失，与总投资和单项投资均有关系 据市场调查显示， A工程的投资前景好于B工程，因此希望A工程的投资额不小B工程。试问应该如何在A、B两个工程之间分配投资，才干既使年利润最大，又使风险损失为最小？ 三、投资问题 该问题是一个非线性多目的规划问题，将它用数学言语描画出来，就是：求 、 ，使 而且满足 对于上述多目的规划问题，假设断策者提出的期望目的是：1每一年的总收益不小于600万元；2希望投资风险损失不超越800万元；3两个目的同等重要。那么，借助Matlab软件中的优化计算工具进展求解，可以得到一个非劣解方案为 750.00万元， 250.00万元matlab程序fun=-0.60*x(1)-0.70*x(2),0.001*x(1)2+0.002*x(2)2+0.001*x(1)*x(2); a=-1,1; b=