版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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)问题一名推销员准备前往若干城市推销产品,然后回到他的出发地。如何为他设计一条最短的旅行路线(从驻地出发,经过每个城市恰
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 互联网广告与品牌建设策略考核试卷
- 化学纤维制造中的智能库存管理与控制考核试卷
- 民宿消防安全协议
- 污水处理工程运行维护合同
- 商业综合体架线施工合同
- 珠宝品牌总经理招聘合同
- 土地交换协议书范例
- 民用建筑管井施工合同
- 有机保健品质量监控策略
- 电视台租赁合同样式
- 人教版2023-2024学年五年级数学上册常考易考突围第三单元:小数除法简便计算“拓展型”专项练习(解析版)
- 妇幼保健院新生儿口腔护理操作考核评分标准
- 2023团校团史团章培训考试题库(含答案)
- 《狼王梦》好书推荐课件
- 购物中心行业营销策略方案
- 拉森钢板桩设计计算书
- 三年级上册第二单元日记 25篇
- 办公耗材采购 投标方案(技术方案)
- 《干部履历表》填写样式
- 29、顾客意见簿(表029)
- 生活离不开规则 教案
评论
0/150
提交评论