《多目标最优化》由会员分享，可在线阅读，更多相关《多目标最优化（47页珍藏版）》请在金锄头文库上搜索。
1、本章内容主要介绍:如何建立目标规划模型如何求解单目标模型只需简单确定一个目标，而将其 余的列为约貶在构建多目标模型时，则需要对问题有较深的 理解，必须考虑更全面一虽然费时较多，却非常有益,更切合实际。【例1】某工厂在计划期内要安排生产甲、乙两种产品。 已知制造甲产品需要A型配件5个,B型配件3个； 制 造乙产品需要A型配件2个,B型配件4个。 而在计划 期内该工厂只能提供A型配件180个，B型配件135个。又知道该工厂每生产一件甲产品可获利润20元，一件乙 产品可获利润15元。问在计划期内甲、乙产品应该各安 排生产多少件，才能使总利润最大？将该例所述情况列成表格:甲A5B3利润（元）20乙现有
2、配件2180413515设心、兀2分别表示生产甲、乙产品的件数，Z表示 总利润，当用线性规划来描述和解决这个问题时, 其数学模型为maxZ = 20xj +15x25x + 2x2 180s.t.3x +4兀2 Q,x2Q坷,兀2为整数#但是，如果站在工厂计划人员的立场上对此进行评 价的话，问题就不是这么简单了。第一，这是一个单目标最优化问题。但是，一般来 说，一个计划问题要满足多方面的要求。例如财务部门物资部门节约资金：消耗尽可能小1销售部门适销对路：产品品种多样1计划部门安排生产：产品批量尽可能大一个计划问题实际上是一个多目标决策问题。只 是由于需要用线性规划来处理，计划人员才不得不 从众
3、多目标要求中硬性选择其一，作为线性规划的 目标函数。但这样做的结果可能严重违背了某些部门的愿望, 因而使生产计划的实施受到影响；或者在一开始就 由于多方面的矛盾而无法从多个目标中选出一个目 标来。第二，线性规划有最优解的必要条件是其可行解集 非空，即各约束条件彼此相容。但是，实际问题 有时不能满足这样的要求。例如，由于设备维修、能源供应、其它产品生产需 要等原因，计划期内可以提供的设备工时不能满足 计划产量工时需要。或由于储备资金的限制，原材料的最大供应量不 能满足计划产量的需要。#第三，线性规划解的可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言的。在实际问题中，决策者在作决策
4、时，往往还会对 它作某种调整和修改，其原因可能是由于数学模 型相对于实际问题的近似性T建模时对实际问题的抽象决策者需要计划人员提供的不是严格的数学上的最 优解，而是可以帮助做出最优决策的参考性的计划, 或是提供多种计划方案。1961 年，查恩斯(A.Charnes)和库柏(W.w.CooPer)提 出目标规划(goal programming),得到广泛重视和较快 发展。目标规划在处理实际决策问题时，承认各项决策要求 (即使是冲突的)的存在有其合理性；在作最终决策时, 不强调其绝对意义上的最优性。因此，目标规划被认为是一种较之线性规划更接近于 实际决策过程的决策工具#求解多目标决策常用的三种方
5、法（或思想）:1. 加权或效用系数法2. 序列或优先级法3. 有效解（非劣解）法1 加权法:加权法把问题中的所有目标用统一的单位来度量（例 女口用钱或效用系数）这种方法的疵心是把多目标模型化成单目标模型。适于计算机求解（例如模型是线性的时候可用一般的单纯形法求解）#橡纭难处在于如何寻到合理的权系数。例如建设高速公路时，既希望减少开支又希望降低 交通伤亡事故，此时能否用金钱来衡量一个人的生命 价值呢？2.序列或优先级法:序列或优先级法不是对每个目标加权，而是按照目标 的轻重缓急，将其分为不同等级再求解。优皮：避免了权系数的困扰，绝大多数决策者都能采 用，事实上他们在许多决策中也正是这样做的。例如
6、决定人员的提升时，许多单位是按其工作态度、 工作能力及对单位的有效价值等这样一个先后顺序来 进行评定的。缺JL：难处在于如何确切地定出各个目标的优先顺序 以获得满意的求解结果。3.有效解（或非劣解）法:即没有任何其他方案 能在各个方面完全胜I 岀这个夢 _ 有效解（或非劣解）法“不会产生”象加权庫或赫 级法所具有的局限性，它将找出全部有效解集（即韭 劣解）以供决策者从中挑选。难处在于实际问题中非劣解太多，难于一一推 荐给决策者。目标规划引例：利润最大化问题某工厂在计划期内要安排生产I、II两种产品，已知有关数据如下表所示:III拥有量原材料kg2111设备台时hr1210利润洽件810试求获利
7、最大的方案。解：这是一个单目标规划问题，可用线性规划模型表 述为：目标函数 max z = 8兀1+10兀2 约束条件2xi + x2 11xx + 2x2 0Xj + 2x2 108xj+10x2=c2X + x2 56可以变化为目标约束：8r1+10x2+d1-d1+=56当右-=0时,目标约束与目标等价绝对约束2xi + x2ll可以变换为目标约束： + X2 +d2_d2+=ll当（VF时，目标约束与绝对约束等价 15#硬约束2 甘约束、目标约束绝对约束：必须严格满足的等式或不等式约束目标约束、目标规划所特有的约束，约束右端项看作 要追求的 曠值，在达到目标值时，允许发生正或负 的偏差
8、软约束例如，原材料的价格不断上涨，增加供应会使成 本提高。故不考虑再购买原材料从而 2xy + x2 11是硬约束3优先因子与权系数目标规划问题常常有多个目标，但这些目标的主 次或轻重缓急是不同的。【重要的目标赋予优先因子P1,次一级的目标赋予优先因子P2, 并规定PkPk+1即表示Pk比 Pk+i有更大的优先权。如果要区别具有相同优先因子的两个目标的差别,则分别赋予它们不同的权系数亏o#cT :决策值超过目标值的部分d-:决策值未达到目标值的部分4 目标规划的目标函数min z二）八三种基本形式:目标类型目标规划格式需要极小化 的偏差变量ZW S bift（x） + dd+ =d+fi（x）
9、 2 叽fi（x） + dd+ = btdfiM = bifi（x） + d-d+ = btd+d+例2引例的目标规划模型:1 原材料供应受严格限制V A #V A #2xi + x2 11硬约束V A #V A #2产品II的产量不低于产品I的产量V A #V A #即兀1 x2 56V A #V A #极小化8x1+10x2+d3_rf3+ =56V A #综上可得目标规划模型 min z = P/J + 匕； + 九）+ 戸3；2xx+兀2 o：,i = 1,2,3建模步骤小结:反映决策者欲望, 如“利润最大”配上期望值 的理想目标1. 建立基础模型2. 为每一个理想目标砂3. 对每一个
10、现实目标新约束都加上正负偏差 变量4将目标按其重要性划分优先级，第一优先 级为硬约束5.建立目标规划函数例3：某单位领导在考虑本单位职工的升级调资方案时, 依次遵守以下规定：1不超过年工资总额60000元2.每级的人数不超过定编规定的人数3.二、三级升级面尽可能达到但不超过现有人数的20%4三级不足编制的人数可录用新职工，又一级的职工 中又10%要退休试据下表数据建立模型等级工资额 （石年）现有人数编制人数20001012二15001215三10001515合计3742参考模型如下：设勺、兀2、无3分别表示提升到一、二级和录用到三级的 新职工人数。各目标确定的优先因子为：P1不超过年工资总额6
11、0000元；P2每级的人数不超过定编制规定的人数P3一二、三级的升级面尽可能达到现有人数的20 %接下来确定模型首先给出基痒橫媲：年工资总额不超过60000元：2000( 10-100.1+Xx) + 1500( 12-xx+x2)+ 1000 ( 15-x2+x3 ) 60000即500可+500兀2+1000兀 3 900每级的人数不超过定编规定的人数:即 Xx 3即X2 -兀1 3即 x3 - x2 01. 10 10*0.1 +Xi 122. 12 兀1 + 兀2 S15315 兀2 +兀3冬15一、三级的升级面不大于现有人数的20%,但尽可 能多提：二级提升、Xi 12*0.2 即 2.4三级提升、x2 15*0.2即兀2S3#500x1+500x2+1000x3 900转化为貝标规划撲媲500x1+500x2+1000x3 + df -1=900极小化#x3 - x2 0可+ d2- -d2+= 3极小化x2-xx + d3- -d3+= 3 d2+ + d3+ d4+兀3 兀2 + 4- _04十=0l 28#极小化目标函数：min z = Pl dx+ + P2( d2+ + d3+ + d4+)+ P3( d5+ + d6+)#冃棵规刻模媲參：min z = Pl + + P2( d2+4- d3500兀1+500兀
