（运筹学与控制论专业论文）求解多目标规划问题的一种途径.pdf

2 0 0 4 年上海大学硕士学位论文 摘要 通常一个求多目标规划问题可以表述为 v 一磐即) 【y m p ) 其中f ( x ) = ( ，l ( z ) ，如( z ) ，一，厶( z ) ) 7 是区域x 上的m 维向量函数， ( z ) 矗”一月0 = l ，2 ，m ) 为连续函数，爿为n 维欧氏空间中的非空闭集 求多目标规划问题的方法在科学技术，工程设计，经济管理等方面有着很 广泛的应用 本文的主要工作是受求解多目标规划的积分总极值算法 1 ，2 的启 发，给出了种求解多目标规划问题的算法我们的算法在每一次迭代 中，构造一个新函数，使得新函数的有效解与弱有效解亦为原函数的有效 解与弱有效绥，从而可以求得多目标规划极小化模型( v m p ) 的全局有效 解或弱有效解，而且概念性算法是收敛的在算法的实现时，我们用数论 中确定性的一致分布的数值积分来逼近水平值和水平集，且不改变搜索 区间，并证明了实现算法的收敛性最后计算了六个多目标优化问题， 通过计算结果，可以看到我们的算法不仅可以求到多于一个的有效解或 者弱有效解，还可以体现各分目标的不同重要性，即我们的算法是有效 的， 在第一章中，我们介绍了几种求多目标规划的算法这些算法中，有 评价函数法，分层序列法，积分总极值算法，目的规划法，交互式法在 第二章中，我们给出了这种求解多目标规划问题的概念性算法和实现算 法，并证明了概念算法和实现算法的收敛性，在第三章中，我们给出了六 个数值计算，说明算法是有效的 关键词：多目标规划，积分型算法，全局有效解，全局弱有效解 2 0 0 4 年上海大学硕士学位论文1 i a b s t r a c t i h em u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e mc a nb es t a t e da sf o l l o w s ( v m p ) y 一磐f ( z ) f = ( f 1 ( x ) ，f 2 ( x ) ，矗l ( 。) ) 7i sav e c t o rf u n c t i o no fi nd i m e n s i o no v e rx ， ( z ) ：r “_ r u = 1 ，2 )，m ) i sac o n t i n u o u sf u n c t i o na n dxi san o n e m p t y c l o s e ds e t t h e r ea r em a n ya p p l i c a t i o n so ft h em u l t i o b j e c t i v ep r o g r a m m i n g i nt h ( 、f i e l dn fs c i e n c ea , n dt e c h n o l o g y o p t i m a ld e s i g nd fe n g i n e e r i n g e c o n o m i c m a n a g e n e n ta n ds oo n t h el ：o a i np u r p o s eo ft h i st h e s i si st op r o p o s ea na l g o r i t h mf o rs o l v i n gm u l t i - o b j e c t i v ep r o g r a m m i n gi nt h el i g h to fi n t e g r a l - l e v e ls e ta l g o r i t h mf o rs o l v i n gt h e m u l t i o b j e c t i v ep r o g r a m m i n gi ne a c hi t e r a t i v ep r o c e s s ，w ec o n s t r u c tn e wf u n c t i o n sw h o s ee f f e c t i v es o l u t i o n sa n dw e a ke f f e c t i v es o l u t i o n sa l s oa r eo r i g i n a lf u n c t i o n s 、e f f e c t i v es o l u t i o n sa n dw e a ke f f e c t i v es o l u t i o n s i nt h i sw a y ，w ec a no b t a l ne f f e c t i v es o l u t i o n so rw e a ke f f e c t i v es o l u t i o n so ft h em u l t i o b j e c t i v ep r o g r a m m i n g ( v m p ) m o r e o v e r ，t h ec o n v e r g e n c eo ft h en o t i o n a la l g o r i t h mi sp r o v e d d u r i n g t h ei m p l e m e n t e da l g r i t h m w ea p p l yt h ed e t e r m i n i s t i cu n i f o r md e s t r i b u t i o nn u m e r i c a li n t e g r a li nn u m b e rt h e o r yt oa p p o r a c ht h el e v e lv a l u ea n dt h el e v e ls e t w i t h o u tc h a n g i n gt h es e a r t hd o m a i n j f u r t h e r m o r e ，w ea l s op r o v et h ec o n v e r g e n c eo f t h ei m p l e m e n t e da l g o r i t h m a tl a s t l w ec a l c u l a t es i xm u k i o b j e c t i v ep r o g r a m m i n g p r o b l e m sp r o mt h eo u t c o m e ，w ec a ns e et h a tt h ea l g o r i t h mc a nn o to n l yo b t a i n m o r et h a no n ee f f e c t i v es o l u t i o no rw e a ke f f e c t i v es o l u t i o n ，b u ta l s oe m b o d yt h e d i f f e r e n ti m p o r t a n c eo fe v e r ys u b h u m t i o n ，t h a ti st os a y , o u ra l g o r i t h mi se f f e c t i v e i nc h a p t e r1 】ab r i e fi n t r o d u c t i o ni s g i v e nt ot h em a i nc l a s s e so fm u l t i 。 o b j e c t i v ep r o g r a m m i n gp r o b l e m ls u c ha sa p p r a i s a b l ef l m c t i o nm e t h o d ，o b j e c t i v e p r o g r a m m i n gm e t h o d ，l a y e r e ds e q u e n c em e t h o d ，s a t i s f a c t o r yl e v e lm e t h o d ，a l t e r n a t i n gm e , h o d ，i n t e g r a lm e t h o d i nc h a p t e r2 ，w ep r o p o s en o t i o n a la l g o r i t h m a n di m p l e m e n t e da l g o r i t h mo ft h i si n t e g r a l - l e v e ls e ta l g o r i t h mf o rs o l v i n gt h e m u l t i o b j e c c i v ep r o g r a m m i n g a tt h es a m et i m e ，w ep r o v et h ec o n v e r g e n c eo ft h e 2 0 0 4 年上海大学硕士学位论文 n o t i o n a la l g o r i t h ma n di m p l e m e n t e da l g o r i t h m i nc h a p t e r3 w ep r e s e n ts i x 1 u n l e i i c a le x a m p l e st os h o wt h a ：o i l ya l g o r i t h ma l ( 、e f f h c t i v e k e yw o r d s ：m 1 1 1 t i ( ) h j e c t i v eo p t i m i z a t k m ，i n t e g r a la l g o r i t i i m ，g l o b a le f f e c t i v e s o l m i o l lg l o b a lw e a ke f f e c t i v es o h t d o n 第一章前言 1 1 引言和定义 研究多于一个目标函数在给定区域上的最优化，又称多目标最优化。通常记 为v m p 在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域， 衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较， 这就是多目标最优化问题多目标最优化问题的最早出现，应追溯到1 7 7 2 年， 当时p r a n k l i n 就提出了多目标矛优化的问题但国际上一般认为多目标最优化问 题最早是由法国经济学家vp a r e t o 在1 8 9 6 年提出的当时他从政治经济学的角 度，把很多不好比较的目标归纳成多目标最优化问题1 9 4 4 年，v o n n e u m a n n 和 jm o r g e n s t e r n 又从对策论( 博弈论) 的角度，提出多个决策者而彼此又互相矛盾 的多目标决策问题1 9 5 1 年，t ck o o p m a n s 从生产与分配的的活动分析中提出 了多目标最优化问题并且第一次提出了p a r e t o 最优化的概念。同年，h wk u h n 和a w t u c k e r 从数学规划的角度，给出了向量极值问题的p a r e t o 最优解的概念， 并研究了这种解的充分与必要条件1 9 5 3 年，a r r o n 等人对凸集提出了有效点的 概念，从此多目标规划逐渐受到人们的关注1 9 6 3 年，l a z a d e h 又从控制论的 角度提出多目标控制问题这期间c h a j n e s ，k a r l i n ，k l i n g e r ，p o l a k ，k e e n e y ， g e o f f r i o n 等人先后都做了较有影响的工作1 9 6 8 年，z j o h n s e n 系统的提出了关 于多目标决策模型的研究报告，这是多目标最优化这门学科开始大发展的一个转 折点 多目标最优化问题从p a x e t o 正式提出到j o h n s e n 的系统总结，先后经过了六、 七十年的时间但是多目标最优化的真正发达时期，并且作为一个数学分支进行 系统的研究，是本世纪七十年代以后的事情1 9 7 5 年，m z e l e n y 写了第一本关于 多目标最优化问题的论文集从1 9 7 2 年开始，以多目标决策命名的国际学术会议 已召开了十多次到现在为止，多目标最优化不仅在理论上取得了很多重要的成 果，并且在应用上其范围也越来越广泛，多目标最优化作为一个工具在解决工程 技术、经济、管理、军事和系统工程等众多方面的问题也越来越显示出它强大的 生命力 2 0 0 4 年上海大学硕士学位论文2 一个多目标规划问题一般如下定义 f v 彳p 1 其中，( z 1 = ( f l ( z ) ，2 ( 。) ， 。( 。) ) 1 是区域x r ”上的m 维向量函数 定义1 1 1 设xcr “是模型( y m 尸) 的约束集，r ( z ) r m 是( y p ) 的向 量目标函数若孑x ，并且不存在。爿使得f ( z ) f ( i ) 且f ( z ) f ( 孟) ， 则称是多目标规划极小化模型m p ) 的全局有效解；若不存在z x 使得 f ( z ) ( f ( 司，则称叠是多目标规划极小化模型( y m p ) 的全局弱有效解；若矿x ， 并且f ( z j 兰f ( z ) ，v x 则称z + 是多目标规划极小化模型( 矿m p ) 的全局绝 对最优解记全局有效解，全局弱有效解，全局绝对最优解的集合分别为e ，1 0 ，e 。 下面几节，我们将对多目标规划的一些方法做简要的介绍，具体可参见文献 f 3 45 ，6 ，孔 1 2 评价函数法 评价函数的基本思想是，根据问题的特点和决策者的意图，构造一个把，n 个分量目标函数转化为一个数值目标函数一一评价函数然后对评价函数进行最 优化，这样就把求解多目标最优化问题转化为求单目标最优化问题了见文献 8 9 l o 1 2 1 。理想点法 其基本思想是：找出各个分目标函数在定义域内的最小值，记为理想点，然 后把每个分目标函数与此理想点的距离平方和记为评价函数对多目标规划问题 y 一必f ( z ) 2 ( ( 。) ，厶( z ) ，一，m ( z ) ) 步骤1 找出各个分目标函数在定义域内的最小值 鬈2 辫五( 。) i = j ，2 ，m 步骤2 定义评价函数： u ( f 0 ) ) = u ( ，1 ，2 ，- ，赢) = 广i 一 j 蚤。卜舻 ( 1 2 i ) 2 0 0 4 年上海大学硕士学位论文 步骤3 求解非线性规划问题 r a 。i x n “( f ( 。) ) 得到的距离理想点最近的点即为最优解 1 2 。2 ，线性加权和法 线性加权和法是最基本的评价函数法其基本思想是，根据各个目标在问题 中的重要程度，分别赋予它们一个数，并把这个数作为该目标的系数然后把这 些带系数的目标函数相加的和函数作为评价函数 步骤1 按各目标 ( z ) 0 = 1 ，2 ，m ) 在问题中的重要程度给出一组权系数： u l 、u 2 ，u m ，要求u ，0 ，且u 。= l 步骤2 求线性加权和函数 m i ：u 。 ( z ) ( 1 22 ) z 上一 。 的最优解，即为问题( v m p ) 的有效解或弱有效解 1 2 3 平方和加权法 其基本思想是；平方和加权法体现了通常的“自报公议”原则一一那些强调 各自目标重要者预先给出一个尽可能好的估计，然后“公议”给出一组表明各目 标性的权系数，最后求解非线性规划给出解答 步骤1 先设定单目标规划的下界( 想象中的最好值) ，即 疗( 。) o ，j = 1 h 2朋a ，= 1 步骤3 求解非线性规划问题 骧“( f ( z ) ) 2 0 0 4 年上海大学硕士学位论文4 1 2 4 极大极小法 人们在处理复杂的困难问题时，往往采取这样一种策略思想，即在最坏的情 况下争取最好的结果在求解多目标最优化问题时，也可采用类似策略思想，即 考虑在对各分量目标最不利的情况下找出最有利的解 步骤1 用各目标函数，。( z ) “= l ，2 ，一，m ) 的最大值作为评价函数的函数值 来构造评价函数，即令 u ( f ) 21 鼍焉 ( z ) )( 1 24 ) 为评价函数，其中f ( x ) = ( 0 ) ，2 ( z ) ，m 严 步骤2 通过上述评价函数u ( f ) 把求解( v m p ) 问题转化为求解单目标最优 化问题 刚m i n “( f ( 。) ) 2 卿1 要笛( ( 。) ) ( 1 2 ，5 ) 可以证明，得出的解为( v m p ) 问题的有效解或弱有效解 1 2 5 极大极小法的转化 此非线性规划问题目标函数不可微，不能直接用基于梯度的算法 蹦m i n u ( f ( 。) ) 2 辫。蛩 ( 。) ) 但是可方便转化为一个简单的非线性规划问题该技巧非常有用，将一个不可微 的规划问题转化为可微的约束规划。 令f _ ，罟焉 ( z ) ) ，则该规划问题可等价为： 般、。 ( 1 2 6 ) s ，o 扛) t ， = 1 ，2 ，一，m( 1 2 7 ) ze x ( 1 , 2 8 ) 1 2 6 乘除法 考虑两个目标得规划问题； 恕 ( 。) ( z ) 口 2 0 0 4 年上海大学硕士学位论文5 步骤1 定义评价函数 搿a ( 。) 止( z ) 0 步骤2 求解非线性规划问题 本节介绍分层序列法 罢野“( ，( z ) ) 。癸譬矗( 2 ) ( z ) 1 3 分层序列法 1 3 1 完全分层法 步骤l 根据各目标的重要程度不同，将m 个目标函数排序假定 最重 要，2 次之，厶最不重要， 步骤2 逐次求解下列m 个单目标问题( r ) 的最优解扩，其中 ( 尸1 ) r a i n 止( z ) 8 o x ( r ) r a i na ( z ) s 扛) = ( 矿) 0 = 1 ，2 ，k 1 ) z x ( = 2 ，3 ，一，m ) ( 1 3 。1 0 ) f 1 3 1 1 1 这种方法得缺点是；当前面的问题最优解唯一时，后面的求解失去意义 我们可以对这种方法进行一下改进：给前面的最优值设定一定的宽容值e o 即此目标值再差e 也是可以接受的 1 3 2 分层评价法 和完全分层法不同，决策者认为m 个目标可分为8 个优先层次，8 一般小于 日 m 记第i 个层次含目标的下标集为厶，i = 1 ，2 ，s 于是u 厶一 1 ，2 ，m 目 2 1 标 ，属于最优先的；目标 ，2 次之，当s = m 时就成了完全分层 法这类分层模型的特点是，通常每一优先层次的目标函数是多个的因此，每 吨 坞 m 3 3 3 q q n 2 0 0 4 年上海大学硕士学位论文 6 一层次对应的不是一个单目标优化问题，而是一个目标个数相对来讲少一些的多 目标规划问题我们假定决策者希望每个目标a 都尽可能地小( 但此时优先层次 不同) ，可行解集为盖分层评价法地步骤可归纳为： 步骤1 令x 1 = x ，= 1 步骤2 选第k 优先层次地评价函数u ：r 【“i 一尉，其中l 女l 表示“中所含 元素的个数 步骤3 利用评价函数“t ，把第优先层次的多目标规划问题转为下列问题： “b ( f k ( z ) ) z x ” ( 1 3 1 5 ) ( 1 3 1 6 ) 得最优解z 和最优目标值u i ，其中几( z ) = ( 。( z ) ， 。( z ) ， ，f k ( z ) ) 7 ， = k l ，k 2 ， ，) 步骤4 检验迭代次数，若= s ，则输出矿，否则进行下一步 步骤5 令x 2 + 1 = x x 2 ( a ( z ) ) su 孙k + 1 一k ，转步骤2 可以证明当每个u ( g ) 是y 的严格单调减函数时，是问题( v m p ) 的一个 有效解，当每个u k ( y ) 是g 的单调减函数时，矿是问题( v m p ) 的一个弱有效解 1 4 积分总极值法 1 9 8 9 年，姜佩磊在文献 1 ，2 中把单目标积分总极值方法与多目标的分层序 列法二者思想联系起来，提出了相关均值与相关方差的概念，得到了一种新的多 目标问题的总体优化算法现将其算法简要介绍如下： 步骤1 取定小的正常向量t 足”，及初值c o 胛，令k ：= o ，g c * ：= 扣 f ( z ) c 2 ) 步骤2 计算相关均值c 1 ：= m ( 只c ) ，相关方差y f ：= y ( f 1c ) ，水平接收 集h g + 一n x = zj f ( z ) 兰c + 1 ) n x 步骤3 若v f e ，则k ：= + 1 ；转步2 ，否则转步4 步骤4 令c + ：= c + 1 ；h p n x = 日g n x ；终止 其中定义问题( y m p ) 的相关均值和相关方差如下：取c r “，c 2 = ( 母，c ，一，c ) 7 使p ( 符c t n x ) o 、 2 0 0 4 年上海大学硕士学位论文 7 作 令 则 作 令 则 作 令 m “f = 赤t n 。，l ( 圳胚幽 l q ( f , c k ) = 而击两上栅。( 肌) 川f ) 2 咖 c ：1 1 = m 1 ( f _ c ) ，e = ( c ：+ 1 ，c l ，一- ，c ) 7 ( g 2 ) h a fn x = ( zf ( z ) 曼c b f l x = zy l ( x ) 曼c ：+ 1 ) r - - c * n 义 了厅l 而f ，2 ( ) m ( sc ) p ( fnx ) j h ，钔x 川p ”中忙 南厶棚。( 胁) 一( 只萨) ) 2 咖 砖“= 尬c “) ，嘴= ( c ；“，c ；“，砖，c 袅) 7 ( 讲) h 罐n x = 如lf 扛) sc r - x = zi 如扛) c 妒1 ) n n x ( 片嚷一，r x ) 嘣肿2 币丢而 n x ，m ( z ) 舡( c ) ( 。 ) 一 i 。( f ，c 。j ) 2 d p n x c 豺1 一尬。( f c 。) 璐= c 0 + 1 = g + 1 = ( c ：+ 1 ，c l + 1 ，- ，c 豺1 ) 7 ( 碟一1 ) 至此，我们令 m c f ，c 2 ) = ( m l ( f ，c ) ，a 如( f 、c ) ， 一 ，a 如。( f c 。) ) t = g + 1 冬e v ( f c ) = ( ( f ，c 。) ，v 2 ( f ，c ) ，( f ) c 。) ) r 砖 ，厶 嚷 ，儿 2 0 0 4 年上海大学硕士学位论文 8 为函数f ( z ) 关于萨的相关均值与相关方差 姜佩磊的概念性算法可以求得多目标规划极小化模型( y m p ) 的全局有效解 或者全局弱有效解，且可以保证概念性算法的收敛但是其实现过程是利用了 m o n t e c a r l o 方法的随机取点，因而实现算法的收敛性没有解决 1 5 目的规划法 目的规划模型最早是1 9 6 1 年c h a l l n e s 和c o o p e r 建立的由于该模型在处理 多目标决策问题上能够提供一种决策者较为乐意接受的方式，去给出偏好信息并 将其偏好信息较和谐地融进模型中，因此它有着广泛地实际直用，构成了一类比 较有效地处理多目标问题的方法在率节中，我们主要介绍目的规划中的几个基 本方法 1 5 1 1 i 目的规划的般模型 目的规划的基本思想其实很简单，主要就是让决策者提出一个目的( 或称靶 子) p = ( ，2 ，m ) ，在可行解集x 中求一个与卢偏差最小的解，即求问题 m i n 如( f 扛) ，f ，a ) f g p ls t z x ( 1 5 1 7 ) ( 1 5 1 8 ) 其中f 和权系数 为央策者所给定，p 为参数，满足l 墨p s m 问题( g p ) 是目的规划的一种模型虽然p 可取区间 1 ，+ o 。1 中的任何值，但从 分析与计算的角度看，p 取1 , 2 或+ o 。最有意义，最初的目的规划就是p = 1 下面我 们仅对目的规划的原始形式加以介绍，关于这些方法的修正可见文献 1 1 ，1 2 ，1 0 】 1 , 5 2 加权平方和法 步骤l ( 定目的步) 让决策者提供目的声和权数k 20 ，曼a ：l ，在这个过程 中尽可能多地向决策者提供帮助 步骤2 ( 求解步) ，求解问题 m i n a k ( a ( 。) 一 ) 2 ( 1 5 1 9 ) k = l s t z x ( 1 5 ，2 0 ) 得最优解i ，输出i ， 2 0 0 4 年上海大学硕士学位论文 8 为区数f ( 叫关于c 。的相关均值与相关方差 姜佩磊的概念性算法可以求得多目标规划极小化模型( v m p ) 的全局有救解 或看全局弱有效解，且可以保证概念性算法的收敛但是其实现过程是利用了 m o n t e c a r l o 方法的随机取点，因而实现算法的收敛性没有解决 1 5目的规划法 目的规划模型最早是1 9 6 1 年c h a , n e s 和c o o p e r 建立的由于该模型在处理 多目标决策问题上能够提供一种决策者较为乐意接受的方式，击给出偏好信息并 将其偏好信息较和谐地融进模型中，因此它有着广泛地实际应用构成了一类t t 较有效地处理多目标问题的方法在本节中，我们主要介绍目的规划中的几个基 本方法 15 1 目的规划的一般模型 目的规划的基本思想其实很简单，主要就是让决策者提出一个目的( 或称靶 n 卢= ( ，厶) ，在可行解集x 中求一个与p 偏差最小的解，即求问题 i l l i n 如( f ( z ) ，f ，a ) ( g p ls t o x ( 1 5 1 7 ) ( 1 5 1 8 ) 其中f 和权系数a 为奂策者所给定，p 为参数，满足is p 。c 问题( g p ) 是目的规划的一种模型虽然p 可取区间【i ，+ o 。 中的任何值，但从 分析与计算的角度看，p 取1 , 2 或+ 最有意义，最初的目的规划就是p = 1 下面我 们仅对目的规划的原始形式加以介绍，关于这些方法的修正可见文献 i i ，1 2 ，i o i 1 5 2 加权平方和法 步骤1 淀目的步) 让决策者提供目的芦和权数h 0 ，h = l ，在这个过程 中尽可能多地向决策者提供帮助 步骤2 ( 求解步) 求解问题 得最优解i ，输出i 得最优解i ，输出i n f i n h ( ( 。) 8 t z x ( 1 5 1 9 f 1 5 ，2 0 2 0 0 4 年上海大学硕士学位论文9 当f ksr a i n ( z ) z x ) ( k = 1 、2 ， ，m ) 时，如果a 0 ，则i 为问题( v m p ) 的一个有效解否则i 有可能只是( v m p ) 的一个弱有效解， 1 5 3 ，加权极大模法 步骤1 ( 定目的步) 让决策者提供目的f 和权数a b 0 ，a = 1 在这个过程 中尽可能多地向失策者提供帮助 步骤2 ( 求解步) 求解问题 m i nt s t h ( 扛) 一f k ) ( k = 1 ，2 ，m ) z x t 0 ( 152 1 ) ( 1 5 2 2 ) ( 15 2 3 ) ( 152 4 ) 得最优解( i ，d ，输出i 当矗m i n f k ( z ) l x x ( = 1 ，2 ，m ) 时，i 为问题( v m p ) 的一个弱有效 解 1 5 4 简单目的规划法 这是用得最为广泛的一类目的规划方法它对应与p = l 的情形 设目的卢和权向量a 已经确定当p = 1 时 d p ( f ( x ) ，卢，a ) = 划a ( 。) 一 i ( 152 5 ) k = 1 在上式中，由于引进了绝对值符号，所以d ，( f ( 。) ，卢，a ) 不再是一个关于z 的可微 函数了，这对数值优化方法来讲不能不算是个较大的缺陷。为克服这一问题，令 d + = ：( i r a ( z ) 一氕i + ( 如) 一矗) )( 1 - 5 2 6 ) 和 = ；“a ) 一 一( a 扛) 一 ) )( 152 7 ) 2 0 0 4 年上海大学硕士学位论文 1 0 当，一1 时问题( g p ) 可改写为 ”1 m i i l a k ( d + d i ) = l s t a ( z ) 十一d ：= f k ( k = 1 ，2 ， ，7 n ) ( s g p ) d = o ( k = l ，2 ，m ) 赡0 ，o ( k = l ，2 ， ，m ) z x 先给出简单目的规划法的算法 步骤1 让决策者给出目的声和权向量a20 ，墨 b ：1 在这个过程中尽可能 = l 多地给决策者提供帮助 步骤2 求解问题( s o p ) ，得最优解( i ，扩，d - ) 输出z 1 6 交互式法 交互式多目标规划方法是近年来应用日趋广泛的一类方法这类方法的最大 特点就是：( 1 ) 无需决策者在一开始就提供他可能无法提供的有关问题的整体偏 好信息；( 2 ) 决策者只需在每一个具体的方案结果上给出局部偏好信息；( 3 ) 由 于求解过程是交互式的，决策者在求解过程中可以对决策问题有愈来愈多和愈深 刻的了解，因此最终求得的解也就比较符合他的偏好 在本节中我们将介绍几个有代表性的交互式多目标规划方法 1 6 1 逐步法( s t e m ) 逐步法( s t e pm e t h o d ) 是第一个用来处理多目标规划问题的交互式算法，见文 献 2 3 它处理的对象是线性问题，以理想点法为基础求解过程包括以下分析和 决策两个阶段：在分析阶段，分析者按理想点法对模型求解，把得到的解及对应 的目标值和问题的理想目标值提供给决策者考虑；在决策阶段，决策者在比较由 分析阶段求得的目标值和理想目标值的基础上，对已满意的目标给出使其目标值 作出让步的宽容量，以换取不满意目标得以改善，再把这些信息提供给分析者继 续求解如此反复，逐步以满意目标的宽容让步换取不满意目标的改善，最后求 得决策者满意的解具体地，逐步宽容约束法的步骤如下： 步骤1 求p 和 ，令x 1 = 盖t = 1 粥 约5 u 札 s 5 5 5 2 0 0 4 年上海大学硕士学位论文 步骤2 求解辅助问题 m i n ( l r ) s ta k ( 碟z 一代) s t ( k = 1 ，2 ，m ) z x 2 ( 16 3 3 ) ( 1 6 3 4 ) ( 163 5 ) 设得最优解( zz ，cz ) 7 步骤3 让决策者比较f ( 一) 和p ( 1 ) 若对所有的目标均表示满意，输出 i = 矿；( 2 ) 若对所有的目标均不满意，或i = t t 仍有一些目标不满意，则无满意 解，停止迭代；( 3 ) 若i 0 令 x 件1 = z x 2 l 。忙) 厶。0 1 ) + 即厶扣) 以( z 4 ) ，j s ，)( 1 6 3 6 ) 和a ，。= 0 ，2 + 1 一。转步骤2 1 6 2 g e o f f r i o n 法 这个方法由g e o f f r i o n ，d y e r 和f e i n b e r y 于1 9 7 2 年提出，见文献( 1 3 】它假定决 策者的效用函数“) 隐含存在，并且连续可微，但并不要求知道u ( ，) 的具体结构， 干是决策者希望获得的最满意的方案应该为问题 ( p ) m a x ( ( 。) ，2 ( 。) ，一，m ( z ) ) s 一2 x ( 1 6 3 7 ) ( 1 6 ，3 8 ) 的最优解其中，1 ( z ) ，2 ( 。) ，( 。) 为目标函数，x 为可行解集，这个方法还 假设： ( 1 ) 每个 ( z ) 可微；( 2 ) x 为紧致凸集，“( ) 为x 上的凹函数 g e o f f r i o n 法的基本思想就是将( p ) 看作一个一般的凸规划问题，著名的f r a n k - w o l f e 算法对问题( p ) 进行迭代由于事先并不知道效用函数u ( ) 的具体表达式， 在迭代过程中需要与决策者多次进行对话，让决策者决定在当前迭代点上的改善 方向以及移动步长具体步骤如下； 步骤1 选择初始可行解。o x ，令= o ， 步骤2 确定效用函数值增加方向，求解子方向问题 ( d 尸) m a x v 。u ( ( 一) ，2 扛) ， ，( z 。) ) t $ s 土z x ( 1 6 3 9 ) ( 1 。6 4 0 ) 2 0 0 4 年上海大学硕士学位论文 1 2 设得最优解矿、令。= y 。一。“为在z 。点使效用函数u ( ) 增加的方向，其中 v 。“( j 表示( ) 关于z 的梯度 步骤3 选择移动步长，让决策者确定毋：0 扩曼t 使得对v 1 0 ，1 】有 ? ( ，】( z 。+ “。) ，2 ( z 。+ 口2 2 ) 一， 1 ( z + n 。2 ) ) u ( f 1 + z ) ，f 2 ( x + a z 。) ， 。( z + a z 。) ) 但内 ：“的具体表达式并不知道，通常将区间【0 ，1 格式化，即取其中的几个值 例如“= 0 ，0 1 ，0 2 ，l ，让决策者判断选择一个最佳的值令x 。+ 1 = z 。+ o k z 步骤4 若| l z 川一1 i 0 为事先取定的终止允许误差 在一定的假设下，可证明g e o f f r i o n 法生成的点列 z 2 ) 收敛到问题( p ) 的最优 解，见文献1 4 1 1 6 3 代理价值权衡法( s w a 、法) ( 1 ) 非交互式s w t 法 代理价值权衡法( s u r r o g a t ew o l , t h l 2 r a d e o f fm e t h o d ) 是由h a i m e s 等人在1 9 7 4 年 提出的一种多目标规划方法它的基本步骤包括： ( t ) 生成一个有效解的代表集合； ( i i ) 对代表集中的每一个有效解得到相应的权衡信息； ( i i i ) 通过决策者和分析者对话得到反映决策者偏好信息的代理价值函数； ( i v ) 根据得到的偏好信息求决策者最满意的解 现具体叙述如下： 步骤1 生成有效解的代表集合建议使用t 一约束法通过适当地选择系列 参数向量e 的值求得有效解的代表集设选定目标 为参考目标，e 约束问题为 m i n ，1 ( o )( 1 6 4 1 ) ( p 1 ( e ) ) s t ( z ) ( = 2 ，3 ，m ) ( 1 6 4 2 ) z x ( 1 6 4 3 ) 步骤2 获取权衡信息，在求解问题( p 1 ( e ) ) 得到最优解。延) 的同时，常可得 到与不等式约束( 1 64 2 ) 对应的k u h n t u c k e r 乘子a 1 ( 。( e ) ) ( k = 2 ，3 ，m ) 步骤3 构造代理价值函数把有效解z ( e ) 和相应的偏权横比提供给决策者， 让他对是否愿意进行某种权衡以及对这种权衡的偏好程度之类的问题给出回答 根据回答的结果构造一个代理价值函数 2 0 0 4 年上海大学硕士学位论文1 3 步骤4 求最满意的方案如果有某一个有效解z ( e o ) 使得 则决策者找到最好的方案因此( 1 64 4 ) 是。( e o ) 为决策者最满意的解的条件若 在代表集合中有这样的。( t o ) ，则求解过程终止，输出s ( t o ) 否则用多元回归方法 去构造代理价值函数 然后求解方程组 u 1 = w l k ( f 2 ，3 ，m )( k = 2 ，3 ，- ，m )( 164 5 ) 。1 ( ，2 ，3 ，) = 0( k = 2 ，3 ，m )( 1 6 4 6 设得解为( 庀，尼，儡) 7 令f o = 髭( k = 2 ，3 ，m ) ，e o = ( e 0 2 ，0 3 ，g o 。) 7 最后 求解问题( p l ( e o ) ) 得最满意得方案。( e o ) 关于参考目标和参数e 得选取原则，见文献【1 4 ，1 5 1 ( 2 ) 交互式s w t 法 非交互式s w t 法需要在第一步生成有效解的一个代表集合当代表集的元 素个数很少时无法提供足够多的信息来构造代理价值函数；当个数很大时，需要 很大的计算量，而且最满意的解z ( e o ) 也不一定落在这个代表集中，此外求解方程 组( 1 64 6 ) 的计算量一般也相当可观为克服这些不足h a i m e s 等人将s w t 法 改进成交互式方法，这就是著名的i s w t 法 i s w t 法只需选取一个初始参向量e 1 = ( e j ，t j ， ，t k ) 7 ，然后在迭代过程中依 每一步迭代时获得的代理价值u l k ( z ( 一) ) 来设置新的e l + l ，以保证“( ( 一) ，2 ( 一) ， 岛( 扩) ) o ( 其中p 是测度) 令 h 世：= f z 。x ，l ( 。) c ： 皿f 缸f 。x ，f 2 ( x ) 曼c 1 4 2 0 0 4 年上海大学硕士学位论文 也二= zz x ，k ( z ) c 。k ) 则定义 峨一h i ： n h 。 n h 。；n 胃。= 步1 ： c 2 = ( c ，c l ， 砖。) 7 ，若r a i n c 。k ，则再对 ( z ) 在h c * 上求局部极 小值，否则转步2 步2 ：构造基准向量0 “，0 = ( 西k 西， ，靠。) t ，函数，c 川( z ) ，c ，。：( 。) ，l ，。m ( 。) 计算相关均值c “1 = m ( f ，c 2 ) 计算相关方差矿f = 矿( fc 。) ，水平接收集月西+ - nx ? r ( x ) sc “1 ) n x 步3 ：如果矿( f c ) ，则：= k + 1 ，那么转步1 ，否则转步4 步4 ：令c 4 = c “，h + = i t c ，停止 下面首先介绍步2 中的基准向量e = ( 丘2 ，西，岛) 7 的构造：对任意的 t = l ，2 ，3 ，m ， 磊。= a ic ；+ b zm i i l n 。+ b 。= 1 钒o ，b ：o 接下来介绍步2 中函数，c ；，。( z ) ，l 5 。( z ) ，。，c 。( z ) 的构造及( v m p ) 的目标 函数f ( x ) 关于c 。相关均值肪( f ，c ) 和相关方差矿( f 1c 2 ) 的定义 ( 1 ) 在第k 次迭代中，令基准量 构造函数 。，满足 计算 8 l + 6 】= 1a