多目标最优化 优秀PPT.ppt

《多目标最优化 优秀PPT.ppt》由会员分享，可在线阅读，更多相关《多目标最优化 优秀PPT.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多目标最优化 第1页，本讲稿共35页本章内容主要介绍：本章内容主要介绍：如何建立目标规划模型如何建立目标规划模型如何求解如何求解 单目标模型只需简单确定一个目标，而将其余单目标模型只需简单确定一个目标，而将其余的列为约束；的列为约束；在构建多目标模型时，则需要对问题有较深的理在构建多目标模型时，则需要对问题有较深的理解，必须考虑更全面解，必须考虑更全面虽然费时较多，却非常有虽然费时较多，却非常有益，更切合实际。益，更切合实际。第2页，本讲稿共35页【例例1】某工厂在计划期内要安排生产甲、乙两种产品。已知某工厂在计划期内要安排生产甲、乙两种产品。已知制造甲产品制造甲产品需要需要A型配件型配件5个

2、，个，B型配件型配件3个；个；制造乙产品制造乙产品需要需要A型配件型配件2个，个，B型配件型配件4个。个。而在计划期内该工厂只而在计划期内该工厂只能能提供提供A型配件型配件180个，个，B型配件型配件135个。个。又知道该工厂每又知道该工厂每生产一件甲产品可生产一件甲产品可获利润获利润20元，一件乙产品可获利润元，一件乙产品可获利润15元。问元。问在计划期内甲、乙产品应该各安排生产多少件，才能使总利润在计划期内甲、乙产品应该各安排生产多少件，才能使总利润最大最大?甲乙现有配件A52180B34135利润（元）2015 将该例所述情况列成表格将该例所述情况列成表格:第3页，本讲稿共35页 设设x

3、1、x2分别表示生产甲、乙产品的件数，分别表示生产甲、乙产品的件数，Z表示总利表示总利润，当用线性规划来描述和解决这个问题时，其数润，当用线性规划来描述和解决这个问题时，其数学模型为学模型为 最优值：最优值：775 x1:32x2:9第4页，本讲稿共35页 但是，如果站在工厂计划人员的立场上对此进行评价但是，如果站在工厂计划人员的立场上对此进行评价的话，问题就不是这么简单了。的话，问题就不是这么简单了。第一第一，这是一个，这是一个单目标单目标最优化问题。但是，一般来说，最优化问题。但是，一般来说，一个计划问题要满足多方面的要求。例如一个计划问题要满足多方面的要求。例如财务部门财务部门利润目标：

4、利润尽可能大利润目标：利润尽可能大物资部门物资部门节约资金：消耗尽可能小节约资金：消耗尽可能小销售部门销售部门适销对路：产品品种多样适销对路：产品品种多样计划部门计划部门安排生产：产品批量尽可能大安排生产：产品批量尽可能大第5页，本讲稿共35页 一个计划问题实际上是一个多目标决策问题。只是由一个计划问题实际上是一个多目标决策问题。只是由于需要用于需要用线性规划线性规划来处理，计划人员才不得不从众多目标要来处理，计划人员才不得不从众多目标要求中硬性选择其一，作为线性规划的目标函数求中硬性选择其一，作为线性规划的目标函数。但这样做的结果可能严重违背了但这样做的结果可能严重违背了某些部门某些部门的愿

5、望，因的愿望，因而使生产计划的实施受到影响；或者在一开始就由于多方面而使生产计划的实施受到影响；或者在一开始就由于多方面的矛盾而无法从多个目标中选出一个目标来。的矛盾而无法从多个目标中选出一个目标来。第6页，本讲稿共35页第二第二，线性规划有最优解的，线性规划有最优解的必要条件必要条件是其可行解集非空，是其可行解集非空，即各约束条件彼此相容。但是，实际问题有时不能满足这即各约束条件彼此相容。但是，实际问题有时不能满足这样的要求样的要求。例如，由于设备维修、能源供应、其它产品生产需要等原例如，由于设备维修、能源供应、其它产品生产需要等原因，计划期内可以提供的设备工时不能满足计划产量工时因，计划期

6、内可以提供的设备工时不能满足计划产量工时需要需要。或由于储备资金的限制，原材料的最大供应量不能或由于储备资金的限制，原材料的最大供应量不能满足计划产量的需要满足计划产量的需要。第7页，本讲稿共35页第三第三，线性规划解的，线性规划解的可行性可行性和和最优性最优性具有十分明确的意义，具有十分明确的意义，但那都是针对特定数学模型而言的。但那都是针对特定数学模型而言的。在实际问题中，决策者在作决策时，往往还会对它作某在实际问题中，决策者在作决策时，往往还会对它作某种调整和修改，其原因可能是由于数学模型相对于实际种调整和修改，其原因可能是由于数学模型相对于实际问题的近似性问题的近似性 近似性近似性建模

