利用Matlab解决数学问题.docx

利用Matlab解决数学问题一、线性规划求解线性规划的Matlab解法单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由George Dantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。这里我们不再详细介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab解法。Matlab5.3中线性规划的标准型为 基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束，LB和UB分别是变量的下界和上界，是的初始值，OPTIONS是控制参数。 例2 求解下列线性规划问题 解 （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 求解线性规划问题 解 编写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编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的整数规划问题或约束矩阵是幺模矩阵时，有时可以直接利用Matlab的函数linprog。例8 求解下列指派问题，已知指派矩阵为 解：编写Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5 8 4 2 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25);for i=1:5 a(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)求得最优指派方案为，最优值为21。三、非线性规划Matlab中非线性规划的数学模型写成以下形式 ,其中是标量函数，是相应维数的矩阵和向量，是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量，其中FUN是用M文件定义的函数；X0是的初始值；A,B,Aeq,Beq定义了线性约束，如果没有等式约束，则A=,B=,Aeq=,Beq=；LB和UB是变量的下界和上界，如果上界和下界没有约束，则LB=，UB=，如果无下界，则LB=-inf，如果无上界，则UB=inf；NONLCON是用M文件定义的非线性向量函数；OPTIONS定义了优化参数，可以使用Matlab缺省的参数设置。 例2 求下列非线性规划问题（i）编写M文件fun1.mfunction f=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)就可以求得当时，最小值。四、图论两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图的顶点，两城镇间的直通铁路为图相应两顶点间的边，得图。对的每一边，赋以一个实数直通铁路的长度，称为的权，得到赋权图。的子图的权是指子图的各边的权和。问题就是求赋权图中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路，它的权叫做间的距离，亦记作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距从近到远为顺序，依次求得到的各顶点的最短路和距离，直至（或直至的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。(i) 令，对，令，。(ii) 对每个（），用代替。计算，把达到这个最小值的一个顶点记为，令。(iii). 若，停止；若，用代替，转(ii)。算法结束时，从到各顶点的距离由的最后一次的标号给出。在进入之前的标号叫T标号，进入时的标号叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，至各项点的最短路也在图上标示出来了。例9 某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市到其它城市间的票价最便宜的路线图。用矩阵（为顶点个数）存放各边权的邻接矩阵，行向量、分别用来存放标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量； 存放始点到第点最短通路中第顶点前一顶点的序号； 存放由始点到第点最短通路的值。求第一个城市到其它城市的最短路径的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;while sum(pb)=2 index=index(1); end index2(temp)=index;endd, index1, index2 3.2 每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为。第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。假设图权的邻接矩阵为，来存放各边长度，其中： ； 之间没有边，在程序中以各边都不可能达到的充分大的数代替； 是之间边的长度，。对于无向图，是对称矩阵，。Floyd算法的基本思想是：递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：是迭代次数，。最后，当时，即是各顶点之间的最短通路值。例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);for k=1:6 for i=1:6 for j=1:6 if b(i,j)b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end endendb, path4.2.1 prim算法构造最小生成树设置两个集合和,其中用于存放的最小生成树中的顶点，集合存放的最小生成树中的边。令集合的初值为（假设构造最小生成树时，从顶点出发），集合的初值为。prim算法的思想是，从所有，的边中，选取具有最小权值的边，将顶点加入集合中，将边加入集合中，如此不断重复，直到时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边。prim算法如下：（i），；（ii）while end例11 用prim算法求右图的最小生成树。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下：clc;clear;M=1000;a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50; a(4,6)=30;a(4,7)=42;a(5,6)=70; a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); jb,kb=find(a(p,tb)=d); j=p(jb(1);k=tb(kb(1); result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresult4.2.1 Kruskal算法构造最小生成树科茹斯克尔（Kruskal）算法是一个好算法。Kruskal算法如下:(i)选，使得。(ii)若已选好，则从中选取，使得 中无圈，且 。(iii)直到选得为止。例12 用Kruskal算法构造例3的最小生成树。我们用存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号改记为此边的另一序号，同时把后面边中所有序号为的改记为。此方法的几何意义是：将序号的这个顶点收缩到顶点，顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。Matlab程序如下：clc;clear;M=1000;a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50; a(4,6)=30;a(4,7)=42;a(5,6)=70; i,j=find(a=0)&(a=M);b=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;while length(result)v2 index(find(index=v1)=v2; else index(find(index=v2)=v1; end data(:,flag)=; index(:,flag)=;endresult旅行商（TSP）问题一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。一个可行的办法是首先求一个Hamilton圈，然后适当修改以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈。（i）对于，构造新的Hamilton圈: ,它是由中删去边和，添加边和而得到的。若，则以代替，叫做的改良圈。（ii）转（i），直至无法改进，停止。用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。这个算法的优劣程度有时能用Kruskal算法加以说明。假设是中的最优圈。则对于任何顶点，是在中的Hamilton轨，因而也是的生成树。由此推知：若是中的最优树，同时和是和关联的两条边，并使得尽可能小，则将是的一个下界。这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不利了。例13 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113解：编写程序如下：clc,cleara(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a(6,:)=0;a=a+a;c1=5 1:4 6;L=length(c1);flag=1;while flag0 flag=0; for