《多目标线性规划研究生考试考研数学_研究生考试-考研数学.pdf》由会员分享，可在线阅读，更多相关《多目标线性规划研究生考试考研数学_研究生考试-考研数学.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1/8 优化与决策 多目标线性规划的若干解法及 MATLAB 实现 指导老师:学生姓名:学 号:2/8 多目标线性规划的若干解法及 MATLAB 实现 （西南交通大学 数学学院 四川 成都 610031）摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍了理想点法、线性加权和法、最大最小法、目标规划法1，然后给出多目标线性规划的模糊数学解法2，最后对每种解法给出例子，并用 Matlab 软件加以实现。关键词：多目标线性规划 Matlab 模糊数学 Some solutions of Multi-objective linear programming and rea
2、lized by Matlab 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
3、-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 一引言 多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不可公度性
4、,要求使所有目标均达到最优解是不可能的,因此多目标规划问题往往只是求其有效解(非劣解)。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、最大最小法、目标规划法，然而这些方法对多目标偏好信息的确定、处理等方面的研究工作较少，本文也给出多目标线性规划的模糊数学解法。二多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函大学数学学院四川成都摘要求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划本文介绍了理想点法线性加权和法最大最小法目标规划法然后给出多目标线性规划的模糊数学解法最后对每种解法给出例子并用软件标之间的矛盾性和不可公
5、度性要求使所有目标均达到最优解是不可能的因此多目标规划问题往往只是求其有效解非劣解目前求解多目标线性规划问题有效解的方法有理想点法线性加权和法最大最小法目标规划法然而这些方法对多目目标线性规划有着两个和两个以上的目标函数且目标函数和约束条件全是线性函数其数学模型表示为约束条件为若式中只有一个则该问题为典型的单目标线性规划我们记则上述多目标线性规划可用矩阵形式表示为约束条件三优化工3/8 数,其数学模型表示为：111 11221221 122221 122maxnnnnrrrrnnzc xc xc xzc xc xc xzc xc xc x （1）约束条件为：11 11221121 122222
6、1 12212,0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbx xx （2）若（1）式中只有一个1 122iiiinnzc xc xc x，则该问题为典型的单目标线性规划。我 们 记:()ijm nAa,()ijr nCc,12(,)Tmbb bb,12(,)Tnxx xx，12(,)TrZZ ZZ.则上述多目标线性规划可用矩阵形式表示为:max ZCx 约束条件：0Axbx （3）三MATLAB 优化工具箱常用函数3 在 MATLAB 软件中，有几个专门求解最优化问题的函数，如求线性规划问题的 linprog、求有约束非线性函数的 fmincon、求最大最
7、小化问题的 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 所对应
8、的值。算法原理：基于 K-T（Kuhn-Tucker）方程解的方法。.x,fval=fminimax(fun,x0,A,b,Aeq,beq,lb,ub)fun 为目标函数的 M 函数,x0 为初值,A,b 为不等式约束的系数,Aeq,beq 为等式约束大学数学学院四川成都摘要求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划本文介绍了理想点法线性加权和法最大最小法目标规划法然后给出多目标线性规划的模糊数学解法最后对每种解法给出例子并用软件标之间的矛盾性和不可公度性要求使所有目标均达到最优解是不可能的因此多目标规划问题往往只是求其有效解非劣解目前求解多目标线性规划问题有效解的方法有理
9、想点法线性加权和法最大最小法目标规划法然而这些方法对多目目标线性规划有着两个和两个以上的目标函数且目标函数和约束条件全是线性函数其数学模型表示为约束条件为若式中只有一个则该问题为典型的单目标线性规划我们记则上述多目标线性规划可用矩阵形式表示为约束条件三优化工4/8 系数,lb,ub 为 x 的下限和上限,fval 求解的 x 所对应的值。算法原理：序列二次规划法。.x,fval=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)fun 为目标函数的 M 函数,x0 为初值,goal 变量为目标函数希望达到的向量值,wight 参数指定目标函数间的
10、权重,A,b 为不等式约束的系数,Aeq,beq 为等式约束系数,lb,ub 为x 的下限和上限,fval 求解的 x 所对应的值。算法原理：目标达到法。四多目标线性规划的求解方法及 MATLAB 实现 4.1 理想点法 在（3）中，先求解r个单目标问题：min(),1,2,jx DZxjr，设其最优值为*jZ，称*12(,)rZZZZ为值域中的一个理想点，因为一般很难达到。于是，在期望的某种度量之下，寻求距离*Z最近的Z作为近似值。一种最直接的方法是最短距离理想点法，构造评价函数*21()riiiZZZ，然后极小化()Z x，即求解*21min()()riix DiZ xZ xZ，并将它的最
11、优解*x作为（3）在这种意义下的“最优解”。例 1：利用理想点法求解 112212121212max()32max()43.2318210,0f xxxfxxxstxxxxx x 解：先分别对单目标求解：求解1()f x最优解的 MATLAB 程序为 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 大学数学学院四川成都摘要求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划本文介绍了理想点法线性加权和法最大最小法目标规划法然后给出多目标线性规划的模糊数学解法最后对每种解法给出例
12、子并用软件标之间的矛盾性和不可公度性要求使所有目标均达到最优解是不可能的因此多目标规划问题往往只是求其有效解非劣解目前求解多目标线性规划问题有效解的方法有理想点法线性加权和法最大最小法目标规划法然而这些方法对多目目标线性规划有着两个和两个以上的目标函数且目标函数和约束条件全是线性函数其数学模型表示为约束条件为若式中只有一个则该问题为典型的单目标线性规划我们记则上述多目标线性规划可用矩阵形式表示为约束条件三优化工5/8 fval=-12.0000 即最优解为 12.求解2()fx最优解的 MATLAB 程序为 f=-4;-3;A=2,3;2,1;b=18;10;lb=0;0;x,fval=lin
13、prog(f,A,b,lb)结果输出为：x=3.0000 4.0000 fval=-24.0000 即最优解为 24.于是得到理想点：（12，24）.然后求如下模型的最优解 2212121212min ()()12()24.2318210,0 x Df xf xfxstxxxxx x 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 5.6488 则对应的目标值分别为1()9.7172f x,2
14、()19.0536fx.4.2 线性加权和法 在具有多个指标的问题中，人们总希望对那些相对重要的指标给予较大的权系数，因而将多目标向量问题转化为所有目标的加权求和的标量问题，基于这个现实，构造如下评价函数，即 1min()()riix DiZ xZ x 将它的最优解*x作为（3）在线性加权和意义下的“最优解”。（i为加权因子，其选取的方法很多，有专家打分法、容限法和加权因子分解法等）.例 2：对例 1 进行线性加权和法求解。（权系数分别取10.5，20.5）解：构造如下评价函数，即求如下模型的最优解。1212121212min0.5(32)0.5(43).2318210,0 xxxxstxxx
15、xx x MATLAB 程序如下：大学数学学院四川成都摘要求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划本文介绍了理想点法线性加权和法最大最小法目标规划法然后给出多目标线性规划的模糊数学解法最后对每种解法给出例子并用软件标之间的矛盾性和不可公度性要求使所有目标均达到最优解是不可能的因此多目标规划问题往往只是求其有效解非劣解目前求解多目标线性规划问题有效解的方法有理想点法线性加权和法最大最小法目标规划法然而这些方法对多目目标线性规划有着两个和两个以上的目标函数且目标函数和约束条件全是线性函数其数学模型表示为约束条件为若式中只有一个则该问题为典型的单目标线性规划我们记则上述多目标线
16、性规划可用矩阵形式表示为约束条件三优化工6/8 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 则对应的目标值分别为1()12f x,2()18fx.4.3 最大最小法 在决策的时候，采取保守策略是稳妥的，即在最坏的情况下，寻求最好的结果，按照此想法，可以构造如下评价函数，即 1()maxii rZZ 然后求解：1()max()ix Dx Di rminZ xminZ x 并将它的最优解*x作为（3）在最大最小意义下的“最优解”。例 3：对例 1 进行最大最小法求解：解：MATLAB 程
17、序如下，首先编写目标函数的 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 6.0000 fval=-12 -18 则对应的目标值分别为1()12f x,2()18fx.4.4 目标规划法 0()x DAppr Z xZ （4）并把原多目标线性规划（3）min()x DZ x称为和目标规划（4）相对应的多目标线性规划。为了用数量来描述（4
18、），我们在目标空间rE中引进点0()Z xZ与之间的某种“距离”0*2 1/21()()riiiiD Z xZZ xZ，这样（4）便可以用单目标0min()x DD Z xZ，来描述了。例 4：对例 1 对进行目标规划法求解：解：MATLAB 程序如下，首先编写目标函数的 M 文件：function f=myfun3(x)大学数学学院四川成都摘要求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划本文介绍了理想点法线性加权和法最大最小法目标规划法然后给出多目标线性规划的模糊数学解法最后对每种解法给出例子并用软件标之间的矛盾性和不可公度性要求使所有目标均达到最优解是不可能的因此多目标规
19、划问题往往只是求其有效解非劣解目前求解多目标线性规划问题有效解的方法有理想点法线性加权和法最大最小法目标规划法然而这些方法对多目目标线性规划有着两个和两个以上的目标函数且目标函数和约束条件全是线性函数其数学模型表示为约束条件为若式中只有一个则该问题为典型的单目标线性规划我们记则上述多目标线性规划可用矩阵形式表示为约束条件三优化工7/8 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,
20、goal,weight,A,b,lb,)结果输出为：x=0.0000 6.0000 fval=-12 -18 则对应的目标值分别为1()12f x,2()18fx.4.5 模糊数学求解方法4 由于多目标线性规划的目标函数不止一个,要想求得某一个点作*x,使得所有的目标函数都达到各自的最大值,这样的绝对最优解通常是不存在的。因此,在具体求解时,需要采取折衷的方案,使各目标函数都尽可能的大。模糊数学规划方法可对其各目标函数进行模糊化处理,将多目标问题转化为单目标,从而求该问题的模糊最优解。具体的方法为：先求在约束条件：0Axbx 下各个单目标,1,2,iZ ir的最大值*iZ和最小值iZ，伸缩因子
21、为*,1,2,iiidZZir 得到*1112max1,2,1,2,0,0nijjiiijnkjjkjnZc xdZd ira xb kmx xx （5）式（5）是一个简单的单目标线性规划问题。最后求得模糊最优解为：*1(,)TnZC xx.利用(5)式来求解的关键是对伸缩指标的id确定,id是我们选择的一些常数,由于在多目标线性规划中,各子目标难以同时达到最大值*iZ，但是可以确定的是各子目标的取值范围，它满足：*iiiZZZ，所以，伸缩因子为id可以按如下取值：*iiidZZ.例 5：对例 1 进行模糊数学方法求解：解：分别求得1()f x,2()fx在约束条件下的最大值为：*(12,24
22、)Z.分别求得1()f x,2()fx在约束条件下的最小值为：(15,0)Z.大学数学学院四川成都摘要求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划本文介绍了理想点法线性加权和法最大最小法目标规划法然后给出多目标线性规划的模糊数学解法最后对每种解法给出例子并用软件标之间的矛盾性和不可公度性要求使所有目标均达到最优解是不可能的因此多目标规划问题往往只是求其有效解非劣解目前求解多目标线性规划问题有效解的方法有理想点法线性加权和法最大最小法目标规划法然而这些方法对多目目标线性规划有着两个和两个以上的目标函数且目标函数和约束条件全是线性函数其数学模型表示为约束条件为若式中只有一个则该问
23、题为典型的单目标线性规划我们记则上述多目标线性规划可用矩阵形式表示为约束条件三优化工8/8 伸缩因子为(27,24)id 然后求如下模型的最优解：1212121212max.322715432402318210,0Zstxxxxxxxxx x 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 5.3165 0.8354 fval=-0.8354 于是原多目标规划问题的模糊最优值为*(7.5571,20.0507)Z.五结
24、论 多目线性标规划是优化问题的一种,由于其存在多个目标,要求各目标同时取得较优的值,使得求解的方法与过程都相对复杂.通过将目标函数进行模糊化处理,可将多目标问题转化为单目标,借助工具软件,从而达到较易求解的目标。参考文献:1 林锉云,董加礼.多目标优化的方法与理论M.长春:吉林教育出版社,1992.8 2 宋业新,胡伟文,张建军.具有模糊系数约束的多目标线性规划J.海军工程大学学报,2004,16(1):40-44.3 龚纯,王正林.精通MATLAB最优化计算M电子工业出版社,2009 4 王嫣,张志宏.模糊线性规划的最优解分析J.北京工商大学学报(自然科学版),2007,25(5):67-6
25、9.大学数学学院四川成都摘要求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划本文介绍了理想点法线性加权和法最大最小法目标规划法然后给出多目标线性规划的模糊数学解法最后对每种解法给出例子并用软件标之间的矛盾性和不可公度性要求使所有目标均达到最优解是不可能的因此多目标规划问题往往只是求其有效解非劣解目前求解多目标线性规划问题有效解的方法有理想点法线性加权和法最大最小法目标规划法然而这些方法对多目目标线性规划有着两个和两个以上的目标函数且目标函数和约束条件全是线性函数其数学模型表示为约束条件为若式中只有一个则该问题为典型的单目标线性规划我们记则上述多目标线性规划可用矩阵形式表示为约束条件三优化工