多目标规划方法.ppt

《多目标规划方法.ppt》由会员分享，可在线阅读，更多相关《多目标规划方法.ppt（66页珍藏版）》请在三一文库上搜索。

1、第六章 多目标规划方法 在地理学研究中，对于许多规划问题 ，常常需要考虑多个目标，如经济效益目 标，生态效益目标，社会效益目标，等等 。为了满足这类问题研究之需要，本章拟 结合有关实例，对多目标规划方法及其在 地理学研究中的应用问题作一些简单地介 绍。 本章主要内容： n多目标规划及其求解技术简介 n目标规划方法 n多目标规划应用实例 多目标规划及其非劣解 n多目标规划求解技术简介 6.1多目标规划及其非劣解 一、多目标规划及其非劣解 （一）任何多目标规划问题，都由两个基本部 分组成： （1）两个以上的目标函数； （2）若干个约束条件。 （二）对于多目标规划问题，可以将其数学模 型一般地描写为

2、如下形式： （6.1.2） （6.1.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.1.6） 式中： 为n维决策变量向量； 为kn矩阵，即目标函数系数矩阵； 为mn矩阵，即约束方程系数矩阵； 为m维的向量，约束向量。 二、多目标规划的非劣解 对于上述多目标规划问题，求解就意味着需要做 出如下的复合选择： 每一个目标

3、函数取什么值，原问题可以得到最 满意的解决？ 每一个决策变量取什么值，原问题可以得到最 满意的解决 ？ 多目标规划问题的求解不能只追求一个目标的最 优化（最大或最小），而不顾其它目标。 非劣解：可以用图6.1.1说明。 图6.1.1 多目标规划的劣解与非劣解 在图6.1.1中，就方案和来说，的 目标值比 大，但其目标值 比小，因此无法确定这两个方案的 优与劣。在各个方案之间，显然：比好，比好， 比好，比好。而对于方案、之间则无法 确定优劣，而且又没有比它们更好的其他方案，所以它们 就被称之为多目标规划问题的非劣解或有效解，其余方案 都称为劣解。所有非劣解构成的集合称为非劣解集。 当目标函数处于

4、冲突状态时，就不会存 在使所有目标函数同时达到最大或最小值的 最优解，于是我们只能寻求非劣解（又称非 支配解或帕累托解）。 一、效用最优化模型 n二、罚款模型 n三、约束模型 n四、目标规划模型 n五、目标达到法 6.2 多目标规划求解技术简介 为了求得多目标规划问题的非劣解，常常需要将多目 标规 划问题转 化为单 目标规 划问题 去处理。实现这 种转化，有如下几种建模方法。 是与各目标函数相关的效用函数的和函数 。 一、效用最优化模型 建摸依据：规划问题的各个目标函数可以通过 一定的方式进行求和运算。这种方法将一系列 的目标函数与效用函数建立相关关系，各目标 之间通过效用函数协调，使多目标规

5、划问题转 化为传统的单目标规划问题： （6.2.1 ） （6.2.2 ） 在用效用函数作为规划目标时，需要确定一组 权值 来反映原问题中各目标函数在总体目标 中的权重，即： 式中，诸 应满足： 若采用向量与矩阵 二、罚款模型 规划决策者对每一个目标函数都能提出所期望的值 （或称满意值）； 通过比较实际值 与期望值 之间的偏差来选择 问题的解，其数学表达式如下： 或写成矩阵形式： 式中， 是与第i个目标函数相关的权重； A是由 组成的mm对 角矩阵。 三、约束模型 理论依据 ：若规划问题的某一目标可以给出一个 可供选择的范围，则该目标就可以作为约束条件而 被排除出目标组，进入约束条件组中。 假如

6、，除第一个目标外，其余目标都可以提出一个 可供选择的范围，则该多目标规划问题就可以转化 为单目标规划问题： 采用矩阵可记为： 四、目标规划模型 也需要预先确定各个目标的期望值 ，同时 给每一个目标赋予一个优先因子和权系数，假定 有K个目标，L个优先级 ，目标规划模型 的数学形式为： （6.2.18 ） （6.2.19 ） （6.2.20 ） 式中： 和 分别表示与 相应的、与 相比 的目标超过值和不足值，即正、负偏差变量 ； 表示第l个优先级； 、 表示在同一优先级 中，不同目标的 正、负偏差变量的权系数。 五、目标达到法 首先将多目标规划模型化为如下标准形式 ： （6.2.21） （6.2.

