利用Matlab解決數(shù)學(xué)問(wèn)地的題目

1、實(shí)用標(biāo)準(zhǔn)文案利用Matlab解決數(shù)學(xué)問(wèn)題一、線性規(guī)劃求解線性規(guī)劃的 Matlab解法單純形法是求解線性規(guī)劃問(wèn)題的最常用、最有效的算法之一。單純形法是首先由George Dantzig 于1947年提出的，近60年來(lái)，雖有許多變形體已被開(kāi)發(fā)，但卻保持著同 樣的基本觀念。由于有如下結(jié)論：若線性規(guī)劃問(wèn)題有有限最優(yōu)解，則一定有某個(gè)最優(yōu)解是可行區(qū)域的一個(gè)極點(diǎn)?；诖耍瑔渭冃畏ǖ幕舅悸肥牵合日页隹尚杏虻囊粋€(gè)極點(diǎn)，據(jù)一定規(guī)則判斷其是否最優(yōu)；若否，則轉(zhuǎn)換到與之相鄰的另一極點(diǎn)，并使目標(biāo)函數(shù)值更優(yōu)；如此下去，直到找到某一最優(yōu)解為止。這里我們不再詳細(xì)介紹單純形法，有興趣的讀者可以參看其它線性規(guī)劃書(shū)籍。下面我們介紹

2、線性規(guī)劃的Matlab解法。Matlab5.3中線性規(guī)劃的標(biāo)準(zhǔn)型為min cTx such that Ax 三 b x基本函數(shù)形式為linprog(c,A,b),它的返回值是向量 x的值。還有其它的一些函數(shù)調(diào)用形 式(在Matlab 指令窗運(yùn)行help linprog可以看到所有的函數(shù)調(diào)用形式)，如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0QPTIONS)這里fval返回目標(biāo)函數(shù)的值，Aeq和beq對(duì)應(yīng)等式約束 Aeq*x = beq, LB和UB分別是變量x的下界和上界，x0是x的初始值，OPTION能控制參數(shù)。例2求解下列線性規(guī)劃問(wèn)題max z = 2x1

3、3x2 - 5x3Xi 2 3 = 7 2x1 -5x2 + x3 2 10x1, x 2, x3 0解(i )編寫(xiě)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指令窗運(yùn)行example1即可得所求結(jié)果。例3求解線性規(guī)劃問(wèn)題min z =2x13x2x3x14x22x3 = 83x12x2 ,6Xl,X2,X3 -0解編寫(xiě)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)、整數(shù)規(guī)劃整數(shù)規(guī)劃問(wèn)題的求解可以使用 Lingo等專用軟件。對(duì)于一般的整數(shù)規(guī)劃規(guī)劃問(wèn)題，無(wú)法直接利用Matlab的函數(shù)，必須利用Matlab編程實(shí)現(xiàn)分枝定界解法和割平面解法。但對(duì)于指派問(wèn)題等特殊的0-1整數(shù)規(guī)劃問(wèn)題或約束矩陣 A是幺模矩陣時(shí)，有時(shí)可以直接利用 Matlab 的函數(shù)linprog。例8求解下列指派問(wèn)題，已知指派矩陣為3821038729764275842359106910-解：編寫(xiě)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)求得最優(yōu)指派方案為x15 = x23 = x32 = x44 = x51 = 1 ,最優(yōu)值為21。三、非線性規(guī)劃Matlab中非線性規(guī)劃的數(shù)學(xué)模型寫(xiě)成以下形式min f(x)Ax BAeq x = BeqC(x) 0 2 . 一 -x1 - x2 +2=0L. x1 , x2 0.(i )編寫(xiě) 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)就可以求得當(dāng)x1 = 1, x2 = 1時(shí)，最小值y = 10。四、圖論兩個(gè)指定頂點(diǎn)之間的最短路徑問(wèn)題如下：給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖G的頂點(diǎn)，兩城

