多目标最优化

1、多目标最优化 第1页，共35页，2022年，5月20日，14点10分，星期二本章内容主要介绍：如何建立目标规划模型如何求解 单目标模型只需简单确定一个目标，而将其余的列为约束； 在构建多目标模型时，则需要对问题有较深的理解，必须考虑更全面虽然费时较多，却非常有益，更切合实际。第2页，共35页，2022年，5月20日，14点10分，星期二【例1】某工厂在计划期内要安排生产甲、乙两种产品。已知制造甲产品需要A型配件5个，B型配件3个； 制造乙产品需要A型配件2个，B型配件4个。 而在计划期内该工厂只能提供A型配件180个，B型配件135个。 又知道该工厂每生产一件甲产品可获利润20元，一件乙产品可

2、获利润15元。问在计划期内甲、乙产品应该各安排生产多少件，才能使总利润最大? 甲乙现有配件A52180B34135利润（元）2015 将该例所述情况列成表格:第3页，共35页，2022年，5月20日，14点10分，星期二 设x1、x2分别表示生产甲、乙产品的件数，Z表示总利润，当用线性规划来描述和解决这个问题时，其数学模型为 最优值：775 x1: 32x2: 9第4页，共35页，2022年，5月20日，14点10分，星期二 但是，如果站在工厂计划人员的立场上对此进行评价的话，问题就不是这么简单了。 第一，这是一个单目标最优化问题。但是，一般来说，一个计划问题要满足多方面的要求。例如财务部门利

3、润目标：利润尽可能大物资部门节约资金：消耗尽可能小销售部门适销对路：产品品种多样计划部门安排生产：产品批量尽可能大第5页，共35页，2022年，5月20日，14点10分，星期二 一个计划问题实际上是一个多目标决策问题。只是由于需要用线性规划来处理，计划人员才不得不从众多目标要求中硬性选择其一，作为线性规划的目标函数 。 但这样做的结果可能严重违背了某些部门的愿望，因而使生产计划的实施受到影响；或者在一开始就由于多方面的矛盾而无法从多个目标中选出一个目标来。第6页，共35页，2022年，5月20日，14点10分，星期二第二，线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容。但是，

4、实际问题有时不能满足这样的要求 。例如，由于设备维修、能源供应、其它产品生产需要等原因，计划期内可以提供的设备工时不能满足计划产量工时需要 。 或由于储备资金的限制，原材料的最大供应量不能满足计划产量的需要 。第7页，共35页，2022年，5月20日，14点10分，星期二第三，线性规划解的可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言的。在实际问题中，决策者在作决策时，往往还会对它作某种调整和修改，其原因可能是由于数学模型相对于实际问题的近似性 近似性建模时对实际问题的抽象 建模时未考虑到的新情况 决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助做出最优决策的参考

5、性的计划，或是提供多种计划方案。第8页，共35页，2022年，5月20日，14点10分，星期二 1961年，查恩斯(A.Charnes)和库柏(W.w.CooPer)提出目标规划(goal programming)，得到广泛重视和较快发展。 目标规划在处理实际决策问题时，承认各项决策要求(即使是冲突的)的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。 因此，目标规划被认为是一种较之线性规划更接近于实际决策过程的决策工具 。第9页，共35页，2022年，5月20日，14点10分，星期二求解多目标决策常用的三种方法（或思想）：加权或效用系数法序列或优先级法有效解（非劣解）法加权法：加

6、权法把问题中的所有目标用统一的单位来度量（例如用钱或效用系数） 这种方法的核心是把多目标模型化成单目标模型。优点：适于计算机求解（例如模型是线性的时候可用一般的单纯形法求解）第10页，共35页，2022年，5月20日，14点10分，星期二 缺点：难处在于如何寻到合理的权系数。序列或优先级法：序列或优先级法不是对每个目标加权，而是按照目标的轻重缓急，将其分为不同等级再求解。优点：避免了权系数的困扰，绝大多数决策者都能采用，事实上他们在许多决策中也正是这样做的。 例如建设高速公路时，既希望减少开支又希望降低交通伤亡事故，此时能否用金钱来衡量一个人的生命价值呢？例如决定人员的提升时，许多单位是按其工

7、作态度、工作能力及对单位的有效价值等这样一个先后顺序来进行评定的。第11页，共35页，2022年，5月20日，14点10分，星期二即没有任何其他方案能在各个方面完全胜出这个解 缺点：难处在于如何确切地定出各个目标的优先顺序以获得满意的求解结果。有效解（或非劣解）法：有效解（或非劣解）法“不会产生”象加权法或优先级法所具有的局限性，它将找出全部有效解集（即非劣解）以供决策者从中挑选。 缺点：难处在于实际问题中非劣解太多，难于一一推荐给决策者。第12页，共35页，2022年，5月20日，14点10分，星期二目标规划引例： 利润最大化问题某工厂在计划期内要安排生产、 两种产品，已知有关数据如下表所示

8、：拥有量原材料 kg2111设备台时 hr1210利润 元/件810 解：这是一个单目标规划问题，可用线性规划模型表述为：试求获利最大的方案。第13页，共35页，2022年，5月20日，14点10分，星期二目标函数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 11第14页，共35页，2022年，5月20日，14点10分，星期二 在实际决策时，还应考虑市场等一系列其他条件，如：（

