多目标规划模型.ppt
《多目标规划模型.ppt》由会员分享,可在线阅读,更多相关《多目标规划模型.ppt(92页珍藏版)》请在麦多课文档分享上搜索。
1、多目标决策方法,李小飞,多目标决策的基本概念 多目标决策的数学模型及其非劣解 多目标决策建模的应用实例,用LINGO软件求解目标规划问题,1. 求解方法概述,LINGO(或LINDO)不能直接求解目标规划问题,但可以通过逐级求解线性规划的方法,求得目标规划问题的满意解。,2. 示例,例1 用LINGO求解目标规划问题,解:首先对应于第一优先等级,建立线性规划问题:用LINGO求解,得最优解0,最优值为0。具体求解过程如下:,启动LINGO软件,窗口如图1所示。,图1,在LINGO工作区中录入以下程序(参见图2) model: min=d1; 10*x1+15*x2+d1_-d1=40; END
2、 其中x1、x2分别代表决策变量 、 ;d1_、d1分别代表偏差变量 、 。,图2,在菜单LINGO下点选“Solve”,或按复合键“Ctrl+S”进行求解。LINGO弹出求解结果报告(参见图3): 详细信息如下,图3,对应于第二优先等级,将 0作为约束条件,建立线性规划问题:,用LINGO求解,得最优解 0 , ,最优值为6。具体LINGO程序及输出信息如下:LINGO程序为(参见图4):,model: min=d2_; 10*x1+15*x2+d1_-d1=40; x1+x2+d2_-d2=10; d1=0; END,图4,LINGO运算后输出为(参见图5):,图5,对应于第三优先等级,将
3、 0, 作为约束条件,建立线性规划问题:,用LINGO求解,得最优解是 ,最优值为7。具体LINGO程序及输出信息如下(参见图6) :,model: min=d3_; 10*x1+15*x2+d1_-d1=40; x1+x2+d2_-d2=10; x2+d3_-d3=7; d1=0; d2_=6; END,图6,LINGO运算后输出为:(参见图7),图7,因此, 0, 就是目标规划的满意解。,第一部分 多目标决策的基本概况,本章将从多目标决策(也称多目标规划)方法的作用出发,通过分析简单的多目标决策问题的几个案例,阐述多目标决策的基本概念。任何决策问题的解决主要依赖于所谓的决策者和分析者。决策
4、者一般指有权挑选行动方案,并能够从中选择满意方案作为最终决策的人员。政府官员、企业行政管理人员均为某类问题的决策者。决策者的作用是:评价和判断各目标的相对重要性;根据目标的当前水平值以及主观的判断和经验,提供关于决策方案的偏好信息。分析者一般指能够提供可行方案和各目标之间的折中信息的人或机器,比如经济学家、工程师、系统分析员、社会学家、计算机等。,只有一个目标的决策问题称为单目标决策(或 单目标规划)问题,相应的解题方法称为单目标方 法。具有2个或2个以上目标的决策问题称为多目标 决策问题,相应的求解方法称为多目标方法。从方 法的特点来看,单目标方法强调分析者的作用,忽 视决策者的作用。而多目
5、标方法则由决策者探寻 和确定备选的可行方案范围,评价目标的相对价值。 从求解过程来看,单目标方法采用统一的单一度量 单位,向决策者提供唯一的最优方案。,由于模型的不准确性和单一目标的片面性,这 种所谓最优的方案并不一定是决策者满意的。自然, 用这种最优方案作为决策者的最终决策具有强迫性 质,往往难以为决策者接受。另一方面,多目标方 法向决策者提供经过仔细选择的备选方案(多种方 案)。这样使得决策者有可能利用自己的知识和经 验对这些方案进行评价和判断,从中找出满意方案 或给出偏好信息以及寻找更多的备选方案。概括起来,多目标决策方法处理实际决策问题 有三个方面的优点:(1)加强了决策者在决策过程
6、中的作用;(2)可以得到范围更为广泛的备选决策 方案;(3)决策问题的模型和分析者对问题的直觉 将更加现实。,多目标决策问题的案例及特点我们介绍两个日常生活中常见的决策问题。第一个是顾客到商店购买衣服。对于顾客而言,购买衣服就是一个决策问题,顾客本人是决策者,各种各样的衣服是行动方案集。该决策问题的解就是顾客最终买到一件合适的衣服(或选择一个满意的方案)。那么,一件衣服(即一个方案)合适否(满意否)应该根据几个指标来评价,比如衣服的质量、价格、大小、式样、颜色等。因此,顾客购买衣服的问题是多目标决策问题。又如,公务人员外出办事总要乘某种交通工具。这也是一个决策问题,决策者是公务员,备选方案是可
7、利用的交通工具。公务员为了选择合适的交通工具,需要考虑几个指标,比如:时间、价格、舒适性、方便程度等。显然这也是一个多目标决策问题。,在生产系统、工程系统、社会经济系统中,多目标决策问题更是屡见不鲜。比如在炼油厂的生产计划中,基本的决策问题是如何根据企业的外部环境与内部条件,制定出具体的作业计划。该计划应能使企业的各种主要的经济指标达到预定的目标。这些指标包括:利润、原油量、成本、能耗等。其他企业一般也有类似的多目标计划决策问题。多目标决策问题有两个共同的特点,即各目标的不可公度性和相互之间的矛盾性。所谓目标的不可公度性指各目标之间没有统一的量纲,因此难以作相互比较。,目标之间的矛盾性是指,如
8、果改进某一目标的值,可能会使另一个或一些目标变差。正因为各目标的不可公度性和相互之间的矛盾性,多目标决策问题不能简单的作为单目标问题来处理。必须深入研究其特征,特别是解的性质。单目标决策一般有最优解,且往往是唯一的,有时可能存在无限多个解。但是这里的“最优”往往带有片面性,不能全而准确的反映决策者的偏好信息。多目标决策问题不存在所谓的“最优”解,只存在满意解。满意解指决策者对于有关的所有目标值都认为满意。,对于单目标决策问题的解一般具有全序最优性,而多目标决策问题的可行方案集中的各方案只有部分序而非全序,并且一般不存在满足最优性的可行解,而只有矛盾性,即,尽管某一个可行解能使n个目标中的某个目
9、标最优,但不可能使其他的n-1个目标同时最优。各目标之间的这种矛盾性是多目标问题的基本特性,不具有这种特性的问题实质上是单目标优化问题。可行解的非劣性正是多目标问题矛盾性所引起的。,非劣性的意义可解释为:设某一可行解 对应的目标函数值为 ,若不存在其他可行解既能在 的基础上改进某一目标的值,同时又不至于使任何别的目标的值变差。在不同的研究方向,非劣性可能有不同的说法,比如,数学家、经济学家和统计学家又称之为“有效性”或“最优性”。下面举一个简单的例子来说明非劣性。,例 试分析下表所示四个方案的非劣性。,解:因 故 。 同理, 。 因此四个方案的优劣性见表。,在图1中,max(f1, f2) .
10、就方案和来说,的 f2 目标值比大,但其目标值 f1 比小,因此无法确定这两个方案的优与劣。在各个方案之间,显然:比好,比好, 比好, 比好。,非劣性可以用下图说明。,图 多目标规划的劣解与非劣解,第二部分 多目标决策的数学模型及其非劣解,一、多目标决策的数学模型,(一)任何多目标决策问题,都由两个基本部分组成:(1)两个以上的目标函数;(2)若干个约束条件。,(二)对于多目标决策问题,可以将其数学模型一般地描写为如下形式:,式中: 为决策变量向量。,缩写形式:,有n个决策变量,k个目标函数,m个约束方程, 则:Z=F(X) 是k维函数向量,(X)是m维函数向量;G是m维常数向量;,多目标规划
11、问题的求解不能只追求一个目标的最优化(最大或最小),而不顾其它目标。 对于上述多目标规划问题,求解就意味着需要做出如下的复合选择:每一个目标函数取什么值,原问题可以得到最满意的解决?每一个决策变量取什么值,原问题可以得到最满意的解决 ?,如上例的各个方案之间,比好,比好, 比好, 比好。,图 多目标规划的劣解与非劣解,而对于方案、之间则无法确定优劣,而且又没有比它们更好的其他方案,所以它们就被称为多目标规划问题的非劣解或有效解,其余方案都称为劣解。 所有非劣解构成的集合称为非劣解集。,当目标函数处于冲突状态时,就不会存在使所有目标函数同时达到最大或最小值的最优解,于是我们只能寻求非劣解。,效用
12、最优化模型罚款模型约束模型目标规划模型,二、多目标决策的非劣解的求解方法,为了求得多目标规划问题的非劣解,常常需要将多目标规划问题转化为单目标规划问题去处理。实现这种转化,有如下几种建模方法。,是与各目标函数相关的效用函数的和函数。,方法一 效用最优化模型(线性加权法),思想:规划问题的各个目标函数可以通过一定的方式进行求和运算。这种方法将一系列的目标函数与效用函数建立相关关系,各目标之间通过效用函数协调,使多目标规划问题转化为传统的单目标规划问题:,但困难是要确定合理的权系数,以反映不同目标之间的重要程度。,在用效用函数作为规划目标时,需要确定一组权值 i 来反映原问题中各目标函数在总体目标
13、中的权重,即:,式中, i 应满足:,向量形式:,方法二 罚款模型(理想点法),思想: 规划决策者对每一个目标函数都能提出所期望的值(或称满意值);通过比较实际值 fi 与期望值 fi* 之间的偏差来选择问题的解,其数学表达式如下:,或写成矩阵形式:,式中, 是与第i个目标函数相关的权重;A是由 (i=1,2,k )组成的mm对角矩阵。,理论依据 :若规划问题的某一目标可以给出一个可供选择的范围,则该目标就可以作为约束条件而被排除出目标组,进入约束条件组中。 假如,除第一个目标外,其余目标都可以提出一个可供选择的范围,则该多目标规划问题就可以转化为单目标规划问题:,方法三 约束模型(极大极小法
14、),方法四 目标规划模型(目标规划法),需要预先确定各个目标的期望值 fi* ,同时给每一个目标赋予一个优先因子和权系数,假定有K个目标,L个优先级( LK),目标规划模型的数学形式为:,式中:di+ 和 di分别表示与 fi 相应的、与fi* 相比的目标超过值和不足值,即正、负偏差变量;pl表示第l个优先级;lk+、lk-表示在同一优先级 pl 中,不同目标的正、负偏差变量的权系数。,1.基本思想 :给定若干目标以及实现这 些目标的优先顺序,在有限的资源条件下,使总的偏离目标值的偏差最小。,三、目标规划方法,假定有L个目标,K个优先级(KL),n个变量。在同一优先级pk中不同目标的正、负偏差
15、变量的权系数分别为kl+ 、kl- ,则多目标规划问题可以表示为:,2.目标规划模型的一般形式,目标函数,目标约束,绝对约束,非负约束,在以上各式中,kl+ 、kl- 分别为赋予pl优先因子的第 k 个目标的正、负偏差变量的权系数,gk为第 k个目标的预期值,xj为决策变量,dk+ 、dk- 分别为第 k 个目标的正、负偏差变量。,目标函数,目标约束,绝对约束,非负约束,目标规划数学模型中的有关概念。,(1) 偏差变量在目标规划模型中,除了决策变量外,还需要引入正、负偏差变量 d +、d - 。其中,正偏差变量表示决策值超过目标值的部分,负偏差变量表示决策值未达到目标值的部分。因为决策值不可能
16、既超过目标值同时又未达到目标值,故有d +d - =0成立。,(2) 绝对约束和目标约束 绝对约束,必须严格满足的等式约束和不等式约束,譬如,线性规划问题的所有约束条件都是绝对约束,不能满足这些约束条件的解称为非可行解,所以它们是硬约束。,目标约束,目标规划所特有的,可以将约束方程右端项看作是追求的目标值,在达到此目标值时允许发生正的或负的偏差 ,可加入正负偏差变量,是软约束。线性规划问题的目标函数,在给定目标值和加入正、负偏差变量后可以转化为目标约束,也可以根据问题的需要将绝对约束转化为目标约束。,若要区别具有相同优先因子 pl 的目标的差别,就可以分别赋予它们不同的权系数i* ( i=1,
17、2,k )。这些优先因子和权系数都由决策者按照具体情况而定。,(3)优先因子(优先等级)与权系数一个规划问题,常常有若干个目标,决策者对各个目标的考虑,往往是有主次的。凡要求第一位达到的目标赋予优先因子 p1 ,次位的目标赋予优先因子 p2 ,并规定plpl+1 (l=1,2,)表示 pl 比 pl+1 有更大的优先权。即:首先保证 p1 级目标的实现,这时可以不考虑次级目标;而p2级目标是在实现p1 级目标的基础上考虑的;依此类推。,(4)目标函数目标规划的目标函数(准则函数)是按照各目标约束的正、负偏差变量和赋予相应的优先因子而构造的。当每一目标确定后,尽可能缩小与目标值的偏离。因此,目标
18、规划的目标函数只能是:,a) 要求恰好达到目标值,就是正、负偏差变量都要尽可能小,即,b) 要求不超过目标值,即允许达不到目标值,就是正偏差变量要尽可能小,即,c) 要求超过目标值,也就是超过量不限,但负偏差变量要尽可能小,即,基本形式有三种:,对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标函数。,(1)目标规划数学模型的形式有:线性模型、非线性模型、整数模型、交互作用模型等; (2)一个目标中的两个偏差变量di-、di+至少一个等于零,偏差变量向量的叉积等于零:dd=0;,(3)一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值,按多个目标的重要性
19、,确定优先等级,顺序求最小值;,(4)按决策者的意愿,事先给定所要达到的目标值。 当期望结果不超过目标值时,目标函数求正偏差变量最小; 当期望结果不低于目标值时,目标函数求负偏差变量最小; 当期望结果恰好等于目标值时,目标函数求正负偏差变量之和最小。,评注:,(5)由目标构成的约束称为目标约束,目标约束具有更大的弹性,允许结果与所制定的目标值存在正或负的偏差;如果决策者要求结果一定不能有正或负的偏差,这种约束称为系统约束;,(6)目标的排序问题。多个目标之间有相互冲突时,决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法,构造各目标的权系数,依据权系数的大小确定目标顺序;,(7)
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
本资源只提供5页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多目标 规划 模型 PPT
![提示](http://www.mydoc123.com/images/bang_tan.gif)