多目标最优化

目标规划一、多目标规划问题的提出：

多目标问题是现实世界中普遍遇到的一类问题，其中希望（或必须）考虑多个相互矛盾目标的影响。

例如证券投资问题中我们希望利润最大而风险最小，生产销售问题中我们希望费用较少而获利很大，等等。本章内容主要介绍：如何建立目标规划模型如何求解

单目标模型只需简单确定一个目标，而将其余的列为约束；

在构建多目标模型时，则需要对问题有较深的理解，必须考虑更全面——虽然费时较多，却非常有益，更切合实际。【例1】某工厂在计划期内要安排生产甲、乙两种产品。已知制造甲产品需要A型配件5个，B型配件3个；制造乙产品需要A型配件2个，B型配件4个。而在计划期内该工厂只能提供A型配件180个，B型配件135个。又知道该工厂每生产一件甲产品可获利润20元，一件乙产品可获利润15元。问在计划期内甲、乙产品应该各安排生产多少件，才能使总利润最大?甲乙现有配件A52180B34135利润（元）2015

将该例所述情况列成表格:

设x1、x2分别表示生产甲、乙产品的件数，Z表示总利润，当用线性规划来描述和解决这个问题时，其数学模型为用LINDO求解：max20x1+15x2s.t.5x1+2x2<1803x1+4x2<135endgin2最优值：775x1:32 x2:9

从线性规划的角度来看，问题似乎已经得到了圆满的解决。

但是，如果站在工厂计划人员的立场上对此进行评价的话，问题就不是这么简单了。第一，这是一个单目标最优化问题。但是，一般来说，一个计划问题要满足多方面的要求。例如财务部门利润目标：利润尽可能大物资部门节约资金：消耗尽可能小销售部门适销对路：产品品种多样计划部门安排生产：产品批量尽可能大

一个计划问题实际上是一个多目标决策问题。只是由于需要用线性规划来处理，计划人员才不得不从众多目标要求中硬性选择其一，作为线性规划的目标函数。但这样做的结果可能严重违背了某些部门的愿望，因而使生产计划的实施受到影响；或者在一开始就由于多方面的矛盾而无法从多个目标中选出一个目标来。第二，线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容。但是，实际问题有时不能满足这样的要求。例如，由于设备维修、能源供应、其它产品生产需要等原因，计划期内可以提供的设备工时不能满足计划产量工时需要。或由于储备资金的限制，原材料的最大供应量不能满足计划产量的需要。第三，线性规划解的可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言的。 在实际问题中，决策者在作决策时，往往还会对它作某种调整和修改，其原因可能是由于数学模型相对于实际问题的近似性近似性建模时对实际问题的抽象建模时未考虑到的新情况决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助做出最优决策的参考性的计划，或是提供多种计划方案。

现代决策强调定量分析和定性分析相结合，强调硬技术和软技术相结合，强调矛盾和冲突的合理性，强调妥协和让步的必要性。线性规划无法胜任这些要求。1961年，查恩斯(A.Charnes)和库柏(W.w.CooPer)提出目标规划(goalprogramming)，得到广泛重视和较快发展。目标规划在处理实际决策问题时，承认各项决策要求(即使是冲突的)的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。

因此，目标规划被认为是一种较之线性规划更接近于实际决策过程的决策工具。求解多目标决策常用的三种方法（或思想）：加权或效用系数法序列或优先级法有效解（非劣解）法加权法：加权法把问题中的所有目标用统一的单位来度量（例如用钱或效用系数）这种方法的核心是把多目标模型化成单目标模型。优点：适于计算机求解（例如模型是线性的时候可用一般的单纯形法求解）

缺点：难处在于如何寻到合理的权系数。序列或优先级法：序列或优先级法不是对每个目标加权，而是按照目标的轻重缓急，将其分为不同等级再求解。优点：避免了权系数的困扰，绝大多数决策者都能采用，事实上他们在许多决策中也正是这样做的。

例如建设高速公路时，既希望减少开支又希望降低交通伤亡事故，此时能否用金钱来衡量一个人的生命价值呢？例如决定人员的提升时，许多单位是按其工作态度、工作能力及对单位的有效价值等这样一个先后顺序来进行评定的。即没有任何其他方案能在各个方面完全胜出这个解

