多目标规划模型

《多目标规划模型》由会员分享，可在线阅读，更多相关《多目标规划模型（45页珍藏版）》请在金锄头文库上搜索。

1、 多目标规划方法 l多目标规划解的讨论非劣解l多目标规划及其求解技术简介效用最优化模型 罚款模型约束模型 目标规划模型目标达到法l目标规划方法l目标规划模型l目标规划的图解法 l求解目标规划的单纯形方法l多目标规划应用实例 多目标规划是数学规划的一个分支。研究多于一个的目标函数在给定区域上的最优化。又称多 目标最优化。通常记为 MOP(multi-objective programming)。在很多实际问题中，例如经济、管理、军事、科学和工程 设计等领域，衡量一个方案的好坏往往难以用一个指标来 判断，而需要用多个目标来比较，而这些目标有时不甚协 调，甚至是矛盾的。因此有许多学者致力于这方面的研

2、究 。1896年法国经济学家 V. 帕雷托最早研究不可比较目标的优 化问题，之后，J.冯诺伊曼、H.W.库恩、A.W.塔克、 A.M.日夫里翁等数学家做了深入的探讨，但是尚未有一个完全令人满意的定义。3求解多目标规划的方法大体上有以下几种：一种是化多为少的方法 ， 即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法 等；另一种叫分层序列法，即把目标按其重要性给出一个序列 ，每次都在前一目标最优解集内求下一个目标最优解，直 到求出共同的最优解。对多目标的线性规划除以上方法外还可以适当修正单纯形 法来求解；还有一种称为层次分析法，是由美国运筹学家 沙旦于70年代提出的，

3、这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据 的情况更为实用。 多目标规划模型（一）任何多目标规划问题，都由两个基本部分组成：（1）两个以上的目标函数；（2）若干个约束条件。 （二）对于多目标规划问题，可以将其数学模型一般地描 写为如下形式： 一 多目标规划及其非劣解 式中： 为决策变量向量。 缩写形式：有n个决策变量，k个目标函数， m个约束方程，则：Z=F(X) 是k维函数向量，(X)是m维函数向量；G是m维常数向量；（1）（2） 对于线性多目标规划问题，可以进一步用矩阵表示：式中： X 为n 维决策变量向量；C 为kn 矩阵，即目标函数系数矩阵；B 为

4、mn 矩阵，即约束方程系数矩阵；b 为m 维的向量，即约束向量。 多目标规划的非劣解 多目标规划问题的求解不能只追求一个目标的最优化（ 最大或最小），而不顾其它目标。对于上述多目标规划问题，求解就意味着需要做出如下 的复合选择： 每一个目标函数取什么值，原问题可以得到最满意 的解决？ 每一个决策变量取什么值，原问题可以得到最满意 的解决 ？在图1中，max(f1, f2) .就方案和来说，的 f2 目标值比大，但其目标值 f1 比小，因此无法确定这两个方案的优与劣。在各个方案之间，显然：比好，比好, 比好, 比好。 非劣解可以用图1说明。图1 多目标规划的劣解与非劣解9而对于方案、 、之间则无

5、法确定优 劣，而且又没有比它们 更好的其他方案，所以 它们就被称为多目标规 划问题的非劣解或有效 解， 其余方案都称为劣解。 所有非劣解构成的集合 称为非劣解集。当目标函数处于冲突状态时，就不会存在使所有目 标函数同时达到最大或最小值的最优解，于是我们只能 寻求非劣解。 效用最优化模型 罚款模型 约束模型 目标规划模型二 多目标规划求解技术简介 为了求得多目标规划问题的非劣解，常常需要将 多目标规划问题转化为单目标规划问题去处理。实现 这种转化，有如下几种建模方法。是与各目标函数相关的效用函数的和函数。 方法一 效用最优化模型（线性加权法） （1） （2） 思想：规划问题的各个目标函数可以通过

