优化建模与LINGO第08章[共56页]

1、优化建模与优化建模与LINDO/LINGO软件软件 第第 8 章目标规划模型章目标规划模型 内容提要内容提要 8.1 线性规划与目标规划线性规划与目标规划 8.2 目标规划的数学模型目标规划的数学模型 8.3 目标规划模型的实例目标规划模型的实例 8.4 数据包络分析数据包络分析 8.1 线性规划与目标规划线性规划与目标规划 线性规划通常考虑一个目标函数线性规划通常考虑一个目标函数(问题简单问题简单) 目标规划考虑多个目标函数目标规划考虑多个目标函数(问题复杂问题复杂) 线性规划线性规划目标规划目标规划 发展发展 演变演变 某企业生产甲、乙两种产品，需要用到某企业生产甲、乙两种产品，需要用到A

2、,B,C三种设备，关三种设备，关 于产品的盈利与使用设备的工时及限制如下表所示。于产品的盈利与使用设备的工时及限制如下表所示。 例例8.18.1 生产安排问题生产安排问题 问该企业应如何安排生产，使得在计划期内总利润最大？问该企业应如何安排生产，使得在计划期内总利润最大？ 1. 线性规划建模线性规划建模 该例该例8.1是一个线性规划问题，直接考虑它的线性规划模型是一个线性规划问题，直接考虑它的线性规划模型 设甲、乙产品的产量分别为设甲、乙产品的产量分别为x1, x2,建立线性规划模型：建立线性规划模型： ;300200 21 xxzMax ,1222. 21 xxts . 0, ,155 ,1

3、64 21 2 1 xx x x 用用Lindo或或Lingo软件求解软件求解,得到最优解得到最优解 .1500, 3, 3 * 21 zxx 2. 目标规划建模目标规划建模 在上例在上例8.1中，企业的经营目标不仅要考虑利润，还需要考中，企业的经营目标不仅要考虑利润，还需要考 虑多个方面，因此增加下列因素虑多个方面，因此增加下列因素(目标目标)： 力求使利润指标不低于力求使利润指标不低于1500元元 考虑到市场需求考虑到市场需求,甲、乙两种产品的产量比应尽量保持甲、乙两种产品的产量比应尽量保持1:2 设备设备A为贵重设备，严格禁止超时使用为贵重设备，严格禁止超时使用 设备设备C可以适当加班，

4、但要控制；设备可以适当加班，但要控制；设备B既要求充分利用，又尽既要求充分利用，又尽 可能不加班，在重要性上，设备可能不加班，在重要性上，设备B是设备是设备C的的3倍倍 从上述问题可以看出，仅用线性规划方法是不够的，需要从上述问题可以看出，仅用线性规划方法是不够的，需要 借助于目标规划的方法进行建模求解借助于目标规划的方法进行建模求解 某汽车销售公司委托一个广告公司在电视上为其做广告，汽某汽车销售公司委托一个广告公司在电视上为其做广告，汽 车销售公司提出三个目标：车销售公司提出三个目标： 例例8.2 汽车广告费问题汽车广告费问题 广告公司必须决定购买两种类型的电视广告展播各多少分钟？广告公司必

5、须决定购买两种类型的电视广告展播各多少分钟？ 第一个目标，至少有第一个目标，至少有40万高收入的男性公民万高收入的男性公民(记为记为HIM)看到这个广告看到这个广告 第二个目标，至少有第二个目标，至少有60万一般收入的公民万一般收入的公民(记为记为LIP)看到这个广告看到这个广告 第三个目标，至少有第三个目标，至少有35万高收入的女性公民万高收入的女性公民(记为记为HIW)看到这个广告看到这个广告 广告公司可以从电视台购买两种类型的广告展播：足球赛中广告公司可以从电视台购买两种类型的广告展播：足球赛中 插播广告和电视系列剧插播广告。广告公司最多花费插播广告和电视系列剧插播广告。广告公司最多花费

