多目标规划求解方法介绍.ppt

《多目标规划求解方法介绍.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§3.3多目标规划求解方法介绍一、约束法1.基本思想：在多个目标函数中选择一个主要目标作为目标函数，其它目标处理为适当的约束。无妨设为主要目标，对其它各目标可预先给定一个期望值，不妨记为，则有求解下列问题：容易证明，约束法求问题(P)的最优解，其Kuhn-Tucker条件与(VP)有效解的K-T条件一致。因此，约束法求得的解是有效解。(P)问题中各目标函数期望值的取得有多种方法，一种方法是取一点，而取得到下列问题：2.算法一般步骤：考虑上述(VP)问题，为主目标。第一步：（1）对，求解单目标问题：得解；（2）计算对应的各目标函数值，并对每个函数，求其p个点值中的最大值Mj和最小值

2、mj。得到下表：Mj与mj规定了在有效解集中的取值范围。x(1)x(p)f1(x)f2(x)…fp(x)m1m2…mpf1(x(1))f2(x(1))…fp(x(1))f1(x(p))f2(x(p))…fp(x(p))M1M2…MpMjmj………第二步：选择整数r>1，确定的r个不同阀值：第三步：对，分别求解问题：各目标函数可对应不同的（共有个约束问题）。求解后可得到(VP)的一有效解集合，是(VP)有效解集合的一个子集。例6：用约束法求解。设为主目标。第一步：分别求解得得f1f2x(1)x(2)Mjmj-3063-1536-30-15选定r=4:求解于是可得四组解，如图15所示

3、。j=2只有一个tf02t0123-15-8-16二、分层序列法：基本步骤：把(VP)中的p个目标按其重要程度排一次序。依次求单目标规划的最优解。2.过程：无妨设其次序为先求解得最优值，记再解得最优值，依次进行，直到得最优值则是在分层序列意义下的最优解集合。3.性质：，即在分层序列意义下的最优解是有效解。证明：反证。设，但，则必存在使即至少有一个j0，使,由于，即，矛盾。得证。4.进一步讨论：上述方法过程中，当某个问题(Pj)的解唯一时，则问题的求解无意义，因为解都是唯一的。实际求解时，有较宽容意义下的分层序列法：取为预先给定的宽容值，整个解法同原方法类似，只是取各约束集合时，分

4、别取为：三、功效系数法：设目标为：其中：要求min；要求max。由于量纲问题，处理目标之间的关系时往往带来困难。1.功效系数法：针对各目标函数，用功效系数表示（俗称“打分”）：满足：或使最满意时，最不满意时（即最差时）。2.常用的两种产生功效系数的方法：（1）线性型：设由于时求，令故取又时求，令故取（2）指数型：先讨论求最大的函数，。考虑：显然，有如下性质：10.当充分大时，；20.是的严格递增函数。（△）为了便于确定b0、b1，选取两个估计值：取为合格值（勉强合格，即可接受）；为不合格值（不合格，即不可接受）。令并取得解得：代入式(△)，得到功效系数：同理可得当时的功效系数：3

5、.利用功效系数求解问题(VP)：设(VP)的功效系数为令构造问题：可以证明：上述问题(P)的最优解，即原问题(VP)的有效解。四、评价函数法：1.理想点法：设，即各单目标问题的最优值。令评价函数，做为目标函数。更一般地，取从不同角度出发，构造评价函数h(F)，求问题,得到(VP)的有效解。下面介绍一些评价函数的构造(即不同的方法)。2.平方和加权法：求出各单目标问题最优值的下界(期望的最好值)。令评价函数其中为预先确定的一组权数，且满足的值为各目标函数的权数，较重要的取值较大。3.范数和加权法：同上面类似，先求出各单目标问题的最优值下界，取，构造评价函数：其中为权系数，且。把此方

6、法与分层序列法结合，取，用于线性多目标规划，即得到目标规划方法（运筹学课中所学的）。4.虚拟目标法：仍如“2、3”得到，设取评价函数：5.线性加权法：预先给出每一目标函数的权系数，满足。取评价函数：线性加权法是最常用的方法之一。此法可直接解释(VP)有效解的Kuhn-Tucker条件。△几何意义：设n=2,p=2。线性加权法解问题：在像空间，(P)等价为问题：记，则。及分别对应单目标问题(P1)及(P2)。当正数确定后，可得问题(PF)的最优值，如图18，可知对应的原像。、。可以利用线性加权法来逼近有效解的集合，但不是一种准确寻找所有有效解的有效方法。当μ从0→-∞时，可得到非劣

7、解的一个子集。如上图19所示。A、B为相应集合的端点。当或时，可能是弱有效解，如下图20。只有，由A到B的其余点为弱有效点。它们对应的原像为弱有效解。例7：其中：，F映射是由x1ox2到f1of2空间的一个线性变换。可行域是多胞形H(A,B,C,D,E,F)。其A(0,0)T、B(6,0)T、C(6,2)T、D(4,4)T、E(1,4)T、F(0,3)T是每两条直线的交点。F(A)=MA=(0,0)T，F(B)=MB=(-30,6)T，F(C)=MC=(-26,-2)T，F(D)