3多目标规划M详解课件.ppt

1、多目标优化模型 一、多一、多 目目 标标 优优 化化 简简 介介?优化(Optimization):从若干可能的方案中寻求某种意义下的最优方案种意义下的最优方案?多目标规划多目标规划（Multiple Objectives Programming）是数学规划的一个分支，研究多于一个目标函数在给定区域上的最优化，又称多目标最优化，通常记为VMP。实例1：投资的收益和风险 市场上有n种资产（如股票、债券、）Si(i=1,n)供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买Si的平均收益率，并预测出购买Si的风险损失

2、率。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的Si中最大的一个风险来度量。购买Si要付交易费，费率已知，并且当购买额不超过最低限额时，交易费按购买最低限额计算（不买当然无须付费）。另外，假定同期银行存款年利率是1%,且既无交易费又无风险。试给该公司设计一种投资组合方案 目标一：使净收益尽可能大；目标二：而总体风险尽可能小。求解算法 转化为单目标 实例2：旅游路线设计 今年暑假，我校要召开“学术会议”，届时来自国内外的许多著名学者都会相聚成都。在会议结束后，主办方希望能安排这些远道而来的贵宾参观四川省境内的著名自然和人文景观，初步设想有如下线路可

3、供选择：一号线：九寨沟、黄龙；二号线：乐山、峨嵋；三号线：四姑娘山、丹巴；四号线：都江堰、青城山；五号线：海螺沟、康定；每条线路中的景点可以全部参观，也可以参观其中之一。不仅如此，一起参观景点的人数越多，每人承担的费用也会越小。车费与车型、乘客人数、路程种类及公里数有关。求解算法 转化为单目标 主办方在会议开始前对所有参会的主办方在会议开始前对所有参会的 100100位代表位代表旅游意向进行了调查，充分考虑这些代表的意愿，旅游意向进行了调查，充分考虑这些代表的意愿，为主办方设计代表们合适的旅游路线，使他们在会为主办方设计代表们合适的旅游路线，使他们在会议结束后的议结束后的1010天时间内花最少

4、的钱游尽可能多的地天时间内花最少的钱游尽可能多的地方。方。目标一：宾客参观意愿满意度尽可能高宾客参观意愿满意度尽可能高 目标二：宾客所花费用尽可能少 目标三：宾客游尽可能多的景点 1.主要目标法 在多目标优化问题中，根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据决策者的经验，选取一定的界限值。这样就可以把次要目标也作为约束来处理，于是就将原多目标问题转化为在新的约束下，求主要目标的单目标优化问题。转化为单目标的具体方法介绍：转化为单目标的具体方法介绍：转化单目标法 2.线性加权和法：按照m个目标 的重要程度，分别乘以一组权系数，然后相加作为目标函数。?miiim

