第6章 多目标规划方法.ppt

1、第六章：多目标规划方法。在地理研究中，对于许多规划问题，往往需要考虑多个目标，如经济效益、生态效益、社会效益等。为了满足这类研究的需要，本章将简要介绍多目标规划方法及其在地理研究中的应用。本章主要内容：多目标规划及其求解技术简介；多目标规划方法的应用实例：多目标规划及其非劣解简介：6.1多目标规划及其非劣解；1.多目标规划及其非劣解：(1)任何多目标规划问题由两个基本组成部分组成：(1)两个以上的目标函数；(2)若干限制。(2)对于多目标规划问题，其数学模型一般可以描述如下：(6.1.2)、(6.1.1)，其中：它是决策变量向量。如果(6.1.1)和(6.1.2)进一步缩写，即在(6.1.3)

2、和(6.1.4)中：它是一个k维函数向量，k是目标函数的个数；是m维函数向量。是一个m维常数向量。m是约束方程的个数。对于线性多目标规划问题，(6.1.3)和(6.1.4)可以进一步用矩阵表示：(6.1.5) (6.1.6): n维决策变量向量；是kn矩阵，即目标函数系数矩阵；是mn矩阵，即约束方程的系数矩阵；是m维向量，约束向量。第二，多目标规划的非劣解，对于上述多目标规划问题，求解意味着作出以下复合选择：每个目标函数取什么值，原问题能最满意地求解？每个决策变量的值是多少，原始问题能最满意地解决吗？多目标规划问题的求解不能只追求一个目标(最大或最小)的优化，而忽略其他目标。非劣解：可以用图6

3、.1.1来解释。图6.1.1多目标规划的劣解和非劣解。在图6.1.1中，就方案和而言，目标值比大，但目标值比小，因此不可能确定这两个方案的优劣。在各种方案中，显而易见的是：更好，更好，更好，更好。然而，不可能确定方案的优劣，也没有更好的方案，所以它们被称为非劣解或多目标规划问题的有效解，而其他方案被称为劣解。由所有非劣解集组成的集合称为非劣解集。当目标函数处于冲突状态时，不会有使所有目标函数同时达到最大或最小的最优解，所以我们只能寻求非劣解(也称为非优解或帕累托解)。1.效用优化模型2。惩罚模式3。约束模型4。目标规划模型5。目标实现方法6.2多目标规划求解技术简介。为了获得多目标规划问题的非

4、劣解，往往需要将多目标规划问题转化为单目标规划问题。有几种建模方法可以实现这种转换。是与每个目标函数相关的效用函数的和函数。1.效用优化模型的建模基础：规划问题的每个目标函数都可以用某种方式进行求和。该方法将一系列目标函数和效用函数联系起来，用效用函数协调目标，从而将多目标规划问题转化为传统的单目标规划问题：(6.2.1)、(6.2.2)。当效用函数作为规划目标时，需要确定一组权重来反映原问题中各目标函数在总体目标中的权重，即在公式中，都应满足以下要求：通过比较实际值与期望值之间的偏差，选择问题的解，其数学表达式如下：或写成矩阵形式：其中权重与目标函数有关；a是由。3.约束模型的理论基础：如果

5、规划问题的某个目标可以给出一个备选范围，那么该目标可以作为约束条件从目标组中排除，并进入约束条件组。如果除了第一个目标以外，所有其他目标都可以提出一个替代范围，那么多目标规划问题可以转化为单目标规划问题：矩阵可以写成：4。目标规划模型、也有必要事先确定每个目标的期望值，同时给每个目标一个优先级因子和权重系数，假设有K个目标和L个优先级。(6.2.18)、(6.2.19)和(6.2.20)，其中：和分别表示与对应和比较的目标超出值和不足值，即正负偏差变量；表示第l个优先级；表示同一优先级中不同目标的正负偏差变量的权重系数。5.目标达成方法：首先，将多目标规划模型建模为以下标准形式：(6.2.21

6、)、(6.2.22)。在求解之前，首先设计一组与目标函数相对应的理想目标值，并求出每个目标对应的权重系数，然后将其设定为松弛因子。然后，将多目标规划问题(6.2.21)(6.2.22)转化为：(6.2.25)、(6.2.24)、(6.2.23)。多目标规划的计算过程可以用目标达成法来解决，目标达成法可以通过调用Matlab软件系统来优化。这一功能的使用可以在教科书的光盘上找到。6.3目标规划法，通过前面章节的介绍和讨论，我们知道目标规划法是解决多目标规划问题的重要技术之一。这种方法是由美国学者查恩斯和库珀在1961年基于线性规划提出的。后来，乌亚舍莱宁、桑。Lee等人进一步给出了解决目标规划问