6、一定的方式进行求和运算。这种方法将一系列的目标函数与效用函数建立相关关系，各目标之间通过效用函数协调，使多目标规划问题转化为传统的单目标规划问题： 在用效用函数作为规划目标时，需要确定一组权值 i 来反映原问题中各目标函数在总体目标中的权重，即 ：式中， i 应满足：向量形式：方法二 罚款模型（理想点法） 思想: 规划决策者对每一个目标函数都能提出所期望的值 （或称满意值）； 通过比较实际值 fi 与期望值 fi* 之间的偏差来选择问题的 解，其数学表达式如下：或写成矩阵形式： 式中， 是与第i个目标函数相关的权重；A是由 (i=1,2,k )组成的mm对角矩阵。理论依据 ：若规划问题的某一目

7、标可以给出一个可供选 择的范围，则该目标就可以作为约束条件而被排除出目标 组，进入约束条件组中。假如，除第一个目标外，其余目标都可以提出一个可供选 择的范围，则该多目标规划问题就可以转化为单目标规划 问题： 方法三 约束模型（极大极小法） 15方法四 目标规划模型（目标规划法） 目标规划与线性规划相比，有以下优点： 1. 线性规则只讨论一个线性目标函数在一组线性约 束条件下的极值问题。 实际问题中，往往要考虑多个目标的决策问题，这些 目标可能互相矛盾，也可能没有统一的度量单位，很 难比较。目标规划就能够兼顾地处理多种目标的关系 ，求得更切合实际的解。 2.线性规划是在满足所有约束条件的可行解中

8、求得最 优解。而在实际问题中往往存在一些相互矛盾的约束 条件，如何在这些相互矛盾的约束条件下，找到一个 满意解就是目标规划所要讨论的问题。163.线性规划问题中的约束条件是不分主次、同等对待 的，是一律要满足的“硬约束”。而在实际问题中， 多个目标和多个约束条件不一定是同等重要的，而是 有轻重缓急和主次之分的，如何根据实际情况确定模 型和求解，使其更合实际是目标规划的任务。 4.线性规划的最优解可以说是绝对意义下的最优，为 求得这个最优解，往往要花去大量的人力、物力和才 力。而在实际问题中，却并不一定需要去找这种最优 解。目标规划所求的满意解是指尽可能地达到或接近 一个或几个已给定的指标值，这

9、种满意解更能够满足 实际的需要。 因此可以认为，目标规划更能够确切描述和解 决经济管理中的许多实际问题。目前目标规划的理论 和方法已经在经济计划、生产管理、经营管理、市场 分析、财务管理等方面得到广泛的应用。三 目标规划方法通过前面的介绍和讨论，我们知道，目标规划方法 是解决多目标规划问题的重要技术之一。这一方法是美国学者查恩斯（A.Charnes）和库 伯（W.W.Cooper）于1961年在线性规划的基础上提 出来的。后来，查斯基莱恩（U.Jaashelainen）和李 （Sang.Lee）等人，进一步给出了求解目标规划问题 的一般性方法单纯形方法。 目标规划模型 目标规划的图解法 求解目

10、标规划的单纯形方法 目标规划模型 给定若干目标以及实现这些目标的优先顺 序，在有限的资源条件下，使总的偏离目 标值的偏差最小。1.基本思想 ：2.目标规划的有关概念例1：某一个企业利用某种原材料和现有设备可生产甲、 乙两种产品，其中，甲、乙两种产品的单价分别为8万元 和10万元；生产单位甲、乙两种产品需要消耗的原材料 分别为2个单位和1个单位，需要占用的设备分别为1单位 台时和2单位台时；原材料拥有量为11个单位；可利用的 设备总台时为10单位台时。试问：如何确定其生产方案 使得企业获利最大？由于决策者所追求的唯一目标是使总产值达到最大 ，这个企业的生产方案可以由如下线性规划模型给出： 求x1

11、，x2，使 将上述问题化为标准后，用单纯形方法求解可得最佳决策方案为: （万元）。 甲乙拥有量 原材料2111 设备(台时)1210 单件利润810生产甲、乙两种产品 ，有关数据如表所示 。试求获利最大的生 产方案？但是，在实际决策时，企业领导者必须考虑市场等 一系列其它条件，如：超过计划供应的原材料，需用高价采购，这就会使生产成本增加。 应尽可能地充分利用设备的有效台时，但不希望加班。 应尽可能达到并超过计划产值指标56万元。这样，该企业生产方案的确定，便成为一个多目标决 策问题，这一问题可以运用目标规划方法进行求解。 根据市场信息，甲种产品的需求量有下降的趋势，因 此甲种产品的产量不应大于