7、鎮(zhèn)間的直通鐵路為圖 G相應(yīng)兩頂點(diǎn)間的邊，得圖 G。對(duì) G的每一邊e,賦以一個(gè)實(shí)數(shù) w(e)直通鐵路的長(zhǎng)度， 稱為e的權(quán)，得到賦權(quán)圖G。G的 子圖的權(quán)是指子圖的各邊的權(quán)和。 問(wèn)題就是求賦權(quán)圖 G中指定的兩個(gè)頂點(diǎn)u0,v0間的具最小 權(quán)的軌。這條軌叫做 Uo,Vo間的最短路，它的權(quán)叫做 Uo,Vo間的距離，亦記作 d(Uo,Vo)。求最短路已有成熟的算法：迪克斯特拉( Dijkstra )算法，其基本思想是按距 u0從近到遠(yuǎn)為順序，依次求得uo到G的各頂點(diǎn)的最短路和距離，直至vo (或直至G的所有頂點(diǎn))算法結(jié)束。為避免重復(fù)并保留每一步的計(jì)算信息，采用了標(biāo)號(hào)算法。下面是該算法。 令 l (Uo) =

8、0 ,對(duì) v #Uo ,令 l (v) =g , So=uo, i=0。(ii) 對(duì)每個(gè) v w Si ( S =V Si),用mipl(v),l (u) w(uv)口由，令ST=SiUu書(shū)。u Si代替l(v)。計(jì)算minl(v),把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為 v：(iii) . 若 i =|V | 1,停止;若 i |V | 1,用 i +1 代替 i,轉(zhuǎn)(ii)算法結(jié)束時(shí)，從Uo到各頂點(diǎn)v的距離由v的最后一次的標(biāo)號(hào)l(v)給出。在v進(jìn)入Si之前的標(biāo)號(hào)l(v)叫T標(biāo)號(hào)，v進(jìn)入Si時(shí)的標(biāo)號(hào)l(v)叫P標(biāo)號(hào)。算法就是不斷修改各項(xiàng)點(diǎn)的T標(biāo)號(hào)，直至獲得P標(biāo)號(hào)。若在算法運(yùn)行過(guò)程中， 將每一頂點(diǎn)獲得

9、 P標(biāo)號(hào)所由來(lái)的邊在圖上標(biāo) 明，則算法結(jié)束時(shí)，u0至各項(xiàng)點(diǎn)的最短路也在圖上標(biāo)示出來(lái)了。例9某公司在六個(gè)城市 Ci, C2 ,，C6中有分公司，從Ci到Cj的直接航程票價(jià)記在下述矩陣的(i, j)位置上。(g表示無(wú)直接航路)，請(qǐng)幫助該公司設(shè)計(jì)一張城市G到其它城市間的票價(jià)最便宜的路線圖。一050C3O4025105001520oO25cd1501020004020100102525O020100551025oO25550用矩陣anM( n為頂點(diǎn)個(gè)數(shù))存放各邊權(quán)的鄰接矩陣，行向量 pb、index1、inde”、d分別用來(lái)存放 P標(biāo)號(hào)信息、標(biāo)號(hào)頂點(diǎn)順序、標(biāo)號(hào)頂點(diǎn)索引、最短通路的值。其中分量1當(dāng)?shù)趇頂

10、點(diǎn)已標(biāo)號(hào)pb(i)=，；0當(dāng)?shù)趇頂點(diǎn)未標(biāo)號(hào)index?。)存放始點(diǎn)到第i點(diǎn)最短通路中第i頂點(diǎn)前一頂點(diǎn)的序號(hào)；d(i)存放由始點(diǎn)到第i點(diǎn)最短通路的值。求第一個(gè)城市到其它城市的最短路徑的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每對(duì)頂點(diǎn)之間的最短路徑計(jì)算賦權(quán)圖中各對(duì)頂點(diǎn)之間最短路徑，顯然可以調(diào)用 Dijkstra 算法。具體方法是：每 次以不同的頂點(diǎn)作為起點(diǎn)，用Dijkstra 算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行n次這樣的操作，就可得到從每一個(gè)頂點(diǎn)到其它頂點(diǎn)的最短路徑。這種算法的時(shí)間復(fù)雜度為O(n3)。第二種解決這一問(wèn)題的方法是由Floyd R W提