7、题的一般方法，即单纯形法。目标规划模型是求解目标规划的单纯形法。本部分的主要内容如下：1 .目标规划模型，给定几个目标和实现这些目标的优先顺序，在资源有限的情况下，使偏离目标值最小化。(1)基本思路：例1:企业可以用一定的原料和现有的设备生产a、b两种产品，其中a、b两种产品的单价分别为8元和10元；甲、乙生产单元消耗的原材料分别为2台和1台，需要占用的设备分别为1台和2台；原材料的所有权是11个单位；可用设备的总数是10。如何确定其生产计划？(2)目标规划的相关概念，如果决策者追求的唯一目标是总产值最大化，那么该企业的生产计划可以由以下线性规划模型给出：寻求、制定、(6.3.1)和满足：其中

8、：是决策变量和目标函数值。将上述问题转化为标准后，用单纯形法可以得到最佳决策方案。然而，在实际决策中，企业领导人必须考虑一系列其他条件，如市场。例如，根据市场信息，对甲产品的需求有下降趋势，所以甲产品的产量不应大于乙产品。超出计划供应的原材料需要高价购买，这将增加生产成本。尽可能充分利用设备的有效时间，但不要加班。计划产值指标应尽可能达到并超过56元。这样，企业生产计划的确定就成为一个多目标决策问题，可以用目标规划法来解决。为了建立目标规划的数学模型，引入了以下概念。1.偏差变量在目标规划模型中，除了决策变量外，还需要引入正偏差变量和负偏差变量。其中，正偏差变量表示判定值超过目标值的部分，负偏

9、差变量表示判定值没有达到目标值的部分。因为决策值不可能超过目标值，也不可能达到目标值，所以这是真的。绝对约束和客观约束必须严格满足的绝对约束、等式约束和不等式约束。例如，线性规划问题的所有约束都是绝对约束，不能满足这些约束的解称为不可行解，因此它们是硬约束。目标约束是目标规划所特有的，它可以作为约束方程的右端项，作为要追求的目标值。当达到该目标值时，允许正偏差或负偏差，并且可以添加正偏差和负偏差变量，这是一个软约束。线性规划问题的目标函数可以在给定目标值并加入正负偏差变量后转化为目标约束，绝对约束也可以根据问题的需要转化为目标约束。目标规划模型的相关概念，目标规划模型的相关概念，3 .优先级因

10、子(优先级)和权重系数规划问题通常有几个目标，决策者通常给每个目标赋予优先级。要实现的第一个目标应给予优先因子，第二个目标应给予优先因子，并规定该比例具有更大的优先性。也就是说，首先，要保证首要目标的实现，那么就不能考虑次要目标；水平目标是在实现水平目标的基础上考虑的；等等。如果我们想用相同的优先级区分不同的目标，我们可以给它们不同的权重系数。这些优先因子和权重系数由决策者根据具体情况确定。目标函数目标规划的目标函数(准则函数)是根据每个目标约束的正负偏差变量和相应的优先因子构造的。确定每个目标后，将与目标值的偏差降至最低。因此，目标规划的目标函数只能如下：有三种基本形式：目标规划模型的相关概

11、念，(6.3.5)，a)要求精确地达到目标值，即正负偏差变量应尽可能小，即，(6.3.6)，b)要求不超过目标值，即不允许达到目标值。也就是说，超额量是无限的，但是负偏差变量应该尽可能小，即(6.3.8)。在实际问题中，根据决策者的要求，可以引入正负偏差变量和目标约束，并给不同的目标赋予相应的优先因子和权重系数，从而构造目标函数和建立模型。例2:在例1中，如果决策者在严格控制原材料供应的基础上考虑：首先，a产品的产量不超过b产品的产量；其次，充分利用有限的设备时，不要加班；第三，产值不低于56元。并分别给出这三个优先因素。尝试建立该问题的目标规划模型。根据问题的含义，该决策问题的目标规划模型为

