多目标规划-matlab程序.doc-资料库

e410082-9778929-4744300845386548633.doc.pdf-第1页.png

第1页 / 共8页

e410082-9778929-4744300845386548633.doc.pdf-第2页.png

第2页 / 共8页

e410082-9778929-4744300845386548633.doc.pdf-第3页.png

第3页 / 共8页

e410082-9778929-4744300845386548633.doc.pdf-第4页.png

第4页 / 共8页

e410082-9778929-4744300845386548633.doc.pdf-第5页.png

第5页 / 共8页

e410082-9778929-4744300845386548633.doc.pdf-第6页.png

第6页 / 共8页

e410082-9778929-4744300845386548633.doc.pdf-第7页.png

第7页 / 共8页

e410082-9778929-4744300845386548633.doc.pdf-第8页.png

第8页 / 共8页

优化与决策 ——多目标线性规划的若干解法及 MATLAB 实现指导老师: XX 教授学生姓名: XX 多目标线性规划的若干解法及 MATLAB 实现丁宏飞（西南交通大学数学学院四川成都 610031）

摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍了理想点法、线性加权和法、最大最小法、目标规划法 [1] ，然后给出多目标线性规划的模糊数学解法 [2] ，最后对每种解法给出例子，并用 Matlab 软件加以实现。关键词：多目标线性规划 Matlab 模糊数学 Some solutions of Multi-objective linear programming and realized by Matlab Ding Hongfei School of Mathematics, Southwest Jiaotong University ,Chengdu, 610031 Abstract: The basic ideas to solve Multi-objective linear programming are transforming the multi-objective problem into single-objective planning, This paper introduces the ideal point method, linear weighted and law, max-min method, the goal programming method, then given multi-objective linear programming Fuzzy mathematics method, finally give examples of each method and used Matlab software to achieve. Key words: Multi-objective Linear Programming Matlab fuzzy mathematics 一．引言多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不可公度性,要求使所有目标均达到最优解是不可能的,因此多目标规划问题往往只是求其有效解(非劣解)。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、最大最小法、目标规划法，然而这些方法对多目标偏好信息的确定、处理等方面的研究工作较少，本文也给出多目标线性规划的模糊数学解法。二．多目标线性规划模型多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函数,其数学模型表示为： c x z     1 1 n n  z c x     2 2 n n       c x z  rn n c x  12 2 c x  22 2  c x 2 2 r c x 11 1 c x 21 1  c x 1 1 r max   r     （1）

约束条件为：         b  1 b  2 a x a x  11 1 1 n n  a x a x  21 1 2 n n     a x a x   1 1 m mn n , x x  1 2 a x 12 2 a x 22 2  a x    2 2 m 0 , , x   n （2）  b m 若（1）式中只有一个 z i  c x 1 1 i  c x 2 2 i   c x in n ，则该问题为典型的单目标线性规划。我们记 : A  ( a )ij m n  , C  ( )ij c r n  , b  ( , b b 1 2 ,  , b m )T , x  ( , x x 1 2 ,  , x n )T ， Z  ( Z Z 1 , 2 ,  , Z r )T . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx Ax b     0 x 约束条件：三．MATLAB 优化工具箱常用函数 [3] （3）在 MATLAB 软件中，有几个专门求解最优化问题的函数，如求线性规划问题的 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 为等式约束系数, lb,ub 为 x 的下限和上限, fval 求解的 x 所对应的值。算法原理：基于 K-T（Kuhn-Tucker）方程解的方法。 ③.[x,fval ]=fminimax(fun,x0,A,b,Aeq,beq,lb,ub) fun 为目标函数的 M 函数, x0 为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为 x 的下限和上限, fval 求解的 x 所对应的值。算法原理：序列二次规划法。 ④.[x,fval ]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub) fun 为目标函数的 M 函数, x0 为初值,goal 变量为目标函数希望达到的向量值, wight 参数指定目标函数间的权重,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为 x 的下限和上限, fval 求解的 x 所对应的值。

