多目标规划求解方法介绍（PPT37页)52617

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.3,多目标规划求解方法介绍,一、约束法,1.基本思想：,在多个目标函数中选择一个主要目标作为目标函数，其它目标处理为适当的约束。,无妨设 为主要目标，对其它各目标 可预先,给定一个期望值，不妨记为 ，,则有,求解下列问题：,容易证明，约束法求问题(P)的最优解，其,Kuhn-Tucker条件与(VP)有效解的K-T条件一致。,因此，约束法求得的解是有效解。,(P)问题中各目标函数期望值的取得有多种方法，,一种方法是取一点 ，而取,得到下列问题：,2.算法一般步骤：,考虑上述(VP)问题，为主目标。,第一步：,（1）对 ，求解单目标问题：,得解 ；,（2）计算 对应的各目标函数值，并对每个函,数 ，求其p个点值中的最大值M,j,和最小值m,j,。得到下表：,M,j,与m,j,规定了 在有效解集中的取值范围。,x,(1),x,(p),f,1,(x)f,2,(x)f,p,(x),m,1,m,2,m,p,f,1,(x,(1),)f,2,(x,(1),)f,p,(x,(1),),f,1,(x,(p),)f,2,(x,(p),)f,p,(x,(p),),M,1,M,2,M,p,M,j,m,j,第二步：,选择整数r1，确定 的r个不同阀值：,第三步：,对 ，分别求解问题：,各目标函数 可对应不同的 （共,有 个约束问题）。求解后可得到(VP)的一有,效解集合，是(VP)有效解集合的一个子集。,例6,：,用约束法求解。设 为主目标。,第一步：分别求解,得,得,f,1,f,2,x,(1),x,(2),M,j,m,j,-30,6,3,-15,3,6,-30,-15,选定r=4:,求解,于是可得四组解，如图15所示。,j=2只有一个,t,f,0,2t,0 1 2 3,-15 -8 -1 6,二、分层序列法：,基本步骤：,把(VP)中的p个目标 按其重,要程度排一次序。依次求单目标规划的最优解。,2.过程：,无妨设其次序为,先求解,得最优值 ，记,再解,得最优值 ，,依次进行，直到,得最优值,则 是在分层序列意义下的最优解集合。,3.性质,：，即在分层序列意义下的最优解是有效解。,证明：反证。设 ，但 ，则必存在,使,即至少有一个j,0,，使 ,由于 ，即,，矛盾。得证。,4.进一步讨论：,上述方法过程中，当某个问题(P,j,)的解唯一时，则,问题 的求解无意义，因为解都是唯一的。,实际求解时，有较宽容意义下的分层序列法：,取 为预先给定的宽容值，整个解法同原,方法类似，只是取各约束集合时，分别取为：,三、功效系数法：,设目标为：,其中：要求min；,要求max。,由于量纲问题，处理目标之间的关系时往往带来困难。,1.功效系数法：,针对各目标函数 ，用功效系数 表示（俗称“打分”）：,满足：或,使最满意时 ，最不满意时（即最差时）。,2.常用的两种产生功效系数的方法：,（1）线性型：,设,由于 时求 ，令,故取,又 时求 ，令,故取,（2）指数型：,先讨论求最大的函数，。,考虑：,显然，有如下性质：,1,0,.当 充分大时，；,2,0,.是 的严格递增函数。,（）,为了便于确定b,0,、b,1,，选取两个估计值 ：,取 为合格值（勉强合格，即可接受）；,为不合格值（不合格，即不可接受）。,令,并取 得,解得：,代入式,(),，得到功效系数：,同理可得当 时的功效系数：,3.利用功效系数求解问题(VP)：,设(VP)的功效系数为,令,构造问题：,可以证明：,上述问题(P)的最优解 ，即原问题,(VP)的有效解。,四、评价函数法：,1.理想点法：,设 ，即各单目标问题的最优值。,令评价函数 ，做为目标函数。,更一般地，取,从不同角度出发，构造评价函数h(F)，求,问题,得到(VP)的有效解。,下面介绍一些评价函数的构造(即不同的方法)。,2.平方和加权法：,求出各单目标问题,最优值的下界 (期望的最好值)。,令评价函数,其中 为预先确定的一组权数，且满足,的值为各目标函数的权数，较重要的取值较大。,3.范数和加权法：,同上面类似，先求出各单目标问题的最优值下界 ，,取 ，构造评价函数：,其中 为权系数，且 。,把此方法与分层序列法结合，取 ，用于线性多目,标规划，即得到目标规划方法（运筹学课中所学的）。,4.虚拟目标法：,仍如“2、3”得到 ，设,取评价函数：,5.线性加权法：,预先给出每一目标函数 的权系数 ，满足,。取评价函数：,线性加权法是最常用的方法之一。,此法可直接解释(VP)有效解的,Kuhn-Tucker条件,。,几何意义：,设n=2,p=2。线性加权法解问题：,在像空间，(P)等价为问题：,记 ，则 。及 分别对应单目标问,题(P,1,)及(P,2,)。,当正数 确定后，可得问题(P,F,)的最优值 ，如,图,18,，可知 对应的原像 。、。,可以利用线性加权法来逼近有效解的集合，但不是一,种准确寻找所有有效解的有效方法。当,从0-时，可,得到非劣解的一个子集。如上,图19,所示。A、B为相应,集合的端点。,当 或 时，可能是弱有效解，,如下,图20,。只有 ，由A到B的其余点为弱有效点。,它们对应的原像为弱有效解。,例7：,其中：，,F映射是由x,1,ox,2,到f,1,of,2,空间的一个线性变换。,可行域是多胞形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)=MD=(-12,-12),T,，,F(E)=ME=(3,-15),T,，F(F)=MF=(6,-12),T,。,F(S)是由F(A)、F(B)、F(C)、F(D)、F(E)、F(F)构,成的多胞形。如,图21,。,图21：,当 ,即 时,即(P,2,)的解:E(1,4),T,对应 F(E)=(3,-15),T,；,当 ,即 时,即(P,1,)的解:B(6,0),T,对应F(B)=(-30,6),T,；,取,=-1,即 时,问题为：,最优解为:C(6,2),T,对应 F(C)=(-26,-2),T,；,取,=-1/2,即 时,问题为：,最优解为:D(4,4),T,对应 F(D)=(-12,-12),T,；,取,=-1/3,即 时,问题为:,最优解为:D(4,4),T,对应 F(D)=(-12,-12),T,。,6.“min-max”法（极小-极大法）,对策论中常遇到“在最不利情况下找出最有利策略”的,问题，即“min-max”问题。,取评价函数,然后求解,设得解 ,是x的函数。如右图。,实用中，可以使用下列,加权形式，取 ，令,为了求解方便，可把问题(P,Mm,)等价化为下列数学规划,问题:,定理：,设 是 的最优解，那么 为(P,Mm,)的最优,解；反之，若 是(P,Mm,)的最优解,且,那么 是 的最优解。,证：设 是问题 的最优解，明显地，有,由第一组约束知：,由目标min t知 取得满足上式的最小值。,对(P,Mm,)的任意可行解x，令,那么 。于是,即 是问题(P,Mm,)的最优解。,反之，考虑 是 的任意可行解，则,（第一组约束）,是(P,Mm,)的最优解，可得，对(P,Mm,)的任意可行解x，有,于是 。即 为 的最优解。,7.乘除法：,设(VP)中，对 ，均有,再设 求min；,求max。,取评价函数,求解,，,。,8.评价函数法的收敛性：,考虑(VP)，h(F(x)为评价函数。,定义：,设 ，,1,0,.若满足 时，均有 ，则称h(F)是F的严格,单调增函数；,2,0,.若满足：当 时，均有 ，则称h(F)是F的,单调增函数。,定理：,若 ，,1,0,.若h(F)是严格单调增函数，则数学规划,的最优解 ；,2,0,.若h(F)是单调增函数，则数学规划,的最优解 。,证明：,1,0,.反证,。设 ，由定义，使,由h(F)的单调增性质，得到,与 是(P,1,)的最优解矛盾。,2,0,.反证,。设 ，由定义，使,由h(F)的单调增性质，得到,与 是(P,2,)的最优解矛盾。证毕。,可以证明，,上述各评价函数：1.理想点法、2.平方和加权法、,范数和加权法、4.虚拟目标法、5.线性加权法()、7.乘,除法均为严格单调增函数；而5.线性加权法()、6.min-max方,法为单调增函数。,由此，根据定理可得，方法5(线性加权法()方法6(min-,max法)得到的解 ；其它各方法得到的解 。,9.确定权系数的方法：,(VP)问题的评价函数h(F(x)中所需预先给出的权系数：,（1）“老手法”,基本过程：,邀请一批“老手”（专家，有经验的人员等），,汲取他们对权系数的意见，加以综合得到权系数。,设有k位“老手”，为了便于其独立发表意见，将事先,准备好的调查表送给他们分别填写。设第i位“老手”对第,j个目标 给出的权系数为 。,针对每个目标函数 ，计算平均权系数：,得到下表：,计算每一位老手i(i=1,2,k)关于平均权系数 评价的,偏差：。,第二轮讨论，请最大偏差的老手首先发表意见，经充,分讨论以达到对目标重要度的正确认识，消除参数估计,中的误解。然后重新评价。,如此反复进行，最后达到较为一致的认识。,（2）,-方法：,对p=2的情形叙述：求 的最优解 。,记 ，像空间的图形如下（,图23,）。,在像空间中，点 确定一条直线L,1,，记其方程,为 。,把上面两个点的坐标代入，得到：。,若问题(VP)不存在绝对最优解(存在,绝对最优解时，上述方程组为一,个点，)，即 。,则有,记 ，,解方程组 得：,取这组 时，线性加权法,的最优解 对应的像点为 ，如图23。,对于一般情况：p2。,记单目标问题 的最优解为 ，记,过p个点 做超平面，得方程组,当(VP)不存在唯一解时，可确定唯一一组解(共p+1个变量，p+1个方程)。,该解 即为一组权系数。,10.有限方案多目标决策问题简介,前述的一些方法均是针对无限方案多目标决策问题,的模型进行讨论的。也是在这一领域中遇到较多的且要,求基础知识较深的一部分内容。,（1）有限方案多目标决策问题的特征及基本思路：,特征：,仅含有限多个方案；,决策情况的范围只涉及分析-评价的内容。,基本解题思路：,筛选排序集结综合,筛选：,对有限个可能方案，按照某种(些)准则，筛去显著不满意的方案，使下一步所考虑的方案尽可能的少；,排序：,根据各属性特征给各属性赋权。然后，按照不同的方法，给各方案排序。,集结：,常用三种技术，对上步得到的不同方法下各方案的排序进行集结(按不同技术的综合评价)。有下列三种技术：,常用的集结方法：,平均值法：,求各方案在不同方法下名次的平均值。按平均值的大小得到集结名次，若平均值相同时，则取方差较小的排在前。,例8：,有四个方案 ，用四种方法 进行,排序，得到下表：,对各方案两两比较(如x,i,与x,j,)，若认为x,i,好于x,j,的方案,多，记为胜(M)，否则记为败(X)(不优于)。,Borda法：,找各方案“胜”的次数之和，进行集结。,Copaland法：,找各方案“胜”(取正)与“败”(取负)次数的代数和，进行集结。,例9：同上例，结果如下。,综合：,上步得到三种技术下的排序，一般仍存在不可比的关系。构造一排序集：当x,i,优于x,j,时，记为 ，否则认为不可比。当 时，节点x,i,位于x,j,上，这样得到一个偏序结构图：,（2）决策矩阵和规范化,决策矩阵：,把各方案x,i,(i=1,2,m)及属性集y,j,(j=1,n)、,列表得到决策矩阵。其中,(方案x,i,的第j个属性值)。,向量规范化：,(化为无量纲值),一般达不到0或1。,x,1,x,4,x,5,x,2,x,3,-第1等级,-第2等级,-第3等级,计算,线性变换规范化：,(使 ),若求最大时,：(,效益,),