优化建模与LINGO第08章.ppt

《优化建模与LINGO第08章.ppt》由会员分享，可在线阅读，更多相关《优化建模与LINGO第08章.ppt（56页珍藏版）》请在三一文库上搜索。

1、优化建模与LINDO/LINGO软件 第 8 章 目标规划模型,内容提要,8.1 线性规划与目标规划 8.2 目标规划的数学模型 8.3 目标规划模型的实例 8.4 数据包络分析,8.1 线性规划与目标规划,线性规划通常考虑一个目标函数(问题简单),目标规划考虑多个目标函数(问题复杂),线性规划,目标规划,某企业生产甲、乙两种产品，需要用到A,B,C三种设备，关于产品的盈利与使用设备的工时及限制如下表所示。,例8.1 生产安排问题,问该企业应如何安排生产，使得在计划期内总利润最大？,1. 线性规划建模,该例8.1是一个线性规划问题，直接考虑它的线性规划模型,设甲、乙产品的产量分别为x1, x2

2、,建立线性规划模型：,用Lindo或Lingo软件求解,得到最优解,2. 目标规划建模,在上例8.1中，企业的经营目标不仅要考虑利润，还需要考虑多个方面，因此增加下列因素(目标)：,力求使利润指标不低于1500元,考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2,设备A为贵重设备，严格禁止超时使用,设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，在重要性上，设备B是设备C的3倍,从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解,某汽车销售公司委托一个广告公司在电视上为其做广告，汽车销售公司提出三个目标：,例8.2 汽车广告费问题,广告

3、公司必须决定购买两种类型的电视广告展播各多少分钟？,第一个目标，至少有40万高收入的男性公民(记为HIM)看到这个广告,第二个目标，至少有60万一般收入的公民(记为LIP)看到这个广告,第三个目标，至少有35万高收入的女性公民(记为HIW)看到这个广告,广告公司可以从电视台购买两种类型的广告展播：足球赛中插播广告和电视系列剧插播广告。广告公司最多花费60万元的电视广告费。每一类广告展播每一分钟的花费及潜在的观众人数如下表所示,3.尝试线性规划建模,对于例8.2考虑建立线性规划模型,设x1, x2分别是足球赛和电视系列剧中插播的分钟数，按照要求，可以列出相应的线性规划模型,用Lindo或Ling

4、o软件求解,会发现该问题不可行。,4. 线性规划建模局限性,线性规划要求所有求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；,线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理。但在实际问题中，目标和约束好似可以相互转化的，处理时不一定要严格区分；,线性规划在处理问题时，将各个约束(也可看作目标)的地位看成同等重要，而在实际问题中，各个目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别,线性规划寻求最优解，而许多实际问题只需要找到满意解就可以了。,8. 2 目标规划的数学模型,为了克服线性规划的局限性,目标规划采用如下手段：,1. 设置偏差变量

5、; 2. 统一处理目标与约束; 3. 目标的优先级与权系数。,目标规划的基本概念,1. 设置偏差变量,用偏差变量(Deviational variables)来表示实际值与目标值 之间的差异，令 - 超出目标的差值，称为正偏差变量 - 未达到目标的差值，称为负偏差变量 其中 与 至少有一个为0,约定如下： 当实际值超过目标值时，有 当实际值未达到目标值时，有 当实际值与目标值一致时，有,2. 统一处理目标与约束,在目标规划中，约束可分两类，一类是对资源有严格限制 的，称为刚性约束(Hard Constraint)；例如在用目标规划 求解例8.1中设备A禁止超时使用，则有刚性约束,另一类是可以不

6、严格限制的，连同原线性规划的目标,构 成柔性约束(Soft Constraint).例如在求解例8.1中，我们 希望利润不低于1500元，则目标可表示为,求解例8.1中甲、乙两种产品 的产量尽量保持1:2的比例， 则目标可表示为,设备C可以适当加班，但要控制， 则目标可表示为,设备B既要求充分利用，又尽可能 不加班，则目标可表示为,从上面的分析可以看到： 如果希望不等式保持大于等于，则极小化负偏差； 如果希望不等式保持小于等于，则极小化正偏差； 如果希望保持等式，则同时极小化正、负偏差,3.目标的优先级与权系数,在目标规划模型中，目标的优先分为两个层次，第一个层次是目标分成不同的优先级，在计算

7、目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以P1,P2,.表示不同的因子,并规定PkPk+1，第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，用权系数的大小来表示目标重要性的差别。,解 在例.1中设备A是刚性约束，其于是柔性约束首先，最重要的指标是企业的利润，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持1:2的比例，列为第二级；再次，设备 B和C的工作时间要有所控制，列为第三级，设备B的重要性是设备C的三倍，因此它们的权重不一样。由此可以得到相应的目标规划模型。,目标规划模型的建立,例8.3 用目标规划方法求解例8. 1,目标规划

8、的一般模型,目标规划模型的一般数学表达式为：,求解目标规划的序贯式算法,其算法是根据优先级的先后次序，将目标规划问题分解成 一系列的单目标规划问题，然后再依次求解。 算法8.1 对于k=1,2,q,求解单目标问题,解 因为每个单目标问题都是一个线性规划问题， 因此可以采用LINDO软件进行求解。按照算法8.1和 例8.3目标规划模型编写单个的线性规划求解程序。 求第一级目标企业利润最大，列出LINDO程序。 程序名：exam0804a.ltx,例8.4 用算法8.1求解例8. 3,目标,解 因求出的目标函数的最优值为，即第一级偏差为 .再求第二级目标，列出其LINDO程序。 程序名：exam0

9、804b.ltx,例8.4 用算法8.1求解例8. 3,修改的目标,增加的约束,解 因求出的目标函数的最优值仍为，即第二级偏差 仍为. 继续求第三级目标，列出其LINDO程序。 程序名：exam0804c.ltx,例8.4 用算法8.1求解例8. 3,求出的目标函数的最优值为29,即第三级偏差为29,分 析结果, x1为2, x2为4, DPLUS1 为100,因此目标规划的 最优解为x *=(2,4),最优利润为1600.,修改的目标,增加的约束,解 按照算法8.1和例8.3目标规划模型编写LINGO求解程 序，列出其LINGO程序, 程序名：exam0805.lg4,例8.5 (继例8.4

10、) 用算法8.1求解例8. 3的LINGO程序,程序运行说明，分三次求解： 在做第一级目标计算时，P(1),P(2)和P(3)分别输入1,0和0，Goal(1)和Goal(2)输入两个较大的数，表示这两项约束不起作用； 在做第二级目标计算时，P(1),P(2)和P(3)分别输入0,1和0，由于第一级的偏差为0，因此Goal(1)为0，Goal(2)输入一个较大的数； 在做第三级计算时，P(1),P(2)和P(3)分别输入0,0和1，由于第一级、第二级的偏差为0，因此Goal(1)和Goal(2)的输入值也为0。 结果可以参见程序演示！,由于在例8.4中虽然给出了目标规划问题的最优解,但需要连续

11、编几个LINDO程序,在使用时不方便,下面使用LINGO软件,编写一个通用程序。,8. 3 目标规划模型的实例,前面介绍了目标规划的求解方法，接着再介绍几个目标规划模型的实例。,某音像商店有5名全职售货员和4名兼职售货员。全职售货员每月工作160小时，兼职售货员每月工作80小时。根据过去的工作记录，全职售货员每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均每小时工资10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。另每出售一张CD盈利1.5元。,例8.6,该商店经理认为，保持稳定的

12、就业水平加上必要的加班，比不加班但就业水平不稳定要好。但全职售货员如果加班过多，就会因疲劳过度而造成效率下降，因此不允许每月加班超过100小时。建立相应的目标规划模型，并运用LINGO软件进行求解。,解 首先建立目标约束的优先级。 P1：下月的CD销售量达到27500张； P2： 限制全职售货员加班时间不超过100小时； P3： 保持全体售货员充分就业，因为充分工作是良 好劳资关系的重要因素，但对全职售货员要比 兼职售货员加倍优先考虑； P4： 尽量减少加班时间，但对两种售货员区别对 待，优先权因子由他们对利润的贡献而定。,例8.6,例8.6,第二，建立目标约束。 (1) 销售目标约束。设 x

13、1 ：全体全职售货员下月的工作时间； x2 ：全体兼职售货员下月的工作时间； ：达不到销售目标的偏差； ：超过销售目标的偏差。 希望下月的销售量超过27500张CD片，因此销售目标为,例8.6,第二，建立目标约束。 (2) 正常工作时间约束，设 ：全体全职售货员下月的停工时间； ：全体全职售货员下月的加班时间； ：全体兼职售货员下月的停工时间； ：全体兼职售货员下月的加班时间。 由于希望保持全体售货员充分就业，同时加倍优先考虑全职售货员,因此工作目标约束为,例8.6,第二，建立目标约束。 (3) 正常工作时间约束，设 ：全体全职售货员下月加班不足100小时的偏差； ：全体全职售货员下月加班超过

