历史百科网

多目标规划

[拼音]:duomubiao guihua

[外文]:multiple objectives programming

数学规划的一个分支,研究多于一个的目标函数在给定区域上被同等地较优化(极小化或极大化)的问题(称为多目标较优化或向量极值)。

多目标极小化问题通常记为(VMP)

其中 是给定的一个向量值目标函数,T表示转置,表示在区域 X上的函数ƒ1(x),ƒ2(x),…,ƒm(x)被同等地极小化。

若(VMP)中的ƒ(x)是x的线性(向量)函数,X是Rn中的多面体,则相应的问题称为多目标线性规划问题。若(VMP)中的ƒ(x)是x的非线性(向量)函数,或X不是Rn中的一个多面体,则称为多目标非线性规划问题。对于多目标规划,解的定义是一个非常重要的问题。

公式∈X,且不存在其他的可行点x使得ƒ(x)≤ƒ(),则称为(VMP)的有效解(这里“≤”表示向量的每一分量间都是“≤”且至少有一个分量间是“<”,而“<”表示它们的每一个分量间都是“<”)。有效解也叫做帕雷托较优解或非劣解。如果塣∈X, 且不存在其他的可行点x使ƒ(x)<ƒ(),则称为(VMP)的弱有效解。设ƒ把X映射到Rm中的可达目标集Y=ƒ(X)。若Y是一紧集,则问题(VMP)的有效解和弱有效解存在。

一个多目标规划问题通常存在许多个有效解。在自然序意义下,因各有效解之间相互不能进行比较。因而要在它们之中加以选择,就需要引入一个偏爱序。这相当于要从决策者那里得到另外的信息。如何选取这种另外的信息以提炼成一种偏爱模式,并且在某种偏爱关系的基础上建立起有关的数学理论,是多目标规划研究的一个重要课题。

1968年A.M.日夫里翁引进了真有效解概念:如果是(VMP)的有效解,且存在一数值M>0,使得对于满足ƒi(x)<ƒi()的每一i和每一x∈X,至少存在一个使 ƒi(x)>ƒ(j)的j(1≤j≤m)有[ƒi()-ƒi(x)]/[ƒj(x)-ƒj()]≤M,则称为问题(VMP)的真有效解。在多目标规划的研究中,还引入了一些其他意义下的解的概念,如局部有效解、库恩-塔克尔意义下的有效解等。对这些解的性质及其相互关系已进行了若干探讨,例如,对伪单调多目标规划、凸多目标规划已研究了有效解的性质,并建立了一些关于有效解和弱有效解的判别准则。在多目标规划的研究中,目标空间并不限于欧氏空间Rm,例如,目标函数是表示一国经济增长的一个动态模型的所有轨线,则目标空间就是一个希尔伯特空间。目前,目标空间是抽象的巴拿赫空间或希尔伯特空间的情形,已有不少研究。

一个与多目标问题(VMP)相关联的单目标问题(Pλ)

是引人重视的,其中λi叫做权系数,叫做权向量。通常要求权系数满足或‖λ‖=1(依Rm中任意选定的模)使之规范化。记,,则有以下的基本定理:

设∈X是(Pλ)的较优解,λ∈Λ,则是(VMP)的弱有效解;若X是凸集,ƒ(x)是X上的凸函数,且是(VMP)的弱有效解,则存在某一λ∈Λ使是(Pλ)的较优解。若λ∈Λ+,是(Pλ)的较优解,则是(VMP)的真有效解;若X是凸集,ƒ(x)是X上的凸函数,且是(VMP)的真有效解,则存在某一λ∈Λ+使是(Pλ)的较优解。

通过带权系数的问题(Pλ),可以把非线性规划的许多结果移置到多目标规划中来。权系数是一种类型的拉格朗日乘子,利用线性泛函来分离 的一切理论都可用于此处。对无限维的情形,对鞍点和对偶定理都可进行研究。从计算方法上来说,求(VMP)的有效解或弱有效解,可归为求参数规划问题 (Pλ)的较优解。当λ遍迹Λ+ 或Λ时,将产生所有的有效解或弱有效解。但是,对于(VMP)的一个给定的有效解或弱有效解,选择一个适当的权向量λ并非易事。这是用权系数求解的弱点。

以下定理在实用中可以检验一个点的有效性,并用来产生一个有效解或判定问题的有效解不存在。其中塣是X中的一个给定点。

(1)塣是 (VMP)的有效解的充分必要条件为塣是(P)的较优解。

