多目标规划模型教材(PPT-92页)

多目标决策方法李小飞多目标决策的基本概念多目标决策的数学模型及其非劣解多目标决策建模的应用实例用LINGO软件求解目标规划问题1.求解方法概述•LINGO（或LINDO）不能直接求解目标规划问题，但可以通过逐级求解线性规划的方法，求得目标规划问题的满意解。2.示例•例1用LINGO求解目标规划问题3,2,1,0,,,710401510..min2133222211121332211jddxxddxddxxddxxtsdPdPdPzjj解：首先对应于第一优先等级，建立线性规划问题：用LINGO求解，得最优解＝0，最优值为0。具体求解过程如下：0,,,401510..min112111211ddxxddxxtsdz启动LINGO软件，窗口如图1所示。图1在LINGO工作区中录入以下程序（参见图2）model:min=d1;10*x1+15*x2+d1_-d1=40;END其中x1、x2分别代表决策变量、；d1_、d1分别代表偏差变量、。1x2x1d1d图2在菜单LINGO下点选“Solve”，或按复合键“Ctrl+S”进行求解。LINGO弹出求解结果报告（参见图3）：详细信息如下图3对应于第二优先等级，将＝0作为约束条件，建立线性规划问题：1d2,1,0,,,010401510..min211222111212jddxxdddxxddxxtsdzjj11dd62d用LINGO求解，得最优解＝0，，最优值为6。具体LINGO程序及输出信息如下：LINGO程序为（参见图4）：model:min=d2_;10*x1+15*x2+d1_-d1=40;x1+x2+d2_-d2=10;d1=0;END图4LINGO运算后输出为（参见图5）：图5对应于第三优先等级，将＝0，作为约束条件，建立线性规划问题：用LINGO求解，得最优解是，，最优值为7。具体LINGO程序及输出信息如下（参见图6）：1d62d3,2,1,0,,,6,0710401510..min2121332222111213jddxxddddxddxxddxxtsdzjj,0,421xx011dd7,632ddmodel:min=d3_;10*x1+15*x2+d1_-d1=40;x1+x2+d2_-d2=10;x2+d3_-d3=7;d1=0;d2_=6;END图6LINGO运算后输出为：（参见图7）图7•因此，＝0，就是目标规划的满意解。,0,421xx11dd7,632dd第一部分多目标决策的基本概况本章将从多目标决策（也称多目标规划）方法的作用出发，通过分析简单的多目标决策问题的几个案例，阐述多目标决策的基本概念。任何决策问题的解决主要依赖于所谓的决策者和分析者。决策者一般指有权挑选行动方案，并能够从中选择满意方案作为最终决策的人员。政府官员、企业行政管理人员均为某类问题的决策者。决策者的作用是：评价和判断各目标的相对重要性；根据目标的当前水平值以及主观的判断和经验，提供关于决策方案的偏好信息。分析者一般指能够提供可行方案和各目标之间的折中信息的人或机器，比如经济学家、工程师、系统分析员、社会学家、计算机等。只有一个目标的决策问题称为单目标决策（或单目标规划）问题，相应的解题方法称为单目标方法。具有2个或2个以上目标的决策问题称为多目标决策问题，相应的求解方法称为多目标方法。从方法的特点来看，单目标方法强调分析者的作用，忽视决策者的作用。而多目标方法则由决策者探寻和确定备选的可行方案范围，评价目标的相对价值。从求解过程来看，单目标方法采用统一的单一度量单位，向决策者提供唯一的最优方案。由于模型的不准确性和单一目标的片面性，这种所谓最优的方案并不一定是决策者满意的。自然，用这种最优方案作为决策者的最终决策具有强迫性质，往往难以为决策者接受。另一方面，多目标方法向决策者提供经过仔细选择的备选方案（多种方案）。这样使得决策者有可能利用自己的知识和经验对这些方案进行评价和判断，从中找出满意方案或给出偏好信息以及寻找更多的备选方案。概括起来，多目标决策方法处理实际决策问题有三个方面的优点：（1）加强了决策者在决策过程中的作用；（2）可以得到范围更为广泛的备选决策方案；（3）决策问题的模型和分析者对问题的直觉将更加现实。多目标决策问题的案例及特点我们介绍两个日常生活中常见的决策问题。第一个是顾客到商店购买衣服。对于顾客而言，购买衣服就是一个决策问题，顾客本人是决策者，各种各样的衣服是行动方案集。该决策问题的解就是顾客最终买到一件合适的衣服（或选择一个满意的方案）。那么，一件衣服（即一个方案）合适否（满意否）应该根据几个指标来评价，比如衣服的质量、价格、大小、式样、颜色等。因此，顾客购买衣服的问题是多目标决策问题。又如，公务人员外出办事总要乘某种交通工具。这也是一个决策问题，决策者是公务员，备选方案是可利用的交通工具。公务员为了选择合适的交通工具，需要考虑几个指标，比如：时间、价格、舒适性、方便程度等。显然这也是一个多目标决策问题。在生产系统、工程系统、社会经济系统中，多目标决策问题更是屡见不鲜。比如在炼油厂的生产计划中，基本的决策问题是如何根据企业的外部环境与内部条件，制定出具体的作业计划。该计划应能使企业的各种主要的经济指标达到预定的目标。这些指标包括：利润、原油量、成本、能耗等。其他企业一般也有类似的多目标计划决策问题。多目标决策问题有两个共同的特点，即各目标的不可公度性和相互之间的矛盾性。所谓目标的不可公度性指各目标之间没有统一的量纲，因此难以作相互比较。目标之间的矛盾性是指，如果改进某一目标的值，可能会使另一个或一些目标变差。正因为各目标的不可公度性和相互之间的矛盾性，多目标决策问题不能简单的作为单目标问题来处理。必须深入研究其特征，特别是解的性质。单目标决策一般有最优解，且往往是唯一的，有时可能存在无限多个解。但是这里的“最优”往往带有片面性，不能全而准确的反映决策者的偏好信息。多目标决策问题不存在所谓的“最优”解，只存在满意解。满意解指决策者对于有关的所有目标值都认为满意。对于单目标决策问题的解一般具有全序最优性，而多目标决策问题的可行方案集中的各方案只有部分序而非全序，并且一般不存在满足最优性的可行解，而只有矛盾性，即，尽管某一个可行解能使n个目标中的某个目标最优，但不可能使其他的n-1个目标同时最优。各目标之间的这种矛盾性是多目标问题的基本特性，不具有这种特性的问题实质上是单目标优化问题。可行解的非劣性正是多目标问题矛盾性所引起的。非劣性的意义可解释为：设某一可行解对应的目标函数值为，若不存在其他可行解既能在的基础上改进某一目标的值，同时又不至于使任何别的目标的值变差。在不同的研究方向，非劣性可能有不同的说法，比如，数学家、经济学家和统计学家又称之为“有效性”或“最优性”。下面举一个简单的例子来说明非劣性。x()Fx()Fx例试分析下表所示四个方案的非劣性。方案目标函数方案的性质F1(x)F2(x)X11021非劣X21418非劣X31216劣X4820劣解：因故。同理，。因此四个方案的优劣性见表。23,12,13,24xxxxxxxx1122(1)(4)108(1)2120(4)FxFxFxFx14xx在图1中，max(f1,f2).就方案①和②来说，①的f2目标值比②大，但其目标值f1比②小，因此无法确定这两个方案的优与劣。在各个方案之间，显然：④比①好，⑤比④好,⑥比②好,⑦比③好……。非劣性可以用下图说明。图多目标规划的劣解与非劣解第二部分多目标决策的数学模型及其非劣解一、多目标决策的数学模型（一）任何多目标决策问题，都由两个基本部分组成：（1）两个以上的目标函数；（2）若干个约束条件。（二）对于多目标决策问题，可以将其数学模型一般地描写为如下形式：)(max(min))(max(min))(max(min))(XfXfXfXFZk21mmgggGXXXX2121)()()()(s.t.式中：为决策变量向量。TnxxxX],,,[21)(max(min)XFZGXts)(..缩写形式：有n个决策变量，k个目标函数，m个约束方程，则：Z=F(X)是k维函数向量，(X)是m维函数向量；G是m维常数向量；多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其它目标。对于上述多目标规划问题，求解就意味着需要做出如下的复合选择：每一个目标函数取什么值，原问题可以得到最满意的解决？每一个决策变量取什么值，原问题可以得到最满意的解决？如上例的各个方案之间，④比①好，⑤比④好,⑥比②好,⑦比③好。图多目标规划的劣解与非劣解而对于方案⑤、⑥、⑦之间则无法确定优劣，而且又没有比它们更好的其他方案，所以它们就被称为多目标规划问题的非劣解或有效解，其余方案都称为劣解。所有非劣解构成的集合称为非劣解集。当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解。效用最优化模型罚款模型约束模型目标规划模型二、多目标决策的非劣解的求解方法为了求得多目标规划问题的非劣解，常常需要将多目标规划问题转化为单目标规划问题去处理。实现这种转化，有如下几种建模方法。)(maxXZGXts)(..是与各目标函数相关的效用函数的和函数。方法一效用最优化模型（线性加权法）思想：规划问题的各个目标函数可以通过一定的方式进行求和运算。这种方法将一系列的目标函数与效用函数建立相关关系，各目标之间通过效用函数协调，使多目标规划问题转化为传统的单目标规划问题：但困难是要确定合理的权系数，以反映不同目标之间的重要程度。在用效用函数作为规划目标时，需要确定一组权值i来反映原问题中各目标函数在总体目标中的权重，即：kiii1max),,2,1(),,(21migxxxinikii11TmaxGXts)(..式中，i应满足：向量形式：方法二罚款模型（理想点法）思想:规划决策者对每一个目标函数都能提出所期望的值（或称满意值）；通过比较实际值fi与期望值fi*之间的偏差来选择问题的解，其数学表达式如下：i21)(minkiiiiffZ),,2,1(),,,(21migxxxini或写成矩阵形式：)()(minFFAFFZTGX)(式中，是与第i个目标函数相关的权重；A是由(i=1,2,…,k)组成的m×m对角矩阵。i理论依据：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中。假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：方法三约束模型（极大极小法）),,,(max(min)211nxxxfZ),,2,1(),,,(21migxxxini),,3,2(maxminkjfffjjj方法四目标规划模型（目标规划法）需要预先确定各个目标的期望值fi*，同时给每一个目标赋予一个优先因子和权系数，假定有K个目标，L个优先级(L≤K)，目标规划模型的数学形式为：LlKkklkklklddpZ11)(min),,,(),,,(migxxxini2121),,,(Kifddfiiii21式中：di+和di－分别表示与fi相应的、与fi*相比的目标超过值和不足值，即正、负偏差变量；pl表示第l个优先级；lk+、lk-表