上海交通大学：《运筹学》教学资源（课程讲义）第九章 多目标优化

第九章多目标优化（书第16章) §9.1引言 在生产、经济、科学和工程活动中经常需要对由多个目标（指标）衡量优劣的方案进行好坏的判别， 例如设计一个导弹，即要其射程远，又要耗燃料少，还要命中率高等：又如选择新厂的厂址，除了要考 虑运费、造价、燃料供应费等经济指标外，还要考虑对环境的污染等社会因素，只有对各种因素的指标 进行综合衡量后，才能做出合理的决策。 设每个可行的方案x∈X需要用m个指标f(x),,f(x)来衡量时，则两两方案之间就不一定能够 比较优劣。这种问题称为多目标决策（优化）问题。一般模型： V-maxf(x)=(f(x),…,fm(x)》 (MMP) s.t.x∈X 其中XcR”为可行域，x=(x,…,xn)为决策变量，(x),…,fm(x)为m个目标函数 f(x)=(f(x),…,fm(x)为目标向量函数。 §9.2基本概念和基本性质 对向量a,b∈Rm，a=(a,…,am)'，b=(b,…,bm)',记 a≤b(b2a)台a,≤b,i=l,…,m; a=bb=a)台a,=b,i=l,…,m: a≤≠b(b≥2≠a台a≤b,a≠b,这时称a劣于b: a<b(b>a)一a,<b,i=1,…,m:这时称严格a劣于b。 注9.2.1向量a,b∈Rm之间不一定有关系a≤b或b≤a。 定义9.2.1设x∈X。若 f(x)≤f(x),x∈X 则称x是(MMP)的最优解。(MMP)的最优解集记作X'。 一般情况下X'=⑦。 定义9.2.2设x∈X。若 (1)若不存在x∈X,使f(x)≥≠f(),则称x是(MMP)的非劣（有效）解。(MMP)的非劣（有效） 解集记作灭： (2)若不存在x∈X,使f(x)>f(),则称x是(MMP)的弱非劣（弱有效）解。(MMP)的弱非劣（有 效)解集记作.。 记Rm={x∈Rm|x≥O},Rm={x∈Rm|x>O}。 定理9.2.1(1)x∈X台f(X)n(f()+R)={f()},(2)x∈X.台f(X)n(f()+R4)=0。 证：(I)必要性。否则存在x∈X:f()≠f(x),f()∈f(x)+R",即元∈X,f()2≠f(),则xg下， 矛盾。 充分性。否则存在元∈X:f()≥≠f()，即元∈X:f()≠f(),f()∈f(x)+R,则 f(X)n(f()+Rm)≠{f()},矛盾。 (2)必要性。否则存在x∈X:f()∈f()+Rm,即元∈X,f()>f(),则x华X,矛盾

1 第九章 多目标优化（书第 16 章） §9．1 引言 在生产、经济、科学和工程活动中经常需要对由多个目标（指标）衡量优劣的方案进行好坏的判别， 例如设计一个导弹，即要其射程远，又要耗燃料少，还要命中率高等；又如选择新厂的厂址，除了要考 虑运费、造价、燃料供应费等经济指标外，还要考虑对环境的污染等社会因素，只有对各种因素的指标 进行综合衡量后，才能做出合理的决策。 设每个可行的方案 x  X 需要用 m 个指标 1 ( ), , ( ) m f x  f x 来衡量时，则两两方案之间就不一定能够 比较优劣。这种问题称为多目标决策（优化）问题。一般模型： max ( ) ( ( ), , ( )) 1 . . T V fx f x f x m st x X     (MMP) 其 中 n X  R 为可行域， 1 (, , )T n x  x x  为决策变量， 1 ( ), , ( ) m f x  f x 为 m 个目标函数 1 ( ) ( ( ), , ( ))T m f x fx f x   为目标向量函数。 §9．2 基本概念和基本性质 对向量 , m ab R  ， 1 (, , )T m aa a   ， 1 (, , )T m bb b   ，记 ( ) , 1, , i i a bb a a b i m     ； ( ) , 1, , i i a bb a a b i m     ； a bb a a ba b      () , ，这时称 a 劣于 b； ( ) , 1, , i i a bb a a b i m     ；这时称严格 a 劣于 b。 注 9.2.1 向量 , m ab R  之间不一定有关系 a b  或b a  。 定义 9.2.1 设 * x  X 。若 * f ( ) ( ), x fx x X    则称 * x 是(MMP)的最优解。(MMP)的最优解集记作 * X 。 一般情况下 * X   。 定义 9.2.2 设 * x  X 。若 （1）若不存在 x  X ，使 f () () x fx  ，则称 x 是(MMP)的非劣（有效）解。(MMP)的非劣（有效） 解集记作 X ； （2）若不存在 x  X ，使 f () () x fx  ，则称 x 是(MMP)的弱非劣（弱有效）解。(MMP)的弱非劣（有 效）解集记作 X w。 记 { | 0} m m R xR x    ， { | 0} m m R xR x    。 定理 9.2.1 (1) ( ) ( ( ) ) { ( )} m x X fX fx R fx      ，(2) ( ) (() ) m w x X fX fx R       。 证：(1)必要性。否则存在 : ( ) ( ), ( ) ( ) m x   X fx fx fx fx R   ，即 x   Xfx fx , () ()  ，则 x  X ， 矛盾。 充分性。否则存在 x    X fx fx : () () ， 即 : ( ) ( ), ( ) ( ) m x   X fx fx fx fx R   ， 则 ( ) ( ( ) ) { ( )} m f X fx R fx    ，矛盾。 (2)必要性。否则存在 : () () m x  X fx fx R   ，即 x   Xfx fx , () ()  ，则 w x  X ，矛盾

充分性。否则存在x∈X:f()>f(),即x∈X:f()ef()+Rm,则f(X)n(f()+Rm)≠⑦， 矛盾。 例：书P439-440 定理9.2.2当X≠0时，X=X。 证：设x∈X,即对所有=l,,m,有 f(x)≤f(x),x∈X 假设xX,存在x∈X:f()2法f(x),即存在：f,()>f,(x),与上式矛盾。因此x'∈X。 反之，设x∈X。因为X'≠0，故存在xeX,即xeX,并且f(x)≤f(x)x∈X)。下面证明 fx)=f(x)。 假设f)≠f(x),则f()≤+f(x),即存在x∈X:f(x)≥≠f(),由此知下E,矛盾，因此知 f()=f(x)。于是有f(x)≤f(x)=f()付x∈X),即x∈X。 *定理9.2.3(1)xcX。。(2)当X是凸集，f(x)2…,fm(x)是X上的严格凹函数时，X=X.。 证：(1)由定义9.2.2即知XcX.。 (2)只要证明X,c灭。设x∈X。，假设xe灭，则存在元∈X:f()2法f()。显然京≠x,故由 (x),…,fm(x)在X上的严格凹性，有 f(+(1-))>元f()+(1-)f(x)2f(x),2∈(0,1) 由于X是凸集，因此x+(1-)x∈X(1∈(0,1)，因此由上式得xg灭.，矛盾，由此得x∈。 定理9.24设X={x∈X1/x)=mxx},则XcX.。 对x∈X,如何判断其是否为有效解呢？考虑单目标优化问题： max之fx) st.x∈X (P) f(x)≥f() 定理9.2.5设x∈X,则 (I)下∈X一x是(P)的最优解： (2)当x是(P)的最优解时，元∈X。 证：（①）必要性。假设x不是(B)的最优解，则存在eX:f闭≥f国.∑f国>2f国)，因此 f()2注f(),即下任X,矛盾。 充分性。假设x生x,则存在元∈X:f()2≠f(),因此元是(P)的可行解，并且 立)>立团，由此得x不是()的最优解，矛盾， (2)同(1)充分性证明。 根据定理9.2.5有如下结论： 设x∈X,三是(B)的最优值。若2f(国)=，则x∈了，否侧x安了。 2