缺点：难处在于如何确切地定出各个目标的优先顺序以获得满意的求解结果。有效解（或非劣解）法：有效解（或非劣解）法“不会产生”象加权法或优先级法所具有的局限性，它将找出全部有效解集（即非劣解）以供决策者从中挑选。

缺点：难处在于实际问题中非劣解太多，难于一一推荐给决策者。目标规划引例：利润最大化问题某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知有关数据如下表所示：ⅠⅡ拥有量原材料kg2111设备台时hr1210利润元/件810

解：这是一个单目标规划问题，可用线性规划模型表述为：试求获利最大的方案。目标函数 maxz=8x1+10x2

约束条件 2x1+x2≤11

x1+2x2≤10

x1,x2≥0可用图解法求得最优决策方案为：

x1*=4,x2*=3,z*=62 x1+2x2≤108x1+10x2=c6123452468102x1+x2≤11

在实际决策时，还应考虑市场等一系列其他条件，如：（1）市场调查发现：Ⅰ的销量有下降趋势，故应考虑适当减少Ⅰ的产量增加Ⅱ的产量，使Ⅰ＜Ⅱ

（2）原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料。（3）为提高效率，应充分利用设备，但不希望加班。（4）市场虽发生变化，但利润应尽可能达到或超过56元。

此时的决策是多目标决策问题——目标规划方法是解决这类决策问题的方法之一。1.正、负偏差变量d+,d- d+:决策值超过目标值的部分

d-

：决策值未达到目标值的部分恒有d+×d-=0与建立目标规划模型有关的概念例如目标z=8x1+10x2≥56

可以变化为目标约束：

8x1+10x2+d1--d1+＝56

当d1-＝0时，目标约束与目标等价绝对约束2x1+x2≤11可以变换为目标约束：

2x1+x2+d2--d2+＝11

当d2+＝0时，目标约束与绝对约束等价硬约束软约束2.绝对约束、目标约束绝对约束：必须严格满足的等式或不等式约束目标约束：目标规划所特有的约束，约束右端项看作要追求的目标值，在达到目标值时，允许发生正或负的偏差

例如，原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料从而2x1+x2≤11是硬约束3.优先因子与权系数

目标规划问题常常有多个目标，但这些目标的主次或轻重缓急是不同的。最重要的目标赋予优先因子P1，次一级的目标赋予优先因子P2，…，并规定Pk>>Pk+1——即表示Pk比Pk+1有更大的优先权。如果要区别具有相同优先因子的两个目标的差别，则分别赋予它们不同的权系数wj。4.目标规划的目标函数minz=g(d＋,d－

)三种基本形式：目标类型目标规划格式需要极小化的偏差变量fi(x)≤bifi(x)＋d－－d＋＝bid＋fi(x)≥bifi(x)＋d－－d＋＝bid－fi(x)＝bifi(x)＋d－－d＋＝bid－＋d＋d+:决策值超过目标值的部分d-

：决策值未达到目标值的部分例2引例的目标规划模型：2.产品Ⅱ的产量不低于产品Ⅰ的产量1.原材料供应受严格限制2x1+x2≤11硬约束x1－x2

＋d1－－d1＋＝0d1＋x1≤

x2极小化即x1－x2≤

03.充分利用设备有效台时，不加班x1＋2x2

＋d2－－d2＋＝10d2－＋d2＋x1＋2x2

＝10极小化4.利润额不小于56元8x1＋10x2＋d3－－d3＋＝56d3－8x1＋10x2≥56极小化【毕】建模步骤小结：建立基础模型为每一个理想目标确定期望值对每一个现实目标和约束都加上正负偏差变量将目标按其重要性划分优先级，第一优先级为硬约束建立目标规划函数反映决策者欲望，如“利润最大”配上期望值的理想目标二、目标规划的图解法：x1x2od1+d1-d2+d2-d3+d3-最优解为黄色线段上任一点一般来说，目标期望值可调整以适应实际情况。硬约束2x1+x2≤11x1－x2

＋d1－－d1＋＝0d1＋极小化练习：

某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：不超过年工资总额60000元每级的人数不超过定编规定的人数二、三级升级面尽可能达到但不超过现有人数的20%三级不足编制的人数可录用新职工，又一级的职工中又10%要退休试据下表数据建立模型等级工资额(元/年)现有人数编制人数一20001012二15001215三10001515合计3742参考模型如下：设x1、x2、x3分别表示提升到一、二级和录用到三级的新职工人数。各目标确定的优先因子为：

