第六章多目标规划

多目标规划Multi-GoalProgramming前面介绍的都是具有单一目标函数的最优化问题。又称为数值优化问题。实际中还会遇到同时追求多个目标的最优化问题。多目标最优化也称多目标规划。例投资决策问题某投资开发公司拥有总资金A亿元，今有n(≥2)个项目可供选择投资，设投资第i(i=1:n)个项目要用自己ai亿元，预计收益bi亿元，应如何决策投资方案？一个好的投资方案显然应该是投资少，收益大的，假设xi=1表示第i个项目被投资

0表示第i个项目不被投资

这样我们只要求出xi(i=1:n)是0还是1就知道每一个项目是否被投资了！xi(i=1:n)称为投资决策变量。这样,可写出我们的最优目标了：maxb1x1+b2x2+…+bnxnmina1x1+a2x2+…+anxn因总资金有限故要有约束:a1x1+a2x2+…+anxn≤A另外还应限定xi只能取0或1故有约束:xi(xi-1)=0,i=1:n从而有数学模型：

maxb1x1+b2x2+…+bnxn

mina1x1+a2x2+…+anxns.t.a1x1+a2x2+…+anxn≤A

xi(xi-1)=0,i=1:ns.t.si(x1,…,xn)≥0,i=1:phj(x1,…,xn)=0,j=1:q这个问题就是考虑在一定限制条件下，多于一个数值目标函数的最优化问题，其一般形式是：1.数学模型(vmp)minf1(x1,x2,…,xn)………….minfr(x1,x2,…,xn)maxgr+1(x1,x2,…,xn)……………maxgm(x1,x2,…,xn)V-minf(x)s.t.s(x)≥0h(x)=0----多目标极小化模型（向量极小化模型）fi(x)称为分量目标函数

而通过取目标函数的相反数可以将求极大转化为求极小，从而有下述一般形式：minf1(x1,x2,…,xn)………….minfm(x1,x2,…,xn)s.t.si(x1,…,xn)≥0,i=1:phj(x1,…,xn)=0,j=1:q.分层VMP

显然，VMP的区分于数值优化的特点之一：在一系列的约束条件下，不仅仅是单纯地追求单个目标的最优，而是同时考虑到多个目标的取值。在实际问题中，显然，有时这些所有的目标按照决策者的偏好或实际问题的要求，所处的地位是不一样的。所以我们可以对这多个目标按不同的优先级层次先后进行最优化。这类模型就称为分层多目标最优化问题。目标规划问题的数学模型(GP)

对于问题，事先已经对每个求解目标确立了明确的函数值，此时规划的任务就是在约束条件的要求下，使得每一目标函数尽可能地逼近给定的函数值。而不是关注于求解各个目标函数的最小值。具体描述如下：给定m个目标函数，事先确定的对应的目标函数值

显然，为了度量函数值与给定的目标值之间的差距，我们必须引入一个标准：向量范数。所以GP问题相应转化为如下的模型采用的范数不同，则对应于不同的求解策略。无穷-范数：使偏离目标的最大值最小。1-范数：使每个函数偏离目标的偏离值之和最小。2。GP问题的有效求解算法偏差变量正偏差变量：负偏差变量：显然引入的变量有如下的性质如果采用1-范数，则问题化为即

新增加了四个约束条件，其中只有一个为非线性约束。显然如果此条件去掉，将使问题的求解极大地简便。(9.1)(9.2)定理(1)(2)若为(2)的最优解，则：必是(1)的最优解。其中：简单GP

目标规划：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。③Z=0：各级目标均已达到

Z>0：部分目标未达到。①目标函数中只有偏差变量。②目标函数总是求偏差变量最小。深入分析1。如果D为x的线性约束集，则显然问题是一个线性规划问题，可以用单纯形或对偶单纯形算法求解。2。D为线性约束集，且问题为按分层次求解的最优化问题，我们称这类问题为线性目标规划问题LDP，这类问题在实际生产管理，商业决策等有广泛的应用范围和重大的实用价值。实际问题中存在绝对最优解的情况是很少见的。2.解的概念与单目标问题相比，这里由于目标函数不是单一的，所以问题的解的概念变的复杂。对问题v-minf(x)s.t.xD(i)绝对最优解

