双目标规划问题的像集与求解

双目标规划问题的像集与求解马赞甫;刘妍瑁【摘要】The objectiveof decision-making ineconomic managementis oftenrelatedto costand benefit.A goodcase inpoint isthat bi-objectiveprogramming basedon cost-benefit analysisis widelyused ineconomicmanagement.However,so far,there isstill alack ofmature algorithmstodetermine thefull solutionof theBi-objective programmingproblem.Ageneral methodwhich wasused toget thePareto solutionor weakParetozsolution fordouble objectiveoptimization problems,was putforward inthisresearch.To bespecific,we constructeda singleobjective programmingwithequality constrainto determinethe frontierof theimage setof doubleobjectiveoptimization problems.Furthermore,we coulddetermine thefrontiersfunctional monotonicityusing Lagrangemultiplier andfinally getthePareto solutionor weakPareto solution.Base onabove stepsAZgen-eral frameworkwas presentedto solvedouble objectiveprogramming经济管理的决策目标往往与成本、收益相关，双目标规划在经济管理中具problem.%有广泛应用然而，尚缺乏成熟的算法确定双目标规划问题的全部解给出双目标规划问题像集的一般性确定法，以求其解，为研究目的所在具体而言，构造一个带等式约束的单目标规划问题，以确定双目标规划问题像集之部分边界，并借助拉格朗日乘子符号判断其单调性，据此确定原问题的帕累托解与弱帕累托解这相当于提供了一个求解双目标规划问题的一般性框架【期刊名称】《经济数学》【年卷，期】2016033002【总页数】页5P75-79【关键词】最优化;双目标规划解法;单目标规划;像集;弱帕累托解【作者】马赞甫;刘妍瑁【作者单位】贵州财经大学贵州省经济系统仿真重点实验室，贵州贵阳贵州财550025;经大学数学与统计学院，贵州贵阳550025【正文语种】中文【中图分类】F224-3多目标规划的解法可区分为间接算法与直接算法两种.间接法的一般思路是将多个目标转换为单一目标进行处理，往往只能得到问题的一个解或部分解.如杨轶华、吕显瑞、刘庆怀等所指出的，间接法存在顾此失彼之缺点口］.直接法则以同伦法为代表，2006通过构造同伦映射确定多目标规划问题的解，直指多目标规划问题本身，可回避间接法之缺点.其中，刘庆怀、林正华考察采用该算法确定问题的最小弱有效解⑵，而2000杨轶华、吕显瑞、文」庆怀等则采用该算法确定多目标规划问题的一个有效解I2006集［］

1.考虑到万事万物好与坏、收益与成本等双分类的普遍性，多目标规划中的双目标规划具有极为重要的应用价值，常用于企业管理决策［］、交通设置优化［］等现实问题.3-56-7不失一般性，双目标规划问题的求解也可借助多目标规划求解方法.事实上,杨轶华、吕显瑞、刘庆怀等考虑了同伦内点算法在双目标规划求解中的应用［］而曾玉华、20061,彭拯同样考虑了双目标规划问题的一种直接算法，即非精确交替方向法⑻.下文2010拟提出双目标规划的一个更具一般性的应用分析框架，从属于直接法，从问题的像集结构入手，试图确定问题的全部解.考虑如下一般形式的双目标规划问题假设目标函数都可微.称为其帕累托解，如果不存在,使得xpwx X£X且其中至少有一个为严格不等式.称为问题的弱帕累托解，如果不存在,使得下列不等式组成立多目标XW£X1x£X规划问题的帕累托解或弱帕累托解其定义依据是目标函数值，因此，研究多目标规划问题的像集是求解多目标规划问题确定其帕累托解与弱帕累托解的最直接手段.特别是，双目标规划问题的像集不仅易于确定，且具有几何直观性，是求取双目标规划问题的便利工具问题⑴的像集定义为与多目标规划问题的帕累托解与弱帕累托解相对应，可分别定义其像集中的帕累托点与弱帕累托点.称为中的帕累托点，如果不存在使得F其中至少存在一个严格不等式.称为中的弱帕累托点，如果不存在使得F显然，如果为多目标规划问题的帕累托解，则其像必为中的帕累托点，反之亦xpex F然.类似地，如果为问题的弱帕累托解,则其像必为中的弱帕累托点，反之亦xweX F然.基于此，可构造单目标规划问题确定双目标规划问题像集的基本特征，以达到确定其帕累托解及与弱帕累托解之目的.确定像集的方法较多，不过，一般具有问题针对性.比如，单一决策变量事实上可定义双目标函数之间的一个参数方程，可采用消除变量方式确定目标函数之间的函数关系.又如，若问题为多目标线性规划形式，可采用凸组合方式确定像集.针对双目标规划

