04多目标规划方法

多目标规规划方法法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）和库库伯（（W.W.Cooper）于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由表6.2.3可知，，，，，为为满意解。检检查检验数行行，发现非基基变量的检验验数为0，这表明该问问题存在多重重解。表2.4在表3.3中，以非基变变量为换换入变量，为换出变量，，经迭代得到到表6.3.4。从表3.4可以看出，，，也也是该该问题的满意意解。一、土地利用用问题二、生产计划划问题三、投资问题题4多目标规划应应用实例我们运用线性性规划方法讨讨论了表1.4所描述的农场作物种植植计划的问题题。但是，由由于线性规划划只有单一的的目标函数，，所以当时我我们建立的作作物种植计划划模型属于单单目标规划模模型，给出的的种植计划方案案，要么使总总产量最大，，要么使总产产值最大；两两个目标无法法兼得。那么么，究竟怎样样制定作物种种植计划，才才能兼顾总产产量和总产值值双重目标呢呢？下面我们们用多目标规规划的思想方方法解决这个个问题。一、土地利用用问题取决策策变量，它表表示在第j等级的耕地上上种植第i种作物的面积积。如果追求求总产量最大大和总产值最最大双重目标标，那么，目目标函数包括括：①追求总产量量最大②追求总产值值最大（4.1）（4.2）根据题意，约约束方程包括括：耕地面积约束束最低收获量约约束（4.3）（4.4）非负约束（4.5）对上述多目标标规划问题，，我们可以采采用如下方法法，求其非劣劣解。1.用线性加权方方法取，，重新构造目目标函数：这样，就将多多目标规划转转化为单目标标线性规划。。用单纯形方法法对该问题求求解，可以得得到一个满意意解（非劣解解）方案，结结果见表6.4.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）式，还包包括正、负负偏差变量量的非负约约束：解上述目标标规划问题题，可以得得到一个非非劣解方案案，详见表表6.4.2。表4.2目标规划的的非劣解方方案（单位：hm2）在此非劣解解方案下，，两个目标标的正、负负偏差变量量分别为，，，，，，。。二、生产计计划问题某企业拟生生产A和B两种产品，，其生产投投资费用分分别为2100元/t和4800元/t。A、B两种产品的的利润分别别为3600元/t和6500元/t。A、B产品每月的的最大生产产能力分别别为5t和8t；市场对这这两种产品品总量的需需求每月不不少于9t。试问该企企业应该如如何安排生生产计划，，才能既能能满足市场场需求，又又节约投资资，而且使使生产利润润达到最大大?该问题是一一个线性多多目标规划划问题。如如果计划决决策变量用用和表表示，，它们分别别代表A、B产品每月的的生产量（（单位：t）；表表示生产A、B两种产品的的总投资费费用（单位位：元）；；表表示生生产A、B两种产品获获得的总利利润（单位位：元）。。那么，该该多目标规规划问题就就是：求和和，，使：而且满足：：对于上述多多目标规划划问题，如如果决策者者提出的期期望目标是是：（1）每个月的的总投资不不超30000元；（2）每个月的的总利润达达到或超过过45000元；（3）两个目标标同等重要要。那么，，借助Matlab软件系统中中的优化计计算工具进进行求解，，可以得到到一个非劣劣解方案为为：按照此方案案进行生产产，该企业业每个月可可以获得