7、时对实际问题的抽象建模时对实际问题的抽象 建模时未考虑到的新情况建模时未考虑到的新情况 决策者需要计划人员提供的不是严格的数学上的最优解，决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助做出最优决策的参考性的计划，或是提供而是可以帮助做出最优决策的参考性的计划，或是提供多种计划方案。多种计划方案。第8页，本讲稿共35页 1961年，查恩斯年，查恩斯(A.Charnes)和库柏和库柏(W.w.CooPer)提出目标提出目标规划规划(goal programming)，得到广泛重视和较快发展。，得到广泛重视和较快发展。目标规划在处理实际决策问题时，目标规划在处理实际决策问题时，承认各

8、项决策要求承认各项决策要求(即即使是冲突的使是冲突的)的存在有其合理性；在作最终决策时，不强调其的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。绝对意义上的最优性。因此，因此，目标规划被认为是一种较之线性规划更接近于实目标规划被认为是一种较之线性规划更接近于实际决策过程的决策工具际决策过程的决策工具。第9页，本讲稿共35页求解多目标决策常用的三种方法（或思想）：求解多目标决策常用的三种方法（或思想）：1.加权或效用系数法加权或效用系数法2.序列或优先级法序列或优先级法3.有效解（非劣解）法有效解（非劣解）法1.加权法：加权法：加权法加权法加权法加权法把问题中的所有目标用把问题中的

9、所有目标用统一的单位统一的单位来度量（例如用钱来度量（例如用钱或效用系数）或效用系数）v 这种方法的这种方法的核心核心是把多目标模型化成单目标模型。是把多目标模型化成单目标模型。优点优点优点优点：适于计算机求解：适于计算机求解（例如模型是线性的时候可用一般的单纯形法求解）（例如模型是线性的时候可用一般的单纯形法求解）第10页，本讲稿共35页 缺点缺点缺点缺点：难处在于如何寻到合理的权系数。：难处在于如何寻到合理的权系数。2.序列或优先级法：序列或优先级法：序列或优先级法序列或优先级法序列或优先级法序列或优先级法不是对每个目标加权，而是按照目标的轻重不是对每个目标加权，而是按照目标的轻重缓急，将

10、其分为不同等级再求解。缓急，将其分为不同等级再求解。优点优点优点优点：避免了权系数的困扰，绝大多数决策者都能采用，：避免了权系数的困扰，绝大多数决策者都能采用，事实上他们在许多决策中也正是这样做的。事实上他们在许多决策中也正是这样做的。例如建设高速公路时，既希望减少开支又希望降低交通例如建设高速公路时，既希望减少开支又希望降低交通伤亡事故，此时能否用金钱来衡量一个人的生命价值呢？伤亡事故，此时能否用金钱来衡量一个人的生命价值呢？例如决定人员的提升时，许多单位是按其工作态度、工作能力例如决定人员的提升时，许多单位是按其工作态度、工作能力及对单位的有效价值等这样一个先后顺序来进行评定的。及对单位的

11、有效价值等这样一个先后顺序来进行评定的。第11页，本讲稿共35页即没有任何其他方案能在各个方面完全胜出这个解 缺点缺点缺点缺点：难处在于如何确切地定出各个目标的优先顺序以：难处在于如何确切地定出各个目标的优先顺序以获得满意的求解结果。获得满意的求解结果。3.有效解（或非劣解）法：有效解（或非劣解）法：有效解（或非劣解）法有效解（或非劣解）法有效解（或非劣解）法有效解（或非劣解）法“不会产生不会产生”象加权法或优先级法象加权法或优先级法所具有的局限性，它将找出全部有效解集（即所具有的局限性，它将找出全部有效解集（即非劣解非劣解）以供决策者从中挑选。以供决策者从中挑选。缺点缺点缺点缺点：难处在于实

12、际问题中非劣解太多，难于一一推荐给：难处在于实际问题中非劣解太多，难于一一推荐给决策者。决策者。第12页，本讲稿共35页目标规划引例：目标规划引例：利润最大化问题利润最大化问题某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两种产品，已知有关数两种产品，已知有关数据如下表所示：据如下表所示：拥有量原材料 kg2111设备台时 hr1210利润 元/件810 解：这是一个单目标规划问题，可用线性规划模型表述解：这是一个单目标规划问题，可用线性规划模型表述为：为：试求获利最大的方案。试求获利最大的方案。第13页，本讲稿共35页目标函数目标函数max z=8x1+10 x2 约束条件约束条件2

