（运筹学与控制论专业论文）多目标规划的一种积分型算法.pdf

2 0 0 4 年上海大学硕士学位论文 摘要 通常一个求多目标规划问题可以表述为 ( y m p ) v 。r a i x n ，( 。) 其中f ( z ) = ( ，( z ) ，丘( z ) ，厶( z ) ) r 是区域x 上的m 维向量函数f i ( x ) ： 兄n _ r ( i = l ，2 ，r n ) 为连续函数，x 为n 维欧氏空间中的非空闭集 求多目标规划问题的方法在科学技术，工程设计，经济管理等方面有着很 广泛的应用 本文的主要工作是对姜佩磊提出的多目标规划的积分总极值算法散 了修正姜佩磊的算法可以求得多目标规划极小化模型( v m p ) 的全局有 效解或者全局弱有效解，且可以保证慨念性算法的收敛但是其实现过 程是利用了m o n t e - c a r l o 方法的随机取点，因而实现算法的收敛性没有解 决本文将修正的积分水平集方法的思想，用于求解多目标规划极小化模 型( v m p ) 修正的算法在每一次迭代中，构造了新函数，使得新函数的有 效解与弱有效解亦为原函数的有效解与弱有效解，并证明了概念性算法 的收敛而在算法的实现时，我们用数论中确定性的一致分布的数值积分 来逼近水平值和水平集，且不改变搜索区间避免了姜佩磊的实现算法中 用m o n t e c a r l o 方法逼近水平集，并收缩迭代区间而造成实现算法不收敛 的弱点，且我们给出了修正的多目标规翊的积分总板啬实琨算法的收敛 性证明 在第一章中，我们介绍了几种求多目标规划的算法这些算法中， 有评价函数法，目的规划法，分层序列法，满意水平法，交互式法，积分 总极值法在第二章中，首先我们提出了一个修正的多目标规划积分型 算法，然后给出相关均值和相关方差的最优性条件，最后证明了概念辩 法的收敛在第三章中，我们给出了实现算法，并证明了实现算法的收 敛性同时给出了一些数值例子，说明修正的多目标规划积分型算法是 有效的在第四章中，我们总结了本文所做的工作以及将来的研究方向 2 0 0 4 年上海大学硕士学位论文 i i 关键词：多目标规划，积分型算法，一致分布佳点集列，全局绝对最优 解，全局有效解，全局弱有效解 2 0 0 4 年上海大学硕士学位论文i i i a b s t r a c t t 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 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 ) 肛。m i x n ，( 。) f ( z ) = ( t l ( z ) ，2 ( z ) ，疗n ( z ) ) 7 a r ev e c t o rf u n c t i o n so fmd i m e n s i o no v e rx 五( ) ：r “- r i = 1 ，2 ，一，f n ) i sc o n t i o m i o n sf l m c t i o na n dx i 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 en n d t i o b j e c t i v ep r o g r a n n n i n g i nt h ef i e mo 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 no fe n g i n e e r i n g ，e c o n o t n i c m a n a g e n e n ta n d s oo n t h em a i np u r p o s eo ft h i st h e s i si st om o d i f y j i a n 9 1 si n t e g r a la l g o r i t h mf o r s 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 g j i a u g sa l g o r i t h mc a no b t a i nt h en m 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 s ( v m p ) g l o b a le f f e c t i v es o h t t i o n0 1 g l o b a lw e a k e f f e c t i v es o l u t i o n ，a t t dp r o v et 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 m b u t j i a n 9 1 sm o n t e - c a r l oa l g o r i t h n lm a k et h ew e a kp o i no ft h ed i v e r g e n c eo ft h ei m p l e m e n t e da l g o r i t h m i n t h i st h e s i s ，w ep r o p o s eam o d i f i e d i n t e g r a l - l e v e ls e t a l g o r i t h mf o rs o l v i n gt 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 ) i ne a c hi t e r a t i v e p r o c e s s w cc o n s t r u c tn e wf l m c t i o n s w h o s ee f f e c t i v es o l u t i o na n dw e a ke f r e c t i v e s o l u t i o na l s oa r eo r i g i n a lf l m c t i o n s se f f e c t i v es o l u t i o na t t dw e a ke f f e c t i v es o h l t i o n a n dw ep r o v et 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 m t h ea l g o r i t h mi s i m p l e m e n t e db ya p p l y i n gt 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 n m r i c a li n t e g r a l i nn u m b e rt h e o r yt oa p p o r a d it h el e v e lv a h ma i l dt h el e v e ls e t b e c a u s eo f n o tc h a n g i n gt h es e a r c hd o m a i n w e c a l la v o i du s i n gj b m g sm o n t e - c a r l oi m p l e m e n t e da l g o r i t i m tt oa p p r o a c ht h el e v e ls e ta n d ( x ) l d , r a c ti t e r a t i v os e t w h i c hm a k e t h ew e a kp o i no ft h ed i v e r g e n c eo ft h ei m l ) l e m e n t e da l g o r i t h m f u r t h e r m o r e w c p r o v et h ec o n v e l g e n r eo ft h em o d i f i e x li n t e g r a l - l e v e ls e ta l g o r i t h m i nc h a p t e r1 , ai ) i i c fi n t r o d u c t i o ni sg i w ! nt ot h en l a i l lc l a s s e so fu n f l t i o b i e c t i v ep r o g r a m m i n gp r o b l e m ，s u c ha sa p p r a i s a b h , f u n c t k mm e t h o d j o b j e ：t i v ep r o g r a m m i n gm e t h o d 1 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 g m e t h o d ，i n t e g r a lm e t h o d i nc h a p t e r2 ，f i r s t l yw ep t o p o s eai n ( ) d i f l e d i u t e g l a i 2 0 0 4 年上海大学硕士学位论文i v 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 gs e c o n d l y , w eg i v e t h eo p t i m a l i t yc o n d i t i o n a tl a s t ，w e p r o v et h ee o l l v e r g e u c co ft h ea l g o r i t h m i n c h a p t e r3 ，w eg i v et h ei m p l e m e n t e da l g o r i t h m a n dp r o v et h ec o n v e r g e n c eo ft h e i m p l e l n e n t e da l g o r i t h m f u r t h e r m o r e ，s e v e r a ln u m e r i c a le x a m p l e sa r ep r e s e n t e d w h i c hs h o wt h a to u t a l g o r i t h ma r ee f f e c t i v e i nc h a p t e r4 ，w es u m m a r i z et h e t h e s i sa n ds u g g e s ts o m ef u t u r er e s e a r c hd i r e c t i o n s k e yw o r d s ：m u l t i o b j e c t i v eo p t i m i z a t i o n ，i n t e g l a la l g o r i t h m 、u n i f o r md i s t r i b u t i o no fg o o dl a t t i c ep o i n ts e q u e n c e g l o b a la b s o l u t es o l u t i o n ，g l o b a le f f e c t i v e s o l u t i o n ，g l o b a lw e a ke f f e c t i v es o l u t i o n 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 签硒巍舢”掣f 夕 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留 论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容。 ( 保密的论文在解密后应遵守此规定) 签名抚胖导师签名：讯期：岛。舣哆 第一章前言 1 1 引言和定义 研究多目标最优化问题的学科称为多目标最优化或多目标规划，它是数学规 划的一个重要分支用数学的语言来说，多目标最优化的研究对象是：多于一个 的数值目标函数在给定区域上的最优化问题由于多个数值目标可用一个向量目 标表示，因此多目标最优化问题有时也叫做向量极值问题早在1 7 7 2 年，f r a n k l i n 就提出了多目标问题矛盾如何协调的问题1 8 3 8 年，c o u r n o t 从经济学角度提出 了多目标问题的模型1 8 9 6 年，p a r e t o 首次从数学角度提出了多目标最优决策 问题1 9 4 4 年，v o nn e u m a n n 从对策论角度奠定了经济行为理论的基础 1 9 5 1 年，k o o p m a n s 在生产和分配问题提出了有效向量的概念，与此同时，k u h n 等 人给出了向量极值问题有效解的必要条件1 9 5 3 年，a r r o w 等人又提出了有效 点的概念至此，多目标规划逐渐受到人们的关注从5 0 年代末到6 0 年代末， c h a r n e s ，k a r l i n ，z e d e h ，k l i n g e r p o l a k ，k e e n e y 和g e o f f o r i o n 等人先后作出了比较有影响 的工作自1 9 7 2 年y u 提出了支配结构等重要概念后，多目标规划理论的研究更 是引入注目从7 0 年代中期起，每年都有若干个以多目标决策或多目标规划为题 的国际性学术会议召开越来越多的人在致力于把多目标决策作为工具去解决水 资源管理，能源规划，光学系统设计，化学配方，投资决策，行政管理等复杂问 题，并取得了一定的成果见文献 8 ，9 一个多目标规划问题一般如下定义 其中f ( x ) = ( ，l ( z ) ，正( z t ，t 。( z ) ) r 是区域xcr “上的m 维向量函数 定义1 1 1 设xcr ”是模型( v m p ) 的约束集，f ( 州r ”7 是( v m p ) 的向 量目标函数若茁x ，并且不存在f x 使得f ( x ) f ( i ) 且f ( z ) f ( i ) 则称i 是多目标规划极小化模型吖p ) 的全局有效解；若不存在z a 使得 f ( x ) f ( e 】，则称i 是多目标规划极小化模型( 1 7 m p ) 的全局弱有效解；若r + x 并且f ( t + ) f ( z ) v x x 则称r + 是多目标规划极一i 、化模型( v m p ) 的全局绝 对最优解记全局有效解，全局弱有效解，全局绝对最优解的集合分别为e 日，易矿 2 0 0 4 年上海大学硕士学位论文 2 下面几节，我们将对多目标规划的一些算法做简要的介绍，具体可参见文献 【2 0 ，2 2 ，2 6 ，2 8 2 9 卜 1 2 评价函数法 评价函数的基本思想是，根据问题的特点和决策者的意图，构造一个把m 个分量目标函数转化为一个数值目标函数一评价函数然后对评价函数进行最 优化，这样就把求解多目标最优化问题转化为求单目标最优化问题了见文献 【l o ，1 1 ，1 5 1 2 1 线性加权和法 线性加权和法是最基本的评价函数法其基本思想是，根据各个目标在问题 中的重要程度，分别赋予它们一个数，并把这个数作为该目标的系数然后把这 些带系数的目标函数相加的和函数作为评价函数 步骤1 按各目标，。( z ) ( i = 1 , 2 ，m ) 在问题中的重要程度给出一组权系数： u l ，u m ，要求w i 0 ，且e w i = 1 步骤2 求线性加权和函数 恕p 删 1 驯 的最优解，即为问题( v m p ) 的有效解或弱有效解 1 2 2 极大极小法 人们在处理复杂的困难问题时，往往采取这洋一种策略思想，即在最坏的情 况下争取最好的结果在求解多目标最优化问题时，也可采用类似策略思想，即 考虑在对各分量曰标最不利的情况下找出最有利的解 步骤1 用各目标函数 ( z ) ( i = l ，2 ，m ) 的最大值作为评价函数的函数值 来构造评价函数，即令 为评价函数，其中f ( 叫= ( ，i ( ：r ) ，f 2 ( x ) ，一，n ( z ) ) 7 122 1 2 0 0 4 年上海大学硕士学位论文 3 步骤2 通过上述评价函数u ( f ) 把求解( v m p ) 问题转化为求解单目标最优 化问题 。r a i x n ( f ( 。) ) - 。m i x n m a 。x 。 f i ( 。) 可以证明，得出的解为( v m p ) 问题的有效解或弱有效解 1 3 目的规划法 ( 1 2 3 ) 目的规划模型最早是1 9 6 1 年c h a r n e s 和c o o p e r 建立的由于该模型在处理 多目标决策问题上能够提供一种决策者较为乐意接受的方式，去给出偏好信息并 将其偏好信息较和谐地融进模型中，因此它有着广泛地实际应用，构成了一类比 较有效地处理多目标问题的方法在本节中，我们主要介绍目的规划中的几个基 本方法 1 3 1 目的规划的一般模型 目的规划的基本思想其实很简单，主要就是让决策者提出一个目的( 或称靶 子) 卢= ( ，2 ，厶) ，在可行解集x 中求一个与f 偏差最小的解，即求问题 ( g p ) m i n 如( f 扛) ，f a ) s t ：r x f 1 34 ) ( 1 35 ) 其中f 和权系数a 为决策者所给定，p 为参数，满足l ps 。 问题( g p ) 是目的规划的一种模型虽然p 可取区间 1 ，+ 。 中的任何值，但从 分析与计算的角度看，p 取1 , 2 或+ 。g 最有意义，最初的目的规划就是p = l 下面 我们仅对目的规划的原始形式加以介绍，关于这些方法的修正可见文献 8 1 3 ，1 5 】 1 3 2 加权平方和法 n z 步骤1 ( 定目的步) 让决策者提供目的f 和权数a i 0 a k = 1 在这个过程 中尽可能多地向决策者提供帮助、 步骤2 ( 求解步) 求解问题 ( 1 3 6 】 ( 1 37 ) ， “ 一 0 ，则i 为问题( v m p ) 的一个有效解否则牙有可能只是( v m p ) 的一个弱有效解 1 3 3 加权极大模法 步骤1 ( 定目的步) 让决策者提供目的卢和权数h 0 ，k = 1 在这个过程 中尽可能多地向决策者提供帮助 步骤2 ( 求解步) 求解问题 ( 13 8 ) ( 1 , 39 ) f 1 3 1 0 1 ( 13 ，1 1 ) 得最优解( 圣，订，输出雪 当五m i n f t ( x ) l x x ( k = 1 ，2 ，一m ) 时，牙为问题( v m p ) 的一个弱有效 解 1 3 4 简单目的规划法 这是用得最为广泛的一类目的规划方法它对应与p = 1 的情形 设目的f 和权向量a 已经确定当p = 1 时 幽( f ( z ) ，卢， ) = a | a ( z ) 一 1 ( 1 3 1 2 ) k = l 在上式中，由于引进了绝对值符号，所以d 。( f 户a 】不再是一个关于：r 的可微 函数了这对数值优化方法来讲不能不算是个较大的缺陷为克服这一问题，令 ：；( | a ( z ) 一 i + ( f d z ) 一a ) ) ( 1 矗1 3 ) 和 靠：；( i ( r ) 一 + ( ( r ) 一五) 1 ( t 31 4 ) 竹2 | i 一 t a z t m t m 2 0 0 4 年上海大学硕士学位论文5 当p = 1 时问题( g p ) 可改写为 m m i n k ( d + 町) k = l s t ( z ) + d i d j = a ( = 1 2 ，m ) ( s g p ) 鲇d = o ( k = 1 ，2 ，m ) d 声0 o ( k = l ，2 ，m ) tfx ( 13 1 5 ) 先给出简单目的规划法的算法 步骤1 让决策者给出目的f 和权向量 20 ，曼h ：1 在这个过程中尽可能 k = l 多地给决策者提供帮助 步骤2 求解问题( s g p ) ，得最优解( 2 ，扩d - ) 输出哥 1 4 分层序列法 本节介绍分层序列法 1 4 1 完全分层法 步骤1 根据各目标的重要程度不同，将r n 个目标函数排序假定，- 最重 要，如次之，m 最不重要 步骤2 逐次求解下列，n 个单目标问题( 最) 的最优解z 。其中 ( p 1 ) m i n ( z ) s x ( p k ) m i n ， ( t ) 6 - f ( z ) = ( f ) ( i = 1 2 ，一，厶一1 ) z x ( = 2 3 m ) 2 0 1 2 1 1 2 2 1 2 3 ) 2 4 1 1 4 2 分层评价法 和完全分层法不同，决策者认为m 个目标可分为一个优先层次，s 一般小于 s m 记第i 个层次含目标的下标集为厶，i = 1 ，2 s 于是ui i = 1 2 ，m 目 2 = l 2 0 0 4 年上海大学硕士学位论文 6 标a ，k i 。属于最优先的；目标a ，k 1 2 次之，当s = m 时就成了完全分层 法，这类分层模型的特点是，通常每一优先层次的目标函数是多个的因此，每 一层次对应的不是一个单目标优化问题，而是一个目标个数相对来讲少一些的多 目标规划问题我们假定决策者希望每个目标a 都尽可能地小( 但此时优先层次 不同) ，可行解集为x 分层评价法地步骤可归纳为： 步骤1 令x 1 = x k = 1 步骤2 选第k 优先屡次地评价函数u k ：r _ r 1 ，其中l 厶l 表示 中所含 元素的个数 步骤3 利用评价函数“女把第k 优先层次的多目标规划问题转为下列问题： n l a x u k ( r ( z ) ) s t2 7e x 8 ( 14 2 5 1 ( 1 4 2 6 ) 得最优解和最优目标值“：其中r ( z ) = ( 厄( z ) 几( 。) ，啊 【( z ) ) 1 ， = l ，如，k l l 。m 步骤4 检验迭代次数，若k = s ，则输出矿：否则进行下一步 步骤5 令x + 1 = z x 2 i “k ( 1 4 ( z ) ) 执+ 1 - k ，转步骤2 可以证明当每个( ) 是y 的严格单调减函数时，x 3 是问题( v m p ) 的一个 有效解，当每个( 扪是y 的单调减函数时，z 5 是问题( v m p ) 的一个弱有效解 1 5满意水平法 本节介绍满意水平法 1 5 1 简单满意水平法 由于决策环境的影响，方案实施中的困难或者计算费用方面的考虑，决策者 往往愿意提出一组目标水平f = ( ，五矗，。) 丁如果方案满足这组目标水平， 则采纳它假定决策者希望每个目标 都尽可能地小，可行解集为x 简单满意 水乎法的计算步骤为： 步骤1 让决策者给定目标水平f 2 0 0 4 年上海大学硕士学位论文 7 步骤2 求解 r a i n f k ( x ) k = l f s p ) s t x a 江) ( 女= 1 2 ，) ( 1 52 7 ) ( 1 5 2 8 ) ( 1 5 2 9 ) 步骤3 若( s p ) 无可行解，则进入下一步；若求得( s p ) 的最优解，则输出 i ，否则式( 1 5 2 7 ) 中的目标函数无下界，取( s p ) 中的任一可行解输出 步骤4 让决策者重新给出目标水平户，回到步骤2 1 5 2 满意水平平衡法 满意水平平衡法( s a t i s f y i n gt r a d e o f fm e t h o d ) 由n a k a y a m a 等人提出，见文献 f 2 1 它的特点是将满意水平方法与理想点法有机地结合起来这个方法还是一个 交互式方法算法可叙述如下假定决策者希望每个目标 都尽可能小，可行解 集为x 步骤l ( 设置理想点) 取理想点f + = ( ，；，e 扁) r 满足厅 r a i n f ( z ) ：r x ) ( i = 1 ，2 ，- - ，m ) 步骤2 ( 设置目标水平) 请决策者给出目标水平f 。= ( 芹，劈，豫) 7 ，令k = 1 步骤3 ( 计算权数) 计算 ；= 百二i z = 1 ，2 ，m ) 步骤4 ( 求r a i n - m a x 问题) 求 t f i n m a x 。瑚，2 ( ) 一彤 3 t j x f l5 3 0 1 ( 1 5 3 1 ) 得最优解一 步骤5 ( 作权衡) 给出目标值f ( 一) = ( 厂1 ( 一) ，2 ( i 一。j 、c r ) ) 丁让决策者将 目标分为三类： ( 1 ) 需要改善，对应的下标集为， ； ( 2 ) 可以放松，对应的下标集为，： ( 3 ) 接受，对应的下标集为，j 如果辟= 曲，则结束迭代，输出一否则，令瘁= ( 一：。) ，i 哦；而让决策者给 出新目标水平芹，i 砖u 臻 2 0 0 4 年上海大学硕士学位论文8 步骤6 ( 可行性检验) 如果系统 慨意枷乩。，。， 有解，则令嚣“= 骨( i = l ：2 ，m ) ，然后转到步骤3 否则让决策者重新给出 口，i 雎u 昭，重新进行可行性检验 1 6 交互式法 交互式多目标规划方法是近年来应用日趋广泛的一类方法这类方法的最大 特点就是：( 1 ) 无需决策者在一开始就提供他可能无法提供的有关问题的整体偏 好信息；( 2 ) 决策者只需在每一个具体的方案结果上给出局部偏好信息；( 3 ) 由 于求解过程是交互式的，决策者在求解过程中可以对决策问题有愈来愈多和愈深 刻的了解，因此最终求得的解也就比较符合他的偏好 在本节中我们将介绍几个有代表性的交互式多目标规划方法 1 6 1 逐步法( s t e m ) 逐步法( s t e pm e t h o d ) 是第一个用来处理多目标规划问题的交互式算法，见文 献 3 】它处理的对象是线性问题，以理想点法为基础求解过程包括以下分析和 决策两个阶段：在分析阶段，分析者按理想点法对模型求解，把得到的解及对应 的目标值和问题的理想目标值提供给决策者考虑；在决策阶段，决策者在比较由 分析阶段求得的目标值和理想目标值的基础上，对已满意的目标给出使其目标值 作出让步的宽容量，以换取不满意目标得以改善，再把这些信息提供给分析者继 续求解如此反复，逐步以满意目标的宽容让步换取不满意目标的改善，最后求 得决策者满意的解具体地，逐步宽容约束法的步骤如下： 步骤1 求f + 和a 令x 1 = x i = 1 步骤2 求解辅助问题 m l i lf ( 只) s 童a ( ( _ _ ： z 一嚣) s ( = 1 2 、- ，m ) 3 x 2 设得最优解( x 2 ，t 。) ， ( 163 2 ) ( 1 6 3 3 ) ( 1 ，6 3 4 ) 2 0 0 4 年上海大学硕士学位论文 9 步骤3 让决策者比较f ( x 2 ) 和p ( 1 ) 若对所有的目标均表示满意，输出 i = x i ；( 2 ) 若对所有的目标均不满意，或i = m 仍有一些目标不满意，则无满意 解，停止迭代；( 3 ) 若i 0 令 x 件1 = z x 。i 。( z ) ( ) + 即方( z ) ，7 ( z4 ) j 8 i ( 1 6 3 5 ) 和九= 0 ，i + 1 _ z 转步骤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 年提出，见文献外它假定决策 者的效用函数“( ) 隐含存在，并且连续可微，坦并不要求知道“( ) 的具体结构， 于是决策者希望获得的最满意的方案应该为问题 ( p ) m a x “( ( z ) 、 ( z ) ，r - ，n ( zj ) s ，t x ( 1 6 3 6 ) ( 1 6 3 7 j 的最优解其中，l ( 。) ，2 ( z ) ，m ( z ) 为目标函数，x 为可行解集，这个方法还 假设：( 1 ) 每个 ( 。) 可微；( 2 ) x 为紧致凸集，u ( ) 为x 上的凹函数 g e o f f r i o n 法的基本思想就是将( p ) 看作一个一般的凸规划问题，著名的f r a n k w j l f e 算法对问题( p ) 进行迭代由于事先并不知道效用函数“( - ) 的具体表达式， 在迭代过程中需要与决策者多次进行对话，让决策者决定在当前迭代点上的改善 方向以及移动步长具体步骤如下： 步骤1 选择初始可行解。o x ，令k = 0 步骤2 确定效用函数值增加方向，求解予方向问题 ( d p ) n i a x v ，( ，l ( m ) 。，2 ( z 。) ，( r ) ) ，i ，_ $ t 1 - x ( 1 6 3 8 ) f l63 9 ) 设得最优解y 。令少= y 。一z 。z 为在z “点使效用函数“( ) 增加的方向，其中 v 捌( ，) 表示“( - ) 关于。r 的梯度 步骤3 选择移动步长，让决策者确定一：0 r sl 使得对v n 【( l 】有 钍( ，l ( z 。+ n k z k ) ，2 ( z + f p 2 “) ，( r + n 。z 。) ) ( ，1 ( f 工。+ ( t z k ) ，f 2 ( z 。+ n 。“) - - ，。( x k + o ：z k ) 2 0 0 4 年上海大学硕士学位论文 1 0 但由于“( ) 的具体表达式并不知道，通常将区间f 0 1 】格式化，即取其中的几个值 例如o l = 0 ，o 1 ，0 2 ，1 ，让决策者判断选择一个最佳的值n 。令+ 1 = 一+ 2 步骤4 若忙+ l 一一 0 为事先取定的终止允许误差， 在一定的假设下，可证明g e o f f r i o n 法生成的点列p 收敛到问题( p ) 的最优 解，见文献【5 1 1 6 3 代理价值权衡法( s w t 法) ( 1 ) 非交互式s w t 法 代理价值权衡法( s u xr o g a t ev r t h t r a d e o f fm e t h o d ) 是由h a i m e s 等人在1 9 7 4 年 提出的一种多目标规划方法它的基本步骤包括： ( i ) 生成一个有效锯的代表集合； ( i i ) 对代表集中的每一个有效解得到相应的权衡信息； ( i i i ) 通过决策者和分析者对话得到反映决策者偏好信息的代理价值函数； ( i v ) 根据得到的偏好信息求决策者最满意的解 现具体叙述如下： 步骤1 生成有效解的代表集合建议使用e 一约束法通过适当地选择一系列 参数向量e 的值求得有效解的代表集设选定目标，i 为参考目标，e 约束问题为 ( p i ( e ) ) s t 步骤2 获取权衡信息，在求解问题( p t ( e ) ) 得到最优解x ( e ) 的同时， 到与不等式约束( 1 6 4 1 ) 对应的k u h n t u c k e r 乘子a i k ( ( e ) ) ( k = 2 ，3 ，r n ) ( 16 。4 0 ) ( 1 6 4 1 ) ( 1 6 4 2 ) 常可得 步骤3 构造代理价值函数把有效解。( c ) 和相应的偏权横比提供给决策者， 让他对是否愿意进行某种权衡以及对这种权衡的偏好程度之类的问题给出回答 根据回答的结果构造一个代理价值函数 步骤4 求最满意的方案如果有某一个有效解r ( e o ) 使得 u i ( ：l ：( f - 0 ) ) = 0( = 2 3 一，) ( t 6 4 ：1 】 则决策者找到最好的方案因此( 1 6 i 4 3 ) 是。( e o ) 为决策者最满意的解的条件若 在代表集合中有这样的r ( e o ) 则求解过程终止，输出。( e o ) 否则用多元回归方法 r32 i | 南 0 作 m l ( f , 萨) 2 丽者两厶。n x ，i ( 引d f “辞) t q ( f , c 卜硒赫厶“n x ( ，l ( 砷刈 萨) ) 2 舡 令 则 作 令 则 作 砖+ 1 = m l ( f 1 c ) ，讲= ( c ：“c 5 ，c 袅) 7 ( c 。) h c n x = 川f ( z ) g f n x = 川f l ( z ) s c ， n tn x 尬( 只萨) 2 南t 胁脚( ( 】 令 则定义 = zf 以垆 z l 。x 、，t ( z ) sc ： z x ，2 ( z - ) c ! ) 月：j ，= zi 。x ，。( z ) ( 1 k 。 = 一致 n 以；n 皿n 也二 2 0 0 4 年上海大学硕士学位论文 1 6 步骤2 构造函数l , d z ) ，1 4 ( z ) ，厶i ( z ) ，并计算相关均值c “，= m f f , c 。) 、 相关方差矿f ：= 矿( f c “) 水平接收集三，c n x = zif ( r ) c 1 n x 步骤3 若y f f ，则 ：= + 1 转步2 ，否则转步4 步骤4 令e + ：= c 。+ 1 ；t t c n x = 一n x ；终止 在算法2 2 中函数墙( z ) ，如( z ) ，c k ( z ) 的构造及问题( v m p ) 的相关均值和 相关方差的定义如下所述： 在第k 次迭代中，构造函数如( z ) ，满足 驯= ，：! 芝如 计算相关均值 m t ( f , c 诤丽1 工如( 喇，- 计算相关方差 u ( f e ) = 两两1上( 厶 ( z ) 一m i ( f , c 。) ) 2 d f z 令 c ：“= m t ( 只c 2 ) ，g = ( c p l ，连，- ，c 袅) r 则 h e f , n x = z l f o ) c f n x = z1 ( 叫s 计+ n - n x 显然，以下命题成立 会题2 2 1c ；“sc ，睹c 证明： c ：+ l = 丽1 上如( 圳p 。志咖( x 如) + 正。椭t 曼“1 1 _ 2 _ jt c ：，t ( x h c , n ) + c f ，一( h ( ，一) 】 = c ； 因为c f = ( + 1 ，c l ，一，4 0 ) 7 ，g 2 = ( c ，c 5 ，c ：。) 丁而c ：c f 易得g s c 。 2 0 0 4 年上海大学硕士学位论文 1 7 构造函数如( z ) ，满足 计算相关均值 计算相关方差 令 ，、f 述z x h c 7 c ；。2 l ，2 ( z ) z h g f 如( 只e ) = 志f 硝川缸 嘲f l c _ ) = 志上( 州圹m 2 ( p , e 嘲2 咖 连州= m 2 ( f , c ) 谚= ( 茸”，c 2 k + i ，砖，c ) 丁 则 日罐n x = zi ，( z ) 谚 n 舅= zi ( 。) sc l + 1 ) n h d n x 同理，以下命题成立 命题2 2 2 毯“s 砖，谚s c f ， 证明参考命题2 , 2 1 ， 构造函数如( z ) ，满足 纠加 。 蚝x 懈； 5 【 ( z ) z 令 则 c 。k + 一l l = m 。_ l ( f c ) 磷。l = ( c ：”，避“c 。k + 一1 1 砖。】t 鳓二一。n x = 川t z ( ，) s 锩一 n x = f z 愉一t ( 一。曼前= j n 抒。江n x 依此类推，以下命题成立 命题2 2 3c 材，sc 4 磷。s 磷一2 证明参考命题2 2 1 2 0 0 4 年上海大学硕士学位论文 1 8 构造函数厶：( 。) ，满足 ，c ic 。，2 妻。，。x c 。h x 。二h 一，c ：一l 计算相关均值 ( f 萨) = 志x f c ；( 喇p 计算相关方差 萨) = 可可1 厶( 如( 蜘一尬“f e - ) ) 2 舡 令 c 等1 = 。( f ，) ，g 兰= ( 冶十1 = c 2 + 1 = ( c “c ! “，c 豺1 ) r 命蜀2 2 4 毒1s 嚎，璐s 镶。 证明参考命题2 2 1 定义2 2 1 令 m ( f , c ) = ( m l ( f 1 c ) ，m 2 ( f , c ) r - ，( f c ) ) 丁= c “+ 1 v ( f , c ) = ( i ，l ( f 1 c 。) ，( f c ) ，- ，( 只c ) ) t 为函数f ( z ) 关于c 的相关均值与相关方差 定理2 2 1 算法产生得向量序列 e 单调下降，水平集序列h c - + tch c k ( k = l ，2 ，t j 证明：因为c + 1 = ( c 。1 ，c 5 “，c 材1 ) 2 ，g = ( 讲，畦c ) 下由命题2 2 j ，命题 o ，2 2 ，命题2 2j ，命题2 2 4 可得，c ：+ 1 毒( i = 1 ，2 ，m ) ，故c + sc ，即向量 p c ， 1 萨) 单调下降因为h c = zj ，( z ) 5c 。+ 1 ) ，h f 。= fjf ( ) c “ 而 向量序列 g 单调下降，易得水平集序列h ( 1 一( 皿、t 2 3 最优性条件 本节我们给出相关均值的最优性条件( 定理2 3 3 定理2 3 4 定理2 3 5 ) 和相 关方差的最优性条件( 定理2 3 6 、定理2 3 7 ，定理2 38 ) 2 0 0 4 年上海大学硕士学位论文 1 9 定理2 3 1 若f z ) 满足假设且1 ?