利用Matlab解决数学问地的题目

实用标准文案精彩文档利用Matlab解决数学问题一、线性规划求解线性规划的Matlab解法单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由GeorgeDantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。这里我们不再详细介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab解法。Matlab5.3中线性规划的标准型为bAxxcTxsuchthatmin基本函数形式为linprog(c,A,b)，它的返回值是向量x的值。还有其它的一些函数调用形式（在Matlab指令窗运行helplinprog可以看到所有的函数调用形式），如：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束beqxAeq*，LB和UB分别是变量x的下界和上界，0x是x的初始值，OPTIONS是控制参数。例2求解下列线性规划问题321532maxxxxz0,,10527321321321xxxxxxxxx解（i）编写M文件c=[2;3;-5];a=[-2,5,-1];b=-10;aeq=[1,1,1];beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1))value=c'*x（ii）将M文件存盘，并命名为example1.m。（iii）在Matlab指令窗运行example1即可得所求结果。例3求解线性规划问题32132minxxxz实用标准文案精彩文档0,,62382432121321xxxxxxxx解编写Matlab程序如下：c=[2;3;1];a=[1,4,2;3,2,0];b=[8;6];[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))二、整数规划整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的10整数规划问题或约束矩阵A是幺模矩阵时，有时可以直接利用Matlab的函数linprog。例8求解下列指派问题，已知指派矩阵为1096109532485724679278310283解：编写Matlab程序如下：c=[382103;87297;6427584235;9106910];c=c(:);a=zeros(10,25);fori=1:5a(i,(i-1)*5+1:5*i)=1;a(5+i,i:5:25)=1;endb=ones(10,1);[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1))求得最优指派方案为15144322315xxxxx，最优值为21。实用标准文案精彩文档三、非线性规划Matlab中非线性规划的数学模型写成以下形式)(minxf0)(0)(xCeqxCBeqxAeqBAx,其中)(xf是标量函数，BeqAeqBA,,,是相应维数的矩阵和向量，)(),(xCeqxC是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量x，其中FUN是用M文件定义的函数)(xf；X0是x的初始值；A,B,Aeq,Beq定义了线性约束BeqXAeqBXA*,*，如果没有等式约束，则A=[],B=[],Aeq=[],Beq=[]；LB和UB是变量x的下界和上界，如果上界和下界没有约束，则LB=[]，UB=[]，如果x无下界，则LB=-inf，如果x无上界，则UB=inf；NONLCON是用M文件定义的非线性向量函数)(),(xCeqxC；OPTIONS定义了优化参数，可以使用Matlab缺省的参数设置。例2求下列非线性规划问题.0,0208)(min212212212221xxxxxxxxxf（i）编写M文件fun1.mfunctionf=fun1(x);f=x(1)^2+x(2)^2+8;和M文件fun2.mfunction[g,h]=fun2(x);g=-x(1)^2+x(2);h=-x(1)-x(2)^2+2;%等式约束（ii）在Matlab的命令窗口依次输入options=optimset;[x,y]=fmincon('fun1',rand(2,1),[],[],[],[],zeros(2,1),[],...'fun2',options)就可以求得当1,121xx时，最小值10y。实用标准文案精彩文档四、图论两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数)(ew—直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点00,vu间的具最小权的轨。这条轨叫做00,vu间的最短路，它的权叫做00,vu间的距离，亦记作),(00vud。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距0u从近到远为顺序，依次求得0u到G的各顶点的最短路和距离，直至0v（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。(i)令0)(0ul，对0uv，令)(vl，}{00uS，0i。(ii)对每个iSv（iiSVS\），用)}()(),({minuvwulvliSu代替)(vl。计算)}({minvliSv，把达到这个最小值的一个顶点记为1iu，令}{11iiiuSS。(iii).若1||Vi，停止；若1||Vi，用1i代替i，转(ii)。算法结束时，从0u到各顶点v的距离由v的最后一次的标号)(vl给出。在v进入iS之前的标号)(vl叫T标号，v进入iS时的标号)(vl叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，0u至各项点的最短路也在图上标示出来了。例9某公司在六个城市621,,,ccc中有分公司，从ic到jc的直接航程票价记在下述矩阵的),(ji位置上。（表示无直接航路），请帮助该公司设计一张城市1c到其它城市间的票价最便宜的路线图。实用标准文案精彩文档055252510550102025251001020402010015252015050102540500用矩阵nna（n为顶点个数）存放各边权的邻接矩阵，行向量pb、1index、2index、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量顶点未标号当第顶点已标号当第iiipb01)(；)(2iindex存放始点到第i点最短通路中第i顶点前一顶点的序号；)(id存放由始点到第i点最短通路的值。求第一个城市到其它城市的最短路径的Matlab程序如下：clear;clc;M=10000;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[zeros(1,4),10,25];a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);a=a+a';pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));d(1:length(a))=M;d(1)=0;temp=1;whilesum(pb)length(a)tb=find(pb==0);d(tb)=min(d(tb),d(temp)+a(temp,tb));tmpb=find(d(tb)==min(d(tb)));temp=tb(tmpb(1));pb(temp)=1;index1=[index1,temp];index=index1(find(d(index1)==d(temp)-a(temp,index1)));iflength(index)=2index=index(1);endindex2(temp)=index;endd,index1,index2实用标准文案精彩文档3.2每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为)(3nO。第二种解决这一问题的方法是由FloydRW提出的算法，称之为Floyd算法。假设图G权的邻接矩阵为0A，nnnnnnaaaaaaaaaA2122221112110来存放各边长度，其中：0iiani,,2,1；ijaji,之间没有边，在程序中以各边都不可能达到的充分大的数代替；ijijwaijw是ji,之间边的长度，nji,,2,1,。对于无向图，0A是对称矩阵，jiijaa。Floyd算法的基本思想是：递推产生一个矩阵序列nkAAAA,,,,,10，其中),(jiAk表示从顶点iv到顶点jv的路径上所经过的顶点序号不大于k的最短路径长度。计算时用迭代公式：)),(),(),,(min(),(111jkAkiAjiAjiAkkkkk是迭代次数，nkji,,2,1,,。最后，当nk时，nA即是各顶点之间的最短通路值。例10用Floyd算法求解例1。矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的Matlab程序如下：clear;clc;M=10000;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[zeros(1,4),10,25];实用标准文案精彩文档a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);b=a+a';path=zeros(length(b));fork=1:6fori=1:6forj=1:6ifb(i,j)b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;endendendendb,path4.2.1prim算法构造最小生成树设置两个集合P和Q,其中P用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为}{1vP（假设构造最小生成树时，从顶点1v出发），集合Q的初值为Q。prim算法的思想是，从所有Pp，PVv的边中，选取具有最小权值的边pv，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到VP时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。prim算法如下：（i）}{1vP，Q；（ii）whileVP~},,min(PVvPpwpvpv}{vPP}{pvQQend例11用prim算法求右图的最小生成树