6、6060万元万元 的电视广告费。每一类广告展播每一分钟的花费及潜在的观的电视广告费。每一类广告展播每一分钟的花费及潜在的观 众人数如下表所示众人数如下表所示 3.尝试线性规划建模尝试线性规划建模 对于例对于例8.2考虑建立线性规划模型考虑建立线性规划模型 设设x1, x2分别是足球赛和电视系列剧中插播的分钟数，按照分别是足球赛和电视系列剧中插播的分钟数，按照 要求，可以列出相应的线性规划模型要求，可以列出相应的线性规划模型 ;00 21 xxMin ,60610. 21 xxts . 0, ,3545 ,60510 ,4037 21 21 21 21 xx xx xx xx 用用Lindo或或

7、Lingo软件求解软件求解,会发现该问题不可行。会发现该问题不可行。 4. 线性规划建模局限性线性规划建模局限性 线性规划要求所有求解的问题必须满足全部的约束，而实线性规划要求所有求解的问题必须满足全部的约束，而实 际问题中并非所有约束都需要严格的满足；际问题中并非所有约束都需要严格的满足； 线性规划只能处理单目标的优化问题，而对一些次目标只线性规划只能处理单目标的优化问题，而对一些次目标只 能转化为约束处理。但在实际问题中，目标和约束好似可以能转化为约束处理。但在实际问题中，目标和约束好似可以 相互转化的，处理时不一定要严格区分；相互转化的，处理时不一定要严格区分； 线性规划在处理问题时，将

8、各个约束线性规划在处理问题时，将各个约束(也可看作目标也可看作目标)的地的地 位看成同等重要，而在实际问题中，各个目标的重要性即位看成同等重要，而在实际问题中，各个目标的重要性即 有层次上的差别，也有在同一层次上不同权重的差别有层次上的差别，也有在同一层次上不同权重的差别 线性规划寻求最优解，而许多实际问题只需要找到满意解线性规划寻求最优解，而许多实际问题只需要找到满意解 就可以了。就可以了。 8. 2 目标规划的数学模型目标规划的数学模型 为了克服线性规划的局限性为了克服线性规划的局限性,目标规划采用如下手段：目标规划采用如下手段： 1. 设置偏差变量设置偏差变量; ; 2. 统一处理目标与

9、约束统一处理目标与约束; ; 3. 目标的优先级与权系数。目标的优先级与权系数。 目标规划的基本概念目标规划的基本概念 1. 设置偏差变量设置偏差变量 用偏差变量用偏差变量( (Deviational variables) )来表示实际值与目标值来表示实际值与目标值 之间的差异，令之间的差异，令 - - 超出目标的差值，称为正偏差变量超出目标的差值，称为正偏差变量 - - 未达到目标的差值，称为负偏差变量未达到目标的差值，称为负偏差变量 其中其中 与与 至少有一个为至少有一个为0 0 约定如下：约定如下： 当实际值超过目标值时，有当实际值超过目标值时，有 当实际值未达到目标值时，有当实际值未达

10、到目标值时，有 当实际值与目标值一致时，有当实际值与目标值一致时，有 d d d d d ; 0, 0 dd ; 0, 0 dd . 0, 0 dd 2. 统一处理目标与约束统一处理目标与约束 在目标规划中，约束可分两类，一类是对资源有严格限制在目标规划中，约束可分两类，一类是对资源有严格限制 的，称为刚性约束的，称为刚性约束(Hard Constraint)；例如在用目标规划；例如在用目标规划 求解例求解例8.1中设备中设备A禁止超时使用，则有刚性约束禁止超时使用，则有刚性约束 另一类是可以不严格限制的，连同原线性规划的目标另一类是可以不严格限制的，连同原线性规划的目标,构构 成柔性约束成柔