13、x1 +x2 11 x1 +2x2 10 x1,x2 0可用图解法求得最优决策方案为：可用图解法求得最优决策方案为：x1*=4,x2*=3,z*=62x1 +2x2 108x1+10 x2=c6123452468102x1 +x2 11第14页，本讲稿共35页 在实际决策时，还应考虑市场等一系列其他条件，如：在实际决策时，还应考虑市场等一系列其他条件，如：（1）市场调查发现：）市场调查发现：的销量有下降趋势，故应考虑适的销量有下降趋势，故应考虑适当减少当减少的产量增加的产量增加的产量，使的产量，使 （2）原材料的价格不断上涨，增加供应会使成本提高。故不）原材料的价格不断上涨，增加供应会使成本提

14、高。故不考虑再购买原材料。考虑再购买原材料。（3）为提高效率，应充分利用设备，但不希望加班。）为提高效率，应充分利用设备，但不希望加班。（4）市场虽发生变化，但利润应尽可能达到或超过）市场虽发生变化，但利润应尽可能达到或超过56元。元。此时的决策是多目标决策问题此时的决策是多目标决策问题目标规划方法是解决目标规划方法是解决这类决策问题的方法之一这类决策问题的方法之一。第15页，本讲稿共35页1.1.正、负偏差变量正、负偏差变量正、负偏差变量正、负偏差变量d d+,d,d-d d+:决策值超过目标值的部分决策值超过目标值的部分 d d-：决策值未达到目标值的部分：决策值未达到目标值的部分 恒有恒

15、有 d d+dd-=0=0例如目标例如目标 z=8x1+10 x2 56 可以变化为目标约束：可以变化为目标约束：8x1+10 x2+d1-d1+56当当d1-0时，目标约束与目标等价时，目标约束与目标等价绝对约束绝对约束 2x1 +x2 11 可以变换为目标约束：可以变换为目标约束：2x1 +x2+d2-d2+11当当d2+0时，目标约束与绝对约束等价时，目标约束与绝对约束等价第16页，本讲稿共35页硬约束软约束2.绝对约束、目标约束绝对约束、目标约束绝对约束绝对约束绝对约束绝对约束：必须严格满足的等式或不等式约束：必须严格满足的等式或不等式约束目标约束目标约束目标约束目标约束：目标规划所特

16、有的约束，约束右端项看作要追求：目标规划所特有的约束，约束右端项看作要追求的目标值，在达到目标值时，允许发生正或负的偏差的目标值，在达到目标值时，允许发生正或负的偏差 例如，原材料的价格不断上涨，增加供应会使成本例如，原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料提高。故不考虑再购买原材料 从而从而 2x1 +x2 11 是硬约束是硬约束第17页，本讲稿共35页3.3.优先因子与权系数优先因子与权系数 目标规划问题常常有多个目标，但这些目标的主次或轻目标规划问题常常有多个目标，但这些目标的主次或轻重缓急是不同的。重缓急是不同的。最重要的目标赋予优先因子最重要的目标赋予优先因子

17、P1P1，次一级的目标赋予优先，次一级的目标赋予优先因子因子P2P2，并规定，并规定P Pk kPPk+1k+1即表示即表示P Pk k比比P Pk+1k+1有更大的有更大的优先权。优先权。如果要区别具有相同优先因子的两个目标的差别，则如果要区别具有相同优先因子的两个目标的差别，则分别赋予它们不同的权系数分别赋予它们不同的权系数w wj j。第18页，本讲稿共35页4.4.目标规划的目标函数目标规划的目标函数 min min z=g(d,d)三种基本形式：三种基本形式：目标类型目标规划格式需要极小化的偏差变量fi(x)bifi(x)dd bidfi(x)bifi(x)dd bidfi(x)bi

18、fi(x)dd biddd d+:决策值超过目标值的部分决策值超过目标值的部分d d-：决策值未达到目标值的部分：决策值未达到目标值的部分第19页，本讲稿共35页例例2 2 引例的目标规划模型：引例的目标规划模型：2.2.产品产品的产量不低于产品的产量不低于产品的产量的产量1.1.原材料供应受严格限制原材料供应受严格限制2x1 +x2 11硬约束硬约束x1x2 d1d1 0d1x1 x2极小化极小化即即x1 x2 0第20页，本讲稿共35页3.3.充分利用设备有效台时，不加班充分利用设备有效台时，不加班x12x2 d2d2 10d2d2x12x2 10极小化极小化4.4.利润额不小于利润额不小

