第10章多目标规划简介

142第10章多目标规划简介§10.1基本概念与术语10.1.1模型举例例1(物资调运优化):假设物资调度部门计划将某种物资从若干个储存仓库，调运到若干个销售网点。考虑到物资的时效性和销售效益，调度部门希望物资在运输过程中尽可能快地到达目的地；考虑到运输的成本，调度部门还希望物资的总运输费用最小。假设m个仓库的物资库存量为1a，…，ma（单位：t)；n个销售网点预计销售量为1b，…，nb（单位：t)。仓库i与销售网点j之间的路程为ijd(单位：km)，单位物资的运费为ijc（元）。用物资吨公里总数来衡量物资的运输品质，吨公里总数最小意味着有适量的物资尽可能快地到达目的地。记从仓库i到销售网点j运送的物资量为ijx。目标函数：（1）物资在运输过程中的吨公里总数为ijijijxd（2）物资运输费用总和为ijijijxc约束条件为产销平衡条件：ijijaxjiijbx优化问题模型：njmixnjbxmiaxxcxdijjiijijijijijijijijij,,1,,,1,0,,1,,,1,s.t.min多目标规划（MOP）问题描述:143)3(,0)()2(,0)(s.t.)1())(,),(),(()(min21EjxhIixgxfxfxfxfjiTp)(xf称为向量值目标函数。变量可行域记为}32|{）（）满足（xRxSnS的像集)(SfZ称为目标可行域，Z中的元素)(xfz称为目标向量。如果不指明约束函数的具体形式，多目标规划问题可以简记为)(min)MOP(xfVSx若每个目标函数)(xfi都是凸函数，并且可行域S是凸集，则（MOP）称为多目标凸规划问题。10.1.2向量集的有效点与弱有效解在讨论向量集的有效点之前，约定如下记号：对于任意两个向量Tnxxxx),,,(21Tnyyyy),,,(21令（1）niyxyxii,,2,1,（2）jjiiyxjniyxyx，使得但存在某个,,,2,1,（3）0xyyx（4）niyxyxii,,2,1,（5）niyxyxii,,2,1,定义1：给定一个向量集nRX，对于点Xx0，若Xx，有xx0，则称0x是X的绝对最小点（即绝对最小向量）。若不存在Xx，使得0xx（0xx），则称0x是X的有效点（弱有效点）。集合X的所有绝对最小点、有效点和弱有效点的集合分别记为aE，pE和wpE。144例2：考虑椭圆}4)2()5.0(|),{(222121xxxxX。aE}0,5.0|{21xxXxEEwpp从几何上看，pE表示椭圆的左下部（包括端点）。约定：非负锥：}0|{xRxRnn正锥：}0|{xRxRnn定理1：给定nRXx0，考虑下面条件：（1）对某nR，函数iiiTxx（Xx）在0x处取到最小值；（2）对某个nR，0，函数xT（Xx）在0x处取到严格最小值；（3）对某个nR，0，函数xT（Xx）在0x处取到最小值。若条件（1）或（2）成立，则0x是X的有效点。若条件（3）成立，则0x是X的弱有效点。10.1.3多目标规划的解及其性质考虑形如式（1）-（3）的多目标规划问题，变量可行域}32|{）（）满足式（xRxSn，目标可行域)(SfZ。定义2：给定一可行点Sx*，若Sx，有)()(*xfxf，则称*x为问题(MOP）的绝对最优解（绝对最小解）。若不存在Sx，使得)()(*xfxf()()(*xfxf),则称*x为问题（MOP）的有效解（弱有效解）。问题（MOP）有效解也称Pareto最优解。将问题（MOP）绝对最优解、有效解、弱有效解集合分别记为aS，pS和wpS。多目标规划的（弱）有效解与其目标可行域的（弱）有效点之间有紧密的联系，概括为如下定理：145定理2：对于问题（MOP)，令)(SfZ表示目标函数在定义域S上的值域（目标可行域）,Z的有效点集和弱有效点集分别记为pZ和wpZ，则（MOP）的有效解集pS和弱有效解集wpS，由下面式子给出：（1）pZfpfxfSxS*})(|{*（2）wpZfwpfxfSxS*})(|{*解集合aS，pS和wpS之间的关系，有如下定理：定理3：对多目标规划问题（MOP)，必有（1）SSSSwppa（2）当aS时，paSS（3）若可行域S为凸集，f是S上严格凸的向量值函数，则wppSS。如果记单目标优化问题)(minxfiSx的最小点的集合为iS，那么多目标规划问题的绝对最优解的集合piiaSS1此外，容易证明wpiSS成立。根据定理3，有如下结论：wppiipSSS1)(例3：求解两目标优化问题TSxxxx),2(min2其中]2,0[S。记目标xxxfz2)(211,xxfz)(22。单目标优化问题)(min]2,0[xfix的最优解集}1{1S，}2{2S,故绝对最优解集aS。该问题的目标可行域为]}0,2[,2|{222212zzzzRzZ根据Z的（弱）有效点定义以及定理2，该问题的有效解集与弱有效解集相等。特别地，]2,1[wppSS。例4：求解两目标优化问题TSxxxxx),2(min2121其中})1,1{(2TS。146记目标21112)(xxxfz,2122)(xxxfz.单目标优化问题)(minxfiSx最优解集})0,0{(1TS，})1,1{(2TS,故绝对最优解集aS。根据定理3中结论(3)，该问题的有效解集与弱有效解集相等.另外，该问题的目标可行域Z为}10,120|{2122112zzxzzxRzZ根据Z的（弱）有效点定义，可以知道]3,1[,12]1,0[,01211212zzzzzzRzZZwpp利用定理2，有])1,0[1()0]1,0([wppSS。§10.2多目标规划的解法10.2.1多目标规划的直接解法多目标规划问题（MOP）的本质在于：各个子目标有可能是相互矛盾的，一个子目标的改善有可能引起另一个子目标的恶化，同时使所有子目标都达到最优值一般是不可能的，只能是在这多个子目标之间进行协调和权衡，使各个子目标尽可能地达到理想值。多目标规划问题的直接解法，就是寻找它的整个最优解集（Pareto有效解集）。除了特殊的情形，计算所有的最优解是比较困难的，因为确定整个有效解集的问题是NP-hard的。目前对直接解法的研究结果还比较少，主要采用间接解法。直接解法的最新进展——多目标遗传算法（MOGA）。多目标规划Pareto最优解一般是一个集合。由于GA是对整个群体所进行的进化运算操作，它处理的是个体的集合，这种相似性使得GA可以作为求解多目标规划问题的Pareto最优解集的一个有效手段。147注1：间接解法的共同特点：将多目标规划问题转化为一个或多个单目标优化问题。通过求解单目标优化问题得到（MOP）的一个或多个最优解。一般并不要求间接解法给出问题的所有最优解。10.2.2基于一个单目标问题的方法基本思想：首先将原来的多目标规划问题（MOP）转化成一个单目标优化问题；然后利用非线性优化算法求解该单目标问题，把所求得的最优解作为问题(MOP）的最优解．—线性加权和法—主要目标法—理想点法—极小化极大法这类方法的核心：保证所构造的单目标问题的最优解是（MOP）的有效解或者弱有效解．线性加权和法：根据p个目标函数jf的重要程度，分别赋予一定的权系数j，然后将所有的目标函数加权求和作为新的目标函数，在（MOP）的可行域S上求出新目标函数的最优值。问题转化为如下单目标优化问题：（λSP）}0)(,0)(|{s.t.)()(minxhxgRxSxxfxfnjjjT其中1,0jjj。f,g,h为向量值函数。主要目标法：根据实际情况，首先确定一个目标函数为主要目标，不妨假设)(1xf为主要目标，而把其余的1-p个目标函数)(xfj作为次要目标。然后借助于决策者的经验，通过选定一定的界限值ju（pj,,2），把次要目标转化为约束条件，通过求解如下的单目标优化问题获得问题（MOP）的最优解：（SP）},,2,)(|{~s.t.)(min1pjuxfSxSxxfjj10.2.3基于多个单目标问题的方法基本思想：根据某种规则，首先将（MOP）问题转化为有一定次序的多个单目标优化问题；然后，依次分别求解这些单目标优化问题，并且把最后一个单目标优化问题的最优解作为原问题的最优解。—分层排序法—重点目标法—分组排序法148这类方法的核心：保证最后一个单目标优化问题的最优解是（MOP）的有效解或者弱有效解。分层排序法：根据目标的重要程度将它们一一排序；然后分别在前一个目标的最优解集中，寻找后一个目标的最优解集，并把最后一个目标的最优解集作为问题（MOP）的最优解。首先，通过求解单目标问题)(min)P(11xfSx得到)P(1的最优解集S1。然后对于,2,3,pj，依次求解单目标优化问题)(min)P(1xfjSxjj得到)P(j的最优解集jS。最后，将pS中的点作为（MOP）的最优解。重点目标法：在p个目标函数中，首先确定最重要的目标，比如)(1xf，并且在S上求出)(1xf的最优解集1S；然后，在1S上求解其余1p个目标对应的多目标规划问题TpSxxfxf))(,),((min)MOP(2'1把（MOP'）的有效解或弱有效解作为（MOP）的最优解．在求解问题（MOP'）时，可以利用前面介绍的方法，将（MOP'）转化为一个单目标优化问题求解。分组排序法：根据某种规则，首先将（MOP）的目标分成若干个组，使得在每个组内的目标的重要程度相差不多，此时，每组目标实际上对应着一个新的多目标规划问题；然后，依次在前一组目标对应问题的最优解集中，寻找后一组目标对应问题的最优解集，并把最后一组目标对应问题的最优解作为（MOP）的最优解．注2：分组排序法实际上是分层排序法的推广形式。分层排序法是针对单个的目标进行分层，求解相应的单目标优化问题;分组排序法则是对一些目标的集合进行分层，求解相应的小规模多目标规划问题．149习题1求解双目标优化问题0,6272s.t.),32(min2121212121xxxxxxxxxx2对于双目标优化问题0,32222s.t.)3,22()(min2121212121222121xxxxxxxxxxxxxxxf（1）若取权向量4/5)(1/5,，试利用线性加权和法求出一个有效解；（2）利用线性加权和法能否求出该问题的所有有效解？（3）你能求出该问题的有效解集吗？