多目标规划的求解方法

Python017

多目标规划的求解方法,第1张

即把多目标规划问题归为单目标的数学规划(线性规划或非线 性规划)问题进行求解,即所谓标 量化的方法,这是基本的算法之一。

①线性加权和法 对于多目标规划问题(VMP),先选取向量

要求λi>0(i=1,2,…,m)

作各目标线性加权和

然后求解单目标数学规 划问题。

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

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

问题 (2)的最优解是问题(VMP)的有效解。理想点法的基本思想是在某种意义下使向量目标函数与所考虑问题的理想点的偏差为极小,来求出多目标规划问题的有 效解。在上述偏差中,p的不同取值代表了不同意义的偏差。当取p=2,λi=1(i=1,2,…,m),则偏差就为距离多目标规划多目标规划。这种情形, 理想点法也叫做最短距离法。 对于问题(VMP),假若目标函数多目标规划 的各个分目标可以按其在问题中的重要程度排出先后次序,并设这个次序为:ƒ1(x),ƒ2(x),…,ƒm(x)。先对第一个目标进行极小化:多目标规 划,设得到的最优解为x。然后,按下述格式依次分层对各目标进行极小化:

式中多目标规划。设k=m时得到问题(3)的最优解x,则在每一多目标规 划的条件下,x是多目标规划(VMP)的有效解。在实用中,为了保证每一多目标规划,常把上述Xk中的等式约束作适当的宽容,即给出一组所谓宽容量 δi(i=1,2,…,m- 1),并以多目标规划代替 (3)中的Xk。在δi>0 的条件下,由多目标规划k代替Xk所得到的x是多目标规划 (VMP)的弱有效解。 对多目标的线性规划除以上方法外还可以适当修正单纯形法来求解;还有一种称为层次分析法,是由美国运筹学家沙旦于70年代提出的,这是一种定性与定量相结 合的多目标决策与分析方法,对于目标结构复杂且缺乏必要的数据的情况更为实用。

目标规划(Goal programming) 目标规划是线性规划的一种特殊应用,能够处理单个主目标与多个目标并存,以及多个主目标与多个次目标并存的问题。

目标规划的模型分为以下两大类:

1.多目标并列模型。

2.优先顺序模型。

①目标规划中的目标不是单一目标而是多目标,既有主要目标又有次要目标。根据主要目标建立部门分目标,构成目标网,形成整个目标体系。制定目标时应注意衡量各个次要目标的权重,各次要目标必须在主要目标完成之后才能给予考虑。

②线性规划只寻求目标函数的最优值,即最大值或最小值。而目标规划,由于是多目标,其目标函数不是寻求最大值或最小值,而是寻求这些目标与预计成果的最小差距,差距越小,目标实现的可能性越大。目标规划中有超出目标和未达目标两种差距。一般以Y+代表超出目标的差距,Y-代表未达目标的差距。Y+和Y-两者之一必为零,或两者均为零。当目标与预计成果一致时,两者均为零,即没有差距。人们求差距,有时求超过目标的差距,有时求未达目标的差距。目标规划的核心问题是确定目标,然后据以建立模型,求解目标与预计成果的最小差距。

目标规划可用一般线性规划求解,也可用备解法求解,还可用单体法求解,或者先用线性规划或备解法求解后,再用单体法验证有无错误。目标规划有时还可以用对偶原理进行运算,依一般规则,将原始问题转换为对偶问题,以减少单体法运算步骤。