多目标优化------------目标规划法 线性规划通常考虑一个目标函数(问题简单) 目标规划考虑多个目标函数(问题复杂) 。

Presentation on theme: "多目标优化------------目标规划法 线性规划通常考虑一个目标函数(问题简单) 目标规划考虑多个目标函数(问题复杂) 。"— Presentation transcript:

1 多目标优化------------目标规划法
线性规划通常考虑一个目标函数(问题简单) 目标规划考虑多个目标函数(问题复杂) 。

2 例 生产安排问题 某企业生产甲、乙两种产品，需要用到A,B,C三种设备，关于产品的盈利与使用设备的工时及限制如下表所示。
问该企业应如何安排生产，使得在计划期内总利润最大？

3 1. 线性规划建模 该例是一个线性规划问题，直接考虑它的线性规划模型 设甲、乙产品的产量分别为x1, x2,建立线性规划模型：
用Lindo或Lingo软件求解,得到最优解

4 2. 目标规划建模 力求使利润指标不低于1500元 考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2
若在上例中，企业的经营目标不仅要考 虑利润，还需要考虑多个方面，因此增加下列因素(目标)： 力求使利润指标不低于1500元 考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2 设备A为贵重设备，严格禁止超时使用 设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，在重要性上，设备B是设备C的3倍 从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解

5 线性规划建模局限性 线性规划要求所有求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；
线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理。但在实际问题中，目标和约束可以相互转化，处理时不一定要严格区分； 线性规划在处理问题时，将各个约束(也可看作目标)的地位看成同等重要，而在实际问题中，各个目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别 线性规划寻求最优解，而许多实际问题只需要找到满意解就可以了。

6 目标规划的数学模型 目标规划的基本概念 为了克服线性规划的局限性,目标规划采用如下手段： 1. 设置偏差变量; 2. 统一处理目标与约束;
1. 设置偏差变量; 2. 统一处理目标与约束; 3. 目标的优先级与权系数。

7 1. 设置偏差变量 用偏差变量(Deviational variables)来表示实际值与目标值 之间的差异，令
　　　 ---- 超出目标的差值，称为正偏差变量 　　　 ---- 未达到目标的差值，称为负偏差变量 　　　　　　　其中 与 至少有一个为0 约定如下： 当实际值超过目标值时，有 当实际值未达到目标值时，有 当实际值与目标值一致时，有

8 2. 统一处理目标与约束 在目标规划中，约束可分两类，一类是对资源有严格限制
的，称为刚性约束(Hard Constraint)；例如在用目标规划 求解生产安排问题中设备A禁止超时使用，则有刚性约束 另一类是可以不严格限制的，连同原线性规划的目标,构 成柔性约束(Soft Constraint).例如在求解生产安排中，我们希望利润不低于1500元，则目标可表示为

9 力求使利润指标不低于1500元 考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2 设备A为贵重设备，严格禁止超时使用 设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，在重要性上，设备B是设备C的3倍 设甲、乙产品的产量分别为x1, x2,建立模型：

10 设备C可以适当加班，但要控制， 则目标可表示为 甲、乙两种产品的产量尽量保持1:2的比例，则目标可表示为 设备B既要求充分利用，又尽可能 不加班，则目标可表示为 从上面的分析可以看到： 如果希望不等式保持大于等于，则极小化负偏差； 如果希望不等式保持小于等于，则极小化正偏差； 如果希望保持等式，则同时极小化正、负偏差．

11 3.目标的优先级与权系数 在目标规划模型中，目标的优先分为两个层次，第一个层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以P1,P2,...表示不同的因子,并规定Pk>>Pk+1，第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，用权系数的大小来表示目标重要性的差别。

12 用目标规划方法求解 解：在生产安排问题中设备A是刚性约束，其余是柔性约束．首先，最重要的指标是企业的利润，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持1:2的比例，列为第二级；再次，设备 B和C的工作时间要有所控制，列为第三级，设备B的重要性是设备C的三倍，因此它们的权重不一样。由此可以得到相应的目标规划模型。

13

14 目标规划模型的实例 前面介绍了目标规划的求解方法，接着再介绍几个目标规划模型的实例。

15 例 计算机公司生产管理问题 某计算机公司生产三种型号的笔记本电脑A,B,C。这三种笔记本电脑需要在复杂的装配线上生产，生产1台A,B,C型号的笔记本电脑分别需要5,8,12小时。 公司装配线正常的生产时间是每月1700小时。公司 营业部门估计A,B,C三种笔记本电脑的利润分别是 每台1000,1440,2520元，而公司预测这个月生产的笔 记本电脑能够全部售出。

16 例 计算机公司生产管理问题 公司经理考虑以下目标： 请列出相应的目标规划模型,并用LINGO软件求解。
第一目标：充分利用正常的生产能力，避免开工不足； 第二目标：优先满足老客户的需求，A,B,C三种型号的电脑 50,50,80台，同时根据三种电脑的纯利润分配不同的权因子； 第三目标：限制装配线加班时间，不允许超过200小时； 第四目标：满足各种型号电脑的销售目标,A,B,C型号分别为 100,120,100台,再根据三种电脑的纯利润分配不同的权因子； 第五目标：装配线的加班时间尽可能少。 请列出相应的目标规划模型,并用LINGO软件求解。

17 解 建立目标约束。 (1) 装配线正常生产 设生产A,B,C型号的电脑为x1, x2, x3台， 装配线正常生产时间未利用数， 装配线加班时间， 希望装配线正常生产,避免开工不足,因此装配线 约束目标为

18 (2) 销售目标 优先满足老客户的需求，并根据三种电脑的纯 利润分配不同的权因子，A,B,C三种型号的电脑每 小时的利润是 因此,老客户的 销售目标约束为

19 (2) 销售目标 (接上) 再考虑一般销售，类似上面的讨论，得到

20 (3) 加班限制 首先是限制装配线加班时间，不允许超过200 小时，因此得到 其次装配线的加班时间尽可能少，即

21 写出相应的目标规划模型：

22 例音像店管理问题 某音像商店有5名全职售货员和4名兼职售货员。全职售货员每月工作160小时，兼职售货员每月工作80小时。根据过去的工作记录，全职售货员每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均每小时工资10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。另每出售一张CD盈利1.5元。 该商店经理认为，保持稳定的就业水平加上必要的加班，比不加班但就业水平不稳定要好。但全职售货员如果加班过多，就会因疲劳过度而造成效率下降，因此不允许每月加班超过100小时。建立相应的目标规划模型，并运用LINGO软件进行求解。

23 例2.3音像店管理问题 解 首先建立目标约束的优先级。 P1：下月的CD销售量达到27500张；
解 首先建立目标约束的优先级。 P1：下月的CD销售量达到27500张； P2： 保持全体售货员充分就业(即尽量满工作量），因为充分工作是良好劳资关系的重要因素，但对全职售货员要比兼职售货员加倍优先考虑； P3： 限制全职售货员加班时间不超过100小时； P4： 尽量减少加班时间，但对两种售货员区别对 待，优先权因子由他们对利润的贡献而定。

24 第二，建立目标约束。 (1) 销售目标约束。设 x1 ：全体全职售货员下月的工作时间； x2 ：全体兼职售货员下月的工作时间； ：达不到销售目标的偏差； ：超过销售目标的偏差。 希望下月的销售量超过27500张CD片，因此销售目标为

25 第二，建立目标约束。 (2) 尽量满工作量约束，设 ：全体全职售货员下月的停工时间； ：全体全职售货员下月的加班时间； ：全体兼职售货员下月的停工时间； ：全体兼职售货员下月的加班时间。 由于希望保持全体售货员充分就业，同时加倍优先考虑全职售货员,因此工作目标约束为

26 第二，建立目标约束。 (3) 正常工作时间约束，设 ：全体全职售货员下月加班不足100小时的偏差； ：全体全职售货员下月加班超过100小时的偏差。 限制全职售货员加班时间不超过100小时，将加班约束看成正常上班约束，不同的是右端加上100小时，因此加班目标约束为

27 第二，建立目标约束。 接上(3) 另外，全职售货员加班1小时，商店得到的利润 为15元(25* =15)，兼职售货员加班1小时，商店得 到的利润为5元(10*1.5-10=5)，因此加班1小时全职售货员 获得的利润是兼职售货员的3倍，故权因子之比为 所以，另一个加班目标约束为：

28 第三，按目标的优先级，写出相应的目标规划模型：

29