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

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

2、线性规划的Matlab解法。Matlab5.3中线性规划的标准型为min cTx such that Ax 三 b x基本函数形式为linprog(c,A,b),它的返回值是向量 x的值。还有其它的一些函数调用形 式(在Matlab 指令窗运行help linprog可以看到所有的函数调用形式)，如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0QPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束 Aeq*x = beq, LB和UB分别是变量x的下界和上界，x0是x的初始值，OPTION能控制参数。例2求解下列线性规划问题max z = 2x1

3、3x2 - 5x3Xi 2 3 = 7 2x1 -5x2 + x3 2 10x1, x 2, x3 0解(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求解线性规划问题min z =2x13x2x3x14x22x3 = 83x12x2 ,6Xl,X2,X3 -0解编写Matlab程序如下：c=2；3；1；a=1,4,2;3,2

4、,0;b=8；6;x,y=linprog(c,-a,-b,口,zeros(3,1)、整数规划整数规划问题的求解可以使用 Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的0-1整数规划问题或约束矩阵 A是幺模矩阵时，有时可以直接利用 Matlab 的函数linprog。例8求解下列指派问题，已知指派矩阵为3821038729764275842359106910-解：编写Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 58 4 2 3 5;9 10 6

5、9 10;c=c(：)；a=zeros(10,25);for i=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)求得最优指派方案为x15 = x23 = x32 = x44 = x51 = 1 ,最优值为21。三、非线性规划Matlab中非线性规划的数学模型写成以下形式min f(x)Ax BAeq x = BeqC(x) 0 2 . 一 -x1 - x2 +2=0L. x1 , x2 0.(i )编写 M文件fun1.mfunction f=f

6、un1(x);f=x(1)A2+x(2)A2+8;和M文件fun2.mfunction g,h=fun2(x);g=-x(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)就可以求得当x1 = 1, x2 = 1时，最小值y = 10。四、图论两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城

7、镇间的直通铁路为图 G相应两顶点间的边，得图 G。对 G的每一边e,赋以一个实数 w(e)直通铁路的长度， 称为e的权，得到赋权图G。G的 子图的权是指子图的各边的权和。 问题就是求赋权图 G中指定的两个顶点u0,v0间的具最小 权的轨。这条轨叫做 Uo,Vo间的最短路，它的权叫做 Uo,Vo间的距离，亦记作 d(Uo,Vo)。求最短路已有成熟的算法：迪克斯特拉( Dijkstra )算法，其基本思想是按距 u0从近到远为顺序，依次求得uo到G的各顶点的最短路和距离，直至vo (或直至G的所有顶点)算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 令 l (Uo) =

8、0 ,对 v #Uo ,令 l (v) =g , So=uo, i=0。(ii) 对每个 v w Si ( S =V Si),用mipl(v),l (u) w(uv)口由，令ST=SiUu书。u Si代替l(v)。计算minl(v),把达到这个最小值的一个顶点记为 v：(iii) . 若 i =|V | 1,停止;若 i |V | 1,用 i +1 代替 i,转(ii)算法结束时，从Uo到各顶点v的距离由v的最后一次的标号l(v)给出。在v进入Si之前的标号l(v)叫T标号，v进入Si时的标号l(v)叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中， 将每一顶点获得

9、 P标号所由来的边在图上标 明，则算法结束时，u0至各项点的最短路也在图上标示出来了。例9某公司在六个城市 Ci, C2 ,，C6中有分公司，从Ci到Cj的直接航程票价记在下述矩阵的(i, j)位置上。(g表示无直接航路)，请帮助该公司设计一张城市G到其它城市间的票价最便宜的路线图。一050C3O4025105001520oO25cd1501020004020100102525O020100551025oO25550用矩阵anM( n为顶点个数)存放各边权的邻接矩阵，行向量 pb、index1、inde”、d分别用来存放 P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量1当第i顶

10、点已标号pb(i)=，；0当第i顶点未标号index?。)存放始点到第i点最短通路中第i顶点前一顶点的序号；d(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

11、;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2index=index(1);endindex2(temp)=index;endd, index1, index23.2每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。具体方法是：每 次以不同的顶点作为起点，用Dijkstra 算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(n3)。第二种解决这一问题的方法是由Floyd R W提

12、出的算法，称之为 Floyd算法。假设图G权的邻接矩阵为A0 ,a11a12a1n 1a2ia22a2nAo 99an1an2ann来存放各边长度，其中：aii 0 i 1,2,，n ；a。=6 i,j之间没有边，在程序中以各边都不可能达到的充分大的数代替；a。=WjWij 是 i,j 之间边的长度，i,j=1,21，n。对于无向图，Ao是对称上!阵，aj=aji。Floyd算法的基本思想是：递推产生一个矩阵序列A0,A1,，Ak,，An,其中Ak(i,j)表示从顶点Vi到顶点Vj的路径上所经过的顶点序号不大于k的最短路径长度。计算时用迭代公式：Ak(i, j) =min(，(i, j), A

13、(i,k) Ay(k,j)k是迭代次数，i, j,k =1,2，n。最后，当k=n时，An即是各顶点之间的最短通路值。例10用Floyd算法求解例1。Floyd 算法的 Matlab矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。 程序如下：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=ze

14、ros(length(b);for k=1:6for i=1:6for j=1:6if b(i,j)b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j);path(i,j尸k;endendendendb, path4.2.1 prim算法构造最小生成树设置两个集合P和Q,其中P用于存放G的最小生成树中的顶点，集合 Q存放G的最小生成树中的边。令集合 P的初值为P=5（假设构造最小生成树时，从顶点Vi出发），集合Q的初值为Q =6。prim算法的思想是，从所有 pP, vV -P的边中，选取具有最小权值的边 pv,将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直Q中包

15、含了最小生成树的所有边。到P =V时，最小生成树构造完毕，这时集合prim算法如下：(i ) P =v1 , Q =；(ii ) while P =Vpv = min( wpv, p P, v V - PP = P vQ = Q pvend例11用prim算法求右图的最小生成树。我们用result3珀的第一、二、三行分别表示生成树边的起点、终点、权集合。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

16、(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)-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.1 Kruskal算法构造最小生成树科茹斯克尔(Kruskal )算法是一个好算法。Kruskal算法如下：(i)选 e w

17、 E(G),使得 w(e1) =min。(ii)若ee,，已选好，则从E(G) ee,，ej中选取e书，使得G e, e2,，ei e书中无圈,且 w(e +) =min。(iii) 直到选得ev为止。例12用Kruskal算法构造例3的最小生成树。我们用index2M存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号u改记为此边的另一序号v,同时把后面边中所有序号为u的改记为v。此方法的几何意义是：将序号 u的这个顶点收缩到 v顶点，u顶点不复存在。后面继续寻查时，发现 某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。Matlab程序如下：clc;clear

18、;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)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag户口； endresult旅行商(TSP)问题一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这个问题称为旅行商 问题。用图论的术语说，就是