[9]问题，本项研究考察其像集的一般性确定方法.不论变量维度如何，双目标规划问题的像集总是二维空间中的点集.因此，可通x过探究像集的结构特别是下边界形式确定双目标规划问题的弱帕累托解.为此，考察如下单目标规划问题其中问题旨在界定多目标规划问题像集的下方边界.该问题为等式约束问题，按照通3常的做法，就,构造拉格朗日函数问题的一阶条件等价于如下方程组XWX这里为函数的梯度向量，.针对给定的参数，假设存在满足拉格朗日条件的与i=l,261其中为问题的最优解，记相应的目标函数最小值为3现需要判断单目标规划问题的最优解是否为多目标规划问题的帕累托解.若在处可导，且则根据包络定理有或者说函数在处01Envelope Theorem

[10]61单调递增，这表明并非多目标规划问题的弱帕累托解.反之，若此时表明在的某领域范围内，两目标函数之间存在此消彼长关系为多目标规划问题的局部帕累托解.除此之外，若暂不能确定是否为双目标规划问题的弱帕累托解.综上，利用单目标规划问题确定多目标规划问题的解，主要关注如下两点其一，给定参数个可能的取值，函数能否在方程的解集中取到最小值.如果单目标规划问题91—最优值负无穷，则满足的可行解满足帕累托解的定义，是多目标规划问题的帕累托解.换言之，即便在处无定义，也不影响求取双目标规划问题的帕累托解.其二，该最61小值点是否满足局部弱帕累托性，即相应的拉格朗日乘子符号如何.若乘子为负，则单目标规划问题的解是多目标规划问题的局部弱帕累托解，否则该解并非弱帕累托解.当然，如果目标函数满足凸性，局部弱帕累托解必然是整体弱帕累托解.进一步地，若就每一个可能的都确定了问题的值，则可据此绘取最小值函数的图像，3从而不难确定像集中的帕累托点与弱帕累托点，同时也得到了双目标规划问题的帕累托解与弱帕累托解.出于求解需要，问题并未完全确定双目标规划问题的像集，仅仅得到其下边界.我们3还可以求解如下最大化问题以确定像集之上边界设问题存在最优值，并记为于是，在给定目标函数取值的情况下，我们确定了目101标函数的变动范围，有从而得到双目标规划问题像集的一个大致认识.2综上，为确定双目标规划问题的像集及弱帕累托解集，其基本步骤可细分为如下三1步首先，确定目标函数在可行解集上的值域；其次，针对目标函数在其值域中的X所有取值求单目标规划问题⑶与⑷的最优解，以确定双目标规划问题像集的下边81,；界与上边界最后，根据问题的拉格朗日乘子符号，判断可行解是否为双目标规划3问题的局部弱帕累托解.当然，视问题不同可将两个目标函数的主次关系进行相应调整，即，也可在给定目标函数取值基础上探讨目标函数的取值范围.第二步要求针对某一目标函数的所有可能取值去确定另一个目标函数的最大值与最小值，事实上已将双目标规划问题转化为单目标规划问题.在数值解法之余，有时亦可确定一个目标函数的最大、最小值相应于另一个目标函数具体取值的函数关系式.做为示例，考虑双目标规划问题

[8]其中约束集按照前方确定像集的基本思路，并考虑到函数在上的值域为任取构造如X下单目标规划问题首先，单目标规划问题的内点解为坐标原点，这要求,显然是原问题的一个弱帕62=0累托解.其次，就任意的非的求取上述单目标规划问题都有可能确定原双目标规划问0题的一个弱帕累托解，当然，还需要结合问题等号约束所对应拉格朗日乘子的符号进行判断比如，若取单目标规划问题的值为此时对应于-这一约02=1,3x14-4x2-2x3=1束条件的拉格朗日乘子这表明该点并非帕累托点.反之，若取,此时单目标规划问题目标函数的最小值为且等式约束对应乘子为表明该点为帕累托点.事实上，就本例而言，完全可以借助单目标规划问题界定像集中的帕累托点.问题为凸规划问题，其条件为最优解的充要条件.就问题的最优解而言，存在广Kuhn-Tucker义拉格朗日乘子入使得al,al,a32xl+3X+al0,以及2x2-4A+a20,2x3+2A+a

30.aiO,i=l,2,3,2,

