数学建模常用算法程序

1、假设图G权的邻接矩阵为A,0aa，a1112aaa2122.,aaan1n21n2n0nn来存放各边长度，其中：iii=1,2,n;ijijij是i,j之间边的长度，i,j=1,2,对于无向图，A是对称矩阵，ijjiiji,j之间没有边，在程序中以各边都不可能达到的充分大的数代替；Floyd算法的基本思想是:递推产生一个矩阵序列A,A，A，A，其中A(i,j)表01knk示从顶点v到顶点v的路径上所经过的顶点序号不大于k的最短路径长度。ij计算时用迭代公式:A(i,j)=min(A(i,j),A(i,k)+A(k,j)kk-1k-1k-1k是迭代次数，i,j,k=1,2,n。最后，当k=n时，

2、A即是各顶点之间的最短通路值。n例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)

3、b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;endendendendb,pathFloyd最短路算法的MATLAB程序%floyd.m%采用floyd算法计算图a中每对顶点最短路%d是矩离矩阵%r是路由矩阵functiond,r=floyd(a)n=size(a,1);d=a;fori=1:nforj=1:nr(i,j)=j;endendrfork=1:nfori=1:nforj=1:nifd(i,k)+d(k,j)d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k)endendendkdrend两个指定顶点之间的最短

4、路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数w(e)直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点u,v间的具最小00权的轨。这条轨叫做u,v间的最短路，它的权叫做u,v间的距离，亦记作d(u,v)。000000求最短路已有成熟的算法：迪克斯特拉(Dijkstra)算法，其基本思想是按距u从近到0远为顺序，依次求得u到G的各顶点的最短路和距离，直至v(或直至G的所有顶点)，00算法

5、结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。令l(u)=0，对v丰u，令l(v)=g，S=u，i=0。0000对每个veS(S=VS)，用iiminl(v),l(u)+w(uv)ueSi代替l(v)。计算minl(v)，把达到这个最小值的一个顶点记为u，令S=SUu。i+1i+1ii+1veSi.若i=IVI-1，停止；若iIVI-1，用i+1代替i，转(ii)。算法结束时，从u到各顶点v的距离由v的最后一次的标号l(v)给出。在v进入S之0i前的标号l(v)叫T标号，v进入S时的标号l(v)叫P标号。算法就是不断修改各项点的Ti标号，直至获得P标号。若在算法运行过程

6、中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，u至各项点的最短路也在图上标示出来了。0例9某公司在六个城市c,c,c中有分公司，从c到c的直接航程票价记在下述126ij矩阵的(i,j)位置上。(g表示无直接航路)，请帮助该公司设计一张城市c到其它城市间的1票价最便宜的路线图。050g4025105001520g25g1501020g4020100102525g20100551025g25550用矩阵a(n为顶点个数)存放各边权的邻接矩阵，行向量pb、index、index、nxn12d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量1当第i顶点已标号pb

7、(i)=;0当第i顶点未标号index(i)存放始点到第i点最短通路中第i顶点前一顶点的序号;2d(i)存放由始点到第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;index

8、2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;whilesum(pb)=2index=index(1);endindex2(temp)=index;endd,index1,index24.2.1prim算法构造最小生成树设置两个集合P和Q，其中P用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P=v（假设构造最小生成树时，从顶点v出发），11集合Q的初值为Q=。prim算法的思想是，从所有peP，veV-P的边中，选取具有最小权值的边pv，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到P=V时，

9、最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。prim算法如下：(i)P=v，Q=；1(ii)whileP=Vpv=minW,peP,veV一PpvP=P+vQ=Q+pvend例11用prim算法求右图的最小生成树。Matlab我们用result的第一、二、三行分别表示生成树边的起点、终点、权集合3xn程序如下：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

10、;a(find(a=0)=M;result=;p=1;tb=2:length(a);whilelength(result)=length(a)-1temp=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.1Kruskal算法构造最小生成树科茹斯克尔(Kruskal)算法是一个好算法。Kruskal算法如下：选eeE(G)，使得w(e)=min。11(ii)若e,e，e已选好，则从E(G

11、)-e,e，,e中选取e，使得12i12ii+1Ge,e,e,e中无圈，且12ii+1w(e)=min。i+1(iii)直到选得e为止。V-1例12用Kruskal算法构造例3的最小生成树。我们用index存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中xn较大序号u改记为此边的另一序号v，同时把后面边中所有序号为u的改记为v。此方法的几何意义是：将序号u的这个顶点收缩到v顶点，u顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。Matlab程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4

12、)=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=;whilelength(result)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag)=;endresult一名推销员准备前往若干城市推销

13、产品，然后回到他的出发地。如何为他设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好(但不一定最优)的解。一个可行的办法是首先求一个Hamilton圈C，然后适当修改C以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈C=vvvv。12n1对于1i+1jn，构造新的Hamilton圈：C=vvvvvvvvvvv,j12ijj-1j-

14、2i+1j+1j+2n1它是由C中删去边vv和vv,添加边vv和vv而得到的。若ii+1jj+1iji+1j+1w(vv)+w(vv)0flag=0;form=1:L-3forn=m+2:L-1ifa(c1(m),c1(n)+a(c1(m+1),c1(n+1)0flag=0;form=1:L-3forn=m+2:L-1ifa(c1(m),c1(n)+a(c1(m+1),c1(n+1).a(c1(m),c1(m+1)+a(c1(n),c1(n+1)flag=1;c1(m+1:n)=c1(n:-1:m+1);endendendendsum1=0;fori=1:L-1sum1=sum1+a(c1(i

15、),c1(i+1);endifsum1sumsum=sum1;circle=c1;endcircle,sum已知非线性整数规划为：Maxz=x2+x2+3x2+4x2+2x2123458x2x3xx2x123450 x99(i=1,，5)ix+x+x+x+x400TOC o 1-5 h z12345s.t.x+2x+2x+x+6x800123452x+x+6x200123x+x+5x20045对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算(100)5=1010个点，其计算量非常之大。然而应用蒙特卡洛去随机计算106个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？下面就分

16、析随机取样采集106个点计算时，应用概率理论来估计一下可信度。不失一般性，假定一个整数规划的最优点不是孤立的奇点。假设目标函数落在高值区的概率分别为0.01，0.00001，则当计算106个点后，有任一个点能落在高值区的概率分别为1-0.9910000000.9999(100多位)，1-0.9999910000000.999954602。解(i)首先编写M文件mente.m定义目标函数f和约束向量函数g,程序如下：functionf,g=mengte(x);f=x(l厂2+x(2厂2+3*x(3厂2+4*x(4厂2+2*x(5)-8*x(l)-2*x(2)-3*x(3).-x(4)-2*x(5);g(1)=sum(x)-400;g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;g(3)