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

1、利用Matlab解决数学问题一、线性规划求解线性规划的Matlab解法单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由GeorgeDantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。这里我们不再详细介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matla

2、b解法。中线性规划的标准型为minctxsuchthatAxbx基本函数形式为linprog(c,A,b),它的返回值是向量x的值。还有其它的一些函数调用形式(在Matlab指令窗运行helplinprog可以看到所有的函数调用形式)，如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束Aeq*X=斶，lb和UB分别是变量x的下界和上界，X0是x的初始值，OPTIONS是控制参数。例2求解下列线性规划问题maxz=2x+3x一5x123x+x+x=712310123x,x,x0123解(i)编写

3、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文件存盘，并命名为。(iii)在Matlab指令窗运行examplel即可得所求结果。例3求解线性规划问题minz=2x+3x+x123x+4x+2x8123612x,x,x0123解编写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等专用软件。对于一般的整数规划规划问题

4、，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的0-1整数规划问题或约束矩阵A是幺模矩阵时，有时可以直接利用Matlab的函数linprog例8求解下列指派问题，已知指派矩阵为TOC o 1-5 h z HYPERLINK l bookmark28 o Current Document _382103_ HYPERLINK l bookmark30 o Current Document 87297 HYPERLINK l bookmark32 o Current Document 64275 HYPERLINK l bookmark

5、34 o Current Document 4235 HYPERLINK l bookmark36 o Current Document 106910解：编写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)求得最优指派方案为x=x=x=x=x=1，最优值为21。1523324451三、非线性规划Matlab中非

6、线性规划的数学模型写成以下形式minf(x)AxBAeq-x=BeqC(x)0Ceq(x)=0其中f(x)是标量函数，A,B,Aeq,Beq是相应维数的矩阵和向量，C(x),Ceq(x)是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量x，其中FUN是用M文件定义的函数f(x)；X0是x的初始值；A,B,Aeq,Beq定义了线性约束A*X0.12(i)编写M文件functionf=fun1(x);f=x(1)A2+x(2F2+8;和M文件functiong,h=fun2(x);g=-x(

7、1)A2+x(2);h=-x(1)-x(2)A2+2;%等式约束(ii)在Matlab的命令窗口依次输入options=optimset;x,y=fmincon(fun1,rand(2,1),zeros(2,1),.fun2,options)就可以求得当x=1,x=1时，最小值y=10。12四、图论两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数w(e)直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和

8、。问题就是求赋权图G中指定的两个顶点u,v间的具最小00权的轨。这条轨叫做U,v间的最短路，它的权叫做u,v间的距离，亦记作d(u,v)。000000求最短路已有成熟的算法：迪克斯特拉(Dijkstra)算法，其基本思想是按距u从近到远为顺序，依次求得u到G的各顶点的最短路和距离，直至v(或直至G的所有顶点)，00算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。令l(u)二0，对v丰u，令l(v)=g，S二u，i二0。0000对每个veS(S=VS)，用iiiminl(v),l(u)+w(uv)ueSi代替l(v)。计算minl(v)，把达到这个最小值的一个顶点记为u

9、，令S二SYu。门i+1i+1ii+1veSi.若iTVI-1，停止；若i1VI-1，用i+1代替i，转(ii)。算法结束时，从u到各顶点v的距离由v的最后一次的标号l(v)给出。在v进入S之0i前的标号l(v)叫T标号，v进入S时的标号l(v)叫p标号。算法就是不断修改各项点的Ti标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，u至各项点的最短路也在图上标示出来了。0例9某公司在六个城市c,c,A,c中有分公司，从c到c.的直接航程票价记在下述126ij矩阵的(i，j)位置上。(表示无直接航路)，请帮助该公司设计一张城市c到其它城市间的票价最

10、便宜的路线图。050g4025105001520g25g1501020g4020100102525g20100551025g25550用矩阵a(n为顶点个数)存放各边权的邻接矩阵，行向量pb、index、index、nxn12d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量fl当第i顶点已标号Pb(i)二仁；0当第i顶点未标号index2(i)存放始点到第i点最短通路中第i顶点前一顶点的序号；d(i)存放由始点到第i点最短通路的值。求第一个城市到其它城市的最短路径的Matlab程序如下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10

11、;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)=2index=index(1);endindex2(temp)=index;endd,index1,index2每对顶点之间的最短路径计算赋权图中各

12、对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(n3)。第二种解决这一问题的方法是由FloydRW提出的算法，称之为Floyd算法。假设图G权的邻接矩阵为A。,a1na2nMannaaATOC o 1-5 h z1112aaAA=2122oMMAaaAn1n2来存放各边长度，其中：a=oi=1,2,A,n；iia=si,j之间没有边，在程序中以各边都不可能达到的充分大的数代替;ija=ww是i,j之间边的

13、长度，j=1,2,A,n。ijijij对于无向图，Ao是对称矩阵，aj=jFloyd算法的基本思想是：递推产生一个矩阵序列A,A,A,A,A,A，其中A(i,j)表o1knk示从顶点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,A,n。最后，当k=n时，A即是各顶点之间的最短通路值。n例10用Floyd算法求解例1。矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的Matlab程序如下：clear;clc;M=1000

14、0;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;endendendendendb,path4.2.1prim算法构造最小生成树设置两个集合P和Q,其中P

15、用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P=v（假设构造最小生成树时，从顶点V出发），集合Q的初值为Q二。prim算法的思想是，从所有peP，veV-P的边中，选取具有最小权值的边Pv，将顶点v加入集合P中，将边Pv加入集合Q中，如此不断重复，直到P=V时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。PvP=P+vQ=Q+pvendMatlab例11用prim算法求右图的最小生成树。我们用result的第一、二、三行分别表示生成树边的起点、终点、权集合。3n程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;

16、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);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)=;endre

17、sult4.2.1Kruskal算法构造最小生成树科茹斯克尔(Kruskal)算法是一个好算法。Kruskal算法如下：选eeE(G)，使得wg)二min。若e,e,A,e已选好，则从E(G)-e,e,A,e中选取e，使得12i12ii+1Ge,e,A,e,e中无圈，且12ii+1w(e)=min。i+1直到选得e为止。例12用Kruskal算法构造例3的最小生成树。我们用index存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中2xn较大序号u改记为此边的另一序号V，同时把后面边中所有序号为u的改记为v。此方法的几何意义是：将序号u的这个顶点收缩到V顶点，u顶点不复存在。后面继

18、续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。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=;whilelength(result)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag)=;endresult旅行商(TSP)问题一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线(从驻地出发，经过每个城市恰