7、22） 在求解之前，先设计与目标函数相应的一组目标 值理想化的期望目标 ,每一个目标 对应的权重系数为 ，再设 为一 松弛因子。那么，多目标规划问题（6.2.21） （6.2.22）就转化为： （6.2.25） （6.2.24） （6.2.23） 用目标达到法求解多目标规划的计算过程 ，可以通过调用Matlab软件系统优化工具箱中 的fgoalattain函数实现。该函数的使用方法，详 见教材的配套光盘。 6.3 目标规划方法 通过上节的介绍和讨论，我们知道，目标规划方 法是解决多目标规划问题的重要技术之一。 这一方法是美国学者查恩斯（A.Charnes）和库 伯（W.W.Cooper）于19

8、61年在线性规划的基础上提出来 的。后来，查斯基莱恩（U.Jaashelainen）和李（ Sang.Lee）等人，进一步给出了求解目标规划问题的一 般性方法单纯形方法。 目标规划模型 求解目标规划的单纯形方法 本节主要内容 ： 一、目标规划模型 给定若干目标以及实现这些目标的优先 顺序，在有限的资源条件下，使总的偏离目标 值的偏差最小。 （一）基本思想 ： 例1：某一个企业利用某种原材料和现有设备 可生产甲、乙两种产品，其中，甲、乙两种 产品的单价分别为8元和10元；生产单位甲、 乙两种产品需要消耗的原材料分别为2个单位 和1个单位，需要占用的设备分别为1台时和2 台时；原材料拥有量为11个

9、单位；可利用的 设备总台时为10台时。试问：如何确定其生 产方案？ （二）目标规划的有关概念 如果决策者所追求的唯一目标是使总产值 达到最大，则这个企业的生产方案可以由如下 线性规划模型给出：求 ， ，使 （6.3.1） 而且满足 ： 式中：和为决策变量，为目标函数值。将上述问 题化为标准后，用单纯形方法求解可得最佳决策 方案为 （万元）。 但是，在实际决策时，企业领导者必须考 虑市场等一系列其它条件，如： 根据市场信息，甲种产品的需求量有下降的 趋势，因此甲种产品的产量不应大于乙种产品 的产量。 超过计划供应的原材料，需用高价采购，这就 会使生产成本增加。 应尽可能地充分利用设备的有效台时，

10、但不希 望加班。 应尽可能达到并超过计划产值指标56元。 这样，该企业生产方案的确定，便成为一个 多目标决策问题，这一问题可以运用目标规划方 法进行求解。 为了建立目标规划数学模型，下面引入有关概念 。 目标规划模型的有关概念 1.偏差变量 在目标规划模型中，除了决策变量外，还需要 引入正、负偏差变量 、 。其中，正偏差变量表 示决策值超过目标值的部分，负偏差变量表示决策 值未达到目标值的部分。 因为决策值不可能既超过目标值同时又未达到 目标值，故有 成立。 2、绝对约束和目标约束 绝对约束，必须严格满足的等式约束和不等 式约束，譬如，线性规划问题的所有约束条件都 是绝对约束，不能满足这些约束

11、条件的解称为非 可行解，所以它们是硬约束。 目标约束，目标规划所特有的，可以将约束 方程右端项看作是追求的目标值，在达到此目标 值时允许发生正的或负的偏差 ，可加入正负偏差 变量，是软约束。 线性规划问题的目标函数，在给定目标值和 加入正、负偏差变量后可以转化为目标约束，也 可以根据问题的需要将绝对约束转化为目标约束 。 目标规划模型的有关概念 目标规划模型的有关概念 3.优先因子（优先等级）与权系数 一个规划问题,常常有若干个目标，决策者对各个 目标的考虑,往往是有主次或轻重缓急的。凡要求第 一位达到的目标赋予优先因子 ，次位的目标赋予 优先因子 ，并规定 表 示 比 有更大的优先权。这就是

