多目标规划方法

多目标规划方法Multi-objectiveProgramming2背景介绍在地理学研究中，对于许多规划问题，常常需要考虑多个目标，如经济效益目标，生态效益目标，社会效益目标，等等。为了满足这类问题研究之需要，本章拟结合有关实例，对多目标规划方法及其在地理学研究中的应用问题作一些简单地介绍。多目标规划及其求解技术简介目标规划方法多目标规划应用实例大纲1多目标规划及其非劣解多目标规划及其非劣解多目标规划求解技术简介5（一）任何多目标规划问题，都由两个基本部分组成：（1）两个以上的目标函数；（2）若干个约束条件。（二）对于多目标规划问题，可以将其数学模型一般地描写为如下形式：一、多目标规划及其非劣解6一、多目标规划及其非劣解（1.2）（1.1）式中：为决策变量向量。7一、多目标规划及其非劣解如果将（1.1）和（1.2）式进一步缩写，即：（1.3）

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