2 充分性。否则存在 x    X fx fx : () () ，即 : () () m x  X fx fx R   ，则 ( ) (() ) m fX fx R     ， 矛盾。 例：书 P439-440 定理 9.2.2 当 * X   时， * X X  。 证：设 * * x  X ，即对所有 i=1,…,m，有 * ( ) ( ), i i f x fx x X    假设 * x  X ，存在 * x    X fx fx : () ( ) ，即存在 0 0 * 0 : () ( ) i i i fx fx   ，与上式矛盾。因此 * x  X 。 反之，设 x  X 。因为 * X   ，故存在 * * x  X ，即 * x  X ，并且 * f ( ) ( )( ) x fx x X   。下面证明 * f () ( ) x fx  。 假设 * f () ( ) x fx  ，则 * f () ( ) x fx  ，即存在 * * x   X fx fx : ( ) () ，由此知 x  X ，矛盾，因此知 * f () ( ) x fx  。于是有 * f ( ) ( ) ( )( ) x fx fx x X    ，即 * x  X 。 *定理 9.2.3 (1) X X  w 。(2)当 X 是凸集， 1 ( ), , ( ) m f x  f x 是 X 上的严格凹函数时， X X  w 。 证：(1)由定义 9.2.2 即知 X X  w 。 (2)只要证明 X X w  。设 w x  X ，假设 x  X ，则存在 x   X fx fx : () ()  。显然 x  x ，故由 1 ( ), , ( ) m f x  f x 在 X 上的严格凹性，有 f x x fx fx fx ( (1 ) ) ( ) (1 ) ( ) ( ), (0,1)              由于 X 是凸集，因此x xX      (1 ) ( (0,1))   ，因此由上式得 w x  X ，矛盾，由此得 x  X 。 定理 9.2.4 设 ** * { | ( ) max ( )} i ii x X X x X fx fx    ，则 * X X i w  。 对 x  X ，如何判断其是否为有效解呢？考虑单目标优化问题： 1 max ( ) s.t. ( ) ( ) m i i f x x X f x fx     ( Px ) 定理 9.2.5 设 x  X ，则 (1) x  X x 是( Px )的最优解； (2) 当 x 是( Px )的最优解时， x  X 。 证：(1) 必要性。假设 x 不是( Px )的最优解，则存在 1 1 : ( ) ( ), ( ) ( ) m m i i i i x X fx fx fx fx         ，因此 f () () x fx   ，即 x  X ，矛盾。 充分性。假设 x  X ，则存在 x   X fx fx : () ()  ，因此 x 是 ( Px ) 的可行解，并且 1 1 () () m m i i i i f x fx       ，由此得 x 不是( Px )的最优解，矛盾。 (2) 同(1)充分性证明。 根据定理 9.2.5 有如下结论： 设 x  X ， * z 是( Px )的最优值。若 * 1 ( ) m i i f x z    ，则 x  X ，否则 x  X

