《matlab常用算法大全(数学建模).doc》由会员分享，可在线阅读，更多相关《matlab常用算法大全(数学建模).doc（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-datematlab常用算法大全(数学建模)本文总结了matlab常用的几个算法，希望对数学建模有帮助。本文总结了matlab常用的几个算法，希望对数学建模有帮助。利用matlab编程FFD算法完成装箱问题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。建立box_main.m-functionbox_count,b
2、=box_main(v)vmax=100;sort(v,descend);n=length(v);b=zeros(1,n);for i=1:n b(i)=vmax;endbox_count=1;for i=1:n for j=1:box_count if v(i)=x(i,2) car=car-x(i,2); item_count=item_count+1; else break; endendy=zeros(item_count,2);for i=1:item_count y(i,1)=x(i,1); y(i,2)=x(i,2);end end主程序为：v= 220, 208, 198, 1
3、92, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1;w= 80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25,
4、28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1;car=1000;item_count,y=chaoshi(v,w,car);y；结果为：ans = Columns 1 through 11 158 58 115 95 82 118 105 69 65 162 90 25 10 22 25 22 32 30 20 20 50 28 Columns 12 through 22 101 125 155 96 88 160 98 56 220 192 100 32
5、 40 50 32 30 55 35 20 80 70 38 Columns 23 through 26 180 77 122 20870 30 48 82最大总价值为3095元，可装入体积为996贪婪算法练习练习题1：考虑1、8、9、11这四种面值的硬币，要找出币值24的零钱，怎么找能使硬币数最少？利用matlab编程求解。解：设xj为二进制变量，如果硬币j被选中，则，xj=1，否则xj=0，则找硬币问题的数学模型如下：min=njjx1；mnjjjxv=1；用贪婪算法求解，其MATLAB程序如下：functionn,x=payback(v,y,m)m,n=size(y);fori=1:nf
6、orj=1:n练习题2：利用matlab编程FFD算法完成下题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。functionnbox,p=sjy(n,v,limitv)m,n=size(v);w=limitv*ones(m,n);p=zeros(n);nbox=0;fori=1:nforj=1:iifv(i)w(j)w(j)=w(j)-v(i);p(i,j)=1;break;elsecontinue;endw(j+1)=w(j+1)-v(i);p(i,j+1)=1;nbox=nbox+1;endend运行结果：p=100000010
7、000100000010000010000001000练习题3：如果把选择策略从“选出一个下标最小的箱子并把物品ai放入该箱子中”（FF算法）改为选择最佳的箱子(已装载物品大小和最大的这个称为bestfit-BF最佳适应算法)，再计算一次上题。比较两次求解的结果。练习题4：背包问题：c=10,5,15,7,6,18,3;w=2,3,5,7,1,4,1;limitw=15;n=7;求最优解。练习题5：“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3,奖品i占用的空间为widm3,价值为vi元,具体的数据如下:vi=220,208,198,192,180,180,16
8、5,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1wi=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1。模型的建立：设xj为
9、二进制变量，如果物品j被选中，则xj=1，否则，xj=0，如此可将本题转化为如下优化模型：max=njjjxv1；s.t.njWxxwjnjjj,2,1,1,0;1L=模型的解决：对此优化问题，我们可以选用价值密度贪婪准则，从剩下的物品中选择可装入购物车的单位价值wvjj，最大的物品，即按wvjj非递增的次序装入物品，只要正被考虑的物品装的进就装入小车。其MATLAB编程代码如下：functiona1,b1=sort1(n,a,b)%按单位价值排序m,n=size(a);d=zeros(m,n);fork=1:nd(k)=a(k)/b(k);end%单位价值forh=1:n-1forj=1:n
10、-h%向后排序ifd(j)clbreak%待放入包的物品重量大于包的重量,跳出循环elsex(i)=1;%x(i)为1时,物品i在包中cl=cl-w(i);p=p+1;%p记录放入背包物品的个数endendfunctionknapsack(n,limitw,w,v)totalc=0;totalw=0;m,n=size(w);%m是w的行数n是w的列数x=zeros(m,n);t=w;%记录原数组k=c;y=x;p,c,w=goodsinknapsack(n,limitw,v,w,x);%排序及计算装箱物品数forj=1:p%装包的p件物品fori=1:n%原n件物品if(w(j)=t(i)&(
11、c(j)=k(i)%被选择的物品装箱y(i)=1;endendendyfori=1:ntotalc=totalc+k(i)*y(i);%背包的总价值ify(i)=1totalw=totalw+t(i);%背包所装载总体积endendtotalwtotalcv=220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1;w=
12、80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1;limitw=1000;n=50;knapsack(n,limitw,w,v)；运行结果为：y=Columns1through161101010111101101Columns17through321011011111110100Columns33through480010100110000000Colum
13、ns49through5000层次分析法matlab源程序disp(请输入判断矩阵A(n阶);A=input(A=);n,n=size(A);x=ones(n,100);y=ones(n,100);m=zeros(1,100);m(1)=max(x(:,1);y(:,1)=x(:,1);x(:,2)=A*y(:,1);m(2)=max(x(:,2);y(:,2)=x(:,2)/m(2);p=0.0001;i=2;k=abs(m(2)-m(1);while kp i=i+1; x(:,i)=A*y(:,i-1); m(i)=max(x(:,i); y(:,i)=x(:,i)/m(i); k=ab
14、s(m(i)-m(i-1);enda=sum(y(:,i);w=y(:,i)/a;t=m(i);disp(w);disp(t); %以下是一致性检验CI=(t-n)/(n-1);RI=0 0 0.52 0.89 1.12 1.26 1.36 1.41 1.46 1.49 1.52 1.54 1.56 1.58 1.59;CR=CI/RI(n);if CR0.1 disp(组合一致性不通过，请重新评分) returnend%下面根据比较阵的结果进行组合result=EigOfOpt*EigOfCri;resultfunction f=AHP1(dim,CmpMatrix)RI=0 0 0.58
15、0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51;%判断该比较阵是不是一致阵%判断该比较阵是不是一致阵V,D=eig(CmpMatrix);%求得特征向量和特征值%求出最大特征值和它所对应的特征向量tempNum=D(1,1);pos=1;for h=1:dim if D(h,h)tempNum tempNum=D(h,h); pos=h; endend eigVector=V(:,pos);maxeig=D(pos,pos);maxeigdimCI=(maxeig-dim)/(dim-1);CR=CI/RI(dim);if CR0.1 disp(准则对目标影响度
16、评分生成的矩阵不是一致阵，请重新评分) returnendCI%归一化sum=0;for h=1:dim sum=sum+eigVector(h);endsumpause,for h=1:dim eigVector(h)=eigVector(h)/sum;endf=eigVector;CI; 多目标线性规划的若干解法及MATLAB实现摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍了理想点法、线性加权和法、最大最小法、目标规划法，然后给出多目标线性规划的模糊数学解法，最后对每种解法给出例子，并用Matlab软件加以实现。关键词：多目标线性规划 Matlab 模糊数
17、学Some solutions of Multi-objective linear programming and realized by MatlabDing HongfeiSchool 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 plann
18、ing, 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
19、Programming Matlab fuzzy mathematics一引言多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不可公度性,要求使所有目标均达到最优解是不可能的,因此多目标规划问题往往只是求其有效解(非劣解)。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、最大最小法、目标规划法，然而这些方法对多目标偏好信息的确定、处理等方面的研究工作较少，本文也给出多目标线性规划的模糊数学解法。二多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函数,其数学模型表示为： （1）约束条件为： （2）若（1）式中
20、只有一个，则该问题为典型的单目标线性规划。我们记:,，.则上述多目标线性规划可用矩阵形式表示为: 约束条件： （3）三MATLAB优化工具箱常用函数在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所对应的值。算法原理：单纯形法
21、的改进方法投影法.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,fva
22、l =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）中，先求解个单目标问题：，设其最优值为，称为值域中的一个理想点，因为一般很难达到。于是，在期望的某种度量之下，寻求距离最近的作为近似值。一种最直接的方法是最短距离理想点法
23、，构造评价函数，然后极小化，即求解，并将它的最优解作为（3）在这种意义下的“最优解”。例1：利用理想点法求解解：先分别对单目标求解：求解最优解的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.0000fval = -12.0000即最优解为12.求解最优解的MATLAB程序为 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.000
24、0即最优解为24.于是得到理想点：（12，24）.然后求如下模型的最优解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则对应的目标值分别为,.4.2线性加权和法在具有多个指标的问题中，人们总希望对那些相对重要的指标给予较大的权系数，因而将多目标向量问题转化为所有目标的加权求和的标量问题，基于这个现实，构造如下评价函数，即将它的最优解作为（3）在线性加权和意义下的“最优
25、解”。（为加权因子，其选取的方法很多，有专家打分法、容限法和加权因子分解法等）.例2：对例1进行线性加权和法求解。（权系数分别取，）解：构造如下评价函数，即求如下模型的最优解。MATLAB程序如下： 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则对应的目标值分别为,.4.3最大最小法在决策的时候，采取保守策略是稳妥的，即在最坏的情况下，寻求最好的结果，按照此想法，可以构造如下评价函数，即然后求解： 并将它的最优解作为（3）在最大最小意义下的“最优解”。例3：对例1进行最大最小
26、法求解：解：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 6.0000fval = -12 -18则对应的目标值分别为,.4.4目标规划法 （4）并把原多目标线性规划（3）称为和目标规划（4）相对应的多目标线性规划。为了用数量来描述（4），我们在目标空间中引进点之间的某种“距离”这样（4）便可
27、以用单目标来描述了。例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 = 0.0000 6.0000fval = -12 -18则对应的目标值分别为,.4.5模糊数学求解方法 由于多目标线性规
28、划的目标函数不止一个,要想求得某一个点作,使得所有的目标函数都达到各自的最大值,这样的绝对最优解通常是不存在的。因此,在具体求解时,需要采取折衷的方案,使各目标函数都尽可能的大。模糊数学规划方法可对其各目标函数进行模糊化处理,将多目标问题转化为单目标,从而求该问题的模糊最优解。 具体的方法为：先求在约束条件： 下各个单目标的最大值和最小值，伸缩因子为得到 （5）式（5）是一个简单的单目标线性规划问题。最后求得模糊最优解为：.利用(5)式来求解的关键是对伸缩指标的确定,是我们选择的一些常数,由于在多目标线性规划中,各子目标难以同时达到最大值，但是可以确定的是各子目标的取值范围，它满足：，所以，伸
29、缩因子为可以按如下取值：.例5：对例1进行模糊数学方法求解：解：分别求得,在约束条件下的最大值为：.分别求得,在约束条件下的最小值为：.伸缩因子为然后求如下模型的最优解：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.8354fval =-0.8354于是原多目标规划问题的模糊最优值为.五结论多目线性标规划是优化问题的一种,由于其存在多个目标,要求各目标同时取得较优的值,使得求解的方法与过程都
30、相对复杂. 通过将目标函数进行模糊化处理,可将多目标问题转化为单目标,借助工具软件,从而达到较易求解的目标。参考文献:1 林锉云,董加礼. 多目标优化的方法与理论M. 长春:吉林教育出版社,1992.82 宋业新,胡伟文,张建军. 具有模糊系数约束的多目标线性规划J. 海军工程大学学报, 2004,16(1):40-44.3 龚纯,王正林. 精通MATLAB最优化计算M电子工业出版社,20094 王嫣,张志宏. 模糊线性规划的最优解分析J. 北京工商大学学报(自然科学版), 2007,25(5):67-69.粒子群算法(1)-粒子群算法简介二、粒子群算法的具体表述 上面罗嗦了半天，那些都是科研
31、工作者写论文的语气，不过，PSO的历史就像上面说的那样。下面通俗的解释PSO算法。 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数 y=1-cos(3*x)*exp(-x)的在0,4最大值。该函数的图形如下：当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在0，4之间随机的
32、洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在0，4之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下：这两个点就是粒子群算法中的粒子。该函数的最大值就是鸟群中的食物计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。更新自己位置的一定公式就是粒子群算法中的位置速度更新公式。下面演示一下这个算法运行一次的大概过程：第一次初始化第一次更新位置第二次更新位置第21次更新最后
33、的结果（30次迭代）最后所有的点都集中在最大值的地方。粒子群算法(2)-标准的粒子群算法在上一节的叙述中，唯一没有给大家介绍的就是函数的这些随机的点（粒子）是如何运动的，只是说按照一定的公式更新。这个公式就是粒子群算法中的位置速度更新公式。下面就介绍这个公式是什么。在上一节中我们求取函数y=1-cos(3*x)*exp(-x)的在0,4最大值。并在0,4之间放置了两个随机的点，这些点的坐标假设为x1=1.5； x2=2.5；这里的点是一个标量，但是我们经常遇到的问题可能是更一般的情况x为一个矢量的情况，比如二维的情况z=2*x1+3*x22的情况。这个时候我们的每个粒子为二维，记粒子P1(x11,x12),P2=(x21,x22),P3=(x31,x32)，.Pn=(xn1,xn2)。这里n为粒子群群体的规模，也就是这个群中粒子的个数，每个粒子的维数为2。更一般的是粒子的维数为q，这样在这个种群中有n个粒子，每个粒子为q 维。 由n个粒子组成的群体对Q维（就是每个粒子的维数）空间进行搜索。每个粒子表示为：xi（xi1,xi2,xi3,.,xiQ），每个粒子对应的速度可以表示为vi=(vi1,vi2,vi3,.,viQ)，每个粒子在搜索时要考虑两个因素：1。自己搜索到的历史最优值 pi ，pi=(pi1,pi2,.,piQ)，i=1,2,3,.,n。2。全部粒子搜