第13卷 第4期运 筹 与 管 理Vol.13,No.42004年8月OPERAT IO NS RESEARCH AN D M ANA GEM EN T SCI EN CEAug.2004收稿日期:2003-10-27基金项目:陕西省教育厅专项科研基金资助项目(03jk065);西安建筑科技大学基础研究基金资助项目(02BR01)作者简介:卢志义(1973-),男,内蒙古包头市人,硕士研究生,从事最优化理论研究;徐裕生(1950-),西安建筑科技大学理学院教授,主要从事最优化理论和不动点理论的研究。
完全分层多目标规划的基线算法卢志义, 徐裕生, 马春晖(西安建筑科技大学理学院,陕西西安710055)摘 要:本文采用基线算法求解完全分层多目标规划问题。
给出了简单完全分层多目标规划基线算法的求解步骤,并对其进行了修正,从而得到完全分层多目标规划的宽容基线算法。
并给出了两个计算实例。
关键词:运筹学;宽容算法;基线算法;多目标规划中图分类号:O22116 文章标识码:A 文章编号:1007-3221(2004)04-0050-05Th e Basic Line Algorithm for Complete Tratified Mu ltiobjective Programmin gLU Zh-i yi,XU Yu -sheng,MA Chun -hui(College of Science,X i .an University o f A rchitecture and Technology ,Xi .an 710055,China)Abstract:In this paper,we make use of the basic line algorithm to solve the complete tratified multiobjective prog ramming.The procedures of solv ing the simple com plete tratified multiobjective program ming are g iven.M eanw hile,w e rev ise it so as to succeed in obtaining the compromise solution of the complete tratified mult-i objective programm ing.T wo examples also are g iven.Key words:operations research;comprom ise algorithm;the basic line algorithm;multiobjective programming0 引言基线算法是一种线性规划的新算法,具有操作方便,迭代次数小,效率高,数值稳定性好等特点,是单纯形法的发展(参见[1])。
我们陆续将此算法推广到与线性规划有关的其它规划。
本文旨在将此算法推广到多目标规划。
较单纯形法而言,用基线算法解决完全分层多目标规划,步骤更简洁,易操作,运算速度更快。
1 简单完全分层多目标规划的基线算法1.1 算法的形成讨论完全分层多目标规划问题L -max [v s =P s c T s x ]ms =1(1)s.t.Ax [bx \0其中c s =(c s 1,,,c sn )(s =1,,,m ),x =(x 1,,,x n )T ,A =a 11,a 1n,,,a q 1,a qn,b =(b 1,,,b q )T .此模型的特点是:每一优先层次只有一个目标函数,且每一优先层次的问题都是一个线性规划问题,因而可以逐层地采用基线算法求解。
将上述模型变为标准型:L -max [v s =P s c Ts x ]m s =1(2)s.t.a 11x 1+,+a 1n x n +x n +1 =b 1,, , ,,a i 1x 1+,+a in x n +x n +i=b i ,,,,,a q 1x 1+,+a qn x n +x n +q=b qx i \0(i =1,,,n +q )或将约束条件简写为s.t.A x +(x n +1,,,x n +q )T =bx i \0(i =1,,,n +q )首先用基线算法求解第一优先层的最优值。
即求解线性规划问题max v 1=c 11x 1+,c 1n x ns.t.A x +(x n +1,,,x n +q )T =bx i \0(i =1,,,n +q )其初表为(表1):表1x 1x 2,x n x n +1,x n +q RH S c 11c 12,c 1n 0,0v 1a 11a 12,a 1n a 1,n +1,a 1,n +qb 1,,,,,,,,a i 1a i 2,a in a i,n +1,a i,n +q b i ,,,,,,,,a q 1a q 2,a qn a q,n +1,a q,n +qb q设求得的最优值为v *1,其最优表为表2,将v 1=v *1代入此最优表,并将第二层目标列入此表得新表(表3),进入第二层次目标的求解过程。
表2x 1x 2,x n x n +1,x n +q RH S c c 11c c 12,c c 1n c c 1,n +l ,c c 1,n +q A 0+B 0v 1a c 11a c 12,a c 1n a c 1,n +1,a c 1,n +qA 1+B 1v 1,,,,,,,, ,a c i 1a c i 2,a c in a c i ,n +1,a c i,n +qA i +B i v *1,,,,,,,, ,a c q 1a c q 2,a c qna c q,n +1,a c q,n +qA q +B q v 1表351第4期 卢志义,等:完全分层多目标规划的基线算法52运筹与管理2004年第13卷表3相当于将条件c11x1+,+c1n x n=v*1作为求解第二层目标最优值的约束条件。
用基线算法求得最优值,这样逐层进行下去直到第m层目标。
由上述求解过程易知,最后一层的最优解必为原问题的有效解。
1.2简单完全分层多目标规划基线算法的步骤step1化为标准形式(2)step2由第一层目标函数与约束条件构成初表用基线算法求解,并令k:=1;step3若k=m,输出最优解与各层目标函数的最优值v*i;否则进入step4;step4将第k层最优表中v k用v*k代换并将第k+1层目标函数加入第k层最优表,用基线算法求解,令k:=k+1,转step3。
1.3例1L-max[P1(x1+3x2),P2(x1+2x3),P3(-x1-2x2-x3)]s.t.x1+x2[5x2[2-x1-x2+x3[4x1,x2,x3\0解第一步,引入松弛变量x4,x5,x6.化为标准型L-m ax[P1(x1+3x2),P2(x1+2x3),P3(-x1-2x2-x3)]s.t.x1+x2+x4=5x2+x5=2-x1-x2+x3+x6=4x i\0(i=1,,,6)第二步,列出第一层初表(表4)表4x1x2x3x4x5x6RH S130000v111010050100102-1-110014x1进基,得基线表(表5)。
表5x1x2x3x4x5x6RH S130000v1v1\00[-2]01005-v1v1[501001020210014+v1v1\-4旋转得(表6):表6x1x2x3x4x5x6RH S1003/20015/2-v1/2v1[15010-1/200-5/2+v1/2v1\50001/2109/2-v1/2v1[9*0011019已知最优表,v*1=9。
第三步,令代入初表并将第二层目标函数加入最优表(表7):表7x 1x 2x 3x 4x 5x 6RH S 102000v 21003/2003010-1/20020001/210001119x 1、x 2进基,得基线表(表8),表8已是最优表。
表8x 1x 2x 3x 4x 5x 6RH S 001-3/400v 2/2-3/2v 3\31003/2003010-1/20020001/21007/41-v 2/2+21/2v 2[21*第四步,将v 2=v *2=21代入上表8,并将第三层目标加入表8得表9,经初等变换,变成表10,此表是最优表,其最优值为v *3=-16。
代入表10得最优解为x =(3,2,9,0,0,0)。
于是得此题的有效解为x =(3,2,9,0,0,0),各优先层次目标的最优值为:v 1=v *1=9,v 2=v *2=21,v 3=v *3=-16。
1.4 说明若到某一层得到的基线表行数等于n +q ,此时,下一层次的求解不必再进行,出现这种情况时说明,以后各优先层次的目标函数在问题中不起作用。
为避免出现这种情况,可进行如下的修正)))宽容完全分层多目标规划的基线算法。
表9x 1x 2x 3x 4x 5x 6RH S -1-2-1000v 3001-3/40091003/2003010-1/20020001/210007/401表10x 1x 2x 3x 4x 5x 6RH S 000100-4v 3-64v 3[-16*001000-3v 3-69v 3[-131000006v 3+99v 3\-33/2010000-2v 3-30v 3[-150000102v 3+32v 3\-16017v 3+112v 3\-162 宽容完全分层多目标规划的基线算法宽容分层算法的基本思想是:从第二层起,在对每一层求解之后给其最优值以适当的宽容,使得下一层次的可行域以适当的放宽,以前一层次目标函数的最优值的偏差,换取后一层次目标函数值的改善。
设给出第k 层次的宽容量为D k \0(k =1,,,m -1),其算法的步骤为:step 1、step 2、step 3同简单完全分层多目标规划基线算法的对应步骤;step 4将第k +1层目标函数加入第k 层最优表,将第k 层最优表中第一行中v k 用v *k -D k 代换,其余行中的v k 仍用v *k 代换,并增加变量列x n +q +k -1,其系数为(0,-1,0,0,0,0)T,继续用基线算法求解.53第4期 卢志义,等:完全分层多目标规划的基线算法54运筹与管理2004年第13卷令k:=k+1,转step3.下面的定理给出了由宽容分层基线算法所求得的解的意义。
定理设X={x I R n|Ax[b,x\0},E X(f,X)是问题(1)的弱有效解,D k\0(k=1,,,m-1).若x I E X(f,X)。