《目标规划1解读》由会员分享，可在线阅读，更多相关《目标规划1解读（30页珍藏版）》请在金锄头文库上搜索。
1、第九章、多目标规划的基本原理 9.1 多目标规划的基本概念 一、多目标规划的特征:单目标：实数比较; 多目标：向量比较 二、定义和符号 记多目标规划问题为： 该多目标规划问题有p个目标，m个约束条件和n个决策变量。 定义1 可行解 若x0满足h i (x)0，（1im），则是MOP的 可行解。 定义2 可行集 问题MOP所有可行解构成的集合为可行集，记 为X。又称决策集。 定义3 目标集 G = F(X) = (f1(x) , f2,(x), . . . , fp(x)xX 目标集G就是可行集X在映像F之下的像集。 性质1 对于任意可行解x0X必有z0 = F ( x0)G 性质2 对于任意z
2、0 G，则至少存在一个可行解x0X，使得 F ( x0)= z0 单目标优化，重点在决策集X， 在X中找最优解。 多目标优化，重点在于目标集G，在G中找满意点。 定义4 理想点 记z* = (f*1，f*，. . . ，f*)称z*为问题MOP在 目标空间中理想点，其中 f*k= Min fk(x) ，xX ，1kp 定义5 绝对最优解 如果有一个解x*，使得F(x*)=z*，则称x*为 绝对最优解。 注意： 1、单目标最优解肯定是可行解 2、多目标绝对最优解不一定是可行解 若x*X，则x*就是绝对最优方案，这种情况不是MOP研究 的情况，主要研究x*X的情况 设有两个P维向量 =（1，2，.
3、 . .，P）=（1，2，. . .，P） 定义6 向量等于，记=， 当且仅当i=i，（ 1ip） 定义7 向量小于，记， 当且仅当ii，（ 1ip）且至少有一分量 t0，对于一切jk，有x*是Pk （u）的最优解 引理4 如果满足凸性假定，且x*是Pk（*）的最优解，那么存 在uj0，jk，使得x*也是Pk（u）的最优解。 三、定理 （说明各问题模型的最优解与MOP非劣解之间的 相互关系） 定理1 如果满足凸性假定，已知x*X*（非劣解集），那么 一定存在w*W，使得x*是P（w*）的最优解。 定理2 如果存在w*W，使得x*是P（w*）的最优解， 而且 满足下列两个条件之一 （1）wj*
4、0，（1 j p） （2）x*是P（w*）的唯一最优解 那么x*一定是多目标规划（MOP）的非劣解。 证：假设对于某个w*W，x*是P（w*）的最优解，那么应该 有： 先用反证法， 如果x*不是MOP的非劣解，即x*X*，那么 一定存在x0X 使得 F(x0) F(x*) （2） 且若（1）wj0 (1 j p)，由上式(2)可推得 与（1）式矛盾。 （2）若x*是P（w*）的唯一最优解， 则（1）式应该为 由反证法假定（2）式，对于w0，有 上式与（3）式矛盾。即定理2得证。 定理3 如果对于某个k,存在u*UK，使得x*是Pk（u*）的最 优解，并且满足下列两个条件之一 1)uj*0，（1
5、 j p，jk）或 2)x*是Pk（u*）的唯一最优解 那么x*一定是MOP的非劣解。 同定理2证明 定理4 当且仅当x*对一切k（1 k p）都是Pk（ * ）的最优 解时，x*是MOP的非劣解。其中， i*= f i（x*）， 1 i p， i k. 证（必要性）（反证法）假定对于某个k，x*不是Pk（ * ） 的最优解，这说明至少存在一个x0X，使得 fk（x0）0，使得对于每一个j(1 j p )，如果有 f j (x)fs(x*M)的s，使得 一个非劣解如果不满足上述条件，则称为不恰当非劣解。 例：Min F(x)=f1(x)，f2(x) s.t.x0，xR 由图中可知，闭区间x1，
6、x2内任一点都是非劣解，但区间 端点x1，x2都是不恰当非劣解。因为对于任意的x=x1+h， h0，都有 而开区间（x1，x2）中的任意一点均是恰当非劣解。 定理3 （1）如果对于w0，x*M是P(w)的最优解，那么x*M是 MOP的恰当非劣解； （2）假定满足凸性条件，如果x*M是MOP的恰当非劣解 ，那么存在w0，x*M一定是P(w)的最优解。 定理4 假定满足凸性条件，MOP的一个可行解x*M 是恰当非 劣解的充要条件是Pk(*)对于所有k都是稳定的。 三、非劣性检验 设x*X，选择0，RP 构造问题 求解单目标最优化问题P()，会有三种情况发生 1.P()有一个有界最优解，且*=0 2
7、.P()有一个有界最优解，且00，使得x*在 XN(x* ，）内是非劣的，即不存在x XN(x* ，)，使得 F(x) F(x*) 定理6 当且仅当对于一切k（k=1，2，.p），x* 是Pk（*）的 局部最优解时，x* 是MOP的局部非劣解。 定理7 如果对于某个k，x*是Pk（*）的严格局部最优解， 那 么x*是MOP的局部非劣解。 定理8 如果X是凸集，所有fj(x)（j=1，2，.,p）都是X上的凸 函数，那么MOP的局部非劣解就是总体非劣解。 9.4 各种非劣解的关系 1.非劣解 x* X* 2.弱非劣解 xW* XW* 3.恰当非劣解 xM* XM* XM* X* XW* X 今后各章只研究非劣解的解法，目标空间中只研究非劣点的 求法，并一律记非劣解为x*，非劣解集为X*，非劣点集为F*。 参考书 多目标决策，宣家骥，湖南科学技术出版 社，1989 多目标线性决策系统理论及应用，石勇 等人，高等教育出版社，2007 多目标决策的理论与方法，徐玖平 等人， 清华大学出版社，2005 最优化原理、方法及求解软件，阳明盛等 人，科学出版社，2006