P1——不超过年工资总额60000元；

P2——每级的人数不超过定编制规定的人数

P3——二、三级的升级面尽可能达到现有人 数的20%接下来确定模型首先给出基本模型：年工资总额不超过60000元：2000(10-10*0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)≤60000即 500x1+500x2x3≤900每级的人数不超过定编规定的人数：

10-10*0.1+x1

≤12 即x1

≤3

12-x1+x2

≤15 即x2-x1

≤3

15-x2+x3

≤15 即x3-x2

≤0一、三级的升级面不大于现有人数的20%，但尽可能多提： 二级提升、x1

≥12*0.2 即x1

≥2.4

三级提升、x2

≥15*0.2 即x2

≥3

x1

≤3

x2-x1

≤3

x3-x2

≤0

x1+d2–-d2+＝3

x2-x1+d3–-d3+＝3

x3-x2+d4–-d4+＝0转化为目标规划模型500x1+500x2x3≤900500x1+500x2x3+d1–-d1+＝900d1+极小化d2++d3++d4+极小化x1

≥2.4x2

≥3x1+d5–-d5+＝2.4x2+d6–-d6+＝3d5-+d6-极小化目标函数：

minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)目标规划模型为：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)s.t. 500x1+500x2x3+d1–-d1+＝900 x1+d2–-d2+＝3 x2-x1+d3–-d3+＝3 x3-x2+d4–-d4+＝0 x1+d5–-d5+＝2.4 x2+d6–-d6+＝3三、目标规划的lindo求解主要思想：化成单目标问题，多阶段求解用lindo求解步骤：模型中约束不变，只取第一优先级为目标函数注：在lindo中输入时，d3-可用d3_表示，d3+可用d3表示。求出最优目标值为z＝d3-

=0。只取第二优先级为目标函数，将上次求解结果的目标值d3-

=0变为约束求出最优目标值为z＝2d1++3d2+=12。只取第三优先级为目标函数，将上次求解结果的目标值2d1++3d2+=12变为约束求解出最优目标值z=d4+=4，此时x1=4，x2=12。OBJECTIVEFUNCTIONVALUE1)4.000000VARIABLEVALUEREDUCEDCOSTD44.0000000.000000X14.0000000.000000X212.0000000.000000D1_0.0000000.800000D16.0000000.000000D2_0.0000001.200000D20.0000000.000000D3_0.0000000.000000D30.0000000.600000D4_0.0000001.000000此时lindo求解结果如下：练习TM公司是一家较小的生产化妆品企业，从前仅生产一种指甲上光油，然而有一次，一个雇员偶然把一罐花生酱倒入上光油中，结果发现这种混合物能够暂时去除脸部的皱纹。这样公司就开始生产两种产品：指甲修饰用的上光油和使人年青的皱纹去除霜，改进后的产品配方需要两种不同的新的基本化学物，列于后表(这两种化学物的名称公司保密)。两种化学物的日用量是限定的，因为只有一个地方供应，且其生产能力巳达最大。由于这个原因，因此，尽管花生酱的供应且是充余的，但公司每天只需购买6磅，以保守产品的配方秘密。产品每加仑利润每加仑所需化学品A的磅数每加仑所需化学品B的磅数每加仑所需花生酱磅数青春霜80441指甲上光油100520日供应量(磅)80486经与公司经理交谈，确定下列几点：1．A、B两种化学品的日用量无论如何不能超过规定，即这些限制是硬约束。2．希望每天利润超过$800；3．每天订购的花生酱保持在6磅水平。

(这样就可以装扮成是为公司食堂进货)4．每天两种产品生产的加仑总数应尽可能少以便节省装运和人力费用。x1＝每天生产的青春霜数(加仑)x2＝每天生产指甲上光油数(加仑)则基础模型为：化学品A的约束化学品B的约束利润目标花生酱的定额求总产量目标值极小的欲望我们假定期望值为每天生产7加仑产品或更少，把这与建立的优先级联系在一起，可以得到如下线性目标规划模型：对于规定的达成向量该问题的解是：

x1＝0(日加仑)(即：不生产青春霜)x2＝8(日加仑)a＝【0，0，0，1】

因为a1＝0，所有硬