3.3 多目标规划求解方法介绍一、约束法 1.基本思想：在多个目标函数中选择一个主要目标作 为目标函数，其它目标处理为适当的约束。无妨设 为主要目标，对其它各目标 可预先 给定一个期望值，不妨记为 ， 则有 求解下列问题：容易证明，约束法求问题(P)的最优解，其 Kuhn-Tucker条件与(VP)有效解的K-T条件一致 。因此，约束法求得的解是有效解。(P)问题中各目标函数期望值的取得有多种方 法， 一种方法是取一点 ，而取 得到下列问题：2. 算法一般步骤：考虑上述(VP)问题， 为主目标。第一步： （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 pMjmj第二步：选择整数r1，确定 的r个不同阀值 ：第三步：对 ，分别求解问题：各目标函数 可对应不同的 （ 共 有 个约束问题）。求解后可得到(VP)的一有 效解集合，是(VP)有效解集合的一个子集。例6：用约束法求解。设 为主目标。 第一步：分别求解得得f1f2x(1)x(2) Mj mj-3063-1536 -30-15选定r=4:求解于是可得四组解，如图15所示。 j=2只有一个tf 02t0 1 2 3 -15 -8 -1 6二、分层序列法： 基本步骤：把(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. 反证。设 ，由定义， 使