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

3.3 多目标规划求解方法介绍 一、约束法 1.基本思想： 在多个目标函数中选择一个主要目标作为 目标函数，其它目标处理为适当的约束。 无妨设 为主要目标，对其它各目标 可预先 给定一个期望值，不妨记为 ， 则有 求解下列问题： mixgts xfxfxFVVP i T p ,1,0)(. )(,),()(m i n)( 1 mixgxS i ,1,0)( )(1xf )(,),(2 xfxf p 00302 , pfff pjxff jSxj ,3,2),(m in0 pjfxf mixgts xf P jj i ,3,2,0)( ,2,1,0)(. )(m in )( 0 1 容易证明，约束法求问题 (P)的最优解，其 Kuhn-Tucker条件与 (VP)有效解的 K-T条件一致。 因此，约束法求得的解是有效解。 (P)问题中各目标函数期望值的取得有多种方法， 一种方法是取一点 ，而取 得到下列问题： 2. 算法一般步骤： 考虑上述 (VP)问题， 为主目标。 Sx )0( pjxff jj ,3,2),( )0(0 pjxfxf mixgts xf P jj i ,3,2),()( ,2,1,0)(. )(m in )( )0( 1 )(xfk 第一步： （ 1）对 ，求解单目标问题： 得解 ； （ 2）计算 对应的各目标函数值，并对每个函 数 ，求其 p个点值中的最大值 Mj和最小值 mj。得到下表： Mj与 mj规定了 在有效解集中的取值范围。 pj ,2,1 Sxts xfVP j j . )(m in)( Tjnjjj xxxx ),( )()(2)(1)( )()2()1( , pxxx )(xfj )(xfj x(1) x(p) f 1(x) f 2(x) f p(x) m 1 m 2 m p f 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 p Mj mj 第二步： 选择整数 r1，确定 的 r个不同阀值： 第三步： 对 ，分别求解问题： 各目标函数 可对应不同的 （共 有 个约束问题）。求解后可得到 (VP)的一有 效解集合，是 (VP)有效解集合的一个子集。 )1,1,0( rtt jj )( kjf j 0jf 1,1,0;,1,1,1),(10 rtpkkjmMr tmf jjjjt 1,1,0 rt pkkjfxf mixgts xf P j j jtj i k t ,1,1,1,0)( ,2,1,0)(. )(m i n )( 1pr 例 6： 用约束法求解。设 为主目标。 第一步：分别求解 0)( 0)( 04)( 06)( 08)( 03)(. )(),()(m i n )( 26 15 24 13 212 211 21 xxg xxg xxg xxg xxxg xxxgts xfxfxFV L V P T 211 25)( xxxf 212 4)( xxxf )(1 xf Sxts xf . )(m in 1 Tx )0,6()1( 得 Sxts xf . )(m in 2 Tx )4,1()2( 得 f1 f2 x(1) x(2) Mj mj -30 6 3 -15 3 6 -30 -15 选定 r=4: 求解 于是可得四组解，如图 15所示。 0)( . )(m in )( 22 1 j j t t fxf Sxts xf P j=2只有一个 6,30,3,)0,6( ;1,5.26,2,)75.1,6( ;8,6.17,1,)2.3,8.4( ;15,3,0,)4,1( 3 2 3 1 3 2 2 2 1 2 1 2 1 1 1 0 2 0 1 0 fftx fftx fftx fftx T T T T t f 02t 0 1 2 3 -15 -8 -1 6 二、分层序列法： 1. 基本步骤： 把 (VP)中的 p个目标 按其重 要程度排一次序。依次求单目标规划的最优解。 2. 过程： 无妨设其次序为 先求解 得最优值 ，记 再解 得最优值 ， 依次进行，直到 得最优值 则 是在分层序列意义下的最优解集合。 )(,),(1 xfxf p pfff , 21 Sxts xfP . )(m in)( 1 1 * 1f SfxfxS *111 )( 1 2 2 . )(m in)( Sxts xfP *2f 1*222 )( SfxfxS 1. )(m in)( p p p Sxts xfP *pf 1*)( pppp SfxfxS 3. 性质 ： ，即在分层序列意义下的最优解是有 效解。 证明：反证。设 ，但 ，则必存在 使 即至少有一个 j0 ，使 , 由于 ，即 ， 矛盾。得证。 4. 进一步讨论： 上述方法过程中，当某个问题 (Pj)的解唯一时，则 问题 的求解无意义，因为解都是唯一的。 实际求解时，有较宽容意义下的分层序列法： 取 为预先给定的宽容值，整个解法同原 方法类似，只是取各约束集合时，分别取为： pj PP ,1 0,0 11 p pjSfxfxS jjjj ,3,2,)( 1* )(m in)( 0 000 * xffxf jSxjj j 0 jSx )()( 00 xfyf jj 1,1),()( 0 jjxfyf jj )()( xFyF Sy* paSxpSx *pap SS 三、功效系数法： 设目标为： 其中： 要求 min； 要求 max。 由于量纲问题，处理目标之间的关系时往往带来困难。 1. 功效系数法： 针对各目标函数 ，用功效 系数 表示（俗称“打分”）： 满足： 或 使最满意时 ，最不满意时（即最差时） 。 2. 常用的两种产生功效系数的方法： （ 1）线性型： 设 0jd1jd 10 jd10 jd pjxfdd jjj ,1,)( ),1)( pjxf j )(,),(1 xfxf pk )(,),(1 xfxf k )(,),(),( 21 xfxfxf p pjfxffxf jjSxjjSx ,2,1,)(m a x,)(m i n m a xm i n jd 由于 时求 ，令 故取 又 时求 ，令 故取 （ 2）指数型： 先讨论求最大的函数， 。 考虑： 显然， 有如下性质： 10. 当 充分大时， ； 20. 是 的严格递增函数。 )()(1 m i nm a xm i n jjjjj fffxfd m a x m i n ,0 ,1 jj jj j ff ff d kj ,1 )()( m i nm a xm i n jjjjj fffxfd m i n m a x ,0 ,1 jj jj j ff ffdpkj ,1 )(max xf j )(min xf j pkj ,1 jd jd jf 1jd jf 0, 1)10( bed jfbbej （） 为了便于确定 b0、 b1，选取两个估计值 ： 取 为合格值（勉强合格，即可接受）； 为不合格值（不合格，即不可接受）。 令 并取 得 解得： 代入式 ( )，得到功效系数： 同理可得当 时的功效系数： 0 11 )(,0 6 6 0.0 )(,3 6 7 9.0 jj e jj j fxfe fxfe d 0jf 1jf 10, jj ff )010( )110( 1 jfbb jfbb ee e ee ee 1 0 0 10 1 10 j j fbb fbb )0()(1,)( 11011010 bffbfffb jjjjj kj ,1 )10()1)( jfjfjfxjfe j ed )10()(1( jfjfxjfjfe j ed 3.利用功效系数求解问题 (VP)： 设 (VP)的功效系数为 令 构造问题： 可以证明： 上述问题 (P)的最优解 ，即原问题 (VP)的有效解。 四、评价函数法： 1.理想点法： 设 ，即各单目标问题的最优值。 令评价函数 ，做为目标函数。 更一般地，取 *x mixgts xfdxFh P i p p j jj ,1,0)(. )()(m a x )( 1 1 p p j jdFh 1 1 )()( pjxfdd jjj ,2,1),( pjxff jSxj ,2,1),(m in* p j jj fxfFh 1 2* )()( qp j q jj fxfFh 1 1 * )()( 从不同角度出发，构造评价函数 h(F)，求 问题 , 得到 (VP)的有效解。 下面介绍一些评价函数的构造 (即不同的方法 )。 2. 平方和加权法： 求出各单目标问题 最优值的下界 (期望的最好值 )。 令评价函数 其中 为预先确定的一组权数，且满足 的值为各目标函数的权数，较重要的取值较大。 Sxts xFh . )(m in j 1;,2,1,0 1 p j jj pj p , 21 p j jjj fxfFh 1 0 )()( mixgts xfP i j j ,2,1,0)(. )(m in)( 0jf j 3. 范数和加权法： 同上面类似，先求出各单目标问题的最优值下界 ， 取 ，构造评价函数： 其中 为权系数，且 。 把此方法与分层序列法结合，取 ，用于线性多目 标规划，即得到目标规划方法（运筹学课中所学的）。 4. 虚拟目标法： 仍如“ 2、 3”得到 ，设 取评价函数： gl 0jf j 1;,2,1,0 1 p j jj pj 1q 1q q p j q jjj fxfxFh 1 1 0 )()( ),2,1(0 pjf j p j jjj ffxfFh 1 200 )()( ),2,1(00 pjf j 5.线性加权法： 预先给出每一目标函数 的权系数 ，满足 。取评价函数： 线性加权法是最常用的方法之一。 此法可直接解释 (VP)有效解的 Kuhn-Tucker条件 。 几何意义： 设 n=2,p=2。线性加权法解问题： j 1,0 1 p j jj p j jj xfxFh 1 )()( )(xfj 1,0, 2121 0)( 0)(. )()(m in )( 2 1 2211 xg xgts xfxf P 在像空间， (P)等价为问题： 记 ，则 。 及 分别对应单目标问 题 (P1)及 (P2)。 当正数 确定后，可得问题 (PF)的最优值 ，如 图 18，可知 对应的原像 。 、 。 )(),( 2211 xffxff 2211 fff f * paSx 00 21 )(),(. m in)( 21 2211 SFffts fffP TF 21, f 可以利用线性加权法来逼近有效解的集合，但不是一 种准确寻找所有有效解的有效方法。当 从 0 -时，可 得到非劣解的一个子集。如上 图 19所示。 A、 B为相应 集合的端点。 当 或 时， 可能是弱有效解， 如下 图 20。只有 ，由 A到 B的其余点为弱有效点。 它们对应的原像为弱有效解。 例 7： )0( 2 )0(0 1 *paEA 0)( 0)( 04)( 06)( 08)( 03)(. )(),()(m i n )( 26 15 24 13 212 211 21 xxg xxg xxg xxg xxxg xxxgts xfxfxFV L V P T x 其中： ， 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。 211 25)( xxxf 212 4)( xxxf 2 1 41 25)( x xMxxF Tc )4,1(2 Tc )2,5(1 图 21： 当 , 即 时 , 即 (P 2)的解 : 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 。 0 1,0 21 21,21 21 0,1 21 SxSFffts xxfff T ,)(),(. 22121m in 21 2121 32,31 21 SxSFffts xxfff T ,)(),(. 23231m in 21 2121 43,41 21 SxSFffts xxfff T ,)(),(. 5.25.04341min 21 2121 6. “min-max”法（极小 -极大法） 对策论中常遇到“在最不利情况下找出最有利策略” 的 问题，即“ min-max”问题。 取评价函数 然后求解 设得解 , 是 x的函数。如右图。 实用中，可以使用下列 加权形式，取 ，令 x )(m a x)( 1 xfxFh jpj pjxfxFh j ,2,1)(m a x)( Sxts pjxfxFhP j Mm . ,2,1)(m a xm i n)(m i n)( 1,0 1 pj jj pjxfxFh jj ,2,1)(m a x)( 为了求解方便，可把问题 (PMm)等价化为下列数学规划 问题 : 定理： 设 是 的最优解，那么 为 (PMm)的最优 解；反之，若 是 (PMm)的最优解 , 且 那么 是 的最优解。 证：设 是问题 的最优解，明显地，有 由第一组约束知： 由目标 min t知 取得满足上式的最小值。 对 (PMm)的任意可行解 x，令 那么 。于是 即 是问题 (PMm)的最优解。 x x )( MmP )( MmP pjxft j ,2,1)(m a x TT tx ),( mixg pjtxfts t P i jMm ,2,1,0)( ,2,1,)(. m in )( TT tx ),( TT tx ),( )( MmP pjxft j ,2,1)(m a x pjxft j ,2,1)(m a x tt t pjxft j ,2,1)(m a x pjxfttpjxf jj ,2,1)(m a x,2,1)(m a x x 反之，考虑 是 的任意可行解，则 （第一组约束） 是 (PMm)的最优解，可得，对 (PMm)的任意可行解 x，有 于是 。即 为 的最优解。 7. 乘除法： 设 (VP)中，对 ，均有 再设 求 min； 求 max。 取评价函数 求解 x )( MmPTT tx ),( )( MmPTT tx ),( pjxft j ,2,1)(m a x pjxfpjxf jj ,2,1)(m a x,2,1)(m a x tt mixgts xFh i ,2,1,0)(. )(m in p kj j k j j xfxfxFh 11 )()()( pjxf j ,2,1,0)( Sx )(,),(),( 21 xfxfxf k )(,),(),( 21 xfxfxf pkk ， 。 8. 评价函数法的收敛性： 考虑 (VP)， h(F(x)为评价函数。 定义： 设 ， 10. 若满足 时，均有 ，则称 h(F)是 F的严格 单调增函数； 20. 若满足：当 时，均有 ，则称 h(F)是 F的 单调增函数。 定理： 若 ， 10. 若 h(F)是严格单调增函数，则数学规划 的最优解 ； 20. 若 h(F)是单调增函数，则数学规划 的最优解 。 pRFF , FF )()( FhFh FF )()( FhFh * wpSx * paSx Sxts xFhP . )(m in)( 1 Sxts xFhP . )(m in)( 2 pRF 证明： 10. 反证 。设 ，由定义， 使 由 h(F)的单调增性质，得到 与 是 (P1)的最优解矛盾。 20. 反证 。设 ，由定义， 使 由 h(F)的单调增性质，得到 与 是 (P2)的最优解矛盾。证毕。 可以证明， 上述各评价函数： 1.理想点法、 2.平方和加权法、 3. 范数和加权法、 4.虚拟目标法、 5.线性加权法 ( )、 7.乘 除法均为严格单调增函数；而 5.线性加权法 ( )、 6. min-max方 法为单调增函数。 由此，根据定理可得，方法 5(线性加权法 ( )方法 6(min- max法 )得到的解 ；其它各方法得到的解 。 * paSx Sy )()( xFyF )()( xFhyFh 0j 0j * wpSx Sy )()( xFyF )()( xFhyFh x x 0j * wpSx * paSx gl 9.确定权系数的方法： (VP)问题的评价函数 h(F(x)中所需预先给出的权系数： （ 1）“老手法” 基本过程： 邀请一批“老手”（专家，有经验的人员 等）， 汲取他们对权系数的意见，加以综合得到权系数。 设有 k位“老手”，为了便于其独立发表意见，将事 先 准备好的调查表送给他们分别填写。设第 i位“老手”对 第 j个目标 给出的权系数为 。 针对每个目标函数 ，计算平均权系数： 得到下表： 1,0, 11 p j jp )(xfj )(xfj ij pjk k i ijj ,2,1,1 1 计算每一位老手 i(i=1,2, ,k)关于平均权系数 评价的 偏差： 。 第二轮讨论，请最大偏差的老手首先发表意见，经充 分讨论以达到对目标重要度的正确认识，消除参数估计 中的误解。然后重新评价。 如此反复进行，最后达到较为一致的认识。 j pjjijij ,2,1, （ 2） -方法： 对 p=2的情形叙述：求 的最优解 。 记 ，像空间的图形如下（ 图 23）。 在像空间中，点 确定一条直线 L1，记其方程 为 。 把上面两个点的坐标代入，得到： 。 若问题 (VP)不存在绝对最优解 (存在 绝对最优解时，上述方程组为一 个点， )，即 。 则有 记 ， 解方程组 得： 2,1,)( jx j Sxts xfP j j . )(min)( )( )2(2)1(1)1(2)2(1 ffff )( )( )1( 1 )2( 12 )2( 2 )1( 21 ff ff )()( )2(2)1(2)1(1)2(1 ffff )(),( 21 )2(2)2(2)1(2)1(2 )()( fxfxff )1(1)1(1)2(1)2(1 )()( fxfxff *abE)2(2)2(1)1(2)1(1 ffff )2(22)2(11 )1(22)1(11 2 )( ff ff )(1, 1212211 ff TT ffff ),(,),( )2(2)2(1)1(2)1(1 2,1,),( )()( jkxff kjkj 取这组 时，线性加权法 的最优解 对应的像点为 ，如图 23。 对于一般情况： p2 。 记单目标问题 的最优解为 ，记 过 p个点 做超平面，得方程组 当 (VP)不存在唯一解时，可确定唯一一组解 ( 共 p+1个变量， p+1个方程 )。 该解 即为一组权系数。 x Sxts xfP j j . )(min)( )(jx pjkxff kjkj ,2,1,),( )()( 0,1 21 )()( 22 )( 11 )2()2( 22 )2( 11 )1()1( 22 )1( 11 jp p pp pp pp pp fff fff fff pkfff Tkpkk ,2,1,),( )()(2)(1 TxfxfxF )(),()( 21 Sxts xfxfxf . )()()(m in 2211 21, , 21 p p , 21 10.有限方案多目标决策问题简介 前述的一些方法均是针对无限方案多目标决策问题 的模型进行讨论的。也是在这一领域中遇到较多的且要 求基础知识较深的一部分内容。 （ 1）有限方案多目标决策问题的特征及基本思路： 特征： 仅含有限多个方案； 决策情况的范围只涉及分析 -评价的内容。 基本解题思路： 筛选 排序 集结 综合 筛选： 对有限个可能方案，按照某种 (些 )准则，筛去显著不满 意的方案，使下一步所考虑的方案尽可能的少； 排序： 根据各属性特征给各属性赋权。然后，按照不同的方法， 给各方案排序。 集结： 常用三种技术，对上步得到的不同方法下各方案的排序 进行集结 (按不同技术的综合评价 )。有下列三种技术： 常用的集结方法： 平均值法： 求各方案在不同方法下名次的平均值。按 平均值的大小得到集结名次，若平均值相同时，则取 方差较小的排在前。 例 8： 有四个方案 ，用四种方法 进行 排序，得到下表： 对各方案两两比较 (如 xi与 xj)，若认为 xi好于 xj的方案 多，记为胜 (M)，否则记为败 (X)(不优于 )。 Borda法： 找各方案“胜”的次数之和，进行集结。 4321 , xxxx 4321 , MMMM Copaland法： 找各方案“胜” (取正 )与“败” (取负 )次 数的代数和，进行集结。 例 9：同上例，结果如下。 综合： 上步得到三种技术下的排序，一般仍存在不可 比的关系。构造一排序集：当 xi优于 xj时，记为 ， 否则认为不可比。当 时，节点 xi位于 xj上，这样 得到一个偏序结构图： ji xx ji xx （ 2）决策矩阵和规范化 决策矩阵： 把各方案 xi (i=1,2, ,m)及属性集 yj(j=1, ,n) 、 列表得到决策矩阵。其中 (方案 xi的第 j个属性值 )。 向量规范化： (化为无量纲值 ) )( ijij xfy Tmjjjj yyyy ),( 21 )1,0(, 1 2 ij m i ijijij zyyz 一般达不到 0或 1。 x1 x4 x5 x2 x3 -第 1等级 -第 2等级 -第 3等级 计算 线性变换规范化： (使 ) 若求最大时 ： (效益 ) , 求最小时： (成本 ) , 其它规范化变换： (统一变换后的属性 ) 求最大时： 求最小时： 统一最优时： ；最劣时： 。 （ 3）权系数的确定： 一般采用类似层次分析法中的两两比较判断 , 构造判断矩阵， 用特征根法 , 或和积法 , 方根法求特征向量的方法确定权系数。 )()( m i nm a xm a x jjijjij yyyyz )()( m i nm a xm i n jjjijij yyyyz 0ijz1ijz 1,0ijz maxjijij yyz 1ijz理想最优时 ma x1 jijij yyz 0ijz最劣时 ijijijij yyyy m in,m a x m i nm a x （ 4）常用的筛选方案的方法： 优选法： 利用非劣性概念。 两方案比较，某一方案 A的各属性不劣于令一方案 B的，其中 至少有一个属性是 A优于 B，则淘汰方案 B。 连接法 (满意法 )： 对每一属性规定一“ 切除值 ” (可接受的最低值 )，当某个方案 的 相应属性低于该值时，即淘汰之。此法的 关键是 确定各属性的 “切除值”。 缺点是 目标之间不能补偿 (如单科成绩特优异学生会 被 淘汰 )。 分离法： 对每一属性规定一“切除值” ，当某个方案的相应属性高于 该 值时，则保留之。此法的“切除值”一般高于连接法的。 利于选择单属性特优方案。 （ 5）排序方法： 有多种常用方法。其中层次分析法是效果较好的方法。