设集合YcRm,函数u:Y→R。 (1)若对任意的y,y2∈Y,有y≤y2→u(y)≤(y2),则称u是Y上的非降函数： (2)若对任意的y,y2∈Y,有y<y2→(y)<u(y2),则称u是Y上的增函数： (3)若对任意的y,y2∈Y,有y≤≠y2→uy)<u(y2),则称u是Y上的严格增函数： 例如： (1)u)=wy-yeR" 其中w=(W,…,"m)'∈Rm。当w≥0时u是Rm上的非降函数，当w≥≠0时u是Rm上的增函数，当p>0 时u是Rm上的严格增函数。 (2)0)=-°-儿。=g-y)P,yeY=eRIy≤y 其中y°=0y,,y0)了eRm,w=(w,,wm)了∈R",p21。当w之0时u是R上的非降函数，当w2注0 时u是Y上的增函数，当w>0时u是Y上的严格增函数。 (3))=->-L。=-ax(0-y),yeYy=eR1y≤y} 其中y°=(y,…,y)了∈Rm,w=(w,…,wm)∈Rm。当m≥0时u是Y上的非降函数，当w>0时u 是Rm上的增函数。 考虑单目标优化问题： max u(f(x)) (P) s.t.x∈X 其中函数：Y→R。 定理9.2.6设x∈X是(P)的最优解，则 (I)当u是Y=)上的增函数时，下∈X.: (2)当u是Y=fX)上的严格增函数时，x∈X。 考虑单目标优化问题： maxw'f(x)-w.f() (P) st.x∈X 其中w=(,…,wm)了∈Rm。 推论9.2.1设x∈X是(P)的最优解，则 (1)当w2≠0时，x∈X: (2)当w>0时，x∈X。 *定理9.2.7设X是凸集。 (1)若(x),…,fm(x)是X上的凹函数，下∈X,则存在而2≠0，使x是(P)的最优解。 (2)若f(x),…,fm(x)是X上的严格凹函数，x∈，则存在币2≠0，使x是(P)的最优解。 证明：(1)由下∈X.和定理9.2.2知，f(X)n(f()+Rm)=⑦，故(f(X)-Rm)∩(f()+Rm)=0。 由f(x),…,f(x)是X上的凹函数知(f(X)-R)是凸集，显然(f()+Rm)是凸集。由凸集分离定理

