（应用数学专业论文）多目标规划的数值建模交互优化方式研究.pdf

摘要 文章简略地介绍了多目标规划闯题的发展过 程、基本理论、求解方法以及基于最小二乘原理的 数据拟合法，详细分析并“比较了目前关于多目标规 划求解的四种方法及其优缺点，特别对今后的发展 方向：交互式多目标决策方法，进行了较深入的研 究。 本文以多目标规划理论和数据拟合法为基础， 把两者有机结合起来，提出了一种求解多目标规划 的新方法；多目标规划的数值建模交互优化，并给 出了详细的算法过程。该方法的特点是：弓l 入权系 数把多目标规划问题转化为单目标规划问题，通过 对单目标规划问题的求解得到计算数据，再对数据 建模，而且考虑到决策者的偏好结构，简化了优化 准则，使得整个算法既简单又实用。同时也适用于 非线性规划，实现了决策者与系统的信息交流以及 决策者对规划过程的参与，具有一定的灵活性。最 后给出了数值实例，验证其有效性。 关键词 多目标规划建模拟合交互优化 t h es t u d yo fn u m e r i c a i m o d e l i n ga n di n t e r a c t i v e 0 p t i u mm e t h o df o r s o l v i n gm u i t i p i e0 b j e c t i v e p r o gr 8 m m i n g a b s t r a c ti nt h i s p a p e r ，d e v e l o p i n gp r o c e s s o f m u l t i p l eo b j e c t i n gp r o g r a m m i n g ，d a t af i t t i n gb a s e do n i c a s t s q u a r et h e o r y a n df o u r m e t h o d sf o r s o l v i n g p r c s e n tm u l t i p l eo b j e c t i r ep r o g r a m m i n ga r e b r i e f l y i n t r o d u c e d e s p e c i a l l y ，t h e f u t u r e d c v o l o p i n g o f i n t e r a c t i v em e t h o df o r m u l t i p l eo b j e c t i v ed e c i s i o ni s a n a l y z e d t h e p a p e rt a k e st h et h e o r y o f m u l t i p l co b j e c t i v e p r o g r a m m i n ga n dd a t af i t t i n g a 3b a s i sa n dc o m b i n e s t h e m s m o o t h l y i t r a i s e sas e wi n t e r a c t i r e o p t i u m m e t h o df o rs o i v i n gm u l t i p l co b j e c t i v ep r o g r a m m i n g b y n u m e r i c a l m o d e l i n g a c e o r d i n g t ot h i sm e t h o d w e f i r s t l y t u r n m u l t i p l eo b j e c t i v eq u e s t i o n i n t o s i n g l e o b j e c t i r eq u e s t i o nb yu s i n g t f o r m a lf i e x i b l c s t r a t e g y ，t h e ng e t d a t a b y t h es o l u t i o no f s i n g l e o b j e c t i v eq u e s t i o na n df i n a l l yc a r t yo u tm a t h e m a t i c a l m o d e l l i n g i n t h e s o l v i n gp r o c e s s - t h eo p t i m u m s t a n d 奎a di s s i m p l i f i e da c c o r d i n g t o s a t i f i a b l i t y s t r u c t u r eo fd e c i s i o n t h ew h o l ea l g o r i t h mi sn o to n l y s i m p l cb u ta l s op r a c t i c a l t h i sm c t h o di s a l s ou s e f u l f o rn o n l i n e a rp r o g r a m m i n g t h em e t h o dr e a l i z e st h ei n f o r m a t i o no f p r o g r a m m i n gp r o b l e m sf o rd e c i s i o n m a k e r sa n di th a s f a i r l yf l e x i b i l i t y o m en u m e r i c a lc x a m p l e sa r eg i v c n t o v e r i f yi t se f f i c a c y a tt h el a s tp a r to ft h ep a p e r k e y w o r d s m u l t i p l eo b j e c t i v ep r o g r a m m i n g ； m o d e l i n g ；f i t t i n g ；i n t e r a c t i v e 。o p t i m i z a t i o n 1 多目标规划与数据拟合问题 人们在做一切工作时，总希望所选用的方案是一切可能方案 中最优的方案。若所考虑的问题只有一个目标作为选择好坏的标 准，人们应设法选取使这一目标在某种意义下达到“最优”的最 优方案。这类问题就是通常的( 单目标) 最优化问题。然而在实 践中。人们所追求的目标往往不只一个，需要考虑多个目标( 标 准) 都尽可能好的闷题。如设计一种新产品，人们常希望在一定 条件下能选择那种同时是质量好，产量高和利润大的方案。这类 在给定条件下同时要求多个目标都尽可能好的最优化问题，就是 所谓多目标最优化问题。 1 1多目标规划的发展过程 研究多目标最优化问题的学科称为多目标最优化或多目标规 划，它是数学规划的一个重要分支。用数学的语言来说，多目标 最优化的研究对象是：多于一个的数值目标函数在给定区域上的 最优化( 极小化或极大化) 问题。由于多个数值目标可用一个向 量目标表示，因此，多目标最优化问题有时也叫做向量极值问题。 多目标最优化的理论和方法，在诸如经济规划，计划管理，金融 决策，能源开发，工程设计，农业种植，卫生保健以及军事科学 等领域有着大量的应用。在经济学，对镱论，系统工程和控制论 等学科的研究中，也常常要涉及到多目标最优化问题。 多目标最优化的思想可以说是萌芽子1 7 7 6 年经济学中的效 用理论。1 8 9 6 年，经济学家v p a r e t o 首先在经济平衡的研究中 提出了多目标最优化问题。引进了被称为p a r e t o 最优的概念。 1 9 4 7 年，数学家j v o nn e u m a n 和0 m o r g e n s t e r n 在对策论的 著作中提及多目标决策问题，引起人们对于多目标最优化研究的 重视。1 9 5 1 年，数理经济学家t c k o o p m a n s 从生产和分配的效 率分析中考虑了多目标最优化问题，引入了有效解的定义并得到 某些基本结果。他的工作为多目标最优化学科莫定了初步的基 础。本世纪6 0 年代以来，人们设计了不少求解多目标最优化问 题的处理方法，并运用它们去解决各种实际问题，取得了效果。 1 9 7 3 年，j l c o c h r a n c e 和m z e l e n y 编集出版了第一本多目 标决策的书，为多目标最优化学科的形成起了推动作用。此后 关于多目标最优化的研究，不论在理论或应用方面都迅速、蓬勃 的开展起来，有关的著作也与日俱增了，目前，多目标规划仍是 一个十分活跃的研究领域。 1 2多目标规翅的理论与方法 多目标规划的数学模型分以下三类。 1 一般多目标最优化模型或一般多目标最优化问题n 求价变量x 一，卫矿一，妇使其满足如下： m a x ( o rt m )，1 ( 工i x h ，舶) e t i 呶o i m 吡)五( 札x ，勘) “ 苏篡三： _ ，= l ，2 ，p k = l 2 ，g 其中1 1 个变量工i ，工2 ，x 。称为决策变量，f 一，f 均为目标函 数，萝j ( 善l ，工。) ，h 。( 工l ，”，工。) 为约柬函数。着题设中既有极 大又有极小都可以统一写成上式的形式：若上式中 f i ( x l ，工。) ( i = 1 ，2 ，m ) ，g j ( x l ，茗。) ( j - - - 1 ，2 ，p ) 或 h k ( 并l ”，善。) ( k = l ，2 ，q ) 之一为决策变量的非线性函数， 则上式叫多目标非线性规划模型，否则为线性规划模型。通常 的上式为一般多目标最优化模型或一般多目标最优化问题。 为了简化， 记z = ( 石1 ，工2 ，工。) 7 ，f ( 工) = ( f l ( 工) ，f 。( 工) ) 7 x = 奴力o 歹= l ，p 工露叫 阻( x ) = 0 k = 1 ，q 为决策可行域，则上述问题进一步简写为： v n 。l a g ( o rr ain)坟x)(vmp) 即v e c t o rm a t h e m a t i c a l p r o g r a 毒n g ( 向量数学规划) 后面 的讨论以多目标极小化模型的形式进行。 2 、分层多目标最优化模型 一般地，对于m ( 2 ) 个目标函数 ( x ) ，厂，( 工l 厂( x ) ，；尤( 工) ；厂( 工) 。，尤( 工) ( 1 l + 1 2 + + l l 2 m ) ， 设按其重要性分成如下的( l 2 ) 个优先层次： 第1 优先层次一厂i ( 如，( 苫) 第2 优先层次- 厂( x ) ，t 臼) ， 第蚍层次一f ) ，t ( x ) ， 则它们在约束条件工e x 之下的分层多目标极小化问题记作： l 一噼献厂l ( 巩。厂，( 州“厂( 椎，厂：( 枷州厂( n 正( 硼 其中p s ( s = l ，l ) 是优先层次记号，表示后面括号中的目标 函数厂( z ) ，f ( x ) ( s 2 1 ，2 ，l ) 属于第s 优先层次，且 各p s 之间有关系 p s p n i ，s 2 l ，l ( 它表示第s 优先层次“优先于”第s + l 优先层次) 。l - - r a i n 即l o x i z o g r a p h i c a lo r d e r 表示按字典序极小化，即依次按记 号p 。，气，p l 的次序逐层地进行极小化。 若记：f 1 ( 工卜，i 。( x ) ，f l 。( x ) ) 1 ， f 2 ( x 产( f ，( 善) ) t ， f l ( 茹) 2 ( 九x ) ，尤( x ) ) ， 则又可记作：l m 。i l l 【p 写( x ) ，p 2 最( 茹) ，p l f l ( x ) i 或l - r a 。i ，n p sf s ( x ) l ：，耀_ r扣l 即l o x i c o g r a p h i c a l l y s t r a t i f i e d ( l s p ) p r o g r a m m i n g 即字典分层规 划。问题( l s p ) 通常叫做具有l 个优先层次的分层多目标最 优化模型或分层多目标极小化模型。 3 目标规划模型【1 】 一般地，设给定m ( t 2 ) 个目标函数和决策者希望它们要 达到的各自对应的目标值如下： 目标函数f l ( x ) , - - - , n ( 工) ， 目标值 于，。 则上述在约束条件工x 下考虑各( x ) ( i = l ，m ) 逼近其 对应目标值于；的问题可记作 o n a p p r f ( x ) e j ( a g p ) 即a p p r o x i m e t e g o a l p r o g r a m m i n g 叫做以夕为目标值的逼 近目标规划模型，式中v a p p r 代表向量逼近。 从上述关于模型的讨论中我们知道，多目标( 向量) 最 优化问题与通常的单目标( 数值) 最优化问题的一个本质的不 同点是问题中的目标是一个向量函数。为要比较这些向量函数 值的“大”“小”，首先需要引进向量空间中向量间的比较关系， 或即“序”的关系。 定义1 a = ( a l ，a m ) t , b = ( b l ，b 皿) t 是m 维欧氏空间r “ 中的两个峙题向量t ( 1 ) 若a i = b j ( i - l ，m ) ，则称向量a 等于向量b ，记作：a = b ( 2 ) 若巩b ；( i _ 1 ，m ) ，则称向量a 小于等于向量b 。 记作：a b 或b a ； ( 3 ) 若a i b ；( i - 1 ，m ) ，并且其中至少有一个是严格不等式， 则称向量a 小于向量b ；记作：8 乏b 或b a ； ( 4 ) 若钆 0 ，x 一是p 的最优解，则；e ( f ，x ) 。 ( 2 ) 若入多o ，；是p 的最饶解，员i j ；e 。( f ，x ) 。 定理4 【2 】设x e r “是非空凸集，仁( f l ，一，f r o ) 7 ：x r m 是 x 上的凸函数，若x e ( f ，x ) ，则存在九 0 入 o ，使x 是p 。 的最优解。 由定理3 、4 可看出，对于凸的多目标规划问题( v m p ) ， 可通过在九。中寻找适当的权向量天和求解( p 。) ，得到决策 者满意的p a r e t o 有效解。对一般的多目标规划问题，也可通 过这一途径得到决策者较为满意的p a r e t o 有效解。 目前，由于单目标模型的求解方法已较成熟。求解多目标 模型的关键是在于如何将多目标问题转换为单目标问题，即如 何引入决策者的偏好。关于多目檑问题的求解，先分四种情况 讨论。 对模型一即一般多目标最优化模型的求勰，文献 1 中详 细介绍了评价函数法，而且，由于采用不同形式的评价函数， 可求得( p ) 的不同意义下的解，这时也就对应了一种不同 的求解方法，如线性加权和法、极大极小法，理想点法等。这 些方法把多目标问题转化成了单目标问题，在一定条件下求出 了单目标问题的最优解，即得到了多目标问题的非劣势解。但 不足之处是这类方法与决策者无法交互。 对( p ) 模型，虽然还有交互规划法。如逐步宽容约束 法。权衡比替代法和逐次线性加权和法。但它们都有其局限性。 如逐步宽容约束法只对求解含线性向量目标函数的多目标极小 化问题，而权衡比替代法则是对求解带线性约束的多目标极小 化问题，逐次线性加权和法更特殊，是求解多目标线性规划的 交互规划法。 对模型二即分层多目标最优模型，有分层求解法。其中完 全分层法的求解是：据各个目标在问题中具有不同的优先层 次，而且每一优先层次都只考虑一个目标的特点，求解时只要 按照模型所规定的优先层次依次对每一层求出_ 最优解，则最后 一层的最优解即为所求解。这种方法的严重缺陷在于：由于多 目标问题是一个相互制约的矛盾体，在求解最优值时，先只考 虑一个目标而忽略其他目标的影响，这样得出的最优解本身不 可靠。加之，这种方法与决策者无法交互，不具有灵活性。而 分层评价法尽管克服了上述每一层只考虑一个目标的限制，在 每一层次的多目标极小化都采用了某评价函数法，但按照它事 先规定的每一层都求解一个多目标极小化问题，这样逐层求 解，在实际操作中，是相当困难的，因两这种“逐层求解过程 只是一个原则的描述n p 。 对模型三即耳标规划模型，有目标规划法，其中极大模目 标点法，与模型一中极大模理想点法类似，而线性化逼近法实 际上就是逐层非线性最优法与模型二中完全分层法原理样。 因而以上两种方法都具有前面所述的不足。 七十年代以来。交互式多目标决策得到了迅速发展，已成 决策理论研究的重要内容。到目前为止，已有多种交互式决策 方法。文献 3 对交互式多目标决策方法及各类方法的研究情 况帮特点进行了详细阐述。 概括起来，交互型方法基本上分为两步： 第一，求解辅助问题；如序贯多目标决策方法( s e m o p s ) 。 这种方法的特点是，决策人给出的愿望目的水平，不是以固定 点的形式给出，而是以“区间值”表示的。其方法的优点是， 在迭代过程中容易看出目标之间的矛盾，因此比较容易修改目 标的目的值。其不足之处是：其一决策人难于设置和重新设置 愿望的水平i 其二，在解辅助问题时，很可能出现不一致的后 果，以致不能有一循序渐进的步骤去确定一集一致的区间目 的。 第二，是分析者和决策者交换信息以改善所得之非劣势 解。近几年又不断有新的成果出现。文献 4 基于改善方向建 ，立了求解多目标决策问题的非劣势解的改善方向法，进而提出 。了考虑决策者偏好结构的交互式改善方向法。并且证明了方法 的收敛性。验证了方法的有效性。这种方法对决策人的素质要 求较高，有时决策人较难准确地回答分析人的问题。文献 5 提出了一个求解多目标非线性规划问题的新的交互式方法。此 法的特点是，通过与决策者的交互对话，来逐次缩小权向量空 间，在对目标空间中的点作筛选后，得到决策人满意的解，该 方法打破了以往在目标空间和决策空间的交互方式。这种方法 同样对决策人的素质要求较高。文献 6 介绍了一种求解多目 标模型的新方法一交互的切比雪夫方法。该方法有以下四个 方面的特点：全丽性，切比雪夫方法能在整个非劣解空间进 行搜索，然后决策者提供在非劣解中差异性最大的若干方案， 这些方案代表各种截然不同的规划方向，与理想点和目标规划 相比，它不会丢掉决策者没有意识到的，潜在的最优解( 满意 解) 。高效性，它不仅可用来解一般的线性规划，整数规划。 而且可用来求解目标非线性问题，特别适合于求解大型模型。 实用性，便于与决策者交互，便于计算机化，便于做多目标 4 决策支持系统。客观性，该方法在首轮迭代中提交决策者的 方案，完全是由计算机随机产生的权重组合所对应产生的，不 包含规划人员的任何主观因素，它提供给决策者有关非劣解集 的各种可能情况是客观的。但该方法在实际应用的不足是在利 用该方法求解时，在每轮迭代中需要对p ( 一般为5 7 ) 个切 比雪夫优化模型进行求解，计算上有一定的复杂性，特别是当 模型的规模较大时。多目标模型的寻优本身是个非常复杂的问 题。另外由于有“实用性”的特点，则需要模型研制人员在模 型和较件方面事先做较多的工作。 以上介绍的四种多目标方法虽各有其优缺点。但笔者认 为，考虑决策者偏好的交互式求解方法将成为多目标求解的主 流。而一个较好的交互式决策方法应具备如下特点：尽量减少 来自决策人的输入信息；应允许决策人改变偏好；决策人和分 析人之间的交互尽量简单；尽量减少决策人的认知负担；能尽 快获得决策人需要的溃意解。 交互式多目标决策在以下方面有待进一步研究和发展： 应用交互式决策方法研究大规模多目标决策问题：研究基于 知识、经验的交互式决策方法，即决镱入的偏好是根据自己的 知识经验作出的； 交互空间不限于目标空间和决策空间，提 出更广泛的空间以便决策人和分析人交互：研究单层的交互 式决策方法推广到多人，多层的交互式决策方法；应用交互 式决策方法研究实际问题；研究确定性的交互决策方法推广 到随机多目标决策问题，即研究参量或系数为随机变量的多目 标决策问题。 1 3 数据掇合法 在科学实验或统计研究中，常常需要从一组测定的数据例 如n 个点( 工 ，y ；) 出发，去求得自变量x 和因变量y 的函数关 系y = 妒( 善) ，这就是由给定的n 个点( x ；，) ，；) i = l ，n 求数据 拟合的问题。由于实验数据往往不准确，因此曲线通过所有的 点会使曲线保留全部观测误差的影响。数据拟合法则不要求曲 线通过所有点( x ；，y ；) ，亦即不要求拟合函数在工；处的偏差 6i = 妒( 工；) 一y j ( i = l ，2 ，n ) 都严格地等于零，但是，为了 使曲线能尽量反映所给数据点的变化趋势，要求6 ；按某种标 准最小还是需要的。常见使6 ；最小的标准有： ( 1 ) 、选取妒( 工) ，使偏差绝对值之和最小 即 阪| i 矿( 藩) 一p i2 - - - m j n ： i - 1扣1 ( 2 ) 、选取妒( ，) ，使偏差最大绝对值最小， 即 熘旧l - 器1 9 ( ( ) 一p ) i - m i n ； ( 3 ) 、选取妒( x ) ，使偏差平方和最小， 即 窭= l 矿( 善i ) 一y i i 2 2 m i n。 扯1“l 为了便于计算，分析与应用，我们较多地根据“使偏差平 方和最小”的原则即最小二乘原则来选取拟合曲线y = 伊( x ) 。 按最小二乘原则选择拟合曲线的方法，称为最小二乘法。 关于最小二乘法的一般提法是：对于给定的数据表： 表一 x而x 2 yy ty 孓 要求在函数类矿= 妒o ( _ j c ) ，尹。( j c ) ，尹。( x ) ( n n ) 中寻找 一个函数y = 矿+ ( 工) ，使误差平方和 抖一1 2m” l i 叫1 2 2 荟。善 伊+ ( x t ) 一y t j2 。恕善 伊( x ) 一y 。 2 ， 其中矿( z ) = a o 妒o ( x ) + a 1 矿l ( x ) + a 。妒。( 工) ( n 扩 佃l j ：土y a i n 鲁 歹= 吉姜p ( a ，b ) 最小，则有 式可以确定式( 2 3 1 ) 中的系 数a b 。 以下几种曲线均可以通过变量替换转化为( 2 3 】) 式， 再用( 2 3 3 ) ，( 2 3 2 ) 式确定系数。 ( 1 ) 双曲线型：一1 ：。+ 鱼 v 令；吨j 1 = v 得u = a + b v ( 2 ) 幂函数型；y = d 矿( 名 o ) 若d o ，令u = l n y ， v = l n t ， 得u = a + b v 若d o 令u = l n y ， 若d d ) 得u = a + b v ( 5 ) 分数指数函数：y = 0 a - - - - l n d ， a = l n ( 一d ) ， a = l a d a = i n ( - d 、 得u = a + b 2 得u = a + b 2 a = l n c ( c o )一 = v 若d o 令u = l n y ，a = l n d ，y = _ 1 ，得u = a 十b v 若d o 令u = l n ( 一y ) ，a = l n ( 一d ) ，v = 得u = a + b v ( 6 ) s 曲线型：y 2 i b j 令三= l l ，e 一= v 得 u=a+bve y 口+ ( 7 ) 对数曲线型：若双对数型l o g y = l o g d + b l o g 令1 0 9 j ，= 1 l ，l o g d = a l o g = v 得u = a + b v 若半对数型：y = a + b 1 0 9 九 令l o g 九= v得y = a + b v ( 8 ) 三角函数型：y = ac o s ( b + a ) 或y = a e o s b + b s i n b 入 令u = a r c c o s 羔得u = a + b x 口 j ，= 盘c o s ba + 量s i n b a 可以转化为y - - a t 0 8 ( b + 口) 。 ( 二) 若呈抛物线的变化，可设： p k ( x ) = a 1 + a 2x + a 3 九2 + + a k 九。一1 ( k ( n ) ( 2 3 4 ) 其中全部待定系数a l ，a 。，a k 由( 1 3 4 ) ( 1 3 6 ) 解 得。 对于两个以上的目标，可按多变量线性拟合法建模。 设y = a o + a l 九l + a 2 九2 + + a k x k ( k 矿通过比较，取抛物线模型 此时综合目标与权系数的关系为： f ( x ) = 1 4 0 9 7 9 8x + 1 4 6 2 x 2 见图一 入 ( 圈一) 2 。、由x x ：的分布，类似上面的讨论可得拟合益线如下 分别为图二、图三： x l ( ) = 0 2 s 0 。1 o 1 s 工s 0 2 o 2 蘑5 o 5 互s 0 6 0 6 2 0 g 0 8 霸9 o 。9 五s l i 毖馋硒h 挖m 8 6 4