多目标规划

《多目标规划》由会员分享，可在线阅读，更多相关《多目标规划（9页珍藏版）》请在装配图网上搜索。

1、方入事r-rrnKiku p.Southwest Ji aptoni优化与决策多目标线性规划的若干解法及 MATLAB 实现指导老师:黄天民教授学生姓名: 丁 飞多目标线性规划的若干解法及MATLAB实现丁宏飞（西南交通大学 数学学院 四川 成都 610031）摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍了理想点法、线性加权和法、最大最小法、目标规划法1 ，然后给出多目标线性规划的模糊数学解法，最后对每种解法给出例子，并用Ma tlab软件加以实现。 关键词：多目标线性规划 Matlab 模糊数学Some solutions of Multi-objectiv

2、e linearprogramming and realized by MatlabDing HongfeiSchool of Mathematics, Southwest Jiaotong University ,Chengdu, 610031Abstract: The basic ideas to solve Multi-objective linear programming are transforming the multi-objective problem into single-objective planning, This paper introduces the idea

3、l 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 mathematic

4、s一引言多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不 可公度性,要求使所有目标均达到最优解是不可能的,因此多目标规划问题往往只是求其有 效解（非劣解）。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、 最大最小法、目标规划法，然而这些方法对多目标偏好信息的确定、处理等方面的研究工作 较少，本文也给出多目标线性规划的模糊数学解法。多目标线性规划模型多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函数,其数学模型表示为：z = c x + c x HF c x111 112 21n nz = c x + c x HF c x

5、1)max 22112222 n nz = c x + c x HF c xrr 1 1 r 2 2rn n约束条件为：a x + a x HH a x b11 11221n n 1a x + a x HH a x b21 122 22n n 22)a x + a x HH a x 012n若(1)式中只有一个z = c x + c x + + c x，则该问题为典型的单目标线性规ii 1 1i 2 2in n划。我们记：A = (a ), C = (c ), b = (b ,b，,b )t , x = (x ,x，x )t ，j mxnj rxn12m12nZ = (Z , Z，,Z)T.1

6、 2 r 则上述多目标线性规划可用矩阵形式表示为:max Z = CxC Ax -(3)I x 0三. MATLAB优化工具箱常用函数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 所对应的值。算法原理：单纯形法

7、的改进方法投影法.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,

8、fval =fgoalattain(fun,xO,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个单目标问题：minZ (x), j二1,2,r，设其最优值为Z*，称 xwD jjZ* = (Z*,Z*)为值域中的一个理想点，因为一般很难达到。于

9、是，在期望的某种度量 12 r之下，寻求距离Z *最近的Z作为近似值。一种最直接的方法是最短距离理想点法，构造评价函数申(Z)二-Z*2 ,H i=1然后极小化9 Z(x)，即求解min 申Z (x)=xeD并将它的最优解x*作为(3)在这种意义下的“最优解” 例 1：利用理想点法求解max f (x) = -3 x + 2 x1 1 2max f (x) = 4x + 3x2 1 2s.t 2x + 3x 18122 x + x 012解：先分别对单目标求解： 求解f(x)最优解的MATLAB程序为 f=3;-2; A=2,3;2,1; b=18;10; lb=0;0; x,fval=lin

10、prog(f,A,b,lb)结果输出为： x = 0.00006.0000fval = -12.0000即最优解为 12.求解f (x)最优解的MATLAB程序为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.0000fval =-24.0000即最优解为 24.于是得到理想点：(12，24). 然后求如下模型的最优解xeDs.t 2x + 3x 18122 x + x 012MATLAB程序如下： A=2,3;2,1; b=18;10; x0=1;1; lb=0;0; x=fmi

11、ncon(-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 5.6488则对应的目标值分别为f (x) 9.7172,f (x) = 19.0536.124.2 线性加权和法 在具有多个指标的问题中，人们总希望对那些相对重要的指标给予较大的权系数，因而 将多目标向量问题转化为所有目标的加权求和的标量问题，基于这个现实，构造如下评价函 数，即min Z (x) = w Z (x)将它的最优解x*作为(3)在线性加权和意义下的“最优解”(w为加权因子，其选取 i的方法很多，有专家打分法、容限法

12、和加权因子分解法等) .例2：对例1进行线性加权和法求解。(权系数分别取w 0.5，w 0.5)12解：构造如下评价函数，即求如下模型的最优解。min0.5x(3x 2x ) + 0.5x(-4x 3x )1 2 1 2s.t 2x + 3x 18122 x + x 012MATLAB程序如下: f=-0.5;-2.5; A=2,3;2,1; b=18;10; lb=0;0; x=linprog(f,A,b,lb)结果输出为：x =0.0000 6.0000则对应的目标值分别为f (x) 12,f (x) 18.124.3 最大最小法在决策的时候，采取保守策略是稳妥的，即在最坏的情况下，寻求最

13、好的结果，按照此想法，可以构造如下评价函数，即申(Z) max Z 1i r 然后求解：min叽Z(x) min max Z (x)xwDxwD 1i 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.00006.0000fval = -12-18则对应的目标值分别为 f(x)12, f(x)18.124.4 目标规划法ApprZ(x) T Z0(4)xeD并把原多目标线性规划(3) minZ(x) 称为和目标规划(4)相对应的多目标线性规划。xeD为了用数量来描述(4)

14、，我们在目标空间Er中引进点Z (x)与Z 0之间的某种“距离”DZ(x)，Z0 Q 九(Z (x)-Z*)2i/2i iii1这样(4)便可以用单目标minDZ(x)，Z0来描述了。xeD例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

15、,weight,A,b,lb,)结果输出为： x =0.0000fval = -126.0000-18则对应的目标值分别为fi(x)二12, f2(x)二18.4.5 模糊数学求解方法 4由于多目标线性规划的目标函数不止一个，要想求得某一个点作x *，使得所有的目标函数都达到各自的最大值,这样的绝对最优解通常是不存在的。因此,在具体求解时,需要采取 折衷的方案,使各目标函数都尽可能的大。模糊数学规划方法可对其各目标函数进行模糊化 处理,将多目标问题转化为单目标,从而求该问题的模糊最优解。C Ax 0ii最小值Z-，伸缩因子为d = Z* -Z-,i = 1,2,rii i imax Z = X

16、工 c x 一 d X Z* - d , i = 1,2, ij j ii i5)j=1工a x 0, x , x , , x 01 2 n式(5)是一个简单的单目标线性规划问题。最后求得模糊最优解为：z*=C(x；,xn)T.利用(5)式来求解的关键是对伸缩指标的d确定，d是我们选择的一些常数,由于在多ii目标线性规划中，各子目标难以同时达到最大值Z*，但是可以确定的是各子目标的取值范i围，它满足：Z - Z 0122 x + 3 x 18122 x + x 012MATLAB程序如下：f=0;0;-1; A=3,-2,27;-4,-3,24;2,3,0;2,1,0; b=15;0;18;1

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