算法原理：目标达到法。四．多目标线性规划的求解方法及 MATLAB 实现 4.1 理想点法在（3）中，先求解 r 个单目标问题： min x D  ( ), Z x j j   ，设其最优值为 * 1,2, jZ ，称 r * Z  ( * Z Z 1 , * 2 ,  为值域中的一个理想点，因为一般很难达到。于是，在期望的某种度量 Z * )r 之下，寻求距离 *Z 最近的 Z 作为近似值。一种最直接的方法是最短距离理想点法，构造评价函数然后极小化 [ Z x ( )] (  Z )  ，即求解 min [  x D  ( )] Z x  r  Z [ i i 1  Z * 2 ] i ， r  i 1  [ ( ) Z x i  Z * 2 ] i ，并将它的最优解 *x 作为（3）在这种意义下的“最优解”。例 1：利用理想点法求解 x 2 max ( ) f x 1 ( ) max f x 2 . 2 s t x   1 2 x   1 , x x  1 2 3 2 x    1 3 4 x x   1 2 18 3 x  10 x 2  2  0 解：先分别对单目标求解： f x 最优解的 MATLAB 程序为 ①求解 1( ) >> f=[3;-2]; A=[2,3;2,1]; b=[18;10]; lb=[0;0]; >> [x,fval]=linprog(f,A,b,[],[],lb) 结果输出为：x = 0.0000 6.0000 fval = -12.0000 f x 最优解的 MATLAB 程序为即最优解为 12. ②求解 2( ) >> f=[-4;-3]; A=[2,3;2,1]; b=[18;10]; lb=[0;0]; >> [x,fval]=linprog(f,A,b,[],[],lb) 结果输出为：x =3.0000 4.0000