3 设集合 m Y R  ，函数 1 uY R :  。 （1） 若对任意的 1 2 yy Y ,  ，有 12 1 2 y y uy uy   () () ，则称 u 是 Y 上的非降函数； （2） 若对任意的 1 2 yy Y ,  ，有 12 1 2 y y uy uy   () () ，则称 u 是 Y 上的增函数； （3） 若对任意的 1 2 yy Y ,  ，有 12 1 2 y y uy uy    () () ，则称 u 是 Y 上的严格增函数； 例如： （1） 1 ( ) m T i i i u y w y wy     ， m y R  其中 1 (,, )T m ww w R    m 。当 w  0 时u是 m R 上的非降函数，当 w  0 时u是 m R 上的增函数，当 w  0 时 u 是 m R 上的严格增函数。 （2） 0 0 1/ , 1 () [ ( )] m p p ii i w p i uy y y w y y       ， 0 { |} m yY yR y y    其中 00 0 1 (,, )T m m yy y R    ， 1 (,, )T m ww w R    m ，p 1。当 w  0 时u是 m R 上的非降函数，当 w  0 时 u 是 Y 上的增函数，当 w  0 时 u 是 Y 上的严格增函数。 （3） 0 0 , 1 ( ) max ( ) ii i w i m uy y y w y y        ， 0 { |} m yY yR y y    其中 00 0 1 (,, )T m m yy y R    ， 1 (,, )T m ww w R    m 。当 w  0 时 u 是 Y 上的非降函数，当 w  0 时 u 是 m R 上的增函数。 考虑单目标优化问题： max ( ( )) s.t. ufx x X  ( Pu ) 其中函数 1 uY R :  。 定理 9.2.6 设 x  X 是( Pu )的最优解，则 (1) 当 u 是 Y=f(X)上的增函数时， w x  X ； (2) 当 u 是 Y=f(X)上的严格增函数时， x  X 。 考虑单目标优化问题： 1 max ( ) ( ) s.t. m T i i i w f x wf x x X     ( Pw ) 其中 1 (,, )T m ww w R    m 。 推论 9.2.1 设 x  X 是( Pw )的最优解，则 (1) 当 w  0 时， w x  X ； (2) 当 w  0 时， x  X 。 *定理 9.2.7 设 X 是凸集。 （1）若 1 ( ), , ( ) m f x  f x 是 X 上的凹函数， w x  X ，则存在 w  0 ，使 x 是( Pw )的最优解。 （2）若 1 ( ), , ( ) m f x  f x 是 X 上的严格凹函数， x  X ，则存在 w  0 ，使 x 是( Pw )的最优解。 证明：（1）由 w x  X 和定理 9.2.2 知， ( ) (() ) m fX fx R     ，故(( ) ) (() ) m m fX R fx R       。 由 1 ( ), , ( ) m f x  f x 是 X 上的凹函数知(( ) ) m f X R   是凸集，显然(() ) m f x R   是凸集。由凸集分离定理