12、：(6.3.9)、(6.3.10)、(6.3.11)、(6.3.12)、(6.3.13)、(6.6)在相同的优先级下，如果不同目标的正负偏差变量的权重系数分别为：(3)目标规划模型的一般形式为：(6.3.15)、(6.3.16)、(6 . 3 . 16)、(6 . 3 . 11) (6.3.17)它们是给定优先级的第一个目标的正负偏差变量、第一个目标的期望值、决策变量和第一个目标的正负偏差变量的权重系数，(6.3.15)是目标函数，(6.3.16)是目标约束，(6.3.17)是绝对约束，(。 其中，其次，单纯形法求解目标规则时，目标规划模型仍然可以用单纯形法求解，并且在求解时作了如下规定：因为

13、目标函数是寻找最小值，所以最优判别式检验数是：因为非基本变量的检验数包含不同等级的优先因子、所以检验数的正负首先取决于正负系数，如果是，则检验数的正负在此基础上，我们可以将单纯形法求解目标规划问题的计算步骤归纳如下：建立一个初始单纯形表，根据表中优先因子的个数将测试数的行排列成L行。检查该行是否有负数，对应的第一个L-1行的系数是否为零。如果是，取最小的一个对应的变量作为换入变量。如果没有负数，转。互换变量根据最小比率规则确定。当存在两个或多个相同的最小比率时，具有较高优先级的变量被选为交换变量。根据单纯形法，进行基变换运算，建立新的计算表，然后返回。当l=L时，计算结束，表中的解是令人满意的

14、解。否则，设置l=l 1并返回。例3:尝试用单纯形法解决例2中描述的目标规划问题：首先，将问题转化为以下标准形式：作为初始基本变量，并列出初始单纯形表。表6.3.1、中的检验编号行被转移，因为该行中没有负的检验编号。因为，设置，返回。发现检验编号行中有、号。因为有，所以它是一个变化的变量，它被传递进来。根据规则计算：所以要换出变量，调入。进行基数转换运算，得到表6.3.2。依此类推，直到得到最终的单纯形表，如表6.3.3所示。表6.3.2，表6.3.3。从表6.2.3可以看出，是令人满意的解决方案。通过检查测试号行，发现非基本变量的测试号为0，这表明该问题有多种解决方案。表6.2.4，在表6.

15、3.3中，以非基数变量作为转入变量和转出变量，通过迭代得到表6.3.4。从表6.3.4中可以看出，也是这个问题的一个令人满意的解决方案。1.土地使用问题2。生产计划问题3。投资问题6.4多目标规划的应用实例。在第5章第1节中，我们使用线性规划方法来讨论表5.1.4中描述的农作物种植计划。然而，由于线性规划只有一个目标函数，我们当时建立的作物种植规划模型属于单目标规划模型，给定的种植规划方案要么使总产量最大化，要么使总产值最大化；你不可能两个目标都有。那么，我们如何才能制定一个作物种植计划，以考虑总产量和总产值的双重目标呢？接下来，我们使用多目标规划来解决这个问题。1.土地利用问题，作为决策变量，表示j级耕地上第一茬作物的种植面积。如果我们追求总产出和总产出最大化的双重目标，那么目标函数包括：总产出最大化，(6.4.1)、(6.4.2)。根据问题的含义，约束方程包括：耕地面积约束、最低收获约束、(6.4.3)、(6.4.4) 1。采用线性加权法，取并重构目标函数：从而将多目标规划转化为单目标线性规划。用单纯形法求解该问题，可以得到满意的解(非劣解)，结果见表6.4.1。方案如下：三级农田全部种植水稻，一级农田全部种植玉米，二级农田种植大豆19.1176公顷，玉米280.8824公顷。在该方案下，线性加权目标函数的