若x*D,使得任意xD，有f1(x*)≤f1(x),f2(x*)≤f2(x),…,fr(x*)≤fr(x)(即f(x*)≤f(x)任意xD)。这也就是说x*为每个单目标问题minfi(x)i=1:r的最优解

s.t.xD或说每个单目标最优解存在且相等则即为绝对最优解所有绝对最优解的集合称为问题的绝对最优解集，记Z*(f,D),简记Z*f1f2D对问题v-minf(x)s.t.xD(ii)有效解

(Pareto解)

若x*D,在D内找不到x使得f1(x)≤f1(x*),f2(x)≤f2(x*),…,fr(x)≤fr(x*),且其中至少有一个是严格小于.所有有效解的集合称为问题的有效解集，记P(f,D),简记P比如minf1(x)minf2(x)s.t.xD

是如图的一维问题。问题无绝对最优解。f1f2Dx*

·

有效解若x*D,在D内找不到x使得

f1(x)≤f1(x*),f2(x)≤f2(x*),…,fr(x)≤fr(x*)，且其中至少有一个是严格小于。现验证minf1(x),xD的最优解x*是多目标问题的一个有效解：按定义只要说明找不到xD使得f1(x)≤f1(x*)f2(x)<f2(x*)f1(x)<f1(x*)f2(x)≤f2(x*)f1(x)<f1(x*)f2(x)<f2(x*)或或f1f2Dx*··

x**f1(x)≤f1(x**)f2(x)<f2(x**)f1(x)<f1(x**)f2(x)≤f2(x**)f1(x)<f1(x**)f2(x)<f2(x**)或或现验证minf2(x),xD的最优解x**是多目标问题的一个有效解：按定义只要说明找不到xD使得Pf1f2Dx*

··

x**

类似,可以验证x*与x**之间的每一点均是有效解，除此以外的点均不是。

此例可见：有效解的概念比绝对最优解的概念要弱好多，这些解虽不是最优但也不算太坏的，故也称非劣解,Pareto(帕莱托)解,或可接受解。有效解是多目标规划问题的求解目的。f1f2Pwx*·比如图中x*就找不到一个x使得f1(x)<f1(x*)f2(x)<f2(x*)对问题v-minf(x)s.t.xD将有效解中的条件稍微放宽得(iii)弱有效解

若x*D,在D内找不到x使得

f1(x)<f1(x*),f2(x)<f2(x*),…,fr(x)<fr(x*).所有弱有效解的集合称为问题的弱有效解集,记Pw(F,D),简记Pw.比如上例中弱有效解集Pw3.各解集间的关系(i)对i=1:r,设Xi*表示minfi(x)s.t.xD

的最优解集,则X*=X1*∩..∩Xr*Proof:x*X*fi(x*)≤fi(x),i=1:r,xDx*Xi*,i=1:r,x*X1*∩..∩Xr*(ii)绝对最优解必为有效解，即X*P(F,D)。Proof:要证x*X*，必x*P(F,D)反设有一个x*X*，但x*P(F,D)由P(F,D)的定义知存在一点x’D,使得f1(x’)≤f1(x*),f2(x’)≤f2(x*),…,fr(x’)≤fr(x*),其中至少有一个严格小于成立。但这个严格成立的小于就与x*为绝对最优解矛盾。(iii)有效解必为弱有效解，即PPw。(iv)各分量目标函数在D上的最优解必为弱有效解，即Xi*Pw,i=1:r.Proof:(iii)(iv)与(ii)类似。由(iii)(iv)可知:(v)P∪(X1*∪X2*∪…∪Xr*)Pw,综上，各解集之间的关系是：

(X1*∩X2*∩…∩Xr*)=X*PPwD.4.评价函数法

对于多目标问题的求解，最好的当然是求出其绝对最优解；但它经常不存在或是不好求，则应求出其有效解，最差的也要求出其弱有效解。事实上，对于实际问题，能求出满足一定要求的有效解或弱有效解就行了。评价函数法的基本思想

根据问题本身的特点和决策者的对问题的要求，构造一个函数(评价函数)，将m个分量目标函数转化为一个数值目标函数，从而将多目标优化问题的求解转化为单目标优化问题。基本概念设