19、于5656元元8x110 x2d3d3 56d38x110 x2 56极小化极小化第21页，本讲稿共35页第22页，本讲稿共35页建模步骤小结：建模步骤小结：1.建立基础模型建立基础模型2.为每一个为每一个理想目标理想目标确定期望值确定期望值3.对每一个对每一个现实目标现实目标和约束都加上正负偏差变和约束都加上正负偏差变量量4.将目标按其重要性划分优先级，第一优先级将目标按其重要性划分优先级，第一优先级为硬约束为硬约束5.建立目标规划函数建立目标规划函数反映决策者欲望，如“利润最大”配上期望值的理想目标第23页，本讲稿共35页例例3：某单位领导在考虑本单位职工的升级调资方案时，依某单位领导在考

20、虑本单位职工的升级调资方案时，依次遵守以下规定：次遵守以下规定：1.不超过年工资总额不超过年工资总额60000元元2.每级的人数不超过定编规定的人数每级的人数不超过定编规定的人数3.二、三级升级面尽可能达到但不超过现有人数的二、三级升级面尽可能达到但不超过现有人数的20%4.三级不足编制的人数可录用新职工，又一级的职工中三级不足编制的人数可录用新职工，又一级的职工中又又10%要退休要退休 试据下表数据建立模型试据下表数据建立模型第24页，本讲稿共35页等级工资额(元/年)现有人数编制人数一20001012二15001215三10001515合计3742第25页，本讲稿共35页参考模型如下：参考

21、模型如下：设设x1、x2、x3分别表示提升到一、二级和录用到三级的新职分别表示提升到一、二级和录用到三级的新职工人数。各目标确定的优先因子为：工人数。各目标确定的优先因子为：P1不超过年工资总额不超过年工资总额60000元；元；P2每级的人数不超过定编制规定的人数每级的人数不超过定编制规定的人数 P3二、三级的升级面尽可能达到现有人二、三级的升级面尽可能达到现有人数的数的20%接下来确定模型接下来确定模型第26页，本讲稿共35页首先给出首先给出基本模型基本模型：年工资总额不超过年工资总额不超过6000060000元元：2000(10-10*0.1+x1)+1500(12-x1+x2)+1000

22、(15-x2+x3)60000即即 500 x1+500 x2+1000 x3 900每级的人数不超过定编规定的人数每级的人数不超过定编规定的人数：1.10-10*0.1+x1 12即即 x1 32.12-x1+x2 15即即 x2-x1 33.15-x2+x3 15即即 x3-x2 0第27页，本讲稿共35页一、三级的升级面不大于现有人数的一、三级的升级面不大于现有人数的20%，但尽可能多，但尽可能多提：提：二级提升、二级提升、x1 12*0.2即即 x1 2.4三级提升、三级提升、x2 15*0.2即即 x2 3第28页，本讲稿共35页 x1 3 x2-x1 3 x3-x2 0 x1+d

23、d2 2-d-d2 2+3 x2-x1+d d3 3-d-d3 3+3 x3-x2+d d4 4-d-d4 4+0转化为转化为目标规划模型目标规划模型500 x1+500 x2+1000 x3 900500 x1+500 x2+1000 x3+d d1 1-d-d1 1+900d d1 1+极小化极小化d d2 2+d+d3 3+d+d4 4+极小化极小化第29页，本讲稿共35页x1 2.4x2 3x1+d d5 5-d-d5 5+2.4x2+d d6 6-d-d6 6+3D D5 5+d+d6 6+极小化极小化目标函数：目标函数：min z=P1 d1+P2(d2+d3+d4+)+P3(d5

24、+d6+)第30页，本讲稿共35页目标规划模型为：目标规划模型为：min z=P1 d1+P2(d2+d3+d4+)+P3(d5-+d6-)s.t.500 x1+500 x2+1000 x3+d1-d1+900 x1+d d2 2-d-d2 2+3 x2-x1+d d3 3-d-d3 3+3 x3-x2+d d4 4-d-d4 4+0 x1+d d5 5-d-d5 5+2.4x2+d d6 6-d-d6 6+3第31页，本讲稿共35页三、目标规划的求解三、目标规划的求解主要思想：化成单目标问题，多阶段求解主要思想：化成单目标问题，多阶段求解第32页，本讲稿共35页求解步骤：求解步骤：1.模型中约束不变，只取第一优先级为目标函数模型中约束不变，只取第一优先级为目标函数求出最优目标值为求出最优目标值为z d3-=0。第33页，本讲稿共35页2.只取第二优先级为目标函数，将上次求解结果的目标值只取第二优先级为目标函数，将上次求解结果的目标值d3-=0变为约束变为约束求出最优目标值为求出最优目标值为z 2d1+3d2+=12。第34页，本讲稿共35页3.只取第三优先级为目标函数，将上次求解结果的目只取第三优先级为目标函数，将上次求解结果的目标值标值2d1+3d2+=12变为约束变为约束第35页，本讲稿共35页