fval =-24.0000 即最优解为 24. 于是得到理想点：（12，24）. 然后求如下模型的最优解 ( ) 12] f x 1  2  [ f x 2 ( ) 24]  2 ( )] min [ f x  x D  3 . 2 x s t x   1 2 x x   2 1 , x x   1 2 2  0  [ 18  10 MATLAB 程序如下： >> A=[2,3;2,1]; b=[18;10]; x0=[1;1]; lb=[0;0]; >> x=fmincon('((-3*x(1)+2*x(2)-12)^2+(4*x(1)+3*x(2)-24)^2)^(1/2)',x0,A,b,[],[],lb,[]) 结果输出为：x = 0.5268 则对应的目标值分别为 1( ) 9.7172 5.6488 f x  2( ) 19.0536 f x  , . 4.2 线性加权和法在具有多个指标的问题中，人们总希望对那些相对重要的指标给予较大的权系数，因而将多目标向量问题转化为所有目标的加权求和的标量问题，基于这个现实，构造如下评价函数，即 min ( ) Z x x D  r   i 1  ( ) Z x i i 将它的最优解 *x 作为（3）在线性加权和意义下的“最优解”。（ i为加权因子，其选取的方法很多，有专家打分法、容限法和加权因子分解法等）. 例 2：对例 1 进行线性加权和法求解。（权系数分别取 1 0.5  ， 2 0.5  ）解：构造如下评价函数，即求如下模型的最优解。 2 ) 0.5 ( 4 x   2  x 1  3 )} x 2 x  1 18  10 min{0.5 (3  . 2 3 x x s t   1 2 x x   2 1 , x x   1 2 2  0 MATLAB 程序如下： >> f=[-0.5;-2.5; A=[2,3;2,1]; b=[18;10]; lb=[0;0]; >> x=linprog(f,A,b,[],[],lb) 6.0000 结果输出为：x =0.0000 则对应的目标值分别为 1( ) 12 f x  2( ) 18 f x  , . 4.3 最大最小法

在决策的时候，采取保守策略是稳妥的，即在最坏的情况下，寻求最好的结果，按照此想法，可以构造如下评价函数，即 (  Z ) max i Z  1 i r   然后求解： min Z x x D  [  ( )]  min x D  max 1 i r   ( ) Z x i 并将它的最优解 *x 作为（3）在最大最小意义下的“最优解”。例 3：对例 1 进行最大最小法求解：解：MATLAB 程序如下，首先编写目标函数的 M 文件： function f=myfun12(x) f(1)=3*x(1)-2*x(2); f(2)=-4*x(1)-3*x(2); >> x0=[1;1];A=[2,3;2,1];b=[18;10];lb=zeros(2,1); >> [x,fval]=fminimax('myfun12',x0,A,b,[],[],lb,[]) 结果输出为：x =0.0000 fval = -12 则对应的目标值分别为 1( ) 12 , 2( ) 18 f x  . 6.0000 -18 f x  4.4 目标规划法 ( ) Appr Z x x D   Z 0 （4）并把原多目标线性规划（3） min ( ) Z x x D  称为和目标规划（4）相对应的多目标线性规划。为了用数量来描述（4），我们在目标空间 rE 中引进点 ( )Z x 0 Z与之间的某种“距离” ( ) D Z x [ Z ， 0 ]  [ r  i 1  (  i ( ) Z x i  Z * 2 1/ 2 ) ] i 这样（4）便可以用单目标 min [ x D  ( ) D Z x ，来描述了。 Z 0 ] 例 4：对例 1 对进行目标规划法求解：解：MATLAB 程序如下，首先编写目标函数的 M 文件： function f=myfun3(x) f(1)=3*x(1)-2*x(2); f(2)=-4*x(1)-3*x(2); >> goal=[18,10]; weight=[18,10]; x0=[1,1]; A=[2,3;2,1]; b=[18,10]; lb=zeros(2,1); >> [x,fval]=fgoalattain('myfun3',x0,goal,weight,A,b,[],[],lb,[]) 结果输出为：x = fval = 6.0000 -18 则对应的目标值分别为 1( ) 12 0.0000 -12 2( ) 18 f x  f x  , .

4.5 模糊数学求解方法 [4] 由于多目标线性规划的目标函数不止一个,要想求得某一个点作 *x ,使得所有的目标函数都达到各自的最大值,这样的绝对最优解通常是不存在的。因此,在具体求解时,需要采取折衷的方案,使各目标函数都尽可能的大。模糊数学规划方法可对其各目标函数进行模糊化处理,将多目标问题转化为单目标,从而求该问题的模糊最优解。 Ax b     具体的方法为：先求在约束条件： 0 x 下各个单目标 , iZ i 最小值 iZ  ，伸缩因子为 d i  Z * i  ,  Z i i   1,2, r   的最大值 * 1,2, iZ 和 r Z   j max n          1 j      1  n c x ij  d i   Z * i    d i i 1,2, r   j （5）得到 a x kj  , b k k j  1,2,  , m 0, , x x 1 2 ,  , x n  0 式（5）是一个简单的单目标线性规划问题。 , 最后求得模糊最优解为： ** Z  * 1( C x  , x * n )T . 利用(5)式来求解的关键是对伸缩指标的 id 确定, id 是我们选择的一些常数,由于在多目标线性规划中,各子目标难以同时达到最大值 * iZ ，但是可以确定的是各子目标的取值范围，它满足： Z   i Z i  ，所以，伸缩因子为 id 可以按如下取值： Z * i d i  Z * i  Z  i . 例 5：对例 1 进行模糊数学方法求解：解：①分别求得 1( ) f x , f x 在约束条件下的最大值为： * 2( ) Z  (12,24) . ②分别求得 1( ) f x , 2( ) f x 在约束条件下的最小值为： Z    ( 15,0) . 伸缩因子为 id  (27,24) 然后求如下模型的最优解：

15    0   max Z   . 3 x s t   1 4 x   1 2 x   1 2 x   1 , x x  1 2 2 2 27 x  3 24 x  2 3 18 x  2 10 x  2 , 0   MATLAB 程序如下： >>f=[0;0;-1]; A=[3,-2,27;-4,-3,24;2,3,0;2,1,0]; b=[15;0;18;10]; lb=[0;0;0] >> [x,fval]=linprog(f,A,b,[],[],lb) 结果输出为：x = 1.0253 0.8354 5.3165 fval =-0.8354 于是原多目标规划问题的模糊最优值为 ** Z  (7.5571,20.0507) . 五．结论多目线性标规划是优化问题的一种,由于其存在多个目标,要求各目标同时取得较优的值,使得求解的方法与过程都相对复杂. 通过将目标函数进行模糊化处理,可将多目标问题转化为单目标,借助工具软件,从而达到较易求解的目标。参考文献: [1] 林锉云,董加礼. 多目标优化的方法与理论[M]. 长春:吉林教育出版社,1992.8 [2] 宋业新,胡伟文,张建军. 具有模糊系数约束的多目标线性规划[J]. 海军工程大学学报, 2004,16(1):40-44. [3] 龚纯,王正林. 精通MATLAB最优化计算[M]电子工业出版社,2009 [4] 王嫣,张志宏. 模糊线性规划的最优解分析[J]. 北京工商大学学报(自然科学版), 2007,25(5):67-69.

资料库

多目标规划-matlab程序.doc

相关推荐

课程资源

热门标签

最新资料