多目标最优化 精选PPT.ppt

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

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

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

3、设设x1、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+1

13、0 x2 约束条件约束条件2x1 +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)b

18、ifi(x)dd bidfi(x)bifi(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

19、极小化极小化4.4.利润额不小于利润额不小于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合计

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

22、0.1+x1)+1500(12-x1+x2)+1000(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

23、页哦 x1 3 x2-x1 3 x3-x2 0 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转化为转化为目标规划模型目标规划模型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+极小化极小化目标函数：目标函数：m

24、in z=P1 d1+P2(d2+d3+d4+)+P3(d5+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页哦