:RrR1,z’,z”Rr,单调增函数：当z’i<z”i,(i=1:r)，总有

(z’)<(z”)严格单调增函数：当z’i≤z”i,(i=1:r,至少有一个严格小于成立)，总有

(z’)<(z”)(z)=u1z1+u2z2+…+urzr,其中ui≥0,i=1:r,u1+…+ur=1显然是单调增函数：若z’<z”则u1z1’+u2z2’+…+urzr’<u1z1”+u2z2”+…+urzr”，即(z’)<(z”)特别地，若ui>0,i=1:r,则可验证(z)是严格单调增函数。f:RnRr,:RrR1,x*是min(f(x))的极小点

s.t.xD若为严格单调增函数，则x*P(f,D)证明:反证法。设x*P(f,D),则必存在一点x’D,使得fi(x’)

≤fi(x*),(i=1:r,至少有一个严格小于成立)，而为严格单调增函数，故(f(x’))<(f(x*))与x*是单目标函数的最优解矛盾！意义：这样只要找到一个适当的函数，求出转化后的单目标问题的最优解，即得到原问题的一个有效解)评价算法的理论依据f:RnRr,:RrR1,x*是min(f(x))的极小点

s.t.xD若为单调增函数，则x*Pw(f,D)意义：这样只要找到一个适当的函数，求出转化后的单目标问题的最优解，即得到原问题的一个弱有效解)

求解原多目标问题，就只要构造为严格单调增或是单调增就行了，这种称为评价函数。这种求解多目标问题的解的方法就称为评价函数法。

不同的构造的方法(当然得到不同的有效解)形成不同的评价函数法。4.1线性加权法

(最基本的评价函数法)

取(z)=u1z1+u2z2+…+urzr,其中ui≥0,i=1:r,u1+…+ur=1显然，是单调增函数：特别地，若ui>0,i=1:r,(z)是严格单调增函数。这样，只要适当选择u的各个分量，即可通过求解单目标问题minu1f1(x)+u2f2(x)+…+urfr(x)s.t.xD得到多目标问题V-minf(x)的有效解或弱有效解。

s.t.xDUi为表征各目标相对重要程度的量(权系数)选的不同会得到不同的有效解(弱有效解)。4.2理想点法

分别求出各个分量目标函数的极小值，然后将这些值作为理想值，让各分量目标函数尽可能地向各处的理想值逼近。从而获得原问题的解理想点分析(2)如果各分量目标函数的最优解不全相等，根据理想点的算法思想，我们要尽量向“理想点”逼近。对逼近的程度，我们用范数加以衡量引入P-范数，构造函数很容，u(F)就是F的严格单调增函数。(1)如果

，则意味着对于同一个解，每个分量目标函数均达到最优值，即是VMP问题的绝对最优解。例如：取p=2平方和加权法对理想点法(f(x))=||F(x)-F*||2加以改造而来首先，将fi*换为fi(x)在D上极小值的一个估计值zi0,而不进行zi*的计算；其次，将根号去掉，不进行根号运算;并将平方和的各项赋予适当的权系数;从而得

(f(x))=u1(f1(x)-z10)2+u2(f2(x)-z20)2+…+um(fm(x)-zm0)2可验证ui>0,i=1:r时为严格单调增函数。5权系数的确定

从前面分析可知，有的方法中需要确定权系数。不同的权系数对应不同的有效解或弱有效解，但对于实际问题中的多目标问题并不是求出的任意有效解或弱有效解都有意义，所以我们必须合理选取权系数。一老手法老手即有关专家、有实践经验的工作者。老手法即是通过汇集多位老手的经验估计来确定权系数。具体来说：设多目标问题有r个目标，今请了q位老手。

在他们对问题有充分的了解后,请他们独自对各目标的重要程度进行评估。常用的确定权系数的方法

设第i位老手对第j个目标赋予的权系数是uij(≥0),当然要求ui1+ui2+…+uir=1,i=1:q再计算各目标的权系数的平均值uj=(u1j+u2j+…+uqj)/q,j=1:r然后计算各老手所提供的权系数与平均值的偏差di=max|uij-uj|,若di<(事先指定的误差限),i=1:q则表明老手们的经验估计无显著差别，权系数u1,…ur可以接