存在币≠0，使 m(f(x)-y)≤m(f()+z),x∈X,y20,z>0 令y=0,z→0，得mf(x)≤mf(),x∈X,即x是(P)的最优解。令x=x,y=0,得0≤mz,z>0, 即币≥0，由此得p2≠0。 (2)这时下=x,故由(1)得(2)。 考虑单目标优化问题： mimV/°-fx儿。=w,(P-fxrp (P.(f)) st.x∈X 其中f°=（°，，fY∈R"，≥maxf(x,i=1…,m,w=(,…,"'∈R"，p之1。 推论9.2.3设∈X是(P,(f))的最优解，则 (1)当w2≠0时，x∈X.； (2)当w>0时，下∈。 考虑单目标优化问题： miny°-fx=2xw,f-fx》 (P(f) s.t.x∈X 其中f°=(f°，，f)了∈R"，f°≥maxf(x),w=(g,…,wn)∈R"。 推论9.24设x∈X是(P(f)的最优解，则当w>0时x∈元。 *定理9.2.8设°=(f°，…，f了∈R"，f°>maxf)。若xeX.,则存在币>0，使x是(Pm) 的最优解。 证明：取可P-石=L,m,则=（网了>0。 假设x不是(P(F)的最优解，则存在x'∈X,使 max而，(f八-fx)<max丽，(f°-f(》=1 得m,(f°-f(x)<1,i=1,…,m,即f°-f(x)<1/m=°-f(),i=1,…,m,亦即 f(x)>f(),i=l,…,m→f(x)>f() 此与x∈矛盾。由此知，下是(Pm)的最优解。 §9.3化多为少的方法 一般来说，要求所有目标同时达到最优是不可能的，有所失才能有所得，有得必有失，即不存在(MVP) 的最优解，因此一般用化多为少的方法求得问题的非劣解或弱非劣解。考虑 V-max f(x)=(f(x),.(x))' (MMP) s.t.x∈X 记f=maxf(x),i=l,…,m,f'=(f,…,fm)∈R"。 4

4 存在 w  0 ，使 ( ( ) ) ( ( ) ), , 0, 0 T T w fx y w fx z x Xy z       令 y z 0, 0   ，得 ( ) ( ), T T wfx wfx x X   ，即 x 是( Pw )的最优解。令 x xy  , 0  ，得 0 ,0 T   wz z ， 即 w  0 ，由此得 w  0 。 （2）这时 X X  w ，故由（1）得（2）。 考虑单目标优化问题： 0 0 1/ , 1 min ( ) [ ( ( )) ] s.t. m p p ii i w p i f fx w f fx x X      ( 0 , ( ) Pw p f ) 其中 00 0 1 (,, )T m m f   ffR  ， 0 max ( ), 1, , i i x X f fxi m     ， 1 (,, )T m ww w R    m ， p 1。 推论 9.2.3 设 x  X 是( 0 , ( ) Pw p f )的最优解，则 (1) 当 w  0 时， w x  X ； (2) 当 w  0 时， x  X 。 考虑单目标优化问题： 0 0 , 1 min ( ) max ( ( )) s.t. ii i w i m f fx w f fx x X       ( 0 , ( ) Pw f  ) 其中 00 0 1 (,, )T m m f   ffR  ， 0 max ( ) i i x X f f x   ， 1 (,, )T m ww w R    m 。 推论 9.2.4 设 x  X 是( 0 , ( ) Pw f  )的最优解，则当 w  0 时 w x  X 。 *定理 9.2.8 设 00 0 1 (,, )T m m f   ffR  ， 0 max ( ) i i x X f f x   。若 w x  X ，则存在 w  0 ，使 x 是( Pw, ) 的最优解。 证明：取 0 1 , 1, , ( ) i i i w im f fx     ，则 1 (,, ) 0 T ww w   m  。 假设 x 不是( 0 , ( ) P F w  )的最优解，则存在 x X ，使 0 0 1 1 max ( ( )) max ( ( )) 1 ii i ii i im im wf fx wf fx       得 0 ( ( )) 1, 1, , wf fx i m ii i     ，即 0 0 ( ) 1/ ( ), 1, , i i ii i f     fx w f fxi m   ，亦即 ( ) ( ), 1, , ( ) ( ) i i f x     f xi m  f x f x 此与 w x  X 矛盾。由此知， x 是( Pw, )的最优解。 §9．3 化多为少的方法 一般来说，要求所有目标同时达到最优是不可能的，有所失才能有所得，有得必有失，即不存在(MVP) 的最优解，因此一般用化多为少的方法求得问题的非劣解或弱非劣解。考虑 max ( ) ( ( ), , ( )) 1 . . T V fx f x f x m st x X     (MMP) 记 * max ( ), 1, , i i x X f fxi m     ， ** * 1 (,, )T m m f   ffR 

1.主要目标法 思想：根据目标的实际意义，确定一个主要目标让其尽可能好，而其余目标作为次要目标，只要满 足一定的条件，从而把次要目标作为约束处理。 不妨设(x)为主要目标希望尽可能大，其余目标f(x),i=2,…,m作为次要目标，要求 f(x)2心，i=2,…,m,则考虑问题： min(x) s.t.x∈X (P) f(x)≥a,i=2,…,m 定理9.3.1设x是(P)的最优解，则x∈X。。 证明：显然下∈X。假设x任X，则存在元∈X,使f()>f(),即()>f(), f()>f()2a,i=2,…,m。因此，元是(P)的最优解，并且f()>f(),与下是(P)的最优解矛 盾。 定理9.3.2设(x)是X上严格凸函数，{x∈X|f(x)≥心，i=2,…,m}是凸集。若x是(P)的最 优解，则x∈灭。 证明：由条件知x是(P)的唯一最优解。假设x生X,则存在元∈X,使f()≥≠f(),即 f()≥f(),f()≥f()2,i=2,…,m。因此，x是(P)的最优解，并且f()≥()，与x是 (P)的唯一最优解矛盾。 2.线性加权和法 思想：根据各个目标在问题中的重要程度，分别赋于一个权系数，目标越重要，则对应的权系数 越大，对各目标线性加权后作为目标函数。 设f(x)的权系数为"，i=1,…,m,则考虑 maxwf(x)-wf(x) =1 (P.) st.x∈X 由推论9.2.2知，如果设x∈X是(P)的最优解，则当w≥≠0时x∈X,。,当w>0时x∈灭。 有时，再要求f(x)≥a,其中a=(a,…,am)'，考虑问题 maxwf(x)=wf(x) st.x∈X (Pa) f(x)za 定理9.3.3设x∈X是(Pa)的最优解，则当w2≠0时x∈X.,当p>0时x∈x。 3.极小极大法 思想：借鉴决策论中保守主义思想，即在最不利情况下寻求做有利的策略。 考虑问题：

5 1． 主要目标法 思想：根据目标的实际意义，确定一个主要目标让其尽可能好，而其余目标作为次要目标，只要满 足一定的条件，从而把次要目标作为约束处理。 不妨设 1f ( ) x 为主要目标希望尽可能大，其余目标 ( ), 2, , i f xi m   作为次要目标，要求 ( ) , 2, , i i f xi m     ，则考虑问题： min ( ) 1 . . ( ) , 2, , i i f x st x X f xi m      ( P ) 定理 9.3.1 设 x 是( P )的最优解，则 w x  X 。 证 明 ：显然 x  X 。假设 w x  X ，则存在 x  X ， 使 f () () x fx   ， 即 1 1 f () () x fx   ， ( ) ( ) , 2, , ii i f x fx i m      。因此，x 是( P )的最优解，并且 1 1 f () () x fx   ，与 x 是( P )的最优解矛 盾。 定理 9.3.2 设 1f ( ) x 是 X 上严格凸函数，{ | ( ) , 2, , } i i x   X fx i m   是凸集。若 x 是( P )的最 优解，则 x  X 。 证明：由条件知 x 是( P )的唯一最优解。假设 x  X ，则存在 x  X ，使 f () () x fx   ，即 1 1 f () () x fx   ， ( ) ( ) , 2, , ii i f x fx i m      。因此，x 是( P )的最优解，并且 1 1 f () () x fx   ，与 x 是 ( P )的唯一最优解矛盾。 2． 线性加权和法 思想：根据各个目标在问题中的重要程度，分别赋于一个权系数，目标越重要，，则对应的权系数 越大，对各目标线性加权后作为目标函数。 设 ( ) i f x 的权系数为 , 1, , wi m i   ，则考虑 1 max ( ) ( ) . . m T i i i w f x wf x st x X     ( Pw ) 由推论 9.2.2 知，如果设 x  X 是( Pw )的最优解，则当 w  0 时 w x  X ，当 w  0 时 x  X 。 有时，再要求 f x( )   ，其中 1 (,, )T     m ，考虑问题 1 max ( ) ( ) . . ( ) m T i i i w f x wf x st x X f x       ( Pw, ) 定理 9.3.3 设 x  X 是( Pw, )的最优解，则当 w  0 时 w x  X ，当 w  0 时 x  X 。 3． 极小极大法 思想：借鉴决策论中保守主义思想，即在最不利情况下寻求做有利的策略。 考虑问题：