lingo-多目标规划模型.ppt
《lingo-多目标规划模型.ppt》由会员分享,可在线阅读,更多相关《lingo-多目标规划模型.ppt(92页珍藏版)》请在咨信网上搜索。
1、 多目标决策方法多目标决策方法 李小飞.l多目标决策的基本概念多目标决策的基本概念l多目标决策的数学模型及其非劣解多目标决策的数学模型及其非劣解l多目标决策建模的应用实例多目标决策建模的应用实例 .用LINGO软件求解目标规划问题.1.求解方法概述LINGO(或LINDO)不能直接求解目标规划问题,但可以通过逐级求解线性规划的方法,求得目标规划问题的满意解。.2.示例例例1 用LINGO求解目标规划问题.解:首先对应于第一优先等级,建立线性规划问题:用LINGO求解,得最优解0,最优值为0。具体求解过程如下:.启动LINGO软件,窗口如图1所示。图1.在LINGO工作区中录入以下程序(参见图2
2、)model:min=d1;10*x1+15*x2+d1_-d1=40;END其中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运算
3、后输出为(参见图5):图5.对应于第三优先等级,将 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、难以作相互比较。.目标之间的矛盾性是指,如果改进某一目标的值,可能会使另一个或一些目标变差。正因为各目标的不可公度性和相互之间的矛盾性,多目标决策问题不能简单的作为单目标问题来处理。必须深入研究其特征,特别是解的性质。单目标决策一般有最优解,且往往是唯一的,有时可能存在无限多个解。但是这里的“最优”往往带有片面性,不能全而准确的反映决策者的偏好信息。多目标决策问题不存在所谓的“最优”解,只存在满意解。满意解指决策者对于有关的所有目标值都认为满意。.对于单目标决策问题的解一般具有全序最优性,而多目标决策问题的可行方案集中的各方案只有部分序而非全序,并且一般不存在满足最优性的可行解,而只有矛盾性,
9、即,尽管某一个可行解能使n个目标中的某个目标最优,但不可能使其他的n-1个目标同时最优。各目标之间的这种矛盾性是多目标问题的基本特性,不具有这种特性的问题实质上是单目标优化问题。可行解的非劣性正是多目标问题矛盾性所引起的。.非劣性的意义可解释为:设某一可行解 对应的目标函数值为 ,若不存在其他可行解既能在 的基础上改进某一目标的值,同时又不至于使任何别的目标的值变差。在不同的研究方向,非劣性可能有不同的说法,比如,数学家、经济学家和统计学家又称之为“有效性”或“最优性”。下面举一个简单的例子来说明非劣性。.例 试分析下表所示四个方案的非劣性。方案方案目标函数目标函数方案的性质方案的性质F1(x
10、)F1(x)F2(x)F2(x)X1X110102121非劣非劣X2X214141818非劣非劣X3X312121616劣劣X4X48 82020劣劣.解:因 故 。同理,。因此四个方案的优劣性见表。.在在图图1中中,max(f1,f2).就就方方 案案 和和 来来 说说,的的 f2 目目标标值值比比大大,但但其其目目标标值值 f1 比比小小,因因此此无无法法确确定定这这两两个个方方案案的的优优与与劣。劣。在在各各个个方方案案之之间间,显显然然:比比好好,比比好好,比比好好,比比好好。非劣性非劣性可以用下图说明。图图 多目标规划的劣解与非劣解多目标规划的劣解与非劣解.第二部分 多目标决策的数学
11、模型及其非劣解.一、多目标决策的数学模型一、多目标决策的数学模型(一)任何多目标决策问题,都由两个基本部分组成:(1)两个以上的目标函数;(2)若干个约束条件。(二)对于多目标决策问题,可以将其数学模型一般地描写为如下形式:式中:为决策变量向量。.缩写形式:有n个决策变量,k个目标函数,m个约束方程,则:Z=F(X)是k维函数向量,(X)是m维函数向量;G是m维常数向量;.多目标规划问题的求解不能只追求一个目标的最优化(最大或最小),而不顾其它目标。对于上述多目标规划问题,求解就意味着需要做出如下的复合选择:每一个目标函数取什么值,原问题可以得到最满意的解决?每一个决策变量取什么值,原问题可以
12、得到最满意的解决?.如上例的各个方案之间,比好,比好,比好,比好。图图 多目标规划的劣解与非劣解多目标规划的劣解与非劣解.而对于方案、之间则无法确定优劣,而且又没有比它们更好的其他方案,所以它们就被称为多目标规划问题的非劣解或有效解,其余方案都称为劣解。所有非劣解构成的集合称为非劣解集。当目标函数处于冲突状态时,就不会存在使所有目标函数同时达到最大或最小值的最优解,于是我们只能寻求非劣解。.效用最优化模型效用最优化模型 罚款模型罚款模型 约束模型约束模型 目标规划模型目标规划模型二、多目标决策的非劣解的求解方法二、多目标决策的非劣解的求解方法 为了求得多目标规划问题的非劣解,常常需要将多目标规
13、划问题转化为单目标规划问题去处理。实现这种转化,有如下几种建模方法。.是与各目标函数相关的效用函数的和函数。方法一方法一 效效用最优化模型用最优化模型(线性加权法线性加权法)思想:规划问题的各个目标函数可以通过一定的方式进行求和运算。这种方法将一系列的目标函数与效用函数建立相关关系,各目标之间通过效用函数协调,使多目标规划问题转化为传统的单目标规划问题:但困难是要确定合理的权系数,以反映不同目标之间的重要程度。.在用效用函数作为规划目标时,需要确定一组权值 i 来反映原问题中各目标函数在总体目标中的权重,即:式中,i 应满足:向量形式:.方法二方法二 罚款模型罚款模型(理想点法)(理想点法)思
14、想:规划决策者对每一个目标函数都能提出所期望的值(或称满意值);通过比较实际值 fi 与期望值 fi*之间的偏差来选择问题的解,其数学表达式如下:或写成矩阵形式:式中,是与第i个目标函数相关的权重;A是由 (i=1,2,k)组成的mm对角矩阵。.理论依据:若规划问题的某一目标可以给出一个可供选择的范围,则该目标就可以作为约束条件而被排除出目标组,进入约束条件组中。假如,除第一个目标外,其余目标都可以提出一个可供选择的范围,则该多目标规划问题就可以转化为单目标规划问题:方法三方法三 约束模型(极大极小法)约束模型(极大极小法).方法四方法四 目标规划模型(目标规划法)目标规划模型(目标规划法)需
15、要预先确定各个目标的期望值 fi*,同时给每一个目标赋予一个优先因子和权系数,假定有K个目标,L个优先级(LK),目标规划模型的数学形式为:式中:di+和 di分别表示与 fi 相应的、与fi*相比的目标超过值和不足值,即正、负偏差变量正、负偏差变量;pl表示第l个优先级;lk+、lk-表示在同一优先级 pl 中,不同目标的正、负偏差变量的权系数。.1.基本思想:给定若干目标以及实现这些目标的优先顺序,在有限的资源条件下,使总的偏离目标值的偏差最小。三、目标规划方法三、目标规划方法.假定有L个目标,K个优先级(KL),n个变量。在同一优先级pk中不同目标的正、负偏差变量的权系数分别为kl+、k
16、l-,则多目标规划问题可以表示为:2.2.目标规划模型的一般形式目标规划模型的一般形式 目标函数目标约束绝对约束非负约束.在以上各式中,kl+、kl-分别为赋予pl优先因子的第 k 个目标的正、负偏差变量的权系数,gk为第 k个目标的预期值,xj为决策变量,dk+、dk-分别为第 k 个目标的正、负偏差变量。目标函数目标函数目标约束目标约束绝对约束绝对约束非负约束非负约束.目标规划数学模型中的有关概念。目标规划数学模型中的有关概念。(1)偏差变量偏差变量 在目标规划模型中,除了决策变量外,还需要引入正、负偏差变量 d+、d-。其中,正偏差变量表示决策值超过目标值的部分,负偏差变量表示决策值未达
17、到目标值的部分。因为决策值不可能既超过目标值同时又未达到目标值,故有d+d-=0成立。(2)绝对约束和目标约束绝对约束和目标约束 绝对约束,必须严格满足的等式约束和不等式约束,譬如,线性规划问题的所有约束条件都是绝对约束,不能满足这些约束条件的解称为非可行解,所以它们是硬约束。.目标约束,目标规划所特有的,可以将约束方程右端项看作是追求的目标值,在达到此目标值时允许发生正的或负的偏差,可加入正负偏差变量,是软约束软约束。线性规划问题的目标函数,在给定目标值和加入正、负偏差变量后可以转化为目标约束,也可以根据问题的需要将绝对约束转化为目标约束。.若要区别具有相同优先因子 pl 的目标的差别,就可
18、以分别赋予它们不同的权系数i*(i=1,2,k)。这些优先因子和权系数都由决策者按照具体情况而定。(3)优先因子(优先等级)与权系数优先因子(优先等级)与权系数 一个规划问题,常常有若干个目标,决策者对各个目标的考虑,往往是有主次的。凡要求第一位达到的目标赋予优先因子 p1,次位的目标赋予优先因子 p2,并规定plpl+1(l=1,2,.)表示 pl 比 pl+1 有更大的优先权。即:首先保证 p1 级目标的实现,这时可以不考虑次级目标;而p2级目标是在实现p1 级目标的基础上考虑的;依此类推。.(4)(4)目标函数目标函数 目标规划的目标函数(准则函数)是按照各目标约束的正、负偏差变量和赋予
19、相应的优先因子而构造的。当每一目标确定后,尽可能缩小与目标值的偏离。因此,目标规划的目标函数只能是:a)要求恰好达到目标值,就是正、负偏差变量都要尽可能小,即 b)要求不超过目标值,即允许达不到目标值,就是正偏差变量要尽可能小,即 c)要求超过目标值,也就是超过量不限,但负偏差变量要尽可能小,即 基本形式有三种:对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标函数。.(1)目标规划数学模型的形式有:线性模型、非线性模型、整数模型、交互作用模型等;(2)一个目标中的两个偏差变量di-、di+至少一个等于零,偏差变量向量的叉积等于零:dd=0;(3)一般目标规划是将多个
20、目标函数写成一个由偏差变量构成的函数求最小值,按多个目标的重要性,确定优先等级,顺序求最小值;(4)按决策者的意愿,事先给定所要达到的目标值。当期望结果不超过目标值时,目标函数求正偏差变量最小;当期望结果不低于目标值时,目标函数求负偏差变量最小;当期望结果恰好等于目标值时,目标函数求正负偏差变量之和最小。评注:评注:.(5)由目标构成的约束称为目标约束,目标约束具有更大的弹性,允许结果与所制定的目标值存在正或负的偏差;如果决策者要求结果一定不能有正或负的偏差,这种约束称为系统约束;(6)目标的排序问题。多个目标之间有相互冲突时,决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法,
21、构造各目标的权系数,依据权系数的大小确定目标顺序;(7)合理的确定目标数。目标规划的目标函数中包含了多个目标,决策者对于具有相同重要性的目标可以合并为一个目标,如果同一目标中还想分出先后次序,可以赋予不同的权系数,按系数大小再排序。.(8)多目标决策问题多目标决策研究的范围比较广泛,在决策中,可能同时要求多个目标达到最优例如,企业在对多个项目投资时期望收益率尽可能最大,投资风险尽可能最小,属于多目标决策问题,本章的目标规划尽管包含有多个目标,但还是按单个目标求偏差变量的最小值,目标函数中不含有决策变量,目标规划只是多目标决策的一种特殊情形本章不讨论多目标规划的求解方法,只给出利用lingo软件
22、求解线性多目标规划的简单程序。.引例引例1 生产计划问题 甲 乙 资源限额 材料 2 3 24 工时 3 2 26 单位利润 4 3 现在工厂领导要考虑市场等一系列其他因素,提出如下目标:(1)根据市场信息,甲产品的销量有下降的趋势,而乙产品的销量有上升的趋势,故考虑乙产品的产量应大于甲产品的产量。(2)尽可能充分利用工时,不希望加班。(3)应尽可能达到并超过计划利润30元。现在的问题是:在原材料不能超计划使用的前提下,如何安排生产才能使上述目标依次实现?.解:(1)决策变量:设每天生产甲、乙两种产品各为x1和x2 偏差变量:对于每一目标,我们引进正、负偏差变量。如对于目标1,设d1-表示乙产
23、品的产量低于甲产品产量的数,d1+表示乙产品的产量高于甲产品产量的数。称它们分别为产量比较的负偏差变量和正偏差变量。则对于目标1,可将它表示为等式约束的形式 -x1+x2+d1-d1+=0 (目标约束)同样设d2-和d2+分别表示安排生产时,低于可利用工时和高于可利用工时,即加班工时的偏差变量,则对目标2,有 3x1+2x2+d2-d2+=26 对于目标3,设d3-和d3+分别表示安排生产时,低于计划利润30元和高于计划利润30元的偏差变量,有:.4x1+3x2+d3-d3+=30 (2)约束条件:有资源约束和目标约束 资源约束:2x1+3x224 目标约束:为上述各目标中得出的约束 (3)目
24、标函数:三个目标依次为:minZ1=d1-,minZ2=d2+d2-,minZ3=d3-因而该问题的数学模型可表述如下:minZ1=d1-,minZ2=d2+d2-,minZ3=d3-2x1+3x224 st -x1+x2+d1-d1+=0 3x1+2x2+d2-d2+=26 4x1+3x2+d3-d3+=30.例 某企业生产甲、乙两种产品,需要用到A,B,C 三种设备,关于产品的赢利与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标:甲乙设备的生产能力(h)A(h/件)2212B(h/件)4016C(h/件)0515赢利(元/件)200300四、多目标规划问题求解的四
25、、多目标规划问题求解的LINGO程序程序.(1)力求使利润指标不低于1500 元;(2)考虑到市场需求,甲、乙两种产品的产量比应尽量 保持1:2;(3)设备A 为贵重设备,严格禁止超时使用;(4)设备C 可以适当加班,但要控制;设备B 既要求充分利用,又尽可能不加班。在重要性上,设备B是设备C 的3倍。建立相应的目标规划模型并求解。甲乙设备的生产能力(h)A(h/件)2212B(h/件)4016C(h/件)0515赢利(元/件)200300.解:设备A 是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润,因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持1:2 的比例,列为第
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- lingo 多目标 规划 模型
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。