12、说，首先保证 级目标的实现，这时可以不考虑次级目标；而 级目标是在实现 级目标的基础上考虑的；依此类 推。若要区别具有相同优先因子 的目标的差别， 就可以分别赋予它们不同的权系数 。这 些优先因子和权系数都由决策者按照具体情况而定 。 4.目标函数 目标规划的目标函数（准则函数）是按照各目标 约束的正、负偏差变量和赋予相应的优先因子而构造 的。当每一目标确定后，尽可能缩小与目标值的偏离 。因此，目标规划的目标函数只能是： 基本形式有三种： 目标规划模型的有关概念 （6.3.5 ） a) 要求恰好达到目标值，就是正、负偏差变量都要 尽可能小,即 （6.3.6 ） b) 要求不超过目标值，即允许达

13、不到目标值，就 是正偏差变量要尽可能小，即 （6.3.7 ） c) 要求超过目标值，也就是超过量不限，但负 偏差变量要尽可能小，即 （6.3.8 ） 在实际问题中，可以根据决策者的要求，引入 正、负偏差变量和目标约束，并给不同目标赋予相 应的优先因子和权系数，构造目标函数，建立模型 。 例2：在例1中，如果决策者在原材料供 应受严格控制的基础上考虑：首先是甲 种产品的产量不超过乙种产品的产量； 其次是充分利用设备的有限台时，不加 班；再次是产值不小于56元。并分别赋 予这三个目标优先因子 。试建立 该问题的目标规划模型。 解：根据题意，这一决策问题的目标规划 模型是 （6.3.9） （6.3.

14、10） （6.3.11） （6.3.12） （6.3.13） （6.3.14） 假定有L个目标，K个优先级(KL)，n个变量。 在同一优先级 中不同目标的正、负偏差变量 的权系数分别为 、 ，则多目标规划问题可 以表示为： （三）目标规划模型的一般形式 （6.3.15） （6.3.16） （6.3.17） （6.3.18） （6.3.19） 在以上各式中， 、 分别为赋予 优先因子的第 个目标的正、负 偏差变量的权系数， 为第 个目标的预期值， 为决策变量， 、 分别为第 个目标的正、负偏差变量， （6.3.15）式为目标函数，（6.3.16）式为目标约束， （6.3.17）式为绝对约束，（6

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

16、否存在负数，且对应的前L-1行的 系数是零。若有，取其中最小者对应的变量为换 入变量，转。若无负数，则转。 按最小比值规则（ 规则）确定换出变量，当 存在两个和两个以上相同的最小比值时，选取具 有较高优先级别的变量为换出变量。 按单纯形法进行基变换运算，建立新的计算表 ，返回。 当l=L时，计算结束，表中的解即为满意解。否 则置l=l+1，返回 。 例3：试用单纯形法求解例2所描述的目标规划问题 解：首先将这一问题化为如下标准形式： 取 为初始基变量，列出初始单纯 形表。 表6.3.1 取 ，检查检验数的 行，因该行无负 检验数，故转。 因为 ，置 ，返回。 检查发现检验数 行中有 ， ，因为

17、有 ，所以 为换入变量，转入。 按 规则计算： ，所以 为换出 变量，转入。 进行换基运算，得到表6.3.2。以此类推，直 至得到最终单纯形表为止，如表6.3.3所示。 表6.3.2 表6.3.3 由表6.2.3可知， ， ，为满意解。检查检 验数行，发现非基变量的检验数为0，这表明该问题 存在多重解。 表6.2.4 在表6.3.3中，以非基变量 为换入变量 ， 为换出变量，经迭代得到表6.3.4。 从表6.3.4可以看出， ， 也 是该问题的满意解。 n一、土地利用问题 n二、生产计划问题 n三、投资问题 6.4 多目标规划应用实例 第5章第1节中，我们运用线性规划方法讨论 了表5.1.4所

18、描述的农场作物种植计划的问题。 但是，由于线性规划只有单一的目标函数，所以 当时我们建立的作物种植计划模型属于单目标规 划模型，给出的种植计划方案，要么使总产量最 大，要么使总产值最大；两个目标无法兼得。那 么，究竟怎样制定作物种植计划，才能兼顾总产 量和总产值双重目标呢？下面我们用多目标规划 的思想方法解决这个问题。 一、土地利用问题 取 决策变量，它表示在第 j 等级的耕地上种植 第i种作物的面积。如果追求总产量最大和总产值最大双 重目标，那么，目标函数包括： 追求总产量最大 追求总产值最大 （6.4.1 ） （6.4.2 ） 根据题意，约束方程包括： v耕地面积约束 v最低收获量约束 （

