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

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