目标规划1解读.ppt

* * * * * * * * * * * 第九章、多目标规划的基本原理 9.1 多目标规划的基本概念 一、多目标规划的特征:单目标：实数比较; 多目标：向量比较 二、定义和符号 记多目标规划问题为： 该多目标规划问题有p个目标，m个约束条件和n个决策变量。 定义1 可行解 若x0满足h i (x)≤0，（1≤i≤m），则是MOP的可行解。 定义2 可行集 问题MOP所有可行解构成的集合为可行集，记为X。又称决策集。 定义3 目标集 G = F(X) = {(f1(x) , f2,(x), . . . , fp(x))∣x∈X } 目标集G就是可行集X在映像F之下的像集。 性质1 对于任意可行解x0∈X必有z0 = F ( x0)∈G 性质2 对于任意z0 ∈G，则至少存在一个可行解x0∈X，使得F ( x0)= z0 单目标优化，重点在决策集X， 在X中找最优解。 多目标优化，重点在于目标集G，在G中找满意点。 定义4 理想点 记z* = (f*1，f*２，. . . ，f*Ｐ)称z*为问题MOP在目标空间中理想点，其中 f*k= Min {fk(x) ，x∈X }，1≤k≤p 定义5 绝对最优解 如果有一个解x*，使得F(x*)=z*，则称x*为绝对最优解。 注意： 1、单目标最优解肯定是可行解 2、多目标绝对最优解不一定是可行解 若x*∈X，则x*就是绝对最优方案，这种情况不是MOP研究的情况，主要研究x*?X的情况 设有两个P维向量 α=（α1，α2，. . .，αP）β=（β1，β2，. . .，βP） 定义6 向量α等于β，记α=β， 当且仅当αi=βi，（1≤i≤p） 定义7 向量α小于β，记α≤β， 当且仅当αi≤βi，（1≤i≤p）且至少有一分量α tβt 定义8 向量α严格小于β，记αβ，当且仅当α iβi（1≤i≤p） 定义9 向量α、β不可比，至少存在两个分量，使得αtβt，αkβk 定义10 劣解 设x0∈X，如果至少存在一个x1∈X，使得F（x1）≤ F（x0），则称x0是劣解。 定义11 非劣解（有效解） 设x0∈X，如果不存在x1∈X，使得关系式F（x1）≤ F（x0）成立，则称x0是非劣解，全体非劣解集合为非劣解集，记X* 定义12 弱非劣解（弱有效解） 设x0∈X，如果不存在x1∈X，使得关系式F（x1） F（x0）成立，则称x0是弱非劣解，全体弱非劣解集合为弱非劣解集，记X*W。 性质3 多目标规划问题（MOP）的非劣解一定是弱非劣解，反之不定。 因为若不存在x1∈X使得关系式F（x1）≤ F（x0）成立，则肯定不存在x2∈X，使得关系式F（x2） F（x0）成立。 性质4 多目标规划问题（MOP）的非劣解x0如果是唯一的，那么它一定就是绝对最优解。 定义13 非劣点（有效点） 若z0∈G，如果不存在z∈G，使得z≤z0 则称z0为目标集G的非劣点，又称有效点。全体非劣点的集合成为非劣点集，记F*。 定义14 弱非劣点（弱有效点） 若z0∈G，如果不存在z∈G，使得zz0 则称z0为目标集G的弱非劣点，又称弱有效点。全体弱非劣点的集合成为弱非劣点集，记F*W。 性质5 MOP目标集G的非劣点一定是弱非劣点，反之不定。 性质6 MOP目标集G中如果只有一个非劣点，则它就一定是理想点。 2是弱有效，但不是有效；1、3是弱有效，同时也是有效。弱有效如果不是有效，则是无效（劣点）。所以目标集所有点分为有效和无效两类；弱有效集也分为有效和无效两类。 三、例1 考虑问题（m=2，m=6，p=2）如下，已知 f1（x）= - 5x1 + 2x2 f2（x）= x1 - 4x2 X={（x1，x2）∣-x1+x2≤3，x1+x2≤8，0≤x1≤6，0≤x2≤4} 求理想点，绝对最优解等。 解：f1*=Minf1（x）=-30 x1=（6，0） f2*=Minf2（x）=-15 x2=（1，4） 理想点 z*=（f1*，f2*）=（-30，-15） 由z* 求x*，即解方程组 - 5x1 + 2x2 =-30 x1 - 4x2=-15 可解得 x*=（25/3，35/6） 由此可见，x*≠x1≠x2，且x*?X，即x*为非可行解。 9.2 多目标规划的基本性质 一、问题模型 记G = {F(x)∣x∈X}为目标集，X*为非劣解集，则X*?X，F*={F(x)∣x∈X*}为非劣点集。 根据MOP构造如下单目标规划（SOP） 1、线性加权问题P(W) 考虑多目标规划 2、第k目标拉格朗日问题Pk（u）