19、6.4.3 ） （6.4.4 ） v非负约束 （6.4.5 ） 对上述多目标规划问题，我们可以采用如下方法 ，求其非劣解。 1.用线性加权方法 取 ，重新构造目标函数： 这样，就将多目标规划转化为单目标线性规划 。 用单纯形方法对该问题求解，可以得到一 个满意解（非劣解）方案，结果见表6.4.1。 此方案是：III等耕地全部种植水稻，I等 耕地全部种植玉米，II等耕地种植大豆19.1176 公顷、种植玉米280.8824公顷。在此方案下， 线性加权目标函数的最大取值为6445600。 表6.4.1 线性加权目标下的非劣解方案（单位：hm2 ） 2.目标规划方法 实际上，除了线性加权求和法以外，

20、我们还可以用目标 规划方法求解上述多目标规划问题。如果我们对总产量 和总产值 ，分别提出一个期望目标值 （kg）， （元），并将两个目标视为相同的 优先级。 如果 、 分别表示对应第一个目标期望值的正、负 偏差变量， 、 分别表示对应于第二个目标期望值的正 、负偏差变量，而且将每一个目标的正、负偏差变量同等看 待（即可将它们的权系数都赋为1），那么，该目标规划问 题的目标函数为： 对应的两个目标约束为： （6.4.8） （6.4.9） 即： 除了目标约束以外，该模型的约束条件，还包括硬约束 和非负约束的限制。其中，硬约束包括耕地面积约束（6.4.3 ）式和最低收获量约束（6.4.4）式；非负约

21、束，不但包括决 策变量的非负约束（6.4.5）式，还包括正、负偏差变量的非 负约束： 解上述目标规划问题，可以得到一个非劣解方案，详见表6.4.2 。 表6.4.2 目标规划的非劣解方案（单位：hm2 ） 在此非劣解方案下，两个目标的正、负偏差变 量分别为 ， ， ， 。 二、生产计划问题 某企业拟生产A和B两种产品，其生产投资 费用分别为2100元/t和4800元/t。A、B两种产 品的利润分别为3600元/t和6500元/t。A、B产 品每月的最大生产能力分别为5t和8t；市场对 这两种产品总量的需求每月不少于9t。试问该 企业应该 如何安排生产计划，才能既能满足市 场需求，又节约投资，而

22、且使生产利润达到最 大? 该问题 是一个线性多目标规划问题。如果计 划决策变量用 和 表示，它们分别代表A、B产品 每月的生产量（单位：t）； 表示生产A、B 两种产品的总投资费用（单位：元）； 表示 生产A、B两种产品获得的总利润（单位：元）。 那么，该多目标规划问题就是：求 和 ，使： 而且满足 ： 对于上述多目标规划问题，如果决策者提 出的期望目标是：（1）每个月的总投资不超 30000元；（2）每个月的总利润达到或超过 45000元；（3）两个目标同等重要。那么，借 助Matlab软件系统中的优化计算工具进行求解 ，可以得到一个非劣解方案为： 按照此方案进行生产，该企业每个月可以获得利

23、 润44000元，同时需要投资29700元。 三、投资问题 某企业拟用1000万元投资于A、B两个项目 的技术改造。设 、 分别表示分配给A、B项 目的投资（万元）。据估计，投资项目A、B的 年收益分别为投资的60%和70%；但投资风险损 失，与总投资和单项投资均有关系： 据市场调查显示， A项目的投资前景好于B 项目，因此希望A项目的投资额不小B项目。试 问应该如何在A、B两个项目之间分配投资，才 能既使年利润最大，又使风险损失为最小？ 该问题 是一个非线性多目标规划问题 ，将它用数学语言描述出来，就是：求 、 ，使： 而且满足： 对于上述多目标规划问题，如果决策者提 出的期望目标是：（1）每一年的总收益不小于 600万元；（2）希望投资风险损失不超过800万 元；（3）两个目标同等重要。那么，借助 Matlab软件中的优化计算工具进行求解，可以 得到一个非劣解方案为： 646.3139万元， 304.1477万元 此方案的投资风险损失为799.3082万元，每 一年的总收益为600.6918万元。