14、100小时的偏差。 限制全职售货员加班时间不超过100小时，将加班约束看成正常上班约束，不同的是右端加上100小时，因此加班目标约束为,例8.6,第二，建立目标约束。 接上(3) 另外，全职售货员加班1小时，商店得到的利润 为15元(25*1.5-22.5=15)，兼职售货员加班1小时，商店得 到的利润为5元(10*1.5-10=5)，因此加班1小时全职售货员 获得的利润是兼职售货员的3倍，故权因子之比为,所以，另一个加班目标约束为：,例8.6,第三，按目标的优先级，写出相应的目标规划模型：,第四，写出相应的LINGO程序，程序名：exam0806.lg4.,程序运行说明，分四次求解： 在做第

15、一级目标计算时，P(1),P(2),P(3)和P(4)分别输入1,0,0和0，Goal(1), Goal(2)和Goal(3)输入两个较大的数，表示这两项约束不起作用； 在做第二级目标计算时，P(1),P(2),P(3)和P(4)分别输入0,1,0和0，由于第一级的偏差为0，因此Goal(1)为0,Goal(2)和Goal(3)输入一个较大的数； 在做第三级计算时，P(1),P(2),P(3)和P(4)分别输入0,0,1和0，由于第一级,第二级的偏差为0，因此Goal(1)和Goal(2)的输入值也为0， Goal(3)输入一个较大的数； 在做第四级计算时，P(1),P(2),P(3)和P(4

16、)分别输入0,0,0和1，由于第一级,第二级和第三级的偏差为0,因此Goal(1),Goal(2)和Goal(3)输入值也为0； 全职售货员总工作时间为900小时(加班100小时)，兼职售货员总工作 时间500小时(加班180小时)，下月共销售CD27500张，商店共获得利润 27500*1.5-800*15-100*22.5-500*10=22000(元) 其结果可以参见程序演示！,某计算机公司生产三种型号的笔记本电脑A,B,C。这 三种笔记本电脑需要在复杂的装配线上生产，生产 1台A,B,C型号的笔记本电脑分别需要5,8,12小时。 公司装配线正常的生产时间是每月1700小时。公司 营业部

17、门估计A,B,C三种笔记本电脑的利润分别是 每台1000,1440,2520元，而公司预测这个月生产的笔 记本电脑能够全部售出。,例8.7,例8.7,公司经理考虑以下目标： 第一目标：充分利用正常的生产能力，避免开工不足； 第二目标：优先满足老客户的需求，A,B,C三种型号的电脑 50,50,80台，同时根据三种电脑的纯利润分配不同的权因子； 第三目标：限制装配线加班时间，不允许超过200小时； 第四目标：满足各种型号电脑的销售目标,A,B,C型号分别为 100,120,100台,再根据三种电脑的纯利润分配不同的权因子； 第五目标：装配线的加班时间尽可能少。 请列出相应的目标规划模型,并用LI

18、NGO软件求解。,例8.7,解 建立目标约束。 (1) 装配线正常生产 设生产A,B,C型号的电脑为x1, x2, x3台， 装配线正常生产时间未利用数， 装配线加班时间， 希望装配线正常生产,避免开工不足,因此装配线 约束目标为,例8.7,例8.7,(2) 销售目标 (接上) 再考虑一般销售，类似上面的讨论，得到,例8.7,(3) 加班限制 首先是限制装配线加班时间，不允许超过200 小时，因此得到,其次装配线的加班时间尽可能少，即,例8.7,写出相应的目标规划模型：,写出相应的LINGO程序，程序名：exam0807.lg4.,程序运行说明： 经5次计算得到x1=100, x2=55, x

19、3=80。装配线生产时间为1900小时，满足装配线加班不超过200小时的要求。能够满足老客户的需求，但未能达到销售目标。销售总利润为 100x1000+55x1440+80x2520=380800(元),其结果可以参见程序演示！,例8.8,已知三个工厂生产的产品供应给四个用户，各工厂 生产量、用户需求量及从各工厂到用户的单位产品 的运输费用如表所示。由于总生产量小于总需求量, 上级部门经研究后，制定了调配方案的8项指标，并 规定重要性的次序是:,例8.8,第一目标：用户4为重要部门,需求量必须全部满足； 第二目标：供应用户1的产品中，工厂3的产品不少 于100个单位；第三目标：每个用户的满足率

20、不低于 80%；第四目标：应尽量满足各用户的需求； 第五目标：新方案的总运费不超过原运输问题的调度 方案的10%；第六目标：因道路限制，工厂2到用户4 的路线应尽量避免运输任务； 第七目标：用户1和用户3的满足率应尽量保持平衡； 第八目标：力求减少总运费。 请列出相应的目标规划模型，并用LINGO软件求解。,例8.8,解 求解原运输问题。 由于总生产量小于总需求量,虚设工厂4,生产量为100 个单位,到各个用户间的运输单价为0,利用第7章介绍 的运输问题的求解方法,用LINGO软件求解,得到总 运费是2950元,运输方案如表所示.,例8.8,从上表可以看出，上述方案中，第一个目标就不满 足，用