(2)若Ψ是有限的,并且∈X是(P塣)的较优解,则是(VMP)的有效解。

(3)若X是凸集,ƒ(x)是 X上的凸函数,问题(P塣)无有限的小值存在,则(VMP)不存在真有效解。这些结果是R.E.温德尔和D.N.李于1977年得到的。

1978年,H.P.本森给出有效解与真有效解之间关系的一个结果:设ƒ(x)是凸集X上的凸函数,S={s∈Rm|s≤ƒ(x)对某一x∈X成立}是闭集,则任意非真有效解必是某一真有效解序列的极限。此外,用K表示所有有效解的 ,Kp表示所有真有效解的 ,若ƒ(x)在闭凸集X上是连续的和凸的,则有关系 ,其中一横表示闭运算。

公式,要求λi>0(i=1,2,…,m)和,作各目标线性加权和 ,然后求解单目标数学规划问题

,   (1)

设是问题(1)的较优解,则可以证明是问题(VMP)的有效解。若选取向量λ≥0,则相应的问题(1)的较优解是多目标规划问题(VMP)的弱有效解。 向量λ的各个分量λi(i=1,2,…,m)通常叫做权系数。它的大小反映了各相应分目标在问题中的重要程度。一般,对权系数的不同选取,可以得到问题(VMP)的不同的有效解或弱有效解。如何选取权系数,对于不同的问题可以有不同的处理方法。

(2)理想点法

为了求解多目标规划问题(VMP),先依次极小化各个分目标。设求得第 i个目标的极小值,则得到Rm中的一个点。由于点ƒ的各个分量对于相应的分目标而言是最理想的值,故称ƒ为问题(VMP)的理想点。选取权系数λi>0(i=1,2,…,m),并作偏差(函数),之后求解数学规划问题

(2)

问题(2)的较优解是问题(VMP)的有效解。理想点法的基本思想是在某种意义下使向量目标函数与所考虑问题的理想点的偏差为极小,来求出多目标规划问题的有效解。在上述偏差中,p的不同取值代表了不同意义的偏差。当取p=2,λi=1(i=1,2,…,m),则偏差就为距离。这种情形,理想点法也叫做最短距离法。

(3)分层求解法

对于问题(VMP),假若目标函数 的各个分目标可以按其在问题中的重要程度排出先后次序,并设这个次序为:ƒ1(x),ƒ2(x),…,ƒm(x)。先对第一个目标进行极小化:,设得到的较优解为x1。然后,按下述格式依次分层对各目标进行极小化:

(3)式中。设k=m时得到问题(3)的较优解xm,则在每一的条件下,xm是多目标规划(VMP)的有效解。在实用中,为了保证每一,常把上述Xk中的等式约束作适当的宽容,即给出一组所谓宽容量 δi(i=1,2,…,m-1),并以代替 (3)中的Xk。在δi>0的条件下,由k代替Xk所得到的xm是多目标规划(VMP)的弱有效解。

简史

多目标较优化思想,最早是在1896年由法国经济学家V.帕雷托提出来的。他从政治经济学的角度考虑把本质上是不可比较的许多目标化成单个目标的较优化问题,从而涉及了多目标规划问题和多目标的概念。1947年,J.冯·诺伊曼和O.莫根施特恩从对策论的角度提出了有多个决策者在彼此有矛盾的情况下的多目标问题。1951年,T.C.库普曼斯从生产和分配的活动中提出多目标较优化问题,引入有效解的概念,并得到一些基本结果。同年,H.W.库恩和A.W.塔克尔从研究数学规划的角度提出向量极值问题,引入库恩-塔克尔有效解概念,并研究了它的必要和充分条件。1963年,L.A.扎德从控制论方面提出多指标较优化问题,也给出了一些基本结果。1968年,A.M.日夫里翁为了排除变态的有效解,引进了真有效解概念,并得到了有关的结果。自70年代以来,多目标规划的研究越来越受到人们的重视。至今关于多目标较优解尚无一种完全令人满意的定义,所以在理论上多目标规划仍处于发展阶段。

严正声明:本文由历史百科网注册或游客用户代雯奇自行上传发布关于» 多目标规划的内容,本站只提供存储,展示,不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益,请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议,尊重和保护作者的劳动成果,转载请标明出处链接和本声明内容:作者:代雯奇;本文链接:https://www.freedefine.cn/wenzhan/129685.html

赞 ()
我是一个广告位
留言与评论(共有 0 条评论)
   
验证码: