《多目标最优化.ppt》由会员分享，可在线阅读，更多相关《多目标最优化.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1多目标规划多目标规划一、多目标规划问题的提出：一、多目标规划问题的提出：多目标问题多目标问题多目标问题多目标问题是现实世界中普遍遇到的一类问题，是现实世界中普遍遇到的一类问题，其中希望（或必须）考虑多个相互矛盾目标的影响。其中希望（或必须）考虑多个相互矛盾目标的影响。例如证券投资问题中我们希望利润最大而风险例如证券投资问题中我们希望利润最大而风险最小，生产销售问题中我们希望费用较少而获利很最小，生产销售问题中我们希望费用较少而获利很大，等等。大，等等。2本章内容主要介绍：本章内容主要介绍：如何建立目标规划模型如何建立目标规划模型如何求解如何求解 单目标模型只需简单确定一个目标，而将其单目标模
2、型只需简单确定一个目标，而将其余的列为约束；余的列为约束；在构建多目标模型时，则需要对问题有较深的在构建多目标模型时，则需要对问题有较深的理解，必须考虑更全面理解，必须考虑更全面虽然费时较多，却非虽然费时较多，却非常有益，更切合实际。常有益，更切合实际。3【例例1】某工厂在计划期内要安排生产甲、乙两种产品。某工厂在计划期内要安排生产甲、乙两种产品。已知已知制造甲产品制造甲产品需要需要A型配件型配件5个，个，B型配件型配件3个；个；制制造乙产品造乙产品需要需要A型配件型配件2个，个，B型配件型配件4个。个。而在计划而在计划期内该工厂只能期内该工厂只能提供提供A型配件型配件180个，个，B型配件型
3、配件135个。个。又知道该工厂每生产一件甲产品可又知道该工厂每生产一件甲产品可获利润获利润20元，一件乙元，一件乙产品可获利润产品可获利润15元。问在计划期内甲、乙产品应该各安元。问在计划期内甲、乙产品应该各安排生产多少件，才能使总利润最大排生产多少件，才能使总利润最大?甲乙现有配件A52180B34135利润（元）2015 将该例所述情况列成表格将该例所述情况列成表格:4 设设x1、x2分别表示生产甲、乙产品的件数，分别表示生产甲、乙产品的件数，Z表示表示总利润，当用线性规划来描述和解决这个问题时，总利润，当用线性规划来描述和解决这个问题时，其数学模型为其数学模型为 最优值：最优值：775
4、x1:32x2:95 但是，如果站在工厂计划人员的立场上对此进行评但是，如果站在工厂计划人员的立场上对此进行评价的话，问题就不是这么简单了。价的话，问题就不是这么简单了。第一第一，这是一个，这是一个单目标单目标最优化问题。但是，一般来最优化问题。但是，一般来说，一个计划问题要满足多方面的要求。例如说，一个计划问题要满足多方面的要求。例如财务部门财务部门利润目标：利润尽可能大利润目标：利润尽可能大物资部门物资部门节约资金：消耗尽可能小节约资金：消耗尽可能小销售部门销售部门适销对路：产品品种多样适销对路：产品品种多样计划部门计划部门安排生产：产品批量尽可能大安排生产：产品批量尽可能大6 一个计划问
5、题实际上是一个多目标决策问题。只一个计划问题实际上是一个多目标决策问题。只是由于需要用是由于需要用线性规划线性规划来处理，计划人员才不得不来处理，计划人员才不得不从众多目标要求中硬性选择其一，作为线性规划的从众多目标要求中硬性选择其一，作为线性规划的目标函数目标函数。但这样做的结果可能严重违背了但这样做的结果可能严重违背了某些部门某些部门的愿望，的愿望，因而使生产计划的实施受到影响；或者在一开始就因而使生产计划的实施受到影响；或者在一开始就由于多方面的矛盾而无法从多个目标中选出一个目由于多方面的矛盾而无法从多个目标中选出一个目标来。标来。7第二第二，线性规划有最优解的，线性规划有最优解的必要条
6、件必要条件是其可行解集非是其可行解集非空，即各约束条件彼此相容。但是，实际问题有时空，即各约束条件彼此相容。但是，实际问题有时不能满足这样的要求不能满足这样的要求。例如，由于设备维修、能源供应、其它产品生产需例如，由于设备维修、能源供应、其它产品生产需要等原因，计划期内可以提供的设备工时不能满足要等原因，计划期内可以提供的设备工时不能满足计划产量工时需要计划产量工时需要。或由于储备资金的限制，原材料的最大供应量不或由于储备资金的限制，原材料的最大供应量不能满足计划产量的需要能满足计划产量的需要。8第三第三，线性规划解的，线性规划解的可行性可行性和和最优性最优性具有十分明确的具有十分明确的意义，
7、但那都是针对特定数学模型而言的。意义，但那都是针对特定数学模型而言的。在实际问题中，决策者在作决策时，往往还会对它在实际问题中，决策者在作决策时，往往还会对它作某种调整和修改，其原因可能是由于数学模型相作某种调整和修改，其原因可能是由于数学模型相对于实际问题的近似性对于实际问题的近似性 近似性近似性建模时对实际问题的抽象建模时对实际问题的抽象 建模时未考虑到的新情况建模时未考虑到的新情况 决策者需要计划人员提供的不是严格的数学上的最决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助做出最优决策的参考性的计划，优解，而是可以帮助做出最优决策的参考性的计划，或是提供多种计划方案。或是提
8、供多种计划方案。9 1961年，查恩斯年，查恩斯(A.Charnes)和库柏和库柏(W.w.CooPer)提提出目标规划出目标规划(goal programming)，得到广泛重视和较快，得到广泛重视和较快发展。发展。目标规划在处理实际决策问题时，目标规划在处理实际决策问题时，承认各项决策要求承认各项决策要求(即使是冲突的即使是冲突的)的存在有其合理性；在作最终决策时，的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。不强调其绝对意义上的最优性。因此，因此，目标规划被认为是一种较之线性规划更接近于目标规划被认为是一种较之线性规划更接近于实际决策过程的决策工具实际决策过程的决策工具。
9、10求解多目标决策常用的三种方法（或思想）：求解多目标决策常用的三种方法（或思想）：1.加权或效用系数法加权或效用系数法2.序列或优先级法序列或优先级法3.有效解（非劣解）法有效解（非劣解）法1.加权法：加权法：加权法加权法加权法加权法把问题中的所有目标用把问题中的所有目标用统一的单位统一的单位来度量（例来度量（例如用钱或效用系数）如用钱或效用系数）v 这种方法的这种方法的核心核心是把多目标模型化成单目标模型。是把多目标模型化成单目标模型。优点优点优点优点：适于计算机求解：适于计算机求解（例如模型是线性的时候可用一般的单纯形法求解）（例如模型是线性的时候可用一般的单纯形法求解）11 缺点缺点缺
10、点缺点：难处在于如何寻到合理的权系数。：难处在于如何寻到合理的权系数。2.序列或优先级法：序列或优先级法：序列或优先级法序列或优先级法序列或优先级法序列或优先级法不是对每个目标加权，而是按照目标不是对每个目标加权，而是按照目标的轻重缓急，将其分为不同等级再求解。的轻重缓急，将其分为不同等级再求解。优点优点优点优点：避免了权系数的困扰，绝大多数决策者都能采：避免了权系数的困扰，绝大多数决策者都能采用，事实上他们在许多决策中也正是这样做的。用，事实上他们在许多决策中也正是这样做的。例如建设高速公路时，既希望减少开支又希望降低例如建设高速公路时，既希望减少开支又希望降低交通伤亡事故，此时能否用金钱来
11、衡量一个人的生命交通伤亡事故，此时能否用金钱来衡量一个人的生命价值呢？价值呢？例如决定人员的提升时，许多单位是按其工作态度、例如决定人员的提升时，许多单位是按其工作态度、工作能力及对单位的有效价值等这样一个先后顺序来工作能力及对单位的有效价值等这样一个先后顺序来进行评定的。进行评定的。12即没有任何其他方案即没有任何其他方案能在各个方面完全胜能在各个方面完全胜出这个解出这个解 缺点缺点缺点缺点：难处在于如何确切地定出各个目标的优先顺序：难处在于如何确切地定出各个目标的优先顺序以获得满意的求解结果。以获得满意的求解结果。3.有效解（或非劣解）法：有效解（或非劣解）法：有效解（或非劣解）法有效解（
12、或非劣解）法有效解（或非劣解）法有效解（或非劣解）法“不会产生不会产生”象加权法或优先象加权法或优先级法所具有的局限性，它将找出全部有效解集（即级法所具有的局限性，它将找出全部有效解集（即非非劣解劣解）以供决策者从中挑选。）以供决策者从中挑选。缺点缺点缺点缺点：难处在于实际问题中非劣解太多，难于一一推：难处在于实际问题中非劣解太多，难于一一推荐给决策者。荐给决策者。13目标规划引例：目标规划引例：利润最大化问题利润最大化问题某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两种产品，已知两种产品，已知有关数据如下表所示：有关数据如下表所示：拥有量拥有量原材料原材料 kg2111设备台时设备
13、台时 hr1210利润利润 元元/件件810 解：这是一个单目标规划问题，可用线性规划模型表述解：这是一个单目标规划问题，可用线性规划模型表述为：为：试求获利最大的方案。试求获利最大的方案。14目标函数目标函数max z=8x1+10 x2 约束条件约束条件2x1 +x2 11 x1 +2x2 10 x1,x2 0可用图解法求得最优决策方案为：可用图解法求得最优决策方案为：x1*=4,x2*=3,z*=62x1 +2x2 108x1+10 x2=c6123452468102x1 +x2 1115 在实际决策时，还应考虑市场等一系列其他条件，如：在实际决策时，还应考虑市场等一系列其他条件，如：（
14、1）市场调查发现：）市场调查发现：的销量有下降趋势，故应考虑的销量有下降趋势，故应考虑适当减少适当减少的产量增加的产量增加的产量，使的产量，使 （2）原材料的价格不断上涨，增加供应会使成本提高。）原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料。故不考虑再购买原材料。（3）为提高效率，应充分利用设备，但不希望加班。）为提高效率，应充分利用设备，但不希望加班。（4）市场虽发生变化，但利润应尽可能达到或超过）市场虽发生变化，但利润应尽可能达到或超过56元。元。此时的决策是多目标决策问题此时的决策是多目标决策问题目标规划方法目标规划方法是解决这类决策问题的方法之一是解决这类决策问题的
15、方法之一。161.1.正、负偏差变量正、负偏差变量正、负偏差变量正、负偏差变量d d+,d,d-d d+:决策值超过目标值的部分决策值超过目标值的部分 d d-：决策值未达到目标值的部分：决策值未达到目标值的部分 恒有恒有 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、价17硬约束硬约束软约束软约束2.绝对约束、目标约束绝对约束、目标约束绝对约束绝对约束绝对约束绝对约束：必须严格满足的等式或不等式约束：必须严格满足的等式或不等式约束目标约束目标约束目标约束目标约束：目标规划所特有的约束，约束右端项看作：目标规划所特有的约束，约束右端项看作要追求的目标值，在达到目标值时，允许发生正或负要追求的目标值，在达到目标值时，允许发生正或负的偏差的偏差 例如，原材料的价格不断上涨，增加供应会使成例如，原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料本提高。故不考虑再购买原材料 从而从而 2x1 +x2 11 是硬约束是硬约束183.3.优先因子与权系数优
17、先因子与权系数 目标规划问题常常有多个目标，但这些目标的主目标规划问题常常有多个目标，但这些目标的主次或轻重缓急是不同的。次或轻重缓急是不同的。最重要的目标赋予优先因子最重要的目标赋予优先因子P1P1，次一级的目标赋，次一级的目标赋予优先因子予优先因子P2P2，并规定，并规定P Pk kPPk+1k+1即表示即表示P Pk k比比P Pk+1k+1有更大的优先权。有更大的优先权。如果要区别具有相同优先因子的两个目标的差别，如果要区别具有相同优先因子的两个目标的差别，则分别赋予它们不同的权系数则分别赋予它们不同的权系数w wj j。194.4.目标规划的目标函数目标规划的目标函数 min min
18、 z=g(d,d)三种基本形式：三种基本形式：目标类型目标类型目标规划格式目标规划格式需要极小化需要极小化的偏差变量的偏差变量fi(x)bifi(x)dd bidfi(x)bifi(x)dd bidfi(x)bifi(x)dd biddd d+:决策值超过目标值的部分决策值超过目标值的部分d d-：决策值未达到目标值的部分：决策值未达到目标值的部分20例例2 2 引例的目标规划模型：引例的目标规划模型：2.2.产品产品的产量不低于产品的产量不低于产品的产量的产量1.1.原材料供应受严格限制原材料供应受严格限制2x1 +x2 11硬约束硬约束x1x2 d1d1 0d1x1 x2极小化极小化即即x
19、1 x2 0213.3.充分利用设备有效台时，不加班充分利用设备有效台时，不加班x12x2 d2d2 10d2d2x12x2 10极小化极小化4.4.利润额不小于利润额不小于5656元元8x110 x2d3d3 56d38x110 x2 56极小化极小化2223建模步骤小结：建模步骤小结：1.建立基础模型建立基础模型2.为每一个为每一个理想目标理想目标确定期望值确定期望值3.对每一个对每一个现实目标现实目标和约束都加上正负偏差和约束都加上正负偏差变量变量4.将目标按其重要性划分优先级，第一优先将目标按其重要性划分优先级，第一优先级为硬约束级为硬约束5.建立目标规划函数建立目标规划函数反映决策者
20、欲望，反映决策者欲望，如如“利润最大利润最大”配上期望值配上期望值的理想目标的理想目标24例例3：某单位领导在考虑本单位职工的升级调资方案时，某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：依次遵守以下规定：1.不超过年工资总额不超过年工资总额60000元元2.每级的人数不超过定编规定的人数每级的人数不超过定编规定的人数3.二、三级升级面尽可能达到但不超过现有人数的二、三级升级面尽可能达到但不超过现有人数的20%4.三级不足编制的人数可录用新职工，又一级的职工三级不足编制的人数可录用新职工，又一级的职工中又中又10%要退休要退休 试据下表数据建立模型试据下表数据建立模型25等级等
21、级工资额工资额(元元/年年)现有人数现有人数编制人数编制人数一一20001012二二15001215三三10001515合计合计374226参考模型如下：参考模型如下：设设x1、x2、x3分别表示提升到一、二级和录用到三级的分别表示提升到一、二级和录用到三级的新职工人数。各目标确定的优先因子为：新职工人数。各目标确定的优先因子为：P1不超过年工资总额不超过年工资总额60000元；元；P2每级的人数不超过定编制规定的人数每级的人数不超过定编制规定的人数 P3二、三级的升级面尽可能达到现有人二、三级的升级面尽可能达到现有人数的数的20%接下来确定模型接下来确定模型27首先给出首先给出基本模型基本模
22、型：年工资总额不超过年工资总额不超过6000060000元元：2000(10-10*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 028一、三级的升级面不大于现有人数的一、三级的升级面不大于现有人数的20%，但尽可，但尽可能多提：能多提：二级提升、二级提升、x1 12*0.2 即即 x1 2.4三级提升、
23、三级提升、x2 15*0.2 即即 x2 329 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+极小化极小化30 x1 2.4x2 3x1+d d5 5-d-d5 5+2.4x2+d d6 6-d-d6 6+3D D5 5+d+d6 6+极小化极小
24、化目标函数：目标函数：min z=P1 d1+P2(d2+d3+d4+)+P3(d5+d6+)31目标规划模型为：目标规划模型为：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+332三、目标规划的求解三、目标规划的求解主要思想：化成单目标问题，多阶段求解主要思想：化成单目标问题，多阶段求解33求解步骤：求解步骤：1.模型中约束不变，只取第一优先级为目标函数模型中约束不变，只取第一优先级为目标函数求出最优目标值为求出最优目标值为z d3-=0。342.只取第二优先级为目标函数，将上次求解结果只取第二优先级为目标函数，将上次求解结果的目标值的目标值d3-=0变为约束变为约束求出最优目标值为求出最优目标值为z 2d1+3d2+=12。353.只取第三优先级为目标函数，将上次求解结果只取第三优先级为目标函数，将上次求解结果的目标值的目标值2d1+3d2+=12变为约束变为约束