第13卷 第4期运 筹 与 管 理
Vol.13,No.42004年8月OPERAT IO NS RESEARCH AN D M ANA GEM EN T SCI EN CE
Aug.2004
收稿日期:2003-10-27
基金项目:陕西省教育厅专项科研基金资助项目(03jk065);西安建筑科技大学基础研究基金资助项目(02BR01)
作者简介:卢志义(1973-),男,内蒙古包头市人,硕士研究生,从事最优化理论研究;徐裕生(1950-),西安建筑科技大学理学院教授,主要从事最优化理论和不动点理论的研究。
完全分层多目标规划的基线算法
卢志义, 徐裕生, 马春晖
(西安建筑科技大学理学院,陕西西安710055)
摘 要:本文采用基线算法求解完全分层多目标规划问题。给出了简单完全分层多目标规划基线算法的求解步骤,并对其进行了修正,从而得到完全分层多目标规划的宽容基线算法。并给出了两个计算实例。关键词:运筹学;宽容算法;基线算法;多目标规划
中图分类号:O22116 文章标识码:A 文章编号:1007-3221(2004)04-0050-05
Th e Basic Line Algorithm for Complete Tratified Mu ltiobjective Programmin g
LU 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 programming
0 引言
基线算法是一种线性规划的新算法,具有操作方便,迭代次数小,效率高,数值稳定性好等特点,是单纯形法的发展(参见[1])。我们陆续将此算法推广到与线性规划有关的其它规划。本文旨在将此算法推广到多目标规划。较单纯形法而言,用基线算法解决完全分层多目标规划,步骤更简洁,易操作,运算速度更快。
1 简单完全分层多目标规划的基线算法
1.1 算法的形成
讨论完全分层多目标规划问题
L -max [v s =P s c T s x ]m
s =1
(1)
s.t.Ax [b
x \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 T
s 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 q
x i \0(i =1,,,n +q )
或将约束条件简写为
s.t.A x +(x n +1,,,x n +q )T =b
x i \0(i =1,,,n +q )
首先用基线算法求解第一优先层的最优值。即求解线性规划问题
max v 1=c 11x 1+,c 1n x n
s.t.A x +(x n +1,,,x n +q )T =b
x i \0(i =1,,,n +q )
其初表为(表1):
表1
x 1
x 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 +q
b 1,,,,,,,,a i 1a i 2,a in a i,n +1,a i,n +q b i ,,,,,,,,a q 1
a q 2
,
a qn a q,n +1
,
a q,n +q
b q
设求得的最优值为v *
1,其最优表为表2,将v 1=v *
1代入此最优表,并将第二层目标列入此表得新表(表3),进入第二层次目标的求解过程。
表2
x 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 +q
A 1+
B 1v 1,,,,,,,, ,
a c i 1a c i 2,a c in a c i ,n +1
,a c i,n +q
A i +
B i v *
1,,,,,,,, ,a c q 1
a c q 2
,
a c qn
a c q,n +1,
a c q,n +q
A q +
B q v 1
表3
51
第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[5
x2[2
-x1-x2+x3[4
x1,x2,x3\0
解第一步,引入松弛变量x4,x5,x6.化为标准型
L-m ax[P1(x1+3x2),P2(x1+2x3),P3(-x1-2x2-x3)]
s.t.x1+x2+x4=5
x2+x5=2
-x1-x2+x3+x6=4
x i\0(i=1,,,6)
第二步,列出第一层初表(表4)
表4
x1x2x3x4x5x6RH S
130000v1
1101005
0100102
-1-110014
x1进基,得基线表(表5)。
表5
x1x2x3x4x5x6RH S
130000v1v1\0
0[-2]01005-v1v1[5
0100102
0210014+v1v1\-4
旋转得(表6):
表6
x1x2x3x4x5x6RH S
1003/20015/2-v1/2v1[15
010-1/200-5/2+v1/2v1\5
0001/2109/2-v1/2v1[9*
0011019
已知最优表,v*1=9。
第三步,令代入初表并将第二层目标函数加入最优表(表7):
表7
x 1x 2x 3x 4x 5x 6RH S 102000v 21003/2003010-1/20020001/21000
1
1
1
9
x 1、x 2进基,得基线表(表8),表8已是最优表。
表8
x 1
x 2x 3x 4x 5x 6RH S 001-3/400v 2/2-3/2
v 3\3
1003/2003010-1/20020001/2100
7/4
1
-v 2/2+21/2
v 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 ,此时,下一层次的求解不必再进行,出现这种情况时说明,以后各优先层次的目标函数在问题中不起作用。
为避免出现这种情况,可进行如下的修正)))宽容完全分层多目标规划的基线算法。
表9
x 1x 2x 3x 4x 5x 6RH S -1-2-1000v 3001-3/40091003/2003010-1/20020001/21000
7/40
1
表10
x 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\-160
1
7v 3+112
v 3\-16
2 宽容完全分层多目标规划的基线算法
宽容分层算法的基本思想是:从第二层起,在对每一层求解之后给其最优值以适当的宽容,使得下一层次的可行域以适当的放宽,以前一层次目标函数的最优值的偏差,换取后一层次目标函数值的改善。
设给出第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)。
x是由宽容完全分层多目标基线算法得到的最优解,则
证明因为v*k是第k(k=1,,,m-1)个层次的最优值,由宽容分层基线算法的运算步骤可知,
x)\v*k-D k,k=1,,m-1.
x I X(3)
f k(
假设
x|E X(f,X),则一定存在某x*I X,且有f(x*)>f( x),也即
f k(x*)>f k( x),k=1,,,m(4)
x),这样,x*即是由(3)和(4)知有,f k(x*)>f k( x)\v*k-D k,(k=1,,,m-1)且f m(x*)>f m(
x是第m优先层次的最优解矛盾。问题得证。
第m层问题的可行解,这和
例2以上题为例.设D1=0,D2=2
第一步,第二步同上题.
对第三步因为D1=0,所以不必增加新变量,依原题步骤进行即可.
第四步,将表8第一行中v2用v*2-2=21-2=19代入,其余行v2仍用v*2=21代入,将第三层目标加入表中,并增加变量x7,其列系数为(0,-1,0,0,0,0),得到表11,变成基线表,得表12,已是最优表.最优值为v*3=-15,此题的最优目标值为v*1=9,v*2=v*2-2=19,v*3=-15.弱有效解为(3,2,8,0,0,0).
比较例1和例2可知,以第2层次目标值减小2为代价,换取了第三层次目标值增加1的结果。
表11
x1x2x3x4x5x6x7RH S
-1-2-10000v3
001-3/400-18
1003/20003
010-1/20002
0001/21000
0007/40100
表12
x1x2x3x4x5x6x7RH S
0001000-4v3-60v3[-15*
001000-1-3v3-37v3[-37/3
10000006v3+93v3\-31/2
[-14
0100000-2v3-28v3
00001002v3+30v3\-15
00000107v3+105v3\-15运算表明,较单纯形法而言,宽容完全分层多目标规划的基线算法具有更为简洁的迭代过程,更快的收敛速度。
参考文献
[1]阮国桢.线性规划基线算法的基本概念[J].计算数学,1999,21(4):441-450.
[2]胡毓达.实用多目标最优化[M].上海:上海科学技术出版社,1990.
[3]徐裕生.优化与决策[M].陕西:陕西科学技术出版社,1998.
[4]胡毓达.多目标规划有效性理论[M].上海:上海科学技术出版社,1994.
[5]Saw aragi Y,Nakayama H,T anino T.Theory of M ultiobjective Optimization[M].Academic Press,Inc.1985.
[6]Gcoffrion A,M.Proper effici ency and the theory of vector maxi m i zation[J],Journal of M athematical Analysis and Applications,1968.22.
ricanxinghuji实习小编一级|消息 | 我的百科 | 我的知道 | 百度首页 | 退出我的贡献草稿箱我的任务为我推荐 新闻网页贴吧知道MP3图片视频百科文库 帮助设置 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 多目标规划 科技名词定义 中文名称：多目标规划 英文名称：multiple objective program 定义：生态系统管理中，为了同时达到两个或两个以上的目标，需要在许多可行性方案中进行选择的整个过程。 所属学科：
生态学（一级学科）；生态系统生态学（二级学科） 本内容由全国科学技术名词审定委员会审定公布 多目标规划是数学规划的一个分支。研究多于一个的目标函数在给定区域上的最优化。又称多目标最优化。通常记为 MOP(multi-objective programming)。 目录 编辑本段 多目标规划 multiple objectives programming 数学规划的一个分支。研究多于一个目标函数在给定区域上的最优化。又称多目标最优化。通常记为 VMP。在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量 多目标规划
一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方面的研究。1896年法国经济学家 V. 帕雷托最早研究不可比较目标的优化问题，之后，J.冯·诺伊曼、H.W.库恩、A.W.塔克尔、A.M.日夫里翁等数学家做了深入的探讨，但是尚未有一个完全令人满意的定义。求解多目标规划的方法大体上有以下几种：一种是化多为少的方法，即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法等；另一种叫分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。对多目标的线性规划除以上方法外还可以适当修正单纯形法来求解；还有一种称为层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。 编辑本段 规划简史 多目标最优化思想，最早是在1896年由法国经济学家V.帕雷托提出来的。他从政治 数学规划 经济学的角度考虑把本质上是不可比较的许多目标化成单个目标的最优 化问题，从而涉及了多目标规划问题和多目标的概念。1947年，J.冯·诺伊曼和O.莫根施特恩从对策论的角度提出了有多个决策者在彼此有矛盾的情 况下的多目标问题。1951年，T.C.库普曼斯从生产和分配的活动中提出多目标最优化问题，引入有效解的概念，并得到一些基本结果。同年，H.W.库恩和 A.W.塔克尔从研究数学规划的角度提出向量极值问题,引入库恩-塔克尔有效解概念，并研究了它的必要和充分条件。1963年，L.A.扎德从控制论方面提出多指标最优化问题，也给出了一些基本结果。1968年，A.M.日夫里翁为了排除变态的有效解，引进了真有效解概念，并得到了有关的结果。自70年代以来，多目标规划的研究越来越受到人们的重视。至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。 编辑本段 求解方法 化多为少的方法 即
多目标规划 multiple objectives programming 数学规划的一个分支。研究多于一个目标函数在给定区域上的最优化。又称多目标最优化。通常记为VMP。在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方面的研究。1896年法国经济学家V.帕雷托最早研究不可比较目标的优化问题，之后，J.冯·诺伊曼、H.W.库恩、A.W.塔克尔、A.M.日夫里翁等数学家做了深入的探讨，但是尚未有一个完全令人满意的定义。求解多目标规划的方法大体上有以下几种：一种是化多为少的方法，即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法等；另一种叫分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。对多目标的线性规划除以上方法外还可以适当修正单纯形法来求解；还有一种称为层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。 1947年，J.冯·诺伊曼和O.莫根施特恩从对策论的角度提出了有多个决策者在彼此有矛盾的情况下的多目标问题。1951年，T.C.库普曼斯从生产和分配的活动中提出多目标最优化问题，引入有效解的概念，并得到一些基本结果。同年，H.W.库恩和A.W.塔克尔从研究数学规划的角度提出向量极值问题，引入库恩-塔克尔有效解概念，并研究了它的必要和充分条件。1963年，L.A.扎德从控制论方面提出多指标最优化问题，也给出了一些基本结果。1968年，A.M.日夫里翁为了排除变态的有效解，引进了真有效解概念，并得到了有关的结果。自70年代以来，多目标规划的研究越来越受到人们的重视。至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。 化多为少 即把多目标规划问题归为单目标的数学规划（线性规划或非线性规划）问题进行求解，即所谓标量化的方法，这是基本的算法之一。 ①线性加权和法对于多目标规划问题（VMP），先选取向量 要求λi>0(i=1,2，…,m) 作各目标线性加权和
122 §17.借助于Matlab 用贯序算法求解目标规 划问题 虽然Matlab 没有提供直接求解目标规划的优化工具，但是根据目标规划的求解思路——单纯形方法。我们可以将一个目标规划问题分解成若干线性规划问题，通过序贯式算法借助于Matlab 优化工具进行求解。 例1：教材第6章第3节中的目标规划问题： - + - + +++=3 322211)(min d p d d p d p Z 11221≤+x x 01121=-+-+ - d d x x 10 22221=-+++ -d d x x 56 1083321=-+++ -d d x x ) 3,2,1(0 ,,,21=≥+ -i d d x x i i 首先将上述问题化为标准形式： - + - + +++=3 322211)(min d p d d p d p Z 112321=++x x x 01121=-+-+ -d d x x
123 10 22221=-+++ -d d x x 56 1083321=-+++ -d d x x ) 3,2,1(0 ,,=≥+ -i d d x i i i 然后按照以下步骤分解计算： 第一步：求解如下线性规划问题： min d1 2x1+x2+x3=11 x1-x2+d1_-d1=0 x1,x2,x3>=0,d1_>=0,d1>=0 对上述线性规划问题，可以借助于Matlab 优化工具中的linprog 函数求解，函数调用命令为： [x,fval]=linprog(f,[],[],Aeq,beq,lb,[]) 其中，参数如下： Aeq= 2 1 1 0 0 0 0 0 0 1 -1 1 -1 beq= 11 0 f= 0 0 0 1 0 0 0 0 lb=
1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min Λ 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x Λ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
多目标线性规划的若干解法及MATLAB 实现 一．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ， 12(,,,)T r Z Z Z Z = . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx = 约束条件：0 Ax b x ≤?? ≥? （3） 二．MATLAB 优化工具箱常用函数[3] 在MA TLAB 软件中，有几个专门求解最优化问题的函数，如求线性规划问题的linprog 、求有约束非线性函数的fmincon 、求最大最小化问题的fminimax 、求多目标达到问题的fgoalattain 等,它们的调用形式分别为： ①.[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) f 为目标函数系数,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为x 的下 限和上限, fval 求解的x 所对应的值。 算法原理：单纯形法的改进方法投影法 ②.[x,fval ]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub ） fun 为目标函数的M 函数, x0为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束
探究多目标电网规划的分层最优化方法 发表时间：2018-04-09T11:05:03.403Z 来源：《基层建设》2017年第36期作者：杜娟1 胡美玲1 刘宝伟1 齐俊杰2 徐世勇2 张 [导读] 摘要：电网是电力系统运行必不可少的一部分，其输电能力对人们日常生活与经济发展都具有重要作用。 1国网山西省电力公司忻州供电公司山西省 034000；2国网山西省电力公司定襄县供电公司山西省 035400 摘要：电网是电力系统运行必不可少的一部分，其输电能力对人们日常生活与经济发展都具有重要作用。本文就多目标电网规划在智能电网的条件下存在的问题进行分析，并对基于智能电网条件下的多目标电网的规划提出参考要点，以此供各位借鉴交流。 关键词：多目标；电网规划；分层最优化；优化方法 引言 随着我国经济的快速发展，能源的消耗与负荷的增长在大幅上升，对电力的需求日益突出。分布式电源DG因其清洁友好、发电方式灵活、供电可靠等特点越来越受到关注。分布式电源接入配电网，会使得配电网的节点电压、支路潮流等发生改变，在给配电网带来许多效益的同时，也会有一些影响。分布式电源不合理的接入位置和接入的容量会引起配电网运行成本、网损等指标出现不利的改变，所以对分布式电源的优化配置是十分必要的。 1多目标电网规划中存在的问题 1.1数学模型复杂 该问题可以划分为两个方面：①目标函数问题。电网优化方面需要考虑到多个因素，如安全性、经济性，若要使两者能够起到互相促进的作用，往往会将安全性指标中能够换算为经济形式的因素，即缺点损失费，化为经济形式并直接代入到目标函数中。从理论层面而言，该方式具有很好的可行性，然而在实际应用中却会存在一些问题，如方案研究阶段中，缺点损失费用要远远少于投资费用的占比，也导致了在进行方案优化时没能够将其置于首要位置，从而使得整个方案无法全面满足安全性和经济性的要求；②约束条件问题。多目标电网规划中，保证安全性依然是最为重要的事情，只有在保证安全的前提下才可以考虑经济性问题，另外，需要将可靠性指标进行转变，使其成为经济形式，才可以被代入到相应的函数中进行计算，然而虽然指标众多，但真正能够在函数计算中起到作用的指标却屈指可数，这也导致了计算过程复杂、计算精度难以优化的问题出现。 1.2人员技术水平不足 在输电规划工作中，除了专业人士外也有部分缺乏工作经验的人员参与。非专业人士在面对一些问题时不能及时进行解决，对相关工作的理解程度也有限，这会使工作中的问题得不到全面有效解决，特别是在一些对技术水平要求较高的工作中，若工作人员计算结果不够准确，会导致工作无法顺利进行。所以，在人员的选用上一定要保证其专业性，如此才能更好地完成电网规划建设工作。 1.3研究对象规模有限 我国电力事业的发展态势持续良好，并在不断优化着电网规划方面的建设，但在进行大规模电网规划时，却也会受到限制，尤其是数学方法方面。在多目标电网规划中，传统数学方法已经难以发挥作用，利用此类方法计算往往会耗费大量的时间，并且准确性不高。虽然如今已经有了一些新型的方法可以应用，如应用效果较佳的遗传算法，其在应用时可以有效优化传统方法中的弊端，最终获得最优解，但从实际应用情况来看，此类方法在很多方面还未完全成熟，尤其在应用到大规模电网求解时，其局限性会十分突出。 1.4分层优化还不够成熟 利用智能电网进行输电需要进行分层优化，但是目前分层优化没有起到实际应有的作用，形式化问题比较严重，虽然暂时对输电工作没有造成太大的影响，可长期以往必然会造成如供电不稳定这样的问题。在规划过程中，需要有统一的参考条件和数据，这样才能及时有效的解决问题，避免电网不稳定等情况的发生。 2多目标电网规划分层的最优化方法 2.1传统意义上的逐步倒推法 该方法的应用也可以产生很大的价值，如其具有拓展性意义，同时也具有实践意义，但传统方式毕竟较为落后，要使其发挥作用需要对其进行不断的优化、完善和创新，逐步倒推法的应用，其最终目的是为了能够使电网规划质量得以提升，并满足经济性要求。安全性是所有电力建设项目中均需要遵循的原则，在此方面也不另外，然而却也有所不同，如分析指导方面，要保证该方面处于安全可靠的状态下，才能够保证之后的校正检验计算方法合理有效。在很多电网规划中均会应用到该方法，且往往能够产生不错的效果，但在应用时却也难以充分保证经济性、可靠性的综合优化，这也是导致电网规划发展缓慢的原因之一。 2.2粒子群遗传算法 粒子群算法简单易行，但在搜索后期容易陷入局部最优，导致出现早熟现象；而遗传算法较通用，且并行性好，但是局部搜索能力较差，在后期搜索效率比较低。本文将两者结合互补，并引入小生境技术的方法对其进行改进。小生境[11]是指特定环境下的一种生存环境，生物在其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后代。在基于小生境的粒子群遗传算法中，首先利用遗传算法进行全局搜索，之后根据小生境技术将粒子划分到各自的小生境群体中，在每一个小生境群体中利用PSO更新自身的位置及速度，其中群体最优值只在此群体中有效。在小生境粒子群遗传算法中，关键的一步是划分种群，也就是要确定小生境群体的半径。 2.3项目资金的合理运用 国家在智能电网输电项目上给予的资金是有限的，因此在制定多目标电网规划中要选择质量高、经济效益好且成本较低的方案，杜绝铺张浪费的现象。在以往的工作中，部分工作人员对投入与产出的关系存在误解，认为投入的资金越多，收获的效果越高。如X市的智能电网多目标输电规划项目，投入了巨额资金，结果其成效与投资相对较少的邻市相差无几。该市相关部门领导事后总结经验教训，认为在项目方案的选择中应加强对资金利用效率的重视，利用科学的手段计算出投入与产出的比例，在保证工作质量的前提下选择价格相对低廉的方案。 2.4以安全可靠性为目标的建设规划法 该方法在应用时会将负荷减少、能量增加作为主要目标，电网规划时，启发式方法的应用尤为重要，其可以使拓展方案要求达到标准，该方法的应用中可以明显的看出灵敏度较高，因此其分析过程也会相对简便，但分析结果质量并不会受到不良影响。如在进行资金规划时，输电设备是重要的组成部分，需要将此部分资金融入到整个方案中，并进行优化设计，在该方法的应用下可以很好的保证资金投入
%遗传算法解决多目标函数规划 clear clc syms x; %Function f1=f(x) f1=x(:,1).*x(:,1)/4+x(:,2).*x(:,2)/4; %function f2=f(x) f2=x(:,1).*(1-x(:,2))+10; NIND=100; MAXGEN=50; NV AR=2; PRECI=20; GGPA=0.9; trace1=[]; trace2=[]; trace3=[]; FielD=[rep([PRECI],[1,NV AR]);[1,1;4,2];rep([1;0;1;1],[NV AR])]; Chrom=crtbp(NIND,NV AR*PRECI); v=bs2rv(Chrom,FielD); gen=1; while gen 桂林电子科技大学 数学与计算科学学院实验报告 实验室：06406 实验日期： 2014年12月6日 院（系） 数学与计算科学学院 年级、专业、班级 12007301 姓名 成绩 课程 名称 运筹学实验 实验项目 名 称 目标规划算法实现 指导 教师 南江霞 一 、实验目的 1、掌握目标规划的数学模型创建方法； 2、掌握目标规划问题的图解法和单纯形法； 3、掌握目标规划问题的软件求解； 4、掌握目标规划问题的满意解的分析方法。 二、实验原理 利用WinQSB 和Lingo 的软件关于线性方程组求解的方法对问题求解。 三、使用仪器，材料 实验指导书、课本、WinQSB 和Lingo 软件。 四、实验内容与步骤 某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。已知除外 购件外，生产一台录音机需要甲车间加工2小时，乙车间装配1小时；生产一台电视机 需要甲车间加工1小时，乙车间装配3小时。两种产品生产出来后均需要经过检验、销 售等环节。已知每台录音机检验销售费用为50元，每电视机检验销售费用为30元。又 甲车间每月可用生产工时为120小时，车间管理费用为80元/小时；乙车间每月可用的 生产工时为150小时，车间管理费用为20元/小时。估计每台录音机利润为100元，每 台电视机利润为75元，又估计下一年度内平均每月可销售录音机50台，电视机80台。 工厂制定月度计划的目标如下： 第一优先级：检验和销售每月不超过4600元； 第二优先级：每月销售录音机不少于50台； 第三优先级：甲乙两车间的生产工时得到充分的利用； 第四优先级：甲车间加班不超过20小时； 第五优先级：每月销售电视机不少于80台； 第六优先级：两个车间加班总时间要有控制； 试确定该厂为达到以上目标的最优月度计划生产数字。 根据题意我们可以得到如下的目标规划： )4()4(min 21655642134231++-+---++++++++=d d P d P d P d d P d P d P z §18. 运用目标达到法求解多目标规划 用目标达到法求解多目标规划的计算过程，可以通过调用Matlab软件系统优化工具箱中的fgoalattain函数实现。 在Matlab的优化工具箱中，fgoalattain函数用于解决此类问题。其数学模型形式为： minγ F(x)-weight ·γ≤goal c(x) ≤0 ceq(x)=0 A x≤b Aeq x=beq lb≤x≤ub 其中，x，weight，goal，b，beq，lb和ub为向量；A和Aeq为矩阵；c(x)，ceq(x)和F(x)为函数。 调用格式： x=fgoalattain(F,x0,goal,weight) x=fgoalattain(F,x0,goal,weight,A,b) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq) 134 x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2) [x,fval]=fgoalattain(…) [x,fval,attainfactor]=fgoalattain(…) [x,fval,attainfactor,exitflag,output]=fgoalattain(…) [x,fval,attainfactor,exitflag,output,lambda]=fgoalattain(…) 说明：F为目标函数；x0为初值；goal为F达到的指定目标；weight为参数指定权重；A、b为线性不等式约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、ub为变量x的上、下界向量；nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x)；options中设置优化参数。 x返回最优解；fval返回解x处的目标函数值；attainfactor返回解x处的目标达到因子；exitflag描述计算的退出条件；output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。 例1：教材第6章第4节第二小节，即生产计划问题： 某企业拟生产A和B两种产品，其生产投资费用分别为2100元/t和4800元/t。A、B两种产品的利润分别为3600元/t和6500元/t。A、B产品每月的最大生产能力分别为5t和8t；市场对这两种产品总量的需求每月不少于9t。试问该企业应该如何安排生产计划，才能既能满足市场需求，又节约投资，而且使生产利润达到最大最。 135 -253- 第二十一章 目标规划 §1 目标规划的数学模型 为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。 例1 某工厂生产I ，II 两种产品，已知有关数据见下表 I II 拥有量 原材料 kg 2 1 11 设 备 hr 1 2 10 利润 元/件 8 10 试求获利最大的生产方案。 解 这是一个单目标的规划问题，用线性规划模型表述为： 21108max x x z += ?????≥≤+≤+0,1021122 12121x x x x x x 最优决策方案为：62,3,4**2*1===z x x 元。 但实际上工厂在作决策方案时，要考虑市场等一系列其它条件。如 （i ）根据市场信息，产品I 的销售量有下降的趋势，故考虑产品I 的产量不大于产品II 。 （ii ）超过计划供应的原材料，需要高价采购，这就使成本增加。 （iii ）应尽可能充分利用设备，但不希望加班。 （iv ）应尽可能达到并超过计划利润指标56元。 这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解决这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。 1. 正、负偏差变量 设d 为决策变量的函数，正偏差变量}0,max{0d d d -=+表示决策值超过目标值的部分，负偏差变量}0,min{0d d d --=-表示决策值未达到目标值的部分， 这里0d 表示d 的目标值。因决策值不可能既超过目标值同时又未达到目标值，即恒有0=?-+d d 。 2. 绝对约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。如：例1的目标函数21108x x z +=可变换为目标约束561081121=-+++-d d x x 。绝对约束11221≤+x x 可变换为目标约束 1122221=-+++-d d x x 。 Excel规划求解工具在多目标规划中的应用 摘要：多目标决策方法是从20世纪70年代中期发展起来的一种决策分析方法。该方法已广泛应用于人口、环境、教育、能源、交通、经济管理等多个领域。文章采用多目标决策方法中分层序列法的思想，应用excel的规划求解工具，对多目标规划问题进行应用研究，并以实例加以说明。 abstract： multi-objective decision method is a kind of decision analysis method from the mid 1970s. the method has been widely used in population， environment， education，energy， traffic， economic management， and other fields. this paper uses the lexicographic method of multi-objective decision method and makes some researches on the multi-objective problem using the excel solver tool and an example to illustrate. 关键词： excel规划求解；多目标规划；分层序列法 key words： excel solver；multi-objective programming；the lexicographic method 中图分类号：tp31 文献标识码：a 文章编号：1006-4311（2013）21-0204-02 0 引言 excel中的规划求解工具只能对单目标的问题进行求解。当遇到多目标问题时，可以把多目标问题先转化为单目标问题，然后求解。 第13卷 第4期运 筹 与 管 理 Vol.13,No.42004年8月OPERAT IO NS RESEARCH AN D M ANA GEM EN T SCI EN CE Aug.2004 收稿日期:2003-10-27 基金项目:陕西省教育厅专项科研基金资助项目(03jk065);西安建筑科技大学基础研究基金资助项目(02BR01) 作者简介:卢志义(1973-),男,内蒙古包头市人,硕士研究生,从事最优化理论研究;徐裕生(1950-),西安建筑科技大学理学院教授,主要从事最优化理论和不动点理论的研究。 完全分层多目标规划的基线算法 卢志义, 徐裕生, 马春晖 (西安建筑科技大学理学院,陕西西安710055) 摘 要:本文采用基线算法求解完全分层多目标规划问题。给出了简单完全分层多目标规划基线算法的求解步骤,并对其进行了修正,从而得到完全分层多目标规划的宽容基线算法。并给出了两个计算实例。关键词:运筹学;宽容算法;基线算法;多目标规划 中图分类号:O22116 文章标识码:A 文章编号:1007-3221(2004)04-0050-05 Th e Basic Line Algorithm for Complete Tratified Mu ltiobjective Programmin g LU 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 programming 0 引言 基线算法是一种线性规划的新算法,具有操作方便,迭代次数小,效率高,数值稳定性好等特点,是单纯形法的发展(参见[1])。我们陆续将此算法推广到与线性规划有关的其它规划。本文旨在将此算法推广到多目标规划。较单纯形法而言,用基线算法解决完全分层多目标规划,步骤更简洁,易操作,运算速度更快。 1 简单完全分层多目标规划的基线算法 1.1 算法的形成 讨论完全分层多目标规划问题 L -max [v s =P s c T s x ]m s =1 (1) s.t.Ax [b x \0 §5.3 目标规划模型 1. 目标规划模型概述 1)引例 目标规划模型是有别于线性规划模型的一类多目标决策问题模型，通过下面的例子，我们可看出这两者的区别。 例1 某工厂的日生产能力为每天500小时，该厂生产A 、B 两种产品，每生产一件A 产品或B 产品均需一小时，由于市场需求有限，每天只有300件A 产品或400件B 产品可卖出去，每出售一件A 产品可获利10元，每出售一件B 产品可获利5元，厂长按重要性大小的顺序列出了下列目标，并要求按这样的目标进行相应的生产。 （1）尽量避免生产能力闲置； （2）尽可能多地卖出产品，但对于能否多卖出A 产品更感兴趣； （3）尽量减少加班时间。 显然，这样的多目标决策问题，是单目标决策的线性规划模型所难胜任的，对这类问题，须采用新的方法和手段来建立对应的模型。 2）相关的几个概念 （1）正、负偏差变量+ d 、- d 正偏差变量+ d 表示决策值 ) ,,2,1(n i x i =超过目标值的部分；负偏差变量 - d 表示决策值 ) ,,2,1(n i x i =未达到目标值的部分；一般而言，正负偏差变量 + d 、- d 的相互关系如下： 当决策值 ) ,,2,1(n i x i =超过规定的目标值时， ,0=>- + d d ；当决策值 ),,2,1(n i x i =未超过规定的目标值时，0 ,0>=- + d d ；当决策值 ) ,,2,1(n i x i =正好等于规定的目标值时， ,0==- + d d 。 （2）绝对约束和目标约束 绝对约束是必须严格满足的等式约束或不等式约束，前述线性规划中的约束 条件一般都是绝对约束；而目标约束是目标规划所特有的，在约束条件中允许目标值发生一定的正偏差或负偏差的一类约束，它通过在约束条件中引入正、负偏差变量+ d 、- d 来实现。 （3）优先因子（优先级）与权系数 目标规划问题常要求许多目标，在这些诸多目标中，凡决策者要求第一位达到的目标赋予优先因子1P ，要求第二位达到的目标赋予优先因子2P ，……，并规定1+>>k k P P ，即1+k P 级目标的讨论是在k P 级目标得以实现后才进行的（这里 n k ,,2,1 =）。若要考虑两个优先因子相同的目标的区别，则可通过赋予它们 不同的权系数 j w 来完成。 3）目标规划模型的目标函数 目标规划的目标函数是根据各目标约束的正、负偏差变量+ d 、- d 和其优先因子来构造的，一般而言，当每一目标值确定后，我们总要求尽可能地缩小与目标值的偏差，故目标规划的目标函数只能是 ) ,( min - +=d d f z 的形式。我们 可将其分为以下三种情形： （1）当决策值) ,,2,1(n i x i =要求恰好等于规定的目标值时，这时正、负 偏差变量+ d 、- d 都要尽可能小，即对应的目标函数为： ) ( min - + +=d d f z ； （2）当决策值) ,,2,1(n i x i =要求不超过规定的目标值时，这时正偏差变 量+ d 要尽可能小，即对应的目标函数为： ) ( min + =d f z ； （3）当决策值 ) ,,2,1(n i x i =要求超过规定的目标值时，这时负偏差变量 - d 要尽可能小，即对应的目标函数为： ) ( min - =d f z 。 目标规划数学模型的一般形式为： ∑∑=+ +-- =+= K k k lk k lk L l l d w d w P z 1 1 ) ( min 路径规划的分类： 一、按路径维数 根据医学影像设备的不同，穿刺手术可以分二维和三维影像导航手术。所以根据应用场合的不同，路径规划也可分为二维路径规划和三维路径规划。 二维路径规划主要应用在超声、CT、X 射线等设备的导航手术中，三维路径规划则主要应用在三维超声、MRI 等设备的导航手术中。 二、按路径形式 根据穿刺路径特点，路径规划又可按照路径形式的不同分为: R 型、S 型、H 型和混合型，即整个路径包含两种以上不同路径形式组合。 三、按规划方向 由路径形式可以看出路径是可逆的，即理论上针可以从目标靶点沿原路返回穿刺至入针点。所以根据路径规划方向可分为正向规划和逆向规划。正向规划即从入针点到目标靶点的穿刺规划，逆向规划是利用针路的可逆性，从目标靶点出发穿刺可以选择的入针区域，来优化入针位姿和整个路径。 四、按规划算法 路径规划按算法大体可分为数值法、搜索法和反解法三大类。 五、算法概述 (一)数值法是通过数值计算的方法来优化路径，通常是利用目标函数的最大或最小值来得到最优路径的方 法。 1)概率法是考虑路径误差的随机性，利用数学概率原理计算穿刺成功率最大的路径。 2)目标函数法是考虑一些优化的指标(如路径最短，绕开障碍物等)，建立目标函数，通过计算目 标函数得到最优解。 (二)搜索法是根据路径形式特点，利用计算机的人工智能搜索算法来搜索可行性路径。 1)路线图法主要思想是将自由空间转换成为一维线段所组成的网络,所要找的路径被局限在这个 网络之中,即将路径规划问题转化成图的搜索问题。 i.可视图法是由麻省理工学院的Tomás Lozano-Pérez和IBM研究院的MichaelA.Wesley 于1979年提出的。其最大特点是将障碍物用多边形包围盒来表达。图1表示某一环境 空间，s、g分别称为起始点和目标点。O1和O2表示两个障碍物。图2是构造出的对 应图1的可视图。利用搜索算法规划出从起始点至目标点的最优路径。 27. 多目标规划 一、线性规划的局限性 1. 线性规划要求所求解问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足； 2. 线性规划只能处理单目标的优化问题，从而对一些次目标只能转化为约束处理，而实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分； 3. 线性规划在处理问题时，将各个约束（也可看成目标）的地位看成同等重要，实际问题中，各个目标的重要性有层次上的差别，在同一层次也可能有不同权重； 4. 线性规划寻找最优解，而许多实际问题只要找到满意解就可以了。 例1 (线性规划——生产安排问题) 某企业生产甲、乙两种产品，需要用到A,B,C三种设备，每天产品盈利与设备使用工时及限制如下表： 问：该企业应如何安排生产，能使总利润最大？ 解：设甲乙产品的产量分别为x 1, x 2，建立线性规划模型： 12121212max 200300 s. t. 2212 416 515 ,0 z x x x x x x x x =++≤≤≤≥ 用Lingo 可求得最优解：x 1=3, x 2=3, z *=1500. 但实际上，企业的经营目标不仅仅是利润，还需要考虑多个方面，比如：增加下列因素（目标） （1） 力求使利润不低于1500元； （2） 考虑市场需求，甲乙两种产品的产量比应尽量保持1:2； （3） 设备A 位贵重设备，严格禁止超时使用； （4）设备C 可以适当加班，但要控制，设备B 既要求充分利用，又尽可能不加班，在重要性上，设备B 是设备C 的3倍。 这就需要用目标规划。 二、目标规划的基本概念 1. 设置偏差变量 偏差变量——表示实际值与目标值之间的差异； d +——表示超出目标的差值，称为正偏差变量；当实际值超过目标值时，有d - = 0，d + > 0; d -——表示未达到目标的差值，称为负偏差变量；当实际值未达到目标值时，有d + = 0，d - > 0. 注：若实际值与目标值一致，有d - = d + = 0.运筹学实验二目标规划算法实现
§18运用目标达到法求解多目标规划
数学建模算法大全目标规划
Excel规划求解工具在多目标规划中的应用
完全分层多目标规划的基线算法
目标规划模型
轨迹规划分类及算法
Matlab学习系列27.-多目标规划
相关主题
文本预览