11、性约束(Soft Constraint).例如在求解例例如在求解例8.1中，我们中，我们 希望利润不低于希望利润不低于1500元，则目标可表示为元，则目标可表示为 .1222 21 xx .1500300200 ;min 21 ddxx d 求解例求解例8.1中甲、乙两种产品中甲、乙两种产品 的产量尽量保持的产量尽量保持1:2的比例，的比例， 则目标可表示为则目标可表示为 设备设备C可以适当加班，但要控制，可以适当加班，但要控制， 则目标可表示为则目标可表示为 . 02 ;min 21 ddxx dd .155 ;min 2 ddx d 设备设备B既要求充分利用，又尽可能既要求充分利用，又尽可

12、能 不加班，则目标可表示为不加班，则目标可表示为 .164 ;min 1 ddx dd 从上面的分析可以看到：从上面的分析可以看到： 如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持大于等于，则极小化负偏差； 如果希望不等式保持小于等于，则极小化正偏差；如果希望不等式保持小于等于，则极小化正偏差； 如果希望保持等式，则同时极小化正、负偏差如果希望保持等式，则同时极小化正、负偏差 3.目标的优先级与权系数目标的优先级与权系数 在目标规划模型中，目标的优先分为两个层次，第一个在目标规划模型中，目标的优先分为两个层次，第一个 层次是目标分成不同的优先级，在计算目标规划时，必层次是目标分

13、成不同的优先级，在计算目标规划时，必 须先优化高优先级的目标，然后再优化低优先级的目标。须先优化高优先级的目标，然后再优化低优先级的目标。 通常以通常以P1,P2,.表示不同的因子表示不同的因子,并规定并规定PkPk+1，第二个，第二个 层次是目标处于同一优先级，但两个目标的权重不一样，层次是目标处于同一优先级，但两个目标的权重不一样， 因此两目标同时优化，用权系数的大小来表示目标重要因此两目标同时优化，用权系数的大小来表示目标重要 性的差别。性的差别。 解在例解在例.1.1中中设备设备A是是刚性约刚性约 束，其于是柔性约束首先，最束，其于是柔性约束首先，最 重要的指标是企业的利润，将它重要的

