多目标规划求解方法介绍(课堂PPT).ppt

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