5、iixfxfu111?)(xfi3.极大极小点法 4.范数理想点法?xfxfuimiXxmi?11maxminmin?pmipiiipfxffxfd11;,?转化单目标法 转化单目标法)(xfi5.评价函数法 以上的各种方法都是由 归结成一个目标其可看作是 的函数 我们可统一称其为评价函数，显然其具有很大的概括性，它不仅包括以上的一些方法，还可以构造新的方法。当然这种构造也不是随意的，一般要根据问题的具体背景和几何意义来构造 )(xfi)()(xfuxU?例：一个生产问题，有关数据如表。问如何安排生产可使总利润最大，产量之和最小。要求第二种原料用完。CBA0124546488010080单位利

6、润 产品 原料 单 耗 甲 乙 总量 解 设 为甲，乙的产量 21,xx则 211minxxz?21210080maxxxz?8054.21?xxts482421?xx61?x0,21?xx双目标规划模型 矛盾的 线性多目标规划模型-线性加权和法 一般形式：)(minXQ)(maxXROXMXFts?)(.化成单目标规划模型化成单目标规划模型 化法一)(minXQaXRts?)(.OXMXF?)(或 bXQts?)(.)(maxXROXMXF?)(化法二?)()1()(minXRXQ?OXMXFts?)(.为目标权重或偏好系数。?均可看成参数，对不同的参数值求出最优解，然后加以讨论，选出 满意

7、解。?,ba为了选修课程门数最少，应学习哪些课程？例 选课策略 要求至少选两门数学课、三门运筹学课和两门计算机课 课号 课名 学分 所属类别 先修课要求 1 微积分 5 数学 2 线性代数 4 数学 3 最优化方法 4 数学；运筹学 微积分；线性代数 4 数据结构 3 数学；计算机 计算机编程 5 应用统计 4 数学；运筹学 微积分；线性代数 6 计算机模拟 3 计算机；运筹学 计算机编程 7 计算机编程 2 计算机 8 预测理论 2 运筹学 应用统计 9 数学实验 3 运筹学；计算机 微积分；线性代数 选修课程最少，且学分尽量多，应学习哪些课程？0-1规划模型 决策变量 目标函数 xi=1

8、选修课号i 的课程（xi=0 不选）?91iixZMin选修课程总数最少 约束条件 最少2门数学课，3门运筹学课，2门计算机课。254321?xxxxx398653?xxxxx29764?xxxx课号 课名 所属类别 1 微积分 数学 2 线性代数 数学 3 最优化方法 数学；运筹学 4 数据结构 数学；计算机 5 应用统计 数学；运筹学 6 计算机模拟 计算机；运筹学 7 计算机编程 计算机 8 预测理论 运筹学 9 数学实验 运筹学；计算机 先修课程要求 74xx?02215?xxx076?xx058?xx02219?xxx最优解：x1=x2=x3=x6=x7=x9=1,其它为0；6门课程

9、，总学分21 02213?xxx0-1规划模型 约束条件 x3=1必有x1=x2=1 2313,xxxx?074?xx模型求解（LINDO）?课号 课名 先修课要求 1 微积分 2 线性代数 3 最优化方法 微积分；线性代数 4 数据结构 计算机编程 5 应用统计 微积分；线性代数 6 计算机模拟 计算机编程 7 计算机编程 8 预测理论 应用统计 9 数学实验 微积分；线性代数 学分最多 多目标优化的处理方法：化成单目标优化。两目标(多目标)规划 987654321322343445xxxxxxxxxWMax?,WZMin?讨论：选修课程最少，学分尽量多，应学习哪些课程？?91iixZMin

10、课程最少?以学分最多为目标，不管课程多少。?以课程最少为目标，不管学分多少。最优解如上，6门课程，总学分21。最优解显然是选修所有9门课程。多目标规划?在课程最少的前提下以学分最多为目标。最优解：x1=x2=x3=x5=x7=x9=1,其它为0；总学分由21增至22。注意：最优解不唯一！课号 课名 学分 1 微积分 5 2 线性代数 4 3 最优化方法 4 4 数据结构 3 5 应用统计 4 6 计算机模拟 3 7 计算机编程 2 8 预测理论 2 9 数学实验 3?LINDO 无法告诉优化问题的解是否唯一。可将x9=1 易为x6=1 增加约束 ，以学分最多为目标求解。691?iix多目标规划

11、?对学分数和课程数加权形成一个目标，如三七开。987654321322343445xxxxxxxxxW?91iixZ最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。课号 课名 学分 1 微积分 5 2 线性代数 4 3 最优化方法 4 4 数据结构 3 5 应用统计 4 6 计算机模拟 3 7 计算机编程 2 8 预测理论 2 9 数学实验 3?WZWZYMin3.07.021?求解算法之一：求解算法之一：转化为单目标转化为单目标 求解算法之二：求解算法之二：目标规划法目标规划法 二、多目标优化目标规划法 线性规划通常考虑一个目标函数(问题简单)目标规划考虑多

12、个目标函数(问题复杂)。甲 乙 设备的生产能力/h A/(h/件)2 2 12 B/(h/件)4 0 16 C/(h/件)0 5 15 赢利/(元/件)200 300 某企业生产甲、乙两种产品，需要用到 A,B,C三种设备，关于产品的盈利与使用设备的工时及限制如下表所示。例 生产安排问题 问该企业应如何安排生产，使得在计划期内总利润最大？1.线性规划建模线性规划建模 该例是一个线性规划问题，直接考虑它的线性规划模型 设甲、乙产品的产量分别为x1,x2,建立线性规划模型：;30020021xxzMax?,1222.21?xxts.0,155,1642121?xxxx用Lindo或Lingo软件求

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

14、2.21?xxts.0,155,1642121?xxxx 目标规划的数学模型目标规划的数学模型 为了克服线性规划的局限性,目标规划采用如下手段：1.设置偏差变量;2.统一处理目标与约束;3.目标的优先级与权系数。目标规划的基本概念 1.设置偏差变量 用偏差变量(Deviational variables)来表示实际值与目标值 之间的差异，令 -超出目标的差值，称为正偏差变量 -未达到目标的差值，称为负偏差变量 其中 与 至少有一个为0 约定如下：?当实际值超过目标值时，有?当实际值未达到目标值时，有?当实际值与目标值一致时，有?d?d?d?d?d;0,0?dd;0,0?dd.0,0?dd 2.

15、统一处理目标与约束 在目标规划中，约束可分两类，一类是对资源有严格限制 的，称为刚性约束(Hard Constraint)；例如在用目标规划 求解生产安排问题中设备A禁止超时使用，则有刚性约束 另一类是可以不严格限制的，连同原线性规划的目标,构 成柔性约束(Soft Constraint).例如在求解生产安排中，我们希望利润不低于1500元，则目标可表示为.122221?xx?.1500300200;min21ddxxd?力求使利润指标不低于1500元?考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2?设备A为贵重设备，严格禁止超时使用?设备C可以适当加班，但要控制；设备B既要求充分利用

16、，又尽可能不加班，在重要性上，设备B是设备C的3倍 设甲、乙产品的产量分别为x1,x2,建立模型：甲 乙 设备的生产能力/h A/(h/件)2 2 12 B/(h/件)4 0 16 C/(h/件)0 5 15 赢利/(元/件)200 300 ;30020021xxzMax?,1222.21?xxts.0,155,1642121?xxxx甲、乙两种产品的产量尽量保持1:2的比例，则目标可表示为 设备C可以适当加班，但要控制，则目标可表示为?.02;min21ddxxdd?.155;min2ddxd设备B既要求充分利用，又尽可能 不加班，则目标可表示为不加班，则目标可表示为?.164;min1dd

17、xdd从上面的分析可以看到：?如果希望不等式保持大于等于，则极小化负偏差；?如果希望不等式保持小于等于，则极小化正偏差；?如果希望保持等式，则同时极小化正、负偏差 3.目标的优先级与权系数目标的优先级与权系数 在目标规划模型中，目标的优先分为两个层次，第一个层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以 P1,P2,.表示不同的因子,并规定PkPk+1，第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，用权系数的大小来表示目标重要性的差别。解：在生产安排问题中设备 A是刚性约束，其余是柔性约束首先，最重要的指标

18、是企业的利润，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持1:2的比例，列为第二级；再次，设备 B和C的工作时间要有所控制，列为第三级，设备B的重要性是设备 C的三倍，因此它们的权重不一样。由此可以得到相应的目标规划模型。用目标规划方法求解用目标规划方法求解 112223334min()(33);zPdP ddPddd?,1222.21?xxts.4,3,2,1,0,155,164,02,15003002002144233122211121?iddxxddxddxddxxddxxii 目标规划模型的实例目标规划模型的实例 前面介绍了目标规划的求解方法，接着再介绍几个目标规划模型的实例

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