14、指标是企业的利润，将它 的优先级列为第一级；其次，甲、的优先级列为第一级；其次，甲、 乙两种产品的产量保持乙两种产品的产量保持1:2的比的比 例，列为第二级；再次，例，列为第二级；再次，设备设备 B 和和C的工作时间要有所控制，列的工作时间要有所控制，列 为第三级，设备为第三级，设备B的重要性是设的重要性是设 备备C的三倍，因此它们的权重不的三倍，因此它们的权重不 一样。由此可以得到相应的目标一样。由此可以得到相应的目标 规划模型。规划模型。 目标规划模型的建立目标规划模型的建立 例例8.3 用目标规划方法求解例用目标规划方法求解例8. 1 );433()(min 43332221 dddPd

15、dPdPz ,1222. 21 xxts . 4 , 3 , 2 , 1, 0, ,155 ,164 , 02 ,1500300200 21 442 331 2221 1121 iddxx ddx ddx ddxx ddxx ii 目标规划的一般模型目标规划的一般模型 目标规划模型的一般数学表达式为：目标规划模型的一般数学表达式为： ; )(min 11 l j jkjjkj q k k dwdwPz , 2 , 1,),(. 1 mibxats ij n j ij ,2, 1,0, ,2, 1,0 ,2, 1, 1 lidd njx ligddxc ii j iiij n j ij 求解目标

16、规划的序贯式算法求解目标规划的序贯式算法 其算法是根据优先级的先后次序，将目标规划问题分解成其算法是根据优先级的先后次序，将目标规划问题分解成 一系列的单目标规划问题，然后再依次求解。一系列的单目标规划问题，然后再依次求解。 算法算法8.1 对于对于k=1,2,q,求解单目标问题求解单目标问题 ; )(min 1 l j jkjjkj dwdwz ,2, 1,),(. 1 mibxats ij n j ij ,2,1,0, ,2,1,0 ,1,2,1,)( ,2,1, * 1 1 lidd njx kszdwdw ligddxc ii j l j jsjjsj iiij n j ij 解解因为

17、每个单目标问题都是一个线性规划问题，因为每个单目标问题都是一个线性规划问题， 因此可以采用因此可以采用LINDOLINDO软件进行求解。按照算法软件进行求解。按照算法8.18.1和和 例例8.38.3目标规划模型编写单个的线性规划求解程序。目标规划模型编写单个的线性规划求解程序。 求第一级目标企业利润最大，列出求第一级目标企业利润最大，列出LINDOLINDO程序。程序。 程序名：程序名：exam0804a.ltxexam0804a.ltx 例例8.4 用算法用算法8.1求解例求解例8. 3 MIN DMINUS1 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2

18、 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 END 求解结果可见求解结果可见 程序演示程序演示 目标目标 解因求出的目标函数的最优值为，即第一级偏差为解因求出的目标函数的最优值为，即第一级偏差为 . .再再求第二级目标，列出其求第二级目标，列出其LINDOLINDO程序。程序。 程序名：程序名：exam0804b.ltxexam0804b.ltx 例例8.4 用算法用算法8.1求解例求解例8. 3 MIN DP

19、LUS2 + DMINUS2 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 DMINUS1 = 0 END 求解结果可见求解结果可见 程序演示程序演示 修改的目标修改的目标 增加的约束增加的约束 解因求出的目标函数的最优值仍为，即第二级偏差解因求出的目标函数的最优值仍为，即第二级偏差 仍为仍为. . 继续继续求第三级目标，列出其求第三级

20、目标，列出其LINDOLINDO程序。程序。 程序名：程序名：exam0804c.ltxexam0804c.ltx 例例8.4 用算法用算法8.1求解例求解例8. 3 MIN 3DPLUS3 + 3DMINUS3+ DPLUS4 SUBJECT TO 2X1 + 2X2 0; yrj (r=1,2,.,s, j=1,2,., n)表示第表示第j个决策单元对第个决策单元对第r种种 输出的产出量，并且满足输出的产出量，并且满足yrj0; vi(i=1,2,.,m)表示第表示第i种输入的一种度量种输入的一种度量 (或称为权或称为权); u r(r=1,2,., s)表示第表示第r种输出的的一种度量种

21、输出的的一种度量(或称为权或称为权). 将上表中的元素写成向量形式，如下表所示将上表中的元素写成向量形式，如下表所示. . 数据包络分析的基本概念数据包络分析的基本概念 X1X2.Xj.Xn v 1 2 . j . n uY1Y2.Yj.Yn 在上表中在上表中, Xj, Yj(j=1,2,.,n)分别为决策单元分别为决策单元j的输入、输出向量，的输入、输出向量，v, u分别分别 为输入、输出权重为输入、输出权重. 对于前面讲的向量表所给出的数据，设对于前面讲的向量表所给出的数据，设 C2R模型模型 为第为第j j个决策单元的评价指数，总可以选择适当的权系数个决策单元的评价指数，总可以选择适当的

22、权系数 u,vu,v, , 使得使得 ,2, 1,nj Xv Yu h j j j T T .,2, 1, 1njh j 第第j个决策单元的评价指数个决策单元的评价指数hj的意义是：在权系数的意义是：在权系数u,v下，下， 投入为投入为vTXj， ， 产出为 产出为uTYj的投入产出比。的投入产出比。 讨论：我们需要考虑某个决策单元讨论：我们需要考虑某个决策单元j0的效率评价指数的效率评价指数hj 为 为 目标，在约束目标，在约束hj 1的的最大值，即分式线性规划最大值，即分式线性规划 C2R模型模型 称上述模型为称上述模型为C2R模型模型 .0,0 ,2, 1, 1 ; 0 0 vu nj Xv Yu Xv Yu V j j j j p T T T T . max ts 为