3.显然,若则必有,从而于是相继可推出，代入约束x20,2x2-4A+a2=0xl=x3=0求得再根据互补条件得到可验证，当时，该可行解-3x1+4x2-2x3=62a2=0,020满足全部的条件，是单目标规划问题的最优解，此时最优值函数为Kuhn-Tucker反之，若则根据约束条件，仅当时有意义.在这种情x2=0,-3x1+4x2-2x3=92620况下，根据知广义拉格朗日乘子由知,相继推出满足2=0,2x2-4A+a20A0条件的解为Kuhn-Tucker此时拉格朗日乘子为而最优值函数为于是，当给定第二个目标函数的取值时，得到第一个目标函数的最小值函数为该最小值函数给出了双目标规划像集的下边界，如图所示.不难判断，当时为单调递1增函数并非双目标规划问题像集中的帕累托点；而当时为单调递减函数是多目标规划问题像集中的帕累托点.因此，任意给定目标函数的的一个取值都可以根据目标函数21的具体取值在可行解集中界定双目标规划问题的相应帕累托有效解.比如，若取62,则在可行集中求解如下方程组£-4即可得到双目标规划问题的一个帕累托解是另外，通过求解单目标规划问题可确定双目标规划问题像集的上边界，不过，问题4⑷的求解对于判断双目标规划问题的弱帕累托解并无实际意义，此处略去其求解过程，仅给出结果.不难验证，单目标规划问题的最优值为因此，就第个目标函数任意给定的一个取值可界定第个目标函数的取值范围为这21相当于确定了双目标规划问题的像集.经济学往往面临价值取向的二维性.经济人总是权衡成本与收益，就生产者而言，产出最大而投入最小；就消费者而言，效用最大而支付最小；就投资者而言，收益最大而风险最小，等等，都是经济人理所当然的考虑.事实上，经济学研究源于资源的稀缺性，经济决策的核心是优化稀缺资源的配置与利用，其中不乏经典的双目标规划问题，也采用了类似的处理方式.比如，微观经济学中生产函数与成本函数的定义.任何生产总是涉及到投入与产出两类目标，问题的像集表现为生产可能集具有帕累托特征或弱帕累托特征的生产方式需具•备如下条件给定投入的情况下，获得最大的产出；或者，在给定产出的情况下，投入成本最小.这两个条件分别定义了生产函数与成本函数，事实上确定了生产可能集的部分边界.显然，这一机理与确定像集边界一致.又比如，金融经济学中资产组合前沿边界的确定事实上即等价于双目标规划问题像集的确定，其决策变量为资产组合权重向量，两个目标函数分别是资产组合权重的方差函数与期望收益函数.问题的经典处理方式即提出的均值-方差模Harry MarkowitzQ952型口］采用了双目标规划像集求解方法，即，在给定期望收益的前提下考察方差的最1小值，或者，在给定方差的前提下谋求期望收益的最大值.处理结果的表现方式亦然，得到了双目标规划问题像集的上下边界，也就是资产组合前沿边界.利用像集探究多目标规划问题的帕累托解与弱帕累托解是一种传统思路，当问题为双目标规划类型时，尤具可行性.从确定双目标规划问题的像集边界入手，以拉格朗日乘子符号或像集边界函数单调性求取问题的局部弱帕累托解，这提供了双目标规划问题的一个分析框架,必须承认,于作者学识，此处仅提出一个分析框架,相关结论并未给出严格的数学证明，不过，该分析框架确实具有较好的应用前景.【相关文献】

[1]杨轶华,吕显瑞,刘庆怀等.求双目标凸规划问题有效解集的内点同伦算法[几吉林大学学报，2006,441:39-

43.

[2]刘庆怀,林正华.求解多目标规划最小弱有效解的同伦内点方法[几应用数学学报,2000,232:188-

195.

[3]于丽英,杨雷.生产计划的双目标混合整数规划模型及其求解[几上海交通大学学报,2001,357:1100-

1102.

[4]王兆杰,高峰,翟桥柱等.高耗能企业关口平衡问题的双目标规划模型[几西安交通大学学报，2013,478:26-

32.

[5]张人千,张兰慷.基于收益-风险双目标规划的随机能力扩张模型臼.系统工程理论与实践,2015,357:1678-

1688.

[6]杜进有,谢汶莉.城市群环路的双目标规划模型[北西南交通大学学报,2006,411:102-

106.

[7]隽海民,裴玉龙,申翔浩.城市客运交通结构生态效用双目标优化模型[几公路交通科技,2012,297:139-

143.

[8]曾玉华,彭拯.一种求解双目标规划的非精确交替方向法[J].运筹学学报,2010,144:121-

128.

[9]魏权龄.经济与管理中的数学规划[M].北京:中国人民大学出版社,

2011.

[10]Paul Milgrom,Ilya Segal.Envelope Theoremfor ArbitraryChoice Sets[J].Econometrica,2002,702:583-

601.[ll]Harry Markowitz.Portfolio Selection[J].Journal ofFinance,1952,71:77-

91.

[12]林铿云,董加礼.多目标优化的方法与理论[M].长春:吉林教育出版社,

1992.

[13]胡毓达.多目标规划有效性理论[M].上海:上海科学技术出版社,

1994.。