9、1）市场调查发现：的销量有下降趋势，故应考虑适当减少的产量增加的产量，使 （2）原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料。 （3）为提高效率，应充分利用设备，但不希望加班。 （4）市场虽发生变化，但利润应尽可能达到或超过56元。 此时的决策是多目标决策问题目标规划方法是解决这类决策问题的方法之一。第15页，共35页，2022年，5月20日，14点10分，星期二1. 正、负偏差变量d+,d- d+ : 决策值超过目标值的部分 d- ：决策值未达到目标值的部分 恒有 d+d-=0与建立目标规划模型有关的概念例如目标 z = 8x1+10 x2 56 可以变化为目标约束： 8

10、x1+10 x2+d1-d1+56当d1 - 0时，目标约束与目标等价绝对约束 2x1 + x2 11 可以变换为目标约束： 2x1 + x2 +d2-d2+11当d2+0时，目标约束与绝对约束等价第16页，共35页，2022年，5月20日，14点10分，星期二硬约束软约束2 . 绝对约束、目标约束绝对约束：必须严格满足的等式或不等式约束目标约束：目标规划所特有的约束，约束右端项看作要追求的目标值，在达到目标值时，允许发生正或负的偏差 例如，原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料 从而 2x1 + x2 11 是硬约束第17页，共35页，2022年，5月20日，14点

11、10分，星期二3 . 优先因子与权系数 目标规划问题常常有多个目标，但这些目标的主次或轻重缓急是不同的。 最重要的目标赋予优先因子P1，次一级的目标赋予优先因子P2，并规定PkPk+1即表示Pk比Pk+1有更大的优先权。 如果要区别具有相同优先因子的两个目标的差别，则分别赋予它们不同的权系数wj。第18页，共35页，2022年，5月20日，14点10分，星期二4 .目标规划的目标函数 min z = g ( d, d )三种基本形式：目标类型目标规划格式需要极小化的偏差变量fi(x) bifi(x) dd bidfi(x) bifi(x) dd bidfi(x) bifi(x) dd bidd

12、d+ : 决策值超过目标值的部分d- ：决策值未达到目标值的部分第19页，共35页，2022年，5月20日，14点10分，星期二例2 引例的目标规划模型：2.产品的产量不低于产品的产量1.原材料供应受严格限制2x1 + x2 11硬约束x1x2 d1d1 0d1x1 x2极小化即x1 x2 0第20页，共35页，2022年，5月20日，14点10分，星期二3.充分利用设备有效台时，不加班x12x2 d2d2 10d2d2x12x2 10极小化4.利润额不小于56元8x110 x2d3d3 56d38x110 x2 56极小化第21页，共35页，2022年，5月20日，14点10分，星期二第22

13、页，共35页，2022年，5月20日，14点10分，星期二建模步骤小结：建立基础模型为每一个理想目标确定期望值对每一个现实目标和约束都加上正负偏差变量将目标按其重要性划分优先级，第一优先级为硬约束建立目标规划函数反映决策者欲望，如“利润最大”配上期望值的理想目标第23页，共35页，2022年，5月20日，14点10分，星期二例3：某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：不超过年工资总额60000元每级的人数不超过定编规定的人数二、三级升级面尽可能达到但不超过现有人数的20%三级不足编制的人数可录用新职工，又一级的职工中又10%要退休 试据下表数据建立模型第24页，共35页

14、，2022年，5月20日，14点10分，星期二等级工资额(元/年)现有人数编制人数一20001012二15001215三10001515合计3742第25页，共35页，2022年，5月20日，14点10分，星期二参考模型如下：设x1、x2、x3分别表示提升到一、二级和录用到三级的新职工人数。各目标确定的优先因子为： P1不超过年工资总额60000元； P2每级的人数不超过定编制规定的人数 P3二、三级的升级面尽可能达到现有人数的20%接下来确定模型第26页，共35页，2022年，5月20日，14点10分，星期二首先给出基本模型：年工资总额不超过60000元： 2000 ( 10-10*0.1+

15、x1 ) + 1500 ( 12-x1+x2 ) + 1000 ( 15-x2+x3 ) 60000即 500 x1+500 x2+1000 x3 900每级的人数不超过定编规定的人数： 10 - 10*0.1 + x1 12即 x1 3 12 - x1 + x2 15即 x2 - x1 3 15 - x2 + x3 15即 x3 - x2 0第27页，共35页，2022年，5月20日，14点10分，星期二一、三级的升级面不大于现有人数的20%，但尽可能多提：二级提升、 x1 12*0.2即 x1 2.4三级提升、 x2 15*0.2即 x2 3第28页，共35页，2022年，5月20日，14

16、点10分，星期二 x1 3 x2 - x1 3 x3 - x2 0 x1 + d2 -d2+ 3 x2 - x1 + d3 -d3+ 3 x3 - x2 + d4 -d4+ 0转化为目标规划模型500 x1+500 x2+1000 x3 900500 x1+500 x2+1000 x3 + d1 -d1+900d1+极小化d2+ + d3+ + d4+极小化第29页，共35页，2022年，5月20日，14点10分，星期二x1 2.4x2 3x1 + d5 -d5+ 2.4x2 + d6 -d6+ 3D5+ + d6+极小化目标函数： min z = P1 d1+ + P2( d2+ + d3+

17、 + d4+ )+ P3( d5+ + d6+ )第30页，共35页，2022年，5月20日，14点10分，星期二目标规划模型为：min z = P1 d1+ + P2( d2+ + d3+ + d4+ )+ P3( d5- + d6- )s.t.500 x1+500 x2+1000 x3 + d1 -d1+900 x1 + d2 -d2+ 3 x2 - x1 + d3 -d3+ 3 x3 - x2 + d4 -d4+ 0 x1 + d5 -d5+ 2.4x2 + d6 -d6+ 3第31页，共35页，2022年，5月20日，14点10分，星期二三、目标规划的求解主要思想：化成单目标问题，多阶