04多目标规划方法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,多目标规划方法,Multi-objective Programming,1,背景介绍,在地理学研究中，对于许多规划问题，常常需要考虑多个目标，如经济效益目标，生态效益目标，社会效益目标，等等。为了满足这类问题研究之需要，本章拟结合有关实例，对多目标规划方法及其在地理学研究中的应用问题作一些简单地介绍。,2,多目标规划及其求解技术简介,目标规划方法,多目标规划应用实例,大纲,3,1,多目标规划及其非劣解,多目标规划及其非劣解,多目标规划求解技术简介,4,（一）任何多目标规划问题，都由两个基本部分组成：,（,1,）两个以上的目标函数；,（,2,）若干个约束条件。,（二）对于多目标规划问题，可以将其数学模,型一般地描写为如下形式：,一、多目标规划及其非劣解,5,一、多目标规划及其非劣解,（,1.2,）,（,1.1,）,式中： 为决策变量向量。,6,一、多目标规划及其非劣解,如果将（,1.1,）和（,1.2,）式进一步缩写，,即：,（,1.3,）,（,1.4,）,式中： 是,k,维函数向量，,k,是目标函数的个数；,是,m,维函数向量；,是,m,维常数向量；,m,是约束方程的个数。,7,一、多目标规划及其非劣解,对于线性多目标规划问题，（,1.3,）和（,1.4,）式可以进一步用矩阵表示：,（,1.5,）,（,1.6,）,式中： 为,n,维决策变量向量；,为,kn,矩阵，即目标函数系数矩阵；,为,mn,矩阵，即约束方程系数矩阵；,为,m,维的向量，约束向量。,8,对于上述多目标规划问题，求解就意味着需要做出如下的复合选择：,每一个目标函数取什么值，原问题可以得到最满意的解决？,每一个决策变量取什么值，原问题可以得到最满意的解决 ？,多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其它目标。,二、多目标规划的非劣解,9,非劣解：可以用图,1.1,说明。,二、多目标规划的非劣解,图,1.1,多目标规划的劣解与非劣解,10,在图,1.1,中，就方案和来说，的 目标值比大，但其目标值 比小，因此无法确定这两个方案的优与劣。在各个方案之间，显然：比好，比好，比好，比好。而对于方案、之间则无法确定优劣，而且又没有比它们更好的其他方案，所以它们就被称之为多目标规划问题的非劣解或有效解，其余方案都称为劣解。所有非劣解构成的集合称为非劣解集。,二、多目标规划的非劣解,11,当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解）。,二、多目标规划的非劣解,12,2,多目标规划求解技术简介,为了求得多目标规划问题的非劣解，常常需要将多目标规划问题转化为单目标规划问题去处理。实现这种转化，有如下几种建模方法。,一、效用最优化模型,二、罚款模型,三、约束模型,四、目标规划模型,五、目标达到法,13,一、效用最优化模型,建摸依据：规划问题的各个目标函数可以通过一定的方式进行求和运算。这种方法将一系列的目标函数与效用函数建立相关关系，各目标之间通过效用函数协调，使多目标规划问题转化为传统的单目标规划问题：,是与各目标函数相关的效用函数的和函数。,（,2.1,）,（,2.2,）,14,在用效用函数作为规划目标时，需要确定一组权值 来反映原问题中各目标函数在总体目标中的权重，即：,式中，诸 应满足：,若采用向量与矩阵,（,2.3,）,（,2.5,）,（,2.6,）,（,2.7,）,（,2.4,）,15,二、罚款模型,规划决策者对每一个目标函数都能提出所期望的值（或称满意值）；,通过比较实际值 与期望值 之间的偏差来选择问题的解，其数学表达式如下：,（,2.8,）,（,2.9,）,16,或写成矩阵形式：,式中， 是与第,i,个目标函数相关的权重；,A,是由 组成的,mm,对角矩阵。,（,2.10,）,（,2.11,）,17,三、约束模型,理论依据 ：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中。,假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：,18,采用矩阵可记为：,（,2.17,）,（,2.16,）,（,2.15,）,（,2.14,）,（,2.13,）,（,2.12,）,19,四、目标规划模型,也需要预先确定各个目标的期望值 ，同时给每一个目标赋予一个优先因子和权系数，假定有,K,个目标，,L,个优先级 ，目标规划模型的数学形式为：,20,式中： 和 分别表示与 相应的、与 相比,的目标超过值和不足值，即正、负偏差变量；,表示第,l,个优先级；,、 表示在同一优先级 中，不同目标的正、负偏差变量的权系数。,（,2.18,）,（,2.19,）,（,2.20,）,21,五、目标达到法,首先将多目标规划模型化为如下标准形式：,（,2.21,）,（,2.22,）,22,在求解之前，先设计与目标函数相应的一组目标值理想化的期望目标,每一个目标对应的权重系数为 ，再设 为一松弛因子。那么，多目标规划问题（,2.21,）（,2.22,）就转化为：,（,2.23,）,（,2.25,）,（,2.24,）,23,用,目标达到法求解多目标规划的计算过程，可以通过调用,Matlab,软件系统优化工具箱中的,fgoalattain,函数实现。该函数的使用方法，详见教材的配套光盘。,24,3,目标规划方法,通过上节的介绍和讨论，我们知道，目标规划方法是解决多目标规划问题的重要技术之一。,这一方法是美国学者查恩斯（,A.Charnes,）和库伯（,W.W.Cooper,）于,1961,年在线性规划的基础上提出来的。后来，查斯基莱恩（,U.Jaashelainen,）和李（,Sang.Lee,）等人，进一步给出了求解目标规划问题的一般性方法,单纯形方法。,25,本节主要内容：,目标规划模型,求解目标规划的单纯形方法,26,一、目标规划模型,（一）基本思想 ：,给定若干目标以及实现这些目标的优先顺序，在有限的资源条件下，使总的偏离目标值的偏差最小。,27,（二）目标规划的有关概念,例,1,：某一个企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价分别为,8,元和,10,元；生产单位甲、乙两种产品需要消耗的原材料分别为,2,个单位和,1,个单位，需要占用的设备分别为,1,台时和,2,台时；原材料拥有量为,11,个单位；可利用的设备总台时为,10,台时。试问：如何确定其生产方案？,28,如果决策者所追求的唯一目标是使总产值达到最大，则这个企业的生产方案可以由如下线性规划模型给出：求 ， ，使,而且满足：,式中：和为决策变量，为目标函数值。将上述问题化为标准后，用单纯形方法求解可得最佳决策方案为 （万元）,（,3.1,）,（,3.2,）,（,3.3,）,（,3.4,）,29,但是，在实际决策时，企业领导者必须考虑市场等一系列其它条件，如：,根据市场信息，甲种产品的需求量有下降的趋势，因此甲种产品的产量不应大于乙种产品的产量。,超过计划供应的原材料，需用高价采购，这就会使生产成本增加。,应尽可能地充分利用设备的有效台时，但不希望加班。,应尽可能达到并超过计划产值指标,56,元。,这样，该企业生产方案的确定，便成为一个多目标决策问题，这一问题可以运用目标规划方法进行求解。,30,为了建立目标规划数学模型，下面引入有关概念。,1.,偏差变量,在目标规划模型中，除了决策变量外，还需要引入正、负偏差变量 、 。其中，正偏差变量表示决策值超过目标值的部分，负偏差变量表示决策值未达到目标值的部分。,因为决策值不可能既超过目标值同时又未达到目标值，故有 成立。,目标规划模型的有关概念,31,2,、绝对约束和目标约束,绝对约束，必须严格满足的等式约束和不等式约束，譬如，线性规划问题的所有约束条件都是绝对约束，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。,目标约束，目标规划所特有的，可以将约束方程右端项看作是追求的目标值，在达到此目标值时允许发生正的或负的偏差 ，可加入正负偏差变量，是软约束。,线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可以转化为目标约束，也可以根据问题的需要将绝对约束转化为目标约束。,目标规划模型的有关概念,32,3.,优先因子（优先等级）与权系数,一个规划问题,常常有若干个目标，决策者对各个目标的考虑,往往是有主次或轻重缓急的。凡要求第一位达到的目标赋予优先因子 ，次位的目标赋予优先因子 ，,，并规定 表示 比 有更大的优先权。这就是说，首先保证 级目标的实现，这时可以不考虑次级目标；而 级目标是在实现 级目标的基础上考虑的；依此类推。若要区别具有相同优先因子 的目标的差别，就可以分别赋予它们不同的权系数 。这些优先因子和权系数都由决策者按照具体情况而定。,目标规划模型的有关概念,33,4.,目标函数,目标规划的目标函数（准则函数）是按照各目标约束的正、负偏差变量和赋予相应的优先因子而构造的。当每一目标确定后，尽可能缩小与目标值的偏离。因此，目标规划的目标函数只能是：,基本形式有三种：,a),要求恰好达到目标值，就是正、负偏差变量都要尽可能小,即,目标规划模型的有关概念,（,3.5,）,（,3.6,）,34,b),要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能小，即,c),要求超过目标值，也就是超过量不限，但负偏差变量要尽可能小，即,在实际问题中，可以根据决策者的要求，引入正、负偏差变量和目标约束，并给不同目标赋予相应的优先因子和权系数，构造目标函数，建立模型。,目标规划模型的有关概念,（,3.7,）,（,3.8,）,35,例,2,：在例,1,中，如果决策者在原材料供应受严格控制的基础上考虑：首先是甲种产品的产量不超过乙种产品的产量；其次是充分利用设备的有限台时，不加班；再次是产值不小于,56,元。并分别赋予这三个目标优先因子 。试建立该问题的目标规划模型。,36,解,：根据题意，这一决策问题的目标规划模型是,（,3.9,）,（,3.10,）,（,3.11,）,（,3.12,）,（,3.13,）,（,3.14,）,37,假定有,L,个目标，,K,个优先级,(KL),，,n,个变量。在同一优先级 中不同目标的正、负偏差变量的权系数分别为 、 ，则多目标规划问题可以表示为：,（三）目标规划模型的一般形式,（,3.15,）,（,3.16,）,（,3.17,）,（,3.18,）,（,3.19,）,38,在以上各式中，,、 分别为赋予 优先因子的第 个目标的正、负偏差变量的权系数，,为第 个目标的预期值，,为决策变量，,、 分别为第 个目标的正、负偏差变量，,（,3.15,）式为目标函数，（,3.16,）式为目标约束，（,3.17,）式为绝对约束，（,3.18,）式和（,3.19,）式为非负约束， 、 、 分别为目标约束和绝对约束中决策变量的系数及约束值。其中， ；,； 。,39,二、求解目标规则的单纯形方法,目标规划模型仍可以用单纯形方法求解,，在求解时作以下规定：,因为目标函数都是求最小值，所以，最优判别检验数,为：,因为非基变量的检验数中含有不同等级的优先因子，,40,所以检验数的正、负首先决定于 的系数 的正、负，若 ，则检验数的正、负就决定于,的系数 的正、负，下面可依此类推。,据此，我们可以总结出求解目标规划问题的单纯形方法的计算步骤如下：,建立初始单纯形表，在表中将检验数行按优先因子个数分别排成,L,行，置 。,41,检查该行中是否存在负数，且对应的前,L-1,行的系数是零。若有，取其中最小者对应的变量为换入变量，转。若无负数，则转。,按最小比值规则（ 规则）确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。,按单纯形法进行基变换运算，建立新的计算表，返回。,当,l=L,时，计算结束，表中的解即为满意解。否则置,l=l+1,，返回 。,42,例,3,：试用单纯形法求解例,2,所描述的目标规划问题,解：,首先将这一问题化为如下标准形式：,43,取 为初始基变量，列出初始单纯形表,。,表,3.1,44,取 ，检查检验数的 行，因该行无负检验数，故转。, 因为 ，置 ，返回。, 检查发现检验数 行中有 ， ，因为有,，所以 为换入变量，转入。,按 规则计算： ，所以 为换出变量，转入。, 进行换基运算，得到表,3.2,。以此类推，直至得到最终单纯形表为止，如表,3.3,所示。,45,表,3.2,46,表,3.3,由表,6.2.3,可知， ， ，为满意解。检查检验数行，发现非基变量的检验数为,0,，这表明该问题存在多重解。,47,表,2.4,在表,3.3,中，以非基变量 为换入变量，,为换出变量，经迭代得到表,6.3.4,。,从表,3.4,可以看出， ， 也是该问题的满意解。,48,一、土地利用问题,二、生产计划问题,三、投资问题,4,多目标规划应用实例,49,我们运用线性规划方法讨论了表,1.4,所描述的农场作物种植计划的问题。但是，由于线性规划只有单一的目标函数，所以当时我们建立的作物种植计划模型属于单目标规划模型，给出的种植计划方案，要么使总产量最大，要么使总产值最大；两个目标无法兼得。那么，究竟怎样制定作物种植计划，才能兼顾总产量和总产值双重目标呢？下面我们用多目标规划的思想方法解决这个问题。,一、土地利用问题,50,取 决策变量，它表示在第,j,等级的耕地上种植第,i,种作物的面积。如果追求总产量最大和总产值最大双重目标，那么，目标函数包括：,追求总产量最大,追求总产值最大,（,4.1,）,（,4.2,）,51,根据题意，约束方程包括：,耕地面积约束,最低收获量约束,（,4.3,）,（,4.4,）,非负约束,（,4.5,）,对上述多目标规划问题，我们可以采用如下方法，求其非劣解。,52,1.,用线性加权方法,取 ，重新构造目标函数：,这样，就将多目标规划转化为单目标线性规划。,53,用单纯形方法对该问题求解，可以得到一个满意解（非劣解）方案，结果见表,6.4.1,。,此方案是：,III,等耕地全部种植水稻，,I,等耕地全部种植玉米，,II,等耕地种植大豆,19.1176,公顷、种植玉米,280.8824,公顷。在此方案下，线性加权目标函数的最大取值为。,54,表,4.1,线性加权目标下的非劣解方案,（单位：,hm,2,）,55,2.,目标规划方法,实际上，除了线性加权求和法以外，我们还可以用目标规划方法求解上述多目标规划问题。如果我们对总产量 和总产值 ，分别提出一个期望目标值 （,kg,）， （元），并将两个目标视为相同的优先级。,如果 、 分别表示对应第一个目标期望值的正、负偏差变量， 、 分别表示对应于第二个目标期望值的正、负偏差变量，而且将每一个目标的正、负偏差变量同等看待（即可将它们的权系数都赋为,1,），那么，该目标规划问题的目标函数为：,56,对应的两个目标约束为：,（,4.8,）,（,4.9,）,即：,57,除了目标约束以外，该模型的约束条件，还包括硬约束和非负约束的限制。其中，硬约束包括耕地面积约束（,4.3,）式和最低收获量约束（,4.4,）式；非负约束，不但包括决策变量的非负约束（,4.5,）式，还包括正、负偏差变量的非负约束：,解上述目标规划问题，可以得到一个非劣解方案，详见表,6.4.2,。,58,表,4.2,目标规划的非劣解方案,（单位：,hm,2,）,在此非劣解方案下，两个目标的正、负偏差变量分别为 ， ， ， 。,59,二、生产计划问题,某企业拟生产,A,和,B,两种产品，其生产投资费用分别为,2100,元,/t,和,4800,元,/t,。,A,、,B,两种产品的利润分别为,3600,元,/t,和,6500,元,/t,。,A,、,B,产品每月的最大生产能力分别为,5t,和,8t,；市场对这两种产品总量的需求每月不少于,9t,。试问该企业应该如何安排生产计划，才能既能满足市场需求，又节约投资，而且使生产利润达到最大,?,60,该问题是一个线性多目标规划问题。如果计划决策变量用 和 表示，它们分别代表,A,、,B,产品每月的生产量（单位：,t,）； 表示生产,A,、,B,两种产品的总投资费用（单位：元）； 表示生产,A,、,B,两种产品获得的总利润（单位：元）。那么，该多目标规划问题就是：求 和 ，使：,61,而且满足：,对于上述多目标规划问题，如果决策者提出的期望目标是：（,1,）每个月的总投资不超,30000,元；（,2,）每个月的总利润达到或超过,45000,元；（,3,）两个目标同等重要。那么，借助,Matlab,软件系统中的优化计算工具进行求解，可以得到一个非劣解方案为：,62,按照此方案进行生产，该企业每个月可以获得利润,44000,元，同时需要投资,29700,元。,63,三、投资问题,某企业拟用,1000,万元投资于,A,、,B,两个项目的技术改造。设 、 分别表示分配给,A,、,B,项目的投资（万元）。据估计，投资项目,A,、,B,的年收益分别为投资的,60%,和,70%,；但投资风险损失，与总投资和单项投资均有关系：,据市场调查显示，,A,项目的投资前景好于,B,项目，因此希望,A,项目的投资额不小,B,项目。试问应该如何在,A,、,B,两个项目之间分配投资，才能既使年利润最大，又使风险损失为最小？,64,该问题是一个非线性多目标规划问题，将它用数学语言描述出来，就是：求 、 ，使：,而且满足：,65,对于上述多目标规划问题，如果决策者提出的期望目标是：（,1,）每一年的总收益不小于,600,万元；（,2,）希望投资风险损失不超过,800,万元；（,3,）两个目标同等重要。那么，借助,Matlab,软件中的优化计算工具进行求解，可以得到一个非劣解方案为：,646.3139,万元， ,304.1477,万元,此方案的投资风险损失为,799.3082,万元，每一年的总收益为,600.6918,万元。,66,