12、乙种产品的产量。21假定有L个目标，K个优先级(KL)，n个变量。在同一 优先级pk中不同目标的正、负偏差变量的权系数分别 为kl+ 、kl- ，则多目标规划问题可以表示为：n 目标规划模型的一般形式 目标函数目标约束绝对约束非负约束22在以上各式中，kl+ 、kl- 分别为赋予pl优先因子的第 k 个目标的正、负偏差变量的权系数， gk为第 k个目标的预期值， xj为决策变量， dk+ 、dk- 分别为第 k 个目标的正、负偏差变量，目标函数目标约束绝对约束非负约束目标规划数学模型中的有关概念。 (1)目标值和正、负偏差变量 目标值是预先给定的某个目标的一个期望值。决策值是当 决策变量选定以

13、后，目标函数的对应值。实现值和目标值之 间的差异称为偏差变量(事先无法确定的未知量),正偏差变量 d +表示决策值超过目标值的部分,负偏差变量d -表示决策值未 达到目标值的部分。因为决策值不可能既超过目标值同时又未达到目标值，故 有 d +d - =0成立。 在引入了目标值和正、负偏差变量后，可以将原目标函数 加上负偏差变量d - ，减去正偏差变量d + ，并其等于目标值， 这样形成一个新的函数方程，把它作为一个新的约束条件， 加入到原问题中去，称这种新的约束条件为目标约束。(2) 绝对约束和目标约束 绝对约束，必须严格满足的等式约束和不等式约束， 譬如，线性规划问题的所有约束条件都是绝对约

14、束，不能 满足这些约束条件的解称为非可行解，所以它们是硬约束 。目标约束，目标规划所特有的，可以将约束方程右端 项看作是追求的目标值，在达到此目标值时允许发生正的 或负的偏差 ，可加入正负偏差变量，是软约束。线性规划问题的目标函数，在给定目标值和加入正 、负偏差变量后可以转化为目标约束，也可以根据问题的 需要将绝对约束转化为目标约束。 (3)目标函数凡满足目标约束和绝对约束的解，应如何判别它的优劣呢 ？从决策者的要求分析,它总希望得到的结果与规定的目标 值之间的偏差愈小愈好，目标函数是按照各目标约束的正 、负偏差变量和赋予相应的优先因子而构造的函数。当每 一目标确定后，尽可能缩小与目标值的偏离

15、。因此，目标 函数只能是：a) 要求恰好达到目标值，就是正、负偏差变量都要尽 可能小,即 b) 要求不超过目标值，即允许达不到目标值，就是正 偏差变量要尽可能小，即c) 要求超过目标值，也就是超过量不限，但负偏差变量 要尽可能小，即 基本形式有三种：对于由绝对约束转化而成的目标约束，也可以根据需要， 按照上面三种方式，将正、负偏差变量列入目标函数中去 。若要区别具有相同优先因子 pl 的目标的差别，就可以 分别赋予它们不同的权系数i* ( i=1,2,k )。这些优先因子和权系数都由决策者按照具体情况而定。(4)优先因子（优先等级）与权系数一个规划问题,常常有若干个目标，决策者对各个目标的考虑,往往是有主次的。凡要求第一位达到的目标赋予优先因子 p1 ，次位的目标赋予优先因子 p2 ，并规定 pl pl+1 (l=1,2,) 表示 pl 比 pl+1 有更大的优先权。即:首先保证p1 级目标的实现，这时可以不考虑次级目标；而p2级目标是在实现p1 级目标的基础上考虑的；依此类推。目标规划问题的求解是分级进行的，首先要求满足子 p1 级 目标的解；然后再保证 p2 级目标不被破坏的前提下依次 类推。总之，是在不破坏上一级目标的前提下，实现下一级 目标的最优。因此，这样最后求出的解就不是通常意义下的 最优