21、户4的需求量得不到满足。下面按照目标的 重要性的等级列出目标规划的约束和目标函数。 设 xi j 为工厂 i 调配给用户 j 的运量.,(1) 供应约束应 严格满足, 即,(2) 供应用户1的产品中, 工厂3的产品不少于100 个单位, 即,例8.8,(3) 需求约束. 各用户的满 足率不低于 80%, 即,需求应尽量 满足各用户 的需求，即,新方案的总运费不超过原运方案的10%（原运输 方案的运费为2950元），即,(5) 工厂2到用户4的路线 应尽量避免运输任务, 即,(6) 用户1和用户3的满足率应尽量保持平衡，即,(7)力求总运 费最少, 即,例8.8,写出相应的目标函数为,写出相应的

22、LINGO程序，程序名：exam0808.lg4.,程序运行说明,其结果可以参见程序演示！,经8次计算，得到最终的计算结果，见下表所示。 总运费为3360元，高于原运费410元，超过原方案 10%的上限115元。,8. 4 数据包络分析,1978年A. Charnes, W. W. Cooper和E. Rhodes 给出了评价决策单元相对有效性的数据包络分 析方法(Data Envelopment Analysis), 即DEA. 目前，数据包络分析(DEA)是评价具有多指 标输入和多指标输出系统的较为有效的方法。,例8.9 (多指标评价问题)某市教委需要对六所重点中学进行 评价,其相应的指标

23、如下表所示,表中的生均投入和非低收入 家庭百分比是输入指标,生均写作得分和生均科技得分是输 出指标.请根据这些指标,评价中哪些学校是相对有效的.,相对有效评价问题,例8.9,为求解例8.9, 先对例表作简单的分析。 学校C的两项输出指标都是最高的,达到29.4和317,应该说,学校C是最有效的.但从另一方面说,对它的投入也是最高的,达到108.13和99.6,因此,它的效率也可能是最低的.究竟如何评价这六所学校呢？这还需要仔细地分析. 这是一个多指标输入和多指标输出的问题,对于这类评价问题,A. Charnes, W. W. Cooper和 E. Rhodes建立了评价决策单元相对有效性的C2

24、R 模型。,假设有n个部门或单位(称为决策单元,Decision Making Units),这n个单元都具有可比性.每个单元有m个输入变量和 s个输出变量,如下表所示.,数据包络分析的基本概念,v1 1 v2 2 ： ： vm m ,1 2 . j . n, 1 u1 2 u2 ： ： s us,在上表中, xij(i=1,2,.,m,j=1,2,., n)表示第j个决策单元对第i种输入的投入 量，并且满足xij0; yrj (r=1,2,.,s, j=1,2,., n)表示第j个决策单元对第r种 输出的产出量，并且满足yrj0; vi(i=1,2,.,m)表示第i种输入的一种度量 (或称为

25、权); u r(r=1,2,., s)表示第r种输出的的一种度量(或称为权). 将上表中的元素写成向量形式，如下表所示.,数据包络分析的基本概念,v ,1 2 . j . n, u,在上表中, Xj, Yj(j=1,2,.,n)分别为决策单元j的输入、输出向量，v, u分别 为输入、输出权重.,对于前面讲的向量表所给出的数据，设,C2R模型,为第j个决策单元的评价指数，总可以选择适当的权系数 u,v, 使得,第j个决策单元的评价指数hj的意义是：在权系数u,v下， 投入为vTXj， 产出为uTYj的投入产出比。,讨论：我们需要考虑某个决策单元j0的效率评价指数hj为 目标，在约束hj 1的最大

26、值，即分式线性规划,C2R模型,称上述模型为C2R模型,为了便于计算将分式线性规划转化成线性规划模型,数据包络分析的求解,定义1: 若该模型中 则称决策单元 j0 是弱DEA 有效的. 定义2: 若该模型中存在最优解 并且, 有 则称决策单元 j0 是弱DEA有效的.,例8.10 (继例8.9) 运用C2R模型求解例8.9.,解 按照C2R模型写出相应的LINGO程序，程序名：exam0810.lg4.,C2R模型的求解,运行程序时，P的值分别输入(1,0,0,0,0,0), (0,1,0,0,0,0), ., (0,0,0,0,0,1)，经过6次计算，得到6个最优目标值 1, 0.9096132, 0.9635345, 0.9143053, 1, 1, 并且对于学校A(决策单元1)有 对于学校E(决策单元5)有 和 对于学校F(决策单元6)有 因此，学校A, E, F是DEA有效的。,布置作业内容,Thank you very much!,完成习题8.1至8.4,