12、出的算法，稱之為 Floyd算法。假設(shè)圖G權(quán)的鄰接矩陣為A0 ,a11a12a1n 1a2ia22a2nAo 99an1an2ann來(lái)存放各邊長(zhǎng)度，其中：aii 0 i 1,2,，n ；a。=6 i,j之間沒(méi)有邊，在程序中以各邊都不可能達(dá)到的充分大的數(shù)代替；a。=WjWij 是 i,j 之間邊的長(zhǎng)度，i,j=1,21，n。對(duì)于無(wú)向圖，Ao是對(duì)稱上!陣，aj=aji。Floyd算法的基本思想是：遞推產(chǎn)生一個(gè)矩陣序列A0,A1,，Ak,，An,其中Ak(i,j)表示從頂點(diǎn)Vi到頂點(diǎn)Vj的路徑上所經(jīng)過(guò)的頂點(diǎn)序號(hào)不大于k的最短路徑長(zhǎng)度。計(jì)算時(shí)用迭代公式：Ak(i, j) =min(，(i, j), A

13、(i,k) Ay(k,j)k是迭代次數(shù)，i, j,k =1,2，n。最后，當(dāng)k=n時(shí)，An即是各頂點(diǎn)之間的最短通路值。例10用Floyd算法求解例1。Floyd 算法的 Matlab矩陣path用來(lái)存放每對(duì)頂點(diǎn)之間最短路徑上所經(jīng)過(guò)的頂點(diǎn)的序號(hào)。 程序如下：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算法構(gòu)造最小生成樹(shù)設(shè)置兩個(gè)集合P和Q,其中P用于存放G的最小生成樹(shù)中的頂點(diǎn)，集合 Q存放G的最小生成樹(shù)中的邊。令集合 P的初值為P=5（假設(shè)構(gòu)造最小生成樹(shù)時(shí)，從頂點(diǎn)Vi出發(fā)），集合Q的初值為Q =6。prim算法的思想是，從所有 pP, vV -P的邊中，選取具有最小權(quán)值的邊 pv,將頂點(diǎn)v加入集合P中，將邊pv加入集合Q中，如此不斷重復(fù)，直Q中包

15、含了最小生成樹(shù)的所有邊。到P =V時(shí)，最小生成樹(shù)構(gòu)造完畢，這時(shí)集合prim算法如下：(i ) P =v1 , Q =；(ii ) while P =Vpv = min( wpv, p P, v V - PP = P vQ = Q pvend例11用prim算法求右圖的最小生成樹(shù)。我們用result3珀的第一、二、三行分別表示生成樹(shù)邊的起點(diǎn)、終點(diǎn)、權(quán)集合。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算法構(gòu)造最小生成樹(shù)科茹斯克爾(Kruskal )算法是一個(gè)好算法。Kruskal算法如下：(i)選 e w

17、 E(G),使得 w(e1) =min。(ii)若ee,，已選好，則從E(G) ee,，ej中選取e書(shū)，使得G e, e2,，ei e書(shū)中無(wú)圈,且 w(e +) =min。(iii) 直到選得ev為止。例12用Kruskal算法構(gòu)造例3的最小生成樹(shù)。我們用index2M存放各邊端點(diǎn)的信息，當(dāng)選中某一邊之后，就將此邊對(duì)應(yīng)的頂點(diǎn)序號(hào)中較大序號(hào)u改記為此邊的另一序號(hào)v,同時(shí)把后面邊中所有序號(hào)為u的改記為v。此方法的幾何意義是：將序號(hào) u的這個(gè)頂點(diǎn)收縮到 v頂點(diǎn)，u頂點(diǎn)不復(fù)存在。后面繼續(xù)尋查時(shí)，發(fā)現(xiàn) 某邊的兩個(gè)頂點(diǎn)序號(hào)相同時(shí)，認(rèn)為已被收縮掉，失去了被選取的資格。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)問(wèn)題一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設(shè)計(jì)一條最短的旅行路線(從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地)？這個(gè)問(wèn)題稱為旅行商 問(wèn)題。用圖論